Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[13.58.39.23] |
|
Сообщ.
#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 Кбайт, скачиваний: 500) |
Сообщ.
#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, в качестве итога чего-нибудь скажешь? |
Сообщ.
#16
,
|
|
|
а как оценивается эффективность? если я буду выводить резульат с пробелами, то может оказаться, что у меня программа как бы менее эффективна.
тогда уж я их уберу #include <iostream> #include <vector> #define MIN(a,b) a < b ? a : b using namespace std; void ProduceSum(vector <unsigned int> &n, unsigned int max); int main(int argc, char* argv[]) { unsigned int num; vector <unsigned int> v; while(cin>>num) { ProduceSum(v,num); } return (0); } void ProduceSum(vector <unsigned int> &n, unsigned int reminder) { int i; if(!reminder) { if(n.size() == 1) return; for(i = 0; i < n.size() - 1; i++) cout<<n[i]<<"+"; cout<<n[i]<<endl; } else { unsigned int newMax = (n.empty()) ? reminder : MIN(*(n.end() - 1), reminder); for(i = 1; i <= newMax; i++) { n.push_back(i); ProduceSum(n, reminder - i); n.erase(n.end() - 1); } } return; } |
Сообщ.
#17
,
|
|
|
Похоже вариантов больше не будет, сегодня подведу итоги и отпостю.
|
Сообщ.
#18
,
|
|
|
Ну, как еще один вариант:
void DoSplit(int num, const std::string& str, int max) { char buff[16]; for (int n = min(max, num); n > 0; n --) { std::string tmp_str(str); if (!tmp_str.empty()) tmp_str +="+"; tmp_str += _itoa(n, buff, 10); if (n == num && !str.empty()) std::cout << tmp_str << std::endl; else DoSplit(num - n, tmp_str, n); } } void SplitInt(int num) { DoSplit(num, "", num); } но эффективным его не назовешь... |
Сообщ.
#19
,
|
|
|
потестил на числе 40 хватило. Время в сек.доли_сек
краткий обзор решений redfred - недождался, нахождение решения медленние чем вывод на экран. trainer - 10.76 tserega - 20.15 experimenter - 20.53 // спец. для tserega, другой вар, был прислан в приват tserega2 - 19.28 flex ferrum - 19.64 Самым хитрым оказался trainer, он сразу формировал строку, а потом выводил на экран. В остальных случаях почти все время съедал вывод на экран. В варианте flex ferruma похоже все ушло на std::string, хотя для решения вполне достаточно 1 массива, вмещающего максимальный ряд. ... еще добавлю коментарии завтра, сегодня уже мне пора. |
Сообщ.
#20
,
|
|
|
А если без учета вывода на экран?
|
Сообщ.
#21
,
|
|
|
Прошу мой вариант снять с конкурса. Он был нацарапан для примера, не претендовал на гениальность, и сразу оговаривалось, что не годится для больших чисел. Разумеется, более оптимальными являются решения, перебирающие не все возможные варианты, а только те которые по сумме совпадают
|
Сообщ.
#22
,
|
|
|
Итак, несколько слов о задаче:
в общем все уже поняли алгоритм, дающий только нужные варианты, приведу свой код void Analyze( unsigned rest, unsigned step, unsigned *prefix, unsigned prefix_size ){ // Вывод if( !rest && prefix_size > 1 ){ for( unsigned i=0;i<prefix_size-1;i++ )cout<< prefix[ i ] << '+'; cout<< prefix[ prefix_size-1 ] << endl; return; } // Итерации for( unsigned i=rest < step ? rest : step;i;--i ){ prefix[ prefix_size ] = i; Analyze( rest - i, i, prefix, prefix_size + 1 ); } } в, общем, логика у всех одинаковая, только разные типы данных, от того и разная скорость... однако, глядя на экран с ответами, можно увидеть "треугольнички единиц", которые дополняют почти все варианты B) Можно, использовать эту "фишку", для этого в начале проинициализировать используемый массив (prefix) одними единицами: int main(int argc, char* argv[]){ unsigned number = 0; cout << "Input number:"; cin >> number; unsigned *prefix = new unsigned[ number ]; for( unsigned i=0;i<number;i++ )prefix[ i ] = 1; // маленькая фишка Analyze( number, number-1, prefix, 0 ); delete []prefix; cout << endl << "Press any key...", getch(); return 0; } теперь можно в блоке "// Итерации" функции Analyze использовать предзаполненные ячейки массива // Итерации for( unsigned i=rest < step ? rest : step;i;--i ){ prefix[ prefix_size ] = i; if( i == 1 ){ // сразу переходим к концу цикла с единицами!! Analyze( 0, i, prefix, prefix_size + (rest - i) + 1 ); } else{ Analyze( rest - i, i, prefix, prefix_size + 1 ); } } --- Результаты без вывода на консоль для числа 75 мин:сек.доли_сек trainer - 0:7.83 tserega - 0:1.12 experimenter - 1:13.8 tserega2 - 0:1.35 flex ferrum - 2:9.35 самый быстрый алгоритм у tserega запустил его на числе 120 и сравнил алгоритмом, что я описал выше tserega - 5:2.49 tserega2 - 6:31.83 sazabis - 1:37.65 При росте числа - выгрыш растет в геометрической ? прогрессии Однако вариант предложенный trainer показал себя с наилучшей стороны и переплюнул все остальные почти в два раза Но и его можно было улучшить используя данную "фишку", только конкретно под этот вариант пришлось создать массив "1+1+1+...+1\n\0"; и подставлять в хвосты с соответствующим сдвигом время работы такого алгоритма для числа 75 - 0:1.30, для 120 - 4:54.3 ( набирает обороты при больших числах и обгоняет tserega ) с выводом на эран обгоняет вариант trainer с разницей ~ в разницу работы алгоритмов. |
Сообщ.
#23
,
|
|
|
Вау! Вот это комментарии и исследование!!!
|
Сообщ.
#24
,
|
|
|
здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное.
кстати, когда следующая задача планируется? мне очень нравится все, но какая конечная цель? еще у меня что-то типа пожелания. эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время. когда планируется следующая задачка? |
Сообщ.
#25
,
|
|
|
Цитата На днях. experimenter, 7.04.04, 09:09 когда планируется следующая задачка? Цитата Придумай задачу - будем решать. experimenter, 7.04.04, 09:09 еще у меня что-то типа пожелания. эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время. |
Сообщ.
#26
,
|
|
|
Мне тоже понравилось! Случайно заметил эту тему, решил поучаствовать. Жду следующую!!!
|
Сообщ.
#27
,
|
|
|
P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость.
|
Сообщ.
#28
,
|
|
|
Цитата trainer,7.04.04, 09:21 Придумай задачу - будем решать. Есть четырёхсвязный список элементов, т.е. в полной укомплектации это решетка . Задача: без использования рекурсии, расцепить все дочерние-нижестоящие элементы, начиная с указанного; без привлечения каких-либо дополнительных ресурсов, но элемент может содержать служебные поля (заполняемые в процессе разцепления и/или формирования). ЯВУ реализации - СИ. Примечание: можно принять допущение, что полной решетки быть не может, т.е. без циклов. |
Сообщ.
#29
,
|
|
|
Цитата experimenter, 7.04.04, 09:09 здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное. Я бы не стал так расстраиваться в конце концов в std, привиденных, вариантах ( experimenter и flex ferrum ) не было использовано то, что массив нет необходимости пересоздовать!, достаточно ограничивать вывод элементов массива Цитата trainer, 7.04.04, 09:41 P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость. e-e! it's cool |
Сообщ.
#30
,
|
|
|
2 Sazabis
так и нигде и не пересоздавал массив. там же везде ссылка стоит. а память, там сроду не должна была кроме одного раза как максимум перераспределиться. |