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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
TaPaH
0 / 0 / 0
Регистрация: 01.04.2013
Сообщений: 21
#1

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

18.12.2013, 11:17. Просмотров 1082. Ответов 3
Метки нет (Все метки)

Условие задачи: дан одномерный массив длины 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++
C++ Все возможные варианты перестановки символов строки
Варианты как разложить 5-значное число на цифры C++
Все возможные суммы элементов массива C++
C++ Двухзначное число втрое больше суммы своих чисел, а квадрат этой суммы равен утроенному начальному числу. Найти это число.
C++ Получить все возможные варианты загрузки ящиков
C++ Получить все возможные варианты комплектов книг. Исправить код
C++ Вывести все возможные варианты перестановок от 1 до n
Рассчитать все возможные варианты для 3 знаков C++
Определить все возможные варианты выплаты суммы N монетами 2 5 10 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     Разложить число на возможные варианты суммы чисел массива
Ответ Создать тему
Опции темы

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