Разложение числа на сумму слагаемых
Пример.Дано целое число S. Требуется получить и вывести на экран все возможные различныеспособы представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1– это один и тот же способ разложения числа 3).Самое сложное в этой задаче – сразу исключить из рассмотрения повторяющиеся последовательности. Для этого будем рассматривать только неубывающие последовательности слагаемых(каждое следующее слагаемое не меньше предыдущего).Все слагаемые будем записывать в массив. Для этого нам понадобится массив (назовемего A) из Sэлементов, поскольку самое длинное представление – это сумма Sединиц. Чтобы нерасходовать память зря, лучше выделять его динамически (см. раздел про массивы).Пусть qэлементов массива (с номерами от 0до q-1) уже стоят на своих местах, причемA[q-1]=m. Каким может быть следующее слагаемое – элемент A[q]? Поскольку последовательность неубывающая, он не может быть меньше m. С другой стороны, он должен быть небольше, чем R=S-S0, где S0– сумма предыдущих элементов.Эти размышления приводят к следующей процедуре, которая принимает в параметрахсумму оставшейся части, массив для записи результата и количество уже определенных элементов последовательности.
void Split(int R, int A[], int q)
{
int i, start = 1;
if ( R <= 0 ) {
Дата добавления: 2015-10-05; просмотров: 1229;