Форум программистов, компьютерный форум CyberForum.ru

Разложить число на возможные варианты суммы чисел массива - C++

Восстановить пароль Регистрация
 
TaPaH
0 / 0 / 0
Регистрация: 01.04.2013
Сообщений: 21
18.12.2013, 11:17     Разложить число на возможные варианты суммы чисел массива #1
Условие задачи: дан одномерный массив длины N и число L. Найти все возможные различные разложения числа L по элементам массива. Массив считается разложением числа L, если сумма его элементов равна L.
Т.е. есть у нас числа в массиве - 1,2,4,5 и если вводим число 7, программа должны вывести на экран комбинации сложений и их количество, тут это 1+2+4 и 2+5, значит комбинаций 2. При этом числа могут повторяться, например - 1, 1, 2, 4, 5 и здесь уже вариантов больше - 1+1+5, 2+4+1, 2+4+1, 5+2 и комбинаций 4. Как бы без языка программирования это понятно, но в голову, как на это дело написать алгоритм, ничего не лезет.
Прошу помощи.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.12.2013, 11:17     Разложить число на возможные варианты суммы чисел массива
Посмотрите здесь:

C++ Все возможные варианты перестановки символов строки
Варианты как разложить 5-значное число на цифры C++
Все возможные суммы элементов массива C++
C++ Двухзначное число втрое больше суммы своих чисел, а квадрат этой суммы равен утроенному начальному числу. Найти это число.
C++ Получить все возможные варианты загрузки ящиков
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
18.12.2013, 11:39     Разложить число на возможные варианты суммы чисел массива #2
Можно динамику прикрутить.

К примеру у тебя есть:
- solution(FIND, ARRAY) - возвращает сколькими способами можно набрать вес FIND в массиве ARRAY
- number_of(FIND, ARRAY) - возвращает сколько раз элемент FIND встречается в массиве ARRAY

Тогда solution(FIND, ARRAY) => number_of(FIND, ARRAY) + (разбиения на два числа) FOR(1<=I<FIND): solution(I, ARRAY) * solution(FIND-I, ARRAY) + разбиения на 3 и т.д. до разбиения на 7 единиц.

Если поймешь как это сделать динамику просто будет написать.
TaPaH
0 / 0 / 0
Регистрация: 01.04.2013
Сообщений: 21
18.12.2013, 11:58  [ТС]     Разложить число на возможные варианты суммы чисел массива #3
Хорошо, а если без solution(FIND, ARRAY) и number_of(FIND, ARRAY)? Просто интересовался с целью прикрутить алгоритм к 1с
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
18.12.2013, 12:13     Разложить число на возможные варианты суммы чисел массива #4
TaPaH, вы меня не правильно поняли.
Цитата Сообщение от outoftime Посмотреть сообщение
К примеру у тебя есть:
Я имел в виду что вы должны сами написать эти функции, что-бы они имели описанную функциональность.
Yandex
Объявления
18.12.2013, 12:13     Разложить число на возможные варианты суммы чисел массива
Ответ Создать тему
Опции темы

Текущее время: 18:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru