Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива. / 25 сообщений из 36, страница 1 из 2
  1  все
30.08.2014, 13:24
    #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, 15:10
    #38733361
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Задача с полпинка решается вложенными циклами в количестве равном размеру массива. Если он неизвестен на этапе кодирования, то рекурсией с одним циклом внутри и одним - снаружи.

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

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

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

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

Как ты это сделал? Наверное ты знаешь алгоритм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:09
    #38733417
kefirko
kefirko
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
maytonkefirko, в четвертой строке твоего поста ты каким-то чудом написал все сочетания из 5.
Как ты это сделал? Наверное ты знаешь алгоритм.
Сарказм збс.
В прикрепленном файлике все есть. Написано вручную. Сначала на листочке, потом, для того чтобы было проще понять суть моего вопроса, набросал табличку. Ведь, чем лучше изложен вопрос, тем больше вероятности получить ответ.
Вручную то я и без алгоритма все варианты переберу, а вот каким должен быть код, для меня загадка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:10
    #38733418
kefirko
kefirko
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Сижу вот теперь читаю про рекурсию.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:17
    #38733422
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
kefirkoСижу вот теперь читаю про рекурсию.
Время теряешь. Я тебе самый простой алгоритм написал. Проще некуда, кода строк 10-15, но никто тебе тут их не напишет. Тут помогают решить а не решают.
Читай про работу с двоичными числами и битовые операции.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:27
    #38733424
VSVLAD
VSVLAD
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Примерно так в Excel будет выглядеть, вроде верно.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:28
    #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:29
    #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:30
    #38733428
kefirko
kefirko
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
Dima T, спасибо, будем копать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 20:39
    #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:45
    #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:49
    #38733437
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
maytonВот помедитируй над этим.
ИМХУ. Глупая подсказка. Немасштабируемо. Гибкости нет. Кое-какие языки позволяют сгенерить код и запустить, там это применимо, но далеко не все языки интерпретаторы :)

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

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

Третье - если разрешено использовать библиотеки длинной арифметики - то берем любую
по основанию 2 и юзаем.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
30.08.2014, 21:07
    #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:19
    #38733449
vmag
vmag
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива.
vmag,

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

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

+ пункт 1 в начале и пунк 3 в конце, нарисуйте блок схему на ватмане,
и отдайте преподу....
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Помогите составить алгоритм перебора всех возможных сумм элементов из исходного массива. / 25 сообщений из 36, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 504ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1341238]:
 0ms
get settings:
 10ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 161ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 74ms
get tp. blocked users:
 2ms
others: 221ms
total:  504ms
x
x
Закрыть


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