Задача №4, Разложение на слагаемые

[Sazabis]

Задача
Дано число от 1 до N, где N натуральное число.
Вывести на экран все возможные комбинации чисел ( от 1 до N-1 ) в сумме дающих заданное число. Формат вывода: <число>+<число>+ ... +<число><символ конца строки>

Пример для числа 3
1+1+1
2+1

Пример для числа 5
1+1+1+1+1
2+1+1+1
2+2+1
3+2
3+1+1
4+1

[trainer]

Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
Например, 1+2 и 2+1
Слагаемые в произвольном порядке или в порядке неубывания или возрастания?

Сообщение отредактировано: trainer - 30.03.04, 10:56

[Lepricon]

N - натуральное или всё-таки целое?

[Sazabis]

Цитата

trainer, 30.03.04, 13:55
Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
Например, 1+2 и 2+1

либо 1+2, либо 2+1

аналогично для 4
либо 2+1+1, либо 1+2+1, либо 1+1+2
в ответе может быть только 1 вариант

порядок не важен! но так как проверятся это будет глазами желательно упорядоченно!

Цитата

Lepricon, 30.03.04, 14:00
N - натуральное или всё-таки целое?

пусть N будет unsigned int ( все-таки программеры по своему цифры различают, нежели математики )

[redfred]

Красивая задачка !

Для чисел N допускающих простой перебор вариантов сгодится такой рекурсивный вариант.

static int   nN;            // Заданное число.
static int * pN;            // Накопитель слагаемых.
static int   iN;            // Счетчик накопителя.
void GoProcedure( int x );  // Рекурсивная процедура.
 
void ShowSumElems( int N )  // РЕШЕНИЕ ЗАДАЧИ.
{
 
  nN = N;
  pN = new int[N+1];
  iN = 0;
 
  GoProcedure(1);
 
  delete pN;
}//---------------------------------------------------------------------------
 
int Sum() { int s=0; for( int i=0; i<iN; i++ ) s += pN[i]; return s; }
//---------------------------------------------------------------------------
 
void GoProcedure( int x )
{
 if(iN == nN) return;                  // Условия выхода из рекурсии.
 
 pN[iN++] = x;
 
 if( nN == Sum() )
   {
     for( int i=0; i<iN; i++ )         // Печатаем подходящий вариант.
        {
          if( i ) printf("+");
                  printf("%i",pN[i]);
        }         printf("\n");
             goto SKIP_RECURSION;      // На зло противникам оператора goto :)
   }
     for( int ix=x; ix < nN; ix++ ) GoProcedure( ix ); // Выходим на следующую ступень рекурсии.
 
SKIP_RECURSION: iN--;
}//---------------------------------------------------------------------------

Вариант перебирает N^N/2 вариантов. Думаю, на числе N=20 комп загнется. Для больших чисел нужны более изящные варианты )

Сообщение отредактировано: trainer - 01.03.13, 13:56

[Sazabis]

redfred,
для 6:
1+1+1+1+1+1
1+1+1+1+2
1+1+1+3
1+1+2+2
1+1+4
1+2+3
1+5

например нет 3 + 3. 4 + 2 и т.д

[redfred]

Верно. Каюсь. Небрежно закодировал

Исправленный вариант:

static int   nN;            // Заданное число.
static int * pN;            // Накопитель слагаемых.
static int   iN;            // Счетчик накопителя.
void GoProcedure( int x );  // Рекурсивная процедура.
 
void ShowSumElems( int N )
{
  nN = N;
  pN = new int[N+1];
  iN = 0;
 
  for( int x=1; x<N; x++ ) GoProcedure(x);
 
  delete pN;
}//---------------------------------------------------------------------------
 
int Sum() { int s=0; for( int i=0; i<iN; i++ ) s += pN[i]; return s; }
//---------------------------------------------------------------------------
 
void GoProcedure( int x )
{
 if(iN == nN) return;                  // Условия выхода из рекурсии.
 
 pN[iN++] = x;
 
 if( nN == Sum() )
   {
     for( int i=0; i<iN; i++ )         // Печатаем подходящий вариант.
        {
          if( i ) printf("+");
                  printf("%i",pN[i]);
        }         printf("\n");
             goto SKIP_RECURSION;      // На зло противникам оператора goto :)
   }
     for( int ix=x; ix < nN; ix++ ) GoProcedure( ix ); // Выходим на следующую ступень рекурсии.
 
SKIP_RECURSION: iN--;
}//---------------------------------------------------------------------------

[trainer]

Вот мой вариант.
Только не спрашивайте о том, как он работает.
Прикреплённый файл: Task004Unit.cpp (1.71 Кбайт, скачиваний: 163)

[Sazabis]

2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )

[Flex Ferrum]

Цитата

Sazabis, 31.03.04, 14:24
2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )

Будут

[KAV_Invariant]

Будут, как только появится свободное время. Завтра на уроках, например

[tserega]

Sazabis, какое ограничение по N? Ограничение по времени есть?

[Sazabis]

Цитата

tserega, 31.03.04, 16:43
Sazabis, какое ограничение по N?

в общем нет, я просто посмотрю на цифре, на которой будет видна на глаз разница между разными алгоритмами

я думаю больше 1000 не понадобится

Цитата

tserega, 31.03.04, 16:43
Ограничение по времени есть?

тоже нет, просто сравню чей быстрее.
Этот алгорим работает дольше чем больше цифра, потому все просто - если на 100 не будет видно разницы - запущу на 200

Я олимпиадные задачки не вел, так что извиняюсь - все кустарным способом.
зы Хотя было бы проще если все было в in.txt - out.txt и время работы проги...

[tserega]

Мое решение (правда, выдает в обратном порядке):

#include <iostream.h>
#define maxSize 10000
 
void main() {
    long m[maxSize];
    long l = 0;
    long N = 5;
    //Main code
    m[0] = N;
    while (1 == 1) {
        int k = l;
        while (k >= 0) {
            if (m[k] > 1) {
                break;
            }
            k--;
        }
        if (k < 0) {
            break;
        }
        m[k]--;
        long s = 1 + l - k;
        l = k;
        while (s > 0) {
            k++;
            if (s < m[k - 1]) {
                m[k] = s;
                s = 0;
            } else {
                m[k] = m[k - 1];
                s -= m[k];
            }
            l++;
        }
        for (int i = 0; i < l; i++) {
            cout << m[i] << "+";
        }
        cout << m[l] << endl;
    }
}

[trainer]

Я так понимаю, вариантов больше не будет.
Sazabis, в качестве итога чего-нибудь скажешь?