На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Отрубание голов у гидры (введение в динам.программирование) , алгоритм, код на С++
    Всем хай! Сходу к делу!

    Есть такая задачка:
    Иван-дурак бьется с многоголовой гидрой (N - число голов, N <= 100K). Иван головы отрубает так: если у гидры четное число голов - он отрубает 9 голов, а если нечетное - 11 голов одним ударом. После каждого удара, если у гидры осталась не срубленной хотя бы одна голова, то отрастает еще 8 новых голов. Гидра побеждена, если после очередного удара мечом у нее не осталось ни одной головы.
    Нужно вычислить, сколько ударов мечом потребуется Ивану для победы, а также, сколько совокупно голов он срубит в течение сражения.


    Разумеется, задача простецкая и легко кодируется, правда, думал, что будет еще проще, т к какую-то сложность добавила проверка последнего удара мечом(многовато if-ов получилось).
    ExpandedWrap disabled
      int main(void)
      {
          const unsigned short HEAD_CHOP_9 = 9;
          const unsigned short HEAD_CHOP_11 = 11;
          const unsigned short HEAD_GROW = 8;
       
          int N;      // число голов у чудовища
          unsigned int countChops = 0;        // кол-во отрубаний
          unsigned int countChopHeads = 0;    // кол-во отрубленных голов
       
          cin >> N;
          
          // пока не все головы срублены у змия
          while(N > 0)
          {
              if(N % 2 == 0)  // четное кол-во голов
              {
                  if(N < HEAD_CHOP_9)     // происходит последнее отрубание (голов может быть меньше 9)
                      countChopHeads = countChopHeads + N;
                  else
                      countChopHeads = countChopHeads + HEAD_CHOP_9;
                  N = N - HEAD_CHOP_9;
              }
              else            // нечетное кол-во голов
              {
                  if(N < HEAD_CHOP_11)    // происходит последнее отрубание (голов может быть меньше 11)
                      countChopHeads = countChopHeads + N;
                  else
                      countChopHeads = countChopHeads + HEAD_CHOP_11;
                  N = N - HEAD_CHOP_11;
              }
              countChops++;
       
              // если головы остались, то дополнительно еще отрастают 8 штук
              if(N > 0)
                  N = N + HEAD_GROW;
          }
       
          cout << endl << countChops << "\t" << countChopHeads << endl;
       
          fflush(stdin);
          cin.get();
       
          return 0;
      }


    но задачу эту нужно решить с ПОМОЩЬЮ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

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

    Для применения динам.программирования нужно иметь:
    1. рекуррентную зависимость элементов динамики
    2. значение начальных состояний
    3. элементарный случай (конец всех вычислений)

    Применительно к поставленной задаче.
    1. Не будем применять никакие рекурсии
    2. Будем использовать одномерный массив для запоминания всех вычислений (этот массив будет выражать нужную нам последовательность, элементы которой связаны рекуррентно).

    Количество голов3333-11=22(22+8=30)30-9=21(21+8=29)29-11=18(18+8=26)...
    Номер удара0123...


    Какая тут рекуррентность?
    Получается такая:
    1. a[i] = a[i - 1] - 9, если N - четное
    2. a[i] = a[i - 1] - 11, если N - нечетное
    3. a[i] = 0, если N - четное И N < 9
    4. a[i] = 0, если N - нечетное И N < 11

    хотя №3 и №4 не чисто какие-то рекуррентные вроде...
    также немного смущает, что во всех 4-рех зависимостях нужно обращаться к N (текущее кол-во голов гидры)

    Какие минусы такого подхода (с массивом):
    1. требуется использовать доп.память
    2. выводить рекуррентные соотношения (в данной задаче они вроде простые, а иногда они абсолютно не очевидны)
    3. нет мемоизации вычислений, т к любое промежуточное вычисление используется лишь ОДНАЖДЫ
    4. нет упрощения кодирования по сравнению с простым циклом без всяких рекуррентностей

    Плюсы:
    1. ВАЖНЕЙШИЙ ПЛЮС: можно получить информацию промежуточную, например, сколько голов было у гидры на 5, 7, 23 ударе (эту информацию можно запросить ПОСЛЕ окончания всех вычислений)
    других плюсов вроде нет )) (плюсом могла быть мемоизация, но здесь ее вроде нет..)

    вопрос: правильно ли я составил алгоритм решения поставленной задачи методом динам.программирования??
    подскажите как быть-то...
      Цитата FasterHarder @
      азумеется, задача простецкая и легко кодируется, правда, думал, что будет еще проще, т к какую-то сложность добавила проверка последнего удара мечом(многовато if-ов получилось).

      Ты просто через одно место решал
      ExpandedWrap disabled
        #include <iostream>
        #include <algorithm>
         
        int main()
        {
            int n = 42;
            int heads = 0, chops = 0;
            while(1)
            {
                int delta;
                if (n % 2 == 0) delta = 9;
                else delta = 11;
                delta = std::min(delta, n);
                
                n -= delta;
                
                chops += 1;
                heads += delta;
                
                if(n > 0) n += 8;
                else break;
            }
            std::cout << chops << " " << heads;
        }

      Не говоря уже о том, что тут в общем-то элементарно выводится прямая формула (достаточно заметить, что если n велико, то два взмаха уменьшат число голов ровно на 4) и, соответственно, задача решается вообще без циклов.
        OpenGL, а я ведь специально выделяю красненьким вопрос, для таких как ты, чтобы было понятно, что же хочет ТС...
        за код тебе спс, правда он мне не нужен, в нем нет ничего такого, что мне пригодилось бы...))
          Да вопрос в принципе странный просто. Ты бы ещё суффиксные деревья или тернарный поиск приплёл сюда. Они ровно так же в тему будут при решении этой задачи.
            Кстати, действительно. Для конкретно этой задачи динамическое программирование чуть ли не худший способ решения.
            Вообще, эта задача лучше всего решается прямой формулой. А если прямая формула не подходит (эта задача всего лишь модель другой задачи с более сложными зависимостями), проще и быстрее просто промоделировать процесс рубки голов.
            0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
            0 пользователей:


            Рейтинг@Mail.ru
            [ Script execution time: 0,0627 ]   [ 16 queries used ]   [ Generated: 19.03.24, 03:20 GMT ]