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

Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Задача №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
    Dixi et ahinam levavi.
      Комбинации, образованные перестановкой слагаемых - это один вариант или разные?
      Например, 1+2 и 2+1
      Слагаемые в произвольном порядке или в порядке неубывания или возрастания?
      Сообщение отредактировано: trainer -
      Во имя Ctrl, Alt и святаго Del, Enter!

      Основам программирования не обучаю. Не интересно.
        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 ( все-таки программеры по своему цифры различают, нежели математики :) )
          Dixi et ahinam levavi.
            Красивая задачка !

            Для чисел 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 -
              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.
                Верно. Каюсь. Небрежно закодировал :)

                Исправленный вариант:
                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--;
                  }//---------------------------------------------------------------------------
                  Вот мой вариант.
                  Только не спрашивайте о том, как он работает. :D
                  Прикреплённый файлПрикреплённый файлTask004Unit.cpp (1.71 Кбайт, скачиваний: 256)
                  Во имя Ctrl, Alt и святаго Del, Enter!

                  Основам программирования не обучаю. Не интересно.
                    2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )
                    Dixi et ahinam levavi.
                      Цитата
                      Sazabis, 31.03.04, 14:24
                      2 ответа уже есть, будут еще желающие ? ( возможно реализовать более бысто )

                      Будут :)
                      "Математики думают, что Бог в уравнениях, нейрологи уверены, что Бог в мозге, а программисты уверены, что Бог — один из них."
                      Морган Фриман
                      Я на blogspot.com.
                        Будут, как только появится свободное время. Завтра на уроках, например :D
                        Я прихожу в бешенство от одной мысли о том, сколько бы я всего узнал, если бы не ходил в школу.
                          Sazabis, какое ограничение по N? Ограничение по времени есть?
                          Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
                            Цитата
                            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.
                              Мое решение (правда, выдает в обратном порядке):
                              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;
                                    }
                                }
                              Р. Беллманн: "Если вы смогли решить задачу, значит это было упражнение; иначе - это научная проблема."
                                Я так понимаю, вариантов больше не будет. :)
                                Sazabis, в качестве итога чего-нибудь скажешь?
                                Во имя Ctrl, Alt и святаго Del, Enter!

                                Основам программирования не обучаю. Не интересно.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Закрыто Adil 14-09-2011: Эпидемия некрофилии



                                [ Script Execution time: 0,1575 ]   [ 16 queries used ]   [ Generated: 27.11.14, 05:12 GMT ]  

                                Rambler's Top100