Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.151.141] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Задача
Дано число от 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 |
Сообщ.
#2
,
|
|
|
Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
Например, 1+2 и 2+1 Слагаемые в произвольном порядке или в порядке неубывания или возрастания? |
Сообщ.
#3
,
|
|
|
N - натуральное или всё-таки целое?
|
Сообщ.
#4
,
|
|
|
Цитата 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 ( все-таки программеры по своему цифры различают, нежели математики ) |
Сообщ.
#5
,
|
|
|
Красивая задачка !
Для чисел 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 комп загнется. Для больших чисел нужны более изящные варианты ) |
Сообщ.
#6
,
|
|
|
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 и т.д |
Сообщ.
#7
,
|
|
|
Верно. Каюсь. Небрежно закодировал
Исправленный вариант: 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--; }//--------------------------------------------------------------------------- |
Сообщ.
#8
,
|
|
|
Вот мой вариант.
Только не спрашивайте о том, как он работает. Прикреплённый файлTask004Unit.cpp (1.71 Кбайт, скачиваний: 503) |
Сообщ.
#9
,
|
|
|
2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )
|
Сообщ.
#10
,
|
|
|
Цитата Sazabis, 31.03.04, 14:24 2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто ) Будут |
Сообщ.
#11
,
|
|
|
Будут, как только появится свободное время. Завтра на уроках, например
|
Сообщ.
#12
,
|
|
|
Sazabis, какое ограничение по N? Ограничение по времени есть?
|
Сообщ.
#13
,
|
|
|
Цитата tserega, 31.03.04, 16:43 Sazabis, какое ограничение по N? в общем нет, я просто посмотрю на цифре, на которой будет видна на глаз разница между разными алгоритмами я думаю больше 1000 не понадобится Цитата tserega, 31.03.04, 16:43 Ограничение по времени есть? тоже нет, просто сравню чей быстрее. Этот алгорим работает дольше чем больше цифра, потому все просто - если на 100 не будет видно разницы - запущу на 200 Я олимпиадные задачки не вел, так что извиняюсь - все кустарным способом. зы Хотя было бы проще если все было в in.txt - out.txt и время работы проги... |
Сообщ.
#14
,
|
|
|
Мое решение (правда, выдает в обратном порядке):
#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; } } |
Сообщ.
#15
,
|
|
|
Я так понимаю, вариантов больше не будет.
Sazabis, в качестве итога чего-нибудь скажешь? |