ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
25 сообщений из 36, страница 1 из 2
  1  все
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733320
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Есть исходный (первый) массив:
(52, 41, 1, 75, 12)
Нужно получить новый (второй) массив, состоящий из всех возможных сумм элементов исходного массива:
(52, 41, 1, 75, 12, 93, 53, 127, 64, 42, 116, 53, 76, 13, 87, 94, 168, 105, 128, 65, 139, 117, 54, 128, 88, 169, 106, 180, 140, 129, 181)

Для большего понимания вопроса см. прикрепленный документ. На первом листе в качестве примера все возможные комбинации для массивов длинной от 1 до 5 элементов, а на втором исходные данные и что должно получиться.

Как должен выглядеть алгоритм для получения второго массива? Ну или хотябы подскажите где копать. Есть предположение что это что-то из теории вероятности, но дальше этого предположения ничего не заходит.
...
Рейтинг: 0 / 0
30.08.2014, 13:24
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733361
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Задача с полпинка решается вложенными циклами в количестве равном размеру массива. Если он неизвестен на этапе кодирования, то рекурсией с одним циклом внутри и одним - снаружи.

Другой вопрос - надо ли отсекать повторения сумм...
...
Рейтинг: 0 / 0
30.08.2014, 15:10
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733378
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Dimitry Sibiryakov, нет не надо.
...
Рейтинг: 0 / 0
30.08.2014, 17:02
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733379
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Dimitry SibiryakovЗадача с полпинка решается вложенными циклами в количестве равном размеру массива. Если он неизвестен на этапе кодирования, то рекурсией с одним циклом внутри и одним - снаружи.
Размер массива неизвестен.
А можно пример?

Dimitry SibiryakovДругой вопрос - надо ли отсекать повторения сумм...
Нет, не надо.
...
Рейтинг: 0 / 0
30.08.2014, 17:04
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733401
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
5 элементов, каждый элемент либо включен в сумму, либо нет, т.е. имеем двоичное число из 5 разрядов, где каждый разряд означает включать соответствующий ему элемент массива в сумму или нет.

Дальше перебор чисел от 1 до 2^5 и проверка: 0й бит =1 - плюсуем 0й элемент массива, 1й бит =1 - плюсуем 1й элемент массива и т.д. Понял как решать?
...
Рейтинг: 0 / 0
30.08.2014, 19:34
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733404
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Dima T5 элементов, каждый элемент либо включен в сумму, либо нет, т.е. имеем двоичное число из 5 разрядов, где каждый разряд означает включать соответствующий ему элемент массива в сумму или нет.

Дальше перебор чисел от 1 до 2^5 и проверка: 0й бит =1 - плюсуем 0й элемент массива, 1й бит =1 - плюсуем 1й элемент массива и т.д. Понял как решать?
Вы мне льстите :)
Я не настолько углублен в тему программирования к сожалению. Попроще есть решение?
...
Рейтинг: 0 / 0
30.08.2014, 19:41
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733408
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kefirkoПопроще есть решение?
Есть. Форум работа. За умеренную денежку порешают твою задачу.
...
Рейтинг: 0 / 0
30.08.2014, 19:47
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733412
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
kefirko, в четвертой строке твоего поста ты каким-то чудом написал все сочетания из 5.

Как ты это сделал? Наверное ты знаешь алгоритм.
...
Рейтинг: 0 / 0
30.08.2014, 20:00
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733417
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
maytonkefirko, в четвертой строке твоего поста ты каким-то чудом написал все сочетания из 5.
Как ты это сделал? Наверное ты знаешь алгоритм.
Сарказм збс.
В прикрепленном файлике все есть. Написано вручную. Сначала на листочке, потом, для того чтобы было проще понять суть моего вопроса, набросал табличку. Ведь, чем лучше изложен вопрос, тем больше вероятности получить ответ.
Вручную то я и без алгоритма все варианты переберу, а вот каким должен быть код, для меня загадка.
...
Рейтинг: 0 / 0
30.08.2014, 20:09
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733418
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Сижу вот теперь читаю про рекурсию.
...
Рейтинг: 0 / 0
30.08.2014, 20:10
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733422
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kefirkoСижу вот теперь читаю про рекурсию.
Время теряешь. Я тебе самый простой алгоритм написал. Проще некуда, кода строк 10-15, но никто тебе тут их не напишет. Тут помогают решить а не решают.
Читай про работу с двоичными числами и битовые операции.
...
Рейтинг: 0 / 0
30.08.2014, 20:17
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733424
Фотография VSVLAD
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VSVLAD
Участник
Примерно так в Excel будет выглядеть, вроде верно.
...
Рейтинг: 0 / 0
30.08.2014, 20:27
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733425
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я добрый, вот тебе еще подсказка
Десятичное (счетчик) 4й бит 3 бит 2й 1й 0й Сумма1 0 0 0 0 1 522 0 0 0 1 0 413 0 0 0 1 1 52 + 414 0 0 1 0 0 1
и т.д.
...
Рейтинг: 0 / 0
30.08.2014, 20:28
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733426
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
VSVLAD, у меня неизвестное кол-во элементов в массиве. Может быть 2, может быть 100. Но за направление спасибо, будем изучать.
...
Рейтинг: 0 / 0
30.08.2014, 20:29
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733427
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
VSVLADПримерно так в Excel будет выглядеть, вроде верно.
В правильном направлении копаешь
...
Рейтинг: 0 / 0
30.08.2014, 20:29
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733428
kefirko
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kefirko
Гость
Dima T, спасибо, будем копать.
...
Рейтинг: 0 / 0
30.08.2014, 20:30
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733433
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kefirkoможет быть 100.
С этим сложнее 2^100 примерно 1000000000000000000000000000000 чисел результата. Ограничься 32-мя, тут всего 16 Гб результат займет :)
...
Рейтинг: 0 / 0
30.08.2014, 20:39
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733434
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Кефирко... Святые угодники....

Вот помедитируй над этим. Хардкорно. Но проясняет первую идейку. Без биткарты.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
{
 for(i=0;i<2;i++){
  for(i1=0;i1<2;i1++){
   for(i2=0;i2<2;i2++){
    for(i3=0;i3<2;i3++){
     for(i4=0;i4<2;i4++){
      printf("%d,",52*i + 41*i1 + 1*i2 + 75*i3 + 12*i4);
     } 
    }
   }
  }
 }
}
...
Рейтинг: 0 / 0
30.08.2014, 20:39
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733435
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vmag
Участник
kefirkoЕсть исходный (первый) массив:
(52, 41, 1, 75, 12)
Нужно получить новый (второй) массив, состоящий из всех возможных сумм элементов исходного массива:
(52, 41, 1, 75, 12, 93, 53, 127, 64, 42, 116, 53, 76, 13, 87, 94, 168, 105, 128, 65, 139, 117, 54, 128, 88, 169, 106, 180, 140, 129, 181)

Мля чё тут получать то, рассказываю на пальцах, какие ещё там рекурсии/шмикурсии, мы енто не проходили:
- первые пять сумм это тупо весь исходный массив (так сказать суммы каждого одного исходного элемента)
- следующие 11 (с 93 по 87) енто суммы всех комбинаций по 2 исходные цифири 93 = 52+41.... а 87 = 75+12
- соответственно дальше идут все суммы всех комбинаций по 3 цифири 94 = 52 + 41 + 1...
---------- по 4 .....
- в конце мля сумма одной единственной комбинации из 5 цифирей 181 = 52 + 41 +1 + 75 + 12

С калькулятором не сидел, просто нахрен сразу бросилося в глаза очевидное....
...
Рейтинг: 0 / 0
30.08.2014, 20:45
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733437
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВот помедитируй над этим.
ИМХУ. Глупая подсказка. Немасштабируемо. Гибкости нет. Кое-какие языки позволяют сгенерить код и запустить, там это применимо, но далеко не все языки интерпретаторы :)

Ты ему рекурсией универсально напиши. Тогда точно можно будет медитировать
...
Рейтинг: 0 / 0
30.08.2014, 20:49
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733438
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Боюсь что в рекурсии он уйдет в астрал. Хоть бы так написал.
...
Рейтинг: 0 / 0
30.08.2014, 20:54
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733440
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonБоюсь что в рекурсии он уйдет в астрал. Хоть бы так написал.
Верно подмечено. По моему про рекурсию надо рассказывать студентам после защиты диплома, и только тем кто сам его писал.
...
Рейтинг: 0 / 0
30.08.2014, 21:00
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733441
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Тут еще вопрос какой глубины решения требует препод. Если тема лабы - рекурсии - то да.
Но ключевым заданием в данной задаче будет не генерация сумм что на мой взгляд тривиально
а собственно генератор сочетаний.

Второе если тема лабы - STL - то можно поискать готовые генераторы сочетаний и использовать их.

Третье - если разрешено использовать библиотеки длинной арифметики - то берем любую
по основанию 2 и юзаем.
...
Рейтинг: 0 / 0
30.08.2014, 21:06
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733442
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vmag
Участник
vmagМля чё тут получать то, рассказываю на пальцах, какие ещё там рекурсии/шмикурсии, мы енто не проходили:
- первые пять сумм это тупо весь исходный массив (так сказать суммы каждого одного исходного элемента)
- следующие 11 (с 93 по 87) енто суммы всех комбинаций по 2 исходные цифири 93 = 52+41.... а 87 = 75+12
- соответственно дальше идут все суммы всех комбинаций по 3 цифири 94 = 52 + 41 + 1...
---------- по 4 .....
- в конце мля сумма одной единственной комбинации из 5 цифирей 181 = 52 + 41 +1 + 75 + 12

С калькулятором не сидел, просто нахрен сразу бросилося в глаза очевидное....

Алгоритм примерно такой:

1. Записываем в результат сразу весь исходный массив (первая очевидная итерация).
2. Считаем сколько элементов в массиве и вычисляем сколько будет видов переборов комбинаций и делаем перебор,
получая суммы и записывая их в результат (например для этого случая):
- перебор всех по 2 цифры и сумма в результат
- ...................по 3 цифры и ..........................
- ...................по 4 цифры и ..........................
3. Записываем в результат последнюю очевидную сумму всех элементов исходного массива...
...
Рейтинг: 0 / 0
30.08.2014, 21:07
| Ответить | Цитировать | Написать  
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
    #38733449
Фотография vmag
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vmag
Участник
vmag,

естественно по пункту 2 переборы будут по:

Если количество элементов N,
то переборы будут от 2-х цифр до N-1 цифр

+ пункт 1 в начале и пунк 3 в конце, нарисуйте блок схему на ватмане,
и отдайте преподу....
...
Рейтинг: 0 / 0
30.08.2014, 21:19
| Ответить | Цитировать | Написать  
25 сообщений из 36, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38733442&tid=1341238]:
 0ms
get settings:
 6ms
get forum list:
 18ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 174ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 67ms
get tp. blocked users:
 1ms
others: 249ms
total:  535ms
созд. / загр.: 535ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]