Задача. Дано целое число S. Требуется получить и вывести на экран все возможные различные способы представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это одинаковый способ разложения числа 3).

Решение.

Самое   сложное   в   этой   задаче    сразу   исключить   из   рассмотрения   повторяющиеся последовательности. Для этого будем рассматривать      только      невозрастающие последовательности слагаемых (каждое следующее слагаемое не больше предыдущего). Все  слагаемые  будем  записывать  в  массив.  Для  этого  нам  понадобится  массив  (назовем его A) из S элементов, поскольку самое длинное представление - это сумма S единиц. Чтобы не расходовать память зря, лучше выделять его динамически (см. раздел про массивы). Пусть q элементов массива (с номерами от 0 до q-1) уже стоят на своих местах, причем A[q-1]=m.   Каким   может   быть   следующее   слагаемое   -   элемент   A[q]?   Поскольку последовательность невозрастающая, он не может быть больше q. С другой стороны, он должен быть не больше, чем S-S0, где S0 - сумма предыдущих элементов.  Очевидно, что минимальное значение этого элемента - единица. Эти  размышления  приводят  к  следующей  процедуре,  которая  принимает  в  параметрах сумму  оставшейся  части,  массив  для  записи  результата  и  количество  уже  определенных элементов последовательности.


void Split(int R, int A[], int q)

{

   int i, last = R;

if ( R == 0 ) PrintData ( A, q );

   else {

     if ( q > 0   &&  last > A[q-1] )

        last = A[q-1];

     for (i = 1; i <= last; i ++ ) {

        A[q] = i;

        Split (R-i, A, q+1);

     }

  }

}

Основная программа вызывает эту процедуру так (используется динамический массив):


#include <stdio.h>

... // здесь надо поместить процедуры Split и PrintData

void main()

{

   int *A, S;

  printf ( "Введите натуральное число ” );

  scanf ( "%d”, &S );

   A = new int[S];

     Split (S, A, 0);

   delete A;

  }


2009-12-19 • Просмотров [ 2551 ]