Разбиение числа на слагаемые, Надо разбить число N на суму из K слагаемых. |
Разбиение числа на слагаемые, Надо разбить число N на суму из K слагаемых. |
DarkWishmaster |
17.04.2011 22:14
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Надо методом перебора. Я сделал, только они повторяются:
1 3 5 - 5 3 1 Может у вас есть алгоритм для этой задачи? Я думал сохранить результаты в массиве, т.е если числа вектора не повторяются с теми что из массива то добавляем в массив, но это не эфективно, думаю есть более простой метод. Спасибо. |
DarkWishmaster |
18.04.2011 16:38
Сообщение
#2
|
Бывалый Группа: Пользователи Сообщений: 168 Пол: Мужской Репутация: 3 |
Забыл сказать что все числа должны быть разными (т.е варианты типа 3 3 9 не печатать)
Вот моя идея: например для n=9, k=3 создаем вектор: 1 2 3 Теперь увеличиваем 3 пока сума вектора не будет N 1 2 4 1 2 5 1 2 6 -> решение теперь идем к переведущему числу, уже к 2 и увеличиваем его на 1 единицу: и опять последний увеличиваем: 1 3 4 1 3 5 -> решение увиличиваем 3 так как 1 4 5 больше N то идем к первому элементу и увеличиваем его 2 3 4 ->решение теперь уже ничего увеличивать нельзя, так как сума будет больше N Вот что я пробовал сделать : Program (Показать/Скрыть)
без рекурсии я знаю как сделать, а тут... Сообщение отредактировано: DarkWishmaster - 18.04.2011 16:39 |
Текстовая версия | 4.06.2024 1:58 |