Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[52.14.85.76] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#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
так и нигде и не пересоздавал массив. там же везде ссылка стоит. а память, там сроду не должна была кроме одного раза как максимум перераспределиться. |