Алгоритм с использованием рекурсии

Question

Я дал три операции на целое число:
A - добавьте 3 номер
B - удваивает количество
C - свопы две последние цифры номера
Я должен написать алгоритм, который проверяет, является ли я могу сделать k простое число с использованием операций A, B, C в n шагов. В конце я должен напечатать последовательность операций, которые я использовал для создания k простых чисел. Давайте предположим, что мы имеем функцию:

bool ifprime(int n); 

Функция ifprime возвращает истинное, когда число является простым и возвращать ложь, когда это не так.

Код:

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

Передайте массив steps размера n вашей функции в качестве четвертого параметра. Передайте N, общий размер массива, в качестве пятого параметра. Положите значение a в steps[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; 
} 

Обратите внимание, что этот подход может быть недостаточно быстрым. Возможно, вам потребуется memoize вашей рекурсии.

Answer 2

Я думаю, что вы не должны использовать корпус переключателя, если хотите оценить все возможности. Вот способ сделать то, что у предназначено: -

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 3

Или просто напечатать, как вы идете (который, вероятно, самый простой способ):

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); 
}