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

Задача
Дано число от 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

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

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

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

Цитата

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 ( все-таки программеры по своему цифры различают, нежели математики )

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

Для чисел 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

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 и т.д

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

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

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

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

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

Цитата

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

Будут

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

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

Цитата

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

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

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

Цитата

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

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

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

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

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

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

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

 
#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
так и нигде и не пересоздавал массив. там же везде ссылка стоит. а память, там сроду не должна была кроме одного раза как максимум перераспределиться.