2015-10-22
920
Else
for (int i = q; i <= N; i ++) {
temp = A[q]; A[q] = A[i]; A[i] = temp; // A[q]<->A[i]
Permutations(A, N, q+1); // рекурсивныйвызов
temp = A[q]; A[q] = A[i]; A[i] = temp; // A[q]<->A[i]
}
}
Разложение числа на сумму слагаемых
Пример. Дано целое число 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) {
PrintData (A, q);
return;
}
if (q > 0) start = A[q-1]; // новыйэлементнеменьше A[q-1]
for (i = start; i <= R; i ++) { // перебратьвседо R
A[q] = i;
Split(R-i, A, q+1); // рекурсивныйвызов
}
}
Основная программа вызывает эту процедуру так (используется динамический массив):
#include <stdio.h>
// здесь надо поместить процедуры Split и PrintData
Main()
{
int *A, S;
printf ("Введите натуральное число ");
scanf ("%d", &S);
A = new int[S]; // выделитьпамять
Split (S, A, 0); // получить все разложения
