Достижение числа 42 путем рекурсии

Question

Я пытаюсь создать игру медведя, в которой пользователь вводит число (n), и программа увидит, сможет ли она достигать числа 42, выполнив некоторые указанные шаги. Если он не может, он уведомляет пользователя о том, что номер не может достичь цели.

Таковы правила:

1. Если п четно, то вы можете вернуть ровно п/2 медведей.
2. Если n делится на 3 или 4, вы можете умножить последние две цифры n и вернуть это многим медведям.
3. Если n делится на 5, то вы можете вернуть ровно 42 медведя.

Вот пример:

• Старт с 250 медведей
• С 250 делится на 5, вы можете вернуть 42 медведей, оставив вас с 208 медведей.
• Начиная с 208 года, вы можете вернуть половину медведей, оставив вас с 104 медведями.
• Начиная с 104 года, вы можете вернуть половину медведей, оставив вас с 52 медведями.
• Поскольку 52 делится на 4, вы можете умножить последние две цифры (в результате получится 10) и вернуть этих 10 медведей. Это оставляет вас с 42 медведями.
• Вы достигли цели!

Вот что я до сих пор:

#include <iostream> 

using namespace std; 

bool bears(int n); 

int main(){ 
    int number; 

    do{ 
     cout<<"enter the amount of bears (press 0 to stop the program): "; 
     cin>>number; 
     if (bears(number)){ 
      cout<<"you have reached the goal!"<<endl; 
     } 

     else{ 
      cout<<"sorry, you have not reached the goal."<<endl; 
     } 

    }while(number != 0); 
} 

bool bears(int n){ 
    if (n < 42){ 
     return false; 
    } 

    else if (n == 42){ 
     return true; 
    } 

    else{ 
     if (n % 5 == 0){ 
      return bears(n - 42); 
     } 

     else if(n % 2 == 0){ 
      return bears(n/2); 
     } 

     else if(n % 4 == 0|| n % 3 == 0) 
     { 
      int one; 
      int two; 
      one=n%10; 
      two=(n%100)/10; 
      return bears(n - one * two); 
     } 
    } 
} 

Моя программа имеет основные правила, но когда я типа в 250 медведей он говорит, что не может достичь цели. Я понимаю, что происходит в коде и почему он не может достичь указанной цели, но как сделать его универсальным, поэтому он будет работать не только для числа 250, но и для других чисел, таких как: 84.

Answer 1

@ Ответ Корристо хорош, но аналогичный алгоритм поиска по глубине может быть использован с минимальными изменениями в вашем коде. Я удалил избыточные if и else (так как мы возвращаемся в каждом состоянии).

Что делает эта функция, вместо использования жадного подхода, такого как ваше решение, оно проверяет все дел, пока не найдет ответ. Ваш код проверяет второе условие только в том случае, если первое условие (делимость на 5) равно , а не, и так далее.

bool bears(int n){ 
    if (n < 42) 
     return false; 

    if (n == 42) 
     return true; 

    // Moves on if condition isn't satisfied 
    if ((n % 5 == 0) && bears(n - 42)) return true; 

    if ((n % 2 == 0) && bears(n/2)) return true; 

    if(n % 4 == 0|| n % 3 == 0) 
    { 
     int one; 
     int two; 
     one=n%10; 
     two=(n%100)/10; 
     return one * two != 0 && bears(n - one * two); 
    } 

    return false; 
} 

Вы можете попробовать оптимизировать его дальше, используя кэш (std::map), в которой хранятся результаты и вернуть сохраненный результат, если вы вычислили его раньше, но это будет только помочь в очень редких случаях.

Answer 2

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

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

Для вашей игры это можно сделать, изменив функцию bears, чтобы получить целые числа std::vector, для которых он проверяет, содержит ли он хотя бы одно число, из которого может быть достигнуто 42.

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

bool bears(std::vector<int> ns) { 
    // first remove all numbers < 42 since the goal cannot be reached from them 
    ns.erase(std::remove_if(std::begin(ns), std::end(ns), 
          [] (auto const& n) { return n < 42; }), 
      std::end(ns)); 

    if (ns.empty()) { 
     return false; 
    } else if (std::any_of(std::cbegin(ns), 
          std::cend(ns), 
          [] (auto const& n) { return n == 42; })) { 
     return true; 
    } else { 
     auto possible_number_of_bears = std::vector<std::vector<int>>{}; 
     std::transform(std::cbegin(ns), 
         std::cend(ns), 
         std::back_inserter(possible_number_of_bears), 
         [] (auto const& n) { 
          auto after_possible_rules = std::vector<int>{}; 
          if (n % 5 == 0) { 
           after_possible_rules.emplace_back(n - 42); 
          } 

          if (n % 2 == 0) { 
           after_possible_rules.emplace_back(n/2); 
          } 

          if (n % 4 == 0 || n % 3 == 0) { 
           int one; 
           int two; 
           one = n % 10; 
           two = (n % 100)/10; 
           // avoid infinite recursion by only adding 
           // the new number if it is different from n 
           if (one * two != 0) { 
            after_possible_rules.emplace_back(n - one * two); 
           } 
          } 
          return after_possible_rules; }); 
     return std::any_of(std::cbegin(possible_number_of_bears), 
          std::cend(possible_number_of_bears), 
          bears); 
    } 
} 

Теперь вам нужно только настроить код вызова в

if (bears({number})) { 
    std::cout << "you have reached the goal!" << std::endl; 
} else { 
    std::cout << "sorry, you have not reached the goal." << std::endl; 
} 

и изменить вперед декларацию bears соответственно.