使用递归的算法

Question

我得到了三个整数操作：
A-将3添加到number
B-将数字
C加倍-交换number
的最后两位数字我应该编写算法来检查我是否可以在n步中使用操作A、B、C制作k素数。最后，我必须打印我用来制作k素数的操作序列。让我们假设我们有函数：

bool ifprime(int n);

当数字为素数时，函数ifprime返回true，否则返回false。

代码：

bool is_possible(int k, int n, int a)
{
    if(ifprime(k))
    {
        return true;
    }
    if(n==0)
    {
        return false;
    }
    switch(a)
    {
        case 1:
            k = A(k); // perform operation A
            break;
        case 2:
            k=B(k); //perform operation B
            break;
        case 3:
            k=C(k); //perform operation C
            break;
    }
    return is_possible(k,n-1,1)||is_possible(k,n-1,2)||is_possible(k,n-1,3);
}

我的问题是，我不知道如何记住正确的路径，然后打印出来。

Answer 1

如果你想评估所有的可能性，我认为你不应该使用开关盒。这里有一个方法可以做到你想要的：-

bool is_possible(int k,int n,int i,char* ch) {

    if(ifprime(k)) {
         ch[i] = '\0';
         return true;
    }

    if(n==0)
       return false;

    if(is_possible(A(k),n-1,i+1,ch)) {

        ch[i] = 'A';
        return true;
    }
    if(is_possible(B(k),n-1,i+1,ch)) {

        ch[i] = 'B';
        return true;
    }
    if(is_possible(C(k),n-1,i+1,ch)) {

        ch[i] = 'C';
        return true;
    }

   return false;

}

if(is_possible(3,5,0,ch))
      print(ch);

Answer 2

或者只需边走边打印（这可能是最简单的方法）：

bool is_possible(int k, int n, int a)
{
    if(ifprime(k))
    {
        return true;
    }
    if(n==0)
    {
        return false;
    }
    std::cout << "n=" << n << " a = " << a << std::endl;
    switch(a)
    {
        case 1:
            k = A(k); // perform operation A
            break;
        case 2:
            k=B(k); //perform operation B
            break;
        case 3:
            k=C(k); //perform operation C
            break;
    }
    return is_possible(k,n-1,1)||is_possible(k,n-1,2)||is_possible(k,n-1,3);
}

Answer 3

将大小为n的数组步骤作为第四个参数传递给您的函数。传递N，数组的总大小，作为第五个参数。输入函数时将a的值放入步骤[N-n]中。不是返回bool，而是返回一个int，说明找到素数需要多少步骤。如果没有找到素数，则返回-1。

您需要返回一个int以了解在达到质数所需的步骤少于n步骤的情况下需要多少步骤才能得出答案。

int is_possible(int k, int n, int a, int[] steps, int N) {
    if(ifprime(k))
    {
        return N-n;
    }
    if (!n)
    {
        return -1;
    }
    steps[N-n] = a;
    ...
    for (int i = 1 ; i <= 3 ; i++) {
        int res = is_possible(k, n-1, i, steps, N);
        if (res != -1) return res;
    }
    return -1;
}

请注意，这种方法可能不够快。您可能需要记住您的递归。