通过递归达到数字42

Question

我正在尝试创建一个用户输入数字(n)的熊游戏,程序将通过执行一些指定的步骤来查看它是否可以达到数字42.如果不能,则通知用户该号码无法达到目标.

这些是规则:

1. 如果n是偶数,那么你可以准确地回馈n/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

@ Corristo的答案很好,但可以使用类似的深度优先搜索算法,只需对代码进行最少的更改.我删除了多余的ifs和elses(因为我们在各种条件下都返回).

这个函数所做的不是像你的解决方案一样使用贪婪的方法,它会测试所有情况,直到找到答案.你的代码测试的第二个条件只有第一条件(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)来进一步优化它,如果您之前已经计算过存储结果并返回存储的结果,但它只会在极少数情况下有所帮助.