На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS RSS
>  Форум на Исходниках.RU
       Программирование
         C/C++
           Borland C++ Builder/Turbo C++ Explorer
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: trainer
Закрыто Adil 14-09-2011: Эпидемия некрофилии

Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )   закрыта · Новое голосование

> Задача №4, Разложение на слагаемые
Sazabis
Сообщ. #1, 30.03.04, 10:37

Master
******
Профиль · PM

Поощрения: 9 Dgm
Рейтинг (т): 122

Задача
Дано число от 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
___________
Dixi et ahinam levavi.
Wizard trainer
Сообщ. #2, 30.03.04, 10:55

Moderator
*********
Профиль · PM

Поощрения: 40 Dgm
Рейтинг (т): 639

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

Сообщение отредактировано: trainer - 30.03.04, 10:56
___________
Во имя Ctrl, Alt и святаго Del, Enter!

Основам программирования не обучаю. Не интересно.
Lepricon
Сообщ. #3, 30.03.04, 11:00
Member
**
Профиль · PM

Рейтинг (т): 1

N - натуральное или всё-таки целое?
___________
В программировании как в математике: всё логично, но неправильно
Sazabis
Сообщ. #4, 30.03.04, 11:08

Master
******
Профиль · PM

Поощрения: 9 Dgm
Рейтинг (т): 122

Цитата
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 ( все-таки программеры по своему цифры различают, нежели математики :) )
___________
Dixi et ahinam levavi.
redfred
Сообщ. #5, 30.03.04, 12:17
Member
**
Профиль · PM

Рейтинг (т): 4

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

Для чисел N допускающих простой перебор вариантов сгодится такой рекурсивный вариант.

ExpandedWrap disabled
    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
Sazabis
Сообщ. #6, 30.03.04, 12:46

Master
******
Профиль · PM

Поощрения: 9 Dgm
Рейтинг (т): 122

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 и т.д
___________
Dixi et ahinam levavi.
redfred
Сообщ. #7, 30.03.04, 13:04
Member
**
Профиль · PM

Рейтинг (т): 4

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

Исправленный вариант:
ExpandedWrap disabled
    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--;
    }//---------------------------------------------------------------------------
Wizard trainer
  Сообщ. #8, 31.03.04, 04:13

Moderator
*********
Профиль · PM

Поощрения: 40 Dgm
Рейтинг (т): 639

Вот мой вариант.
Только не спрашивайте о том, как он работает. :D
Прикреплённый файл: Прикреплённый файлTask004Unit.cpp (1.71 Кбайт, скачиваний: 215)
___________
Во имя Ctrl, Alt и святаго Del, Enter!

Основам программирования не обучаю. Не интересно.
Sazabis
Сообщ. #9, 31.03.04, 11:24

Master
******
Профиль · PM

Поощрения: 9 Dgm
Рейтинг (т): 122

2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )
___________
Dixi et ahinam levavi.
Wizard Flex Ferrum
Сообщ. #10, 31.03.04, 11:53

Wizard
*********
Профиль · PM

Поощрения: 25 Dgm
Рейтинг (т): 470

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

Будут :)
___________
"Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
Морган Фриман
Я на blogspot.com.
KAV_Invariant
Сообщ. #11, 31.03.04, 13:35

Master
******
Профиль · PM

Поощрения: 2 Dgm
Рейтинг (т): 131

Будут, как только появится свободное время. Завтра на уроках, например :D
___________
Я прихожу в бешенство от одной мысли о том, сколько бы я всего узнал, если бы не ходил в школу.
tserega
Сообщ. #12, 31.03.04, 13:43

Profi
*****
Профиль · PM

Поощрения: 1 Dgm
Рейтинг (т): 80

Sazabis, какое ограничение по N? Ограничение по времени есть?
___________
Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
Sazabis
Сообщ. #13, 31.03.04, 14:18

Master
******
Профиль · PM

Поощрения: 9 Dgm
Рейтинг (т): 122

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

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

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

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


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

Я олимпиадные задачки не вел, так что извиняюсь - все кустарным способом.
зы Хотя было бы проще если все было в in.txt - out.txt и время работы проги...
___________
Dixi et ahinam levavi.
tserega
Сообщ. #14, 31.03.04, 14:22

Profi
*****
Профиль · PM

Поощрения: 1 Dgm
Рейтинг (т): 80

Мое решение (правда, выдает в обратном порядке):
ExpandedWrap disabled
    #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;
        }
    }
___________
Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
Wizard trainer
Сообщ. #15, 04.04.04, 06:15

Moderator
*********
Профиль · PM

Поощрения: 40 Dgm
Рейтинг (т): 639

Я так понимаю, вариантов больше не будет. :)
Sazabis, в качестве итога чего-нибудь скажешь?
___________
Во имя Ctrl, Alt и святаго Del, Enter!

Основам программирования не обучаю. Не интересно.
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:

> Форум на Исходниках.RU · C/C++ · Borland C++ Builder/Turbo C++ Explorer

Закрыто Adil 14-09-2011: Эпидемия некрофилии

Страницы: (2) [1] 2  все закрыта · Новое голосование


[ Script Execution time: 0,1868 ]   [ 16 queries used ]   [ Generated: 18.04.14, 23:15 GMT ]  

Rambler's Top100