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

а как оценивается эффективность? если я буду выводить резульат с пробелами, то может оказаться, что у меня программа как бы менее эффективна.
тогда уж я их уберу

 
#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;
}

Сообщение отредактировано: experimenter - 04.04.04, 07:54

Похоже вариантов больше не будет, сегодня подведу итоги и отпостю.

Ну, как еще один вариант:

 
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);
}

но эффективным его не назовешь...

потестил на числе 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 массива, вмещающего максимальный ряд.

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

А если без учета вывода на экран?

Прошу мой вариант снять с конкурса. Он был нацарапан для примера, не претендовал на гениальность, и сразу оговаривалось, что не годится для больших чисел. Разумеется, более оптимальными являются решения, перебирающие не все возможные варианты, а только те которые по сумме совпадают

Итак, несколько слов о задаче:

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

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 с разницей ~ в разницу работы алгоритмов.

Вау! Вот это комментарии и исследование!!!

здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное.
кстати, когда следующая задача планируется? мне очень нравится все, но какая конечная цель?
еще у меня что-то типа пожелания.
эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время.
когда планируется следующая задачка?

Цитата

experimenter, 7.04.04, 09:09
когда планируется следующая задачка?

На днях.

Цитата

experimenter, 7.04.04, 09:09
еще у меня что-то типа пожелания.
эта задачка очень похожа на переборную и вместо вывода на экран лучше искать какой-то минимум на всей области решений или что-то типа того, тогда легче оценивать время.

Придумай задачу - будем решать.

Мне тоже понравилось! Случайно заметил эту тему, решил поучаствовать. Жду следующую!!!

P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость.

Цитата trainer,7.04.04, 09:21

Придумай задачу - будем решать.

Есть четырёхсвязный список элементов, т.е. в полной укомплектации это решетка .
Задача: без использования рекурсии, расцепить все дочерние-нижестоящие элементы, начиная с указанного; без привлечения каких-либо дополнительных ресурсов, но элемент может содержать служебные поля (заполняемые в процессе разцепления и/или формирования). ЯВУ реализации - СИ.
Примечание: можно принять допущение, что полной решетки быть не может, т.е. без циклов.

Цитата

experimenter, 7.04.04, 09:09
здорово, конечно. а потом говорят, что ООП программирование такое же эффективное, как и процедурное.

Я бы не стал так расстраиваться в конце концов в std, привиденных, вариантах
( experimenter и flex ferrum ) не было использовано то, что массив нет необходимости пересоздовать!, достаточно ограничивать вывод элементов массива

Цитата

trainer, 7.04.04, 09:41
P.S. Я так понимаю, народ понемногу созревает к соревнованиям на скорость.

e-e! it's cool

2 Sazabis
так и нигде и не пересоздавал массив. там же везде ссылка стоит. а память, там сроду не должна была кроме одного раза как максимум перераспределиться.