Algorithm using recursion

Question

I am given three operation on integer:
A - add 3 to number
B - doubles the number
C - swaps two last digits of number
I am supposed to write algorithm that checks if i can make k prime number using operations A,B,C in n steps. At the end i have to print the sequence of operations that i used to make k prime number. Lets assume we have function:

bool ifprime(int n);

The function ifprime returns true when the number is prime and return false when it is not.

The code:

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

My problem is that i do not know how to remember the correct path and then print it.

at the time when you've detected the positive result print a message, after every recursive call if the return value is true print a message. once debugged replace "print a message" with appropriate output step — bobah
– bobah, Commented Dec 7, 2013 at 19:08
Did you mean enter "print message" 'if(ifprime(k)){cout << a; return true;}' I do not really understand. When i print message after detection i won't be able to print all steps. I would be extremely grateful if you could explain me this one more time. — Marcin Majewski
– Marcin Majewski, Commented Dec 7, 2013 at 19:16
every time your is_possible() is about to return true, including cases when it returns a value from the recursive call to itself, log the message. — bobah
– bobah, Commented Dec 7, 2013 at 19:53

Sergey Kalinichenko · Accepted Answer · 2013-12-07 19:15:12Z

2

Pass an array steps of size n to your function as the forth parameter. Pass N, the total size of the array, as the fifth parameter. Put the value of a into steps[N-n] upon entering the function. Rather than returning bool, return an int that says how many steps it took to find a prime. If no prime has been found, return -1.

You need to return an int to know how many steps it took to come up with an answer in situations when it took less than n steps to reach a prime.

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

Note that this approach may not be fast enough. You may need to memoize your recursion.

answered Dec 7, 2013 at 19:15

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Marcin Majewski Over a year ago

I think i understood it, but i have question. "..." this three dots mean that code

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

?

Sergey Kalinichenko Over a year ago

@MarcinMajewski Yes - I did not want to copy the parts of your code that did not change. Did you check the link on memoization?

Marcin Majewski Over a year ago

I checked and it was very useful to understand the idea of "memorization". I will try to use this in this code. Thank you

Angus Comber · Accepted Answer · 2013-12-07 19:22:06Z

1

Or just print as you go (which is probably simplest way):

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

answered Dec 7, 2013 at 19:22

Angus Comber

9,86414 gold badges65 silver badges117 bronze badges

Comments

Vikram Bhat · Accepted Answer · 2013-12-07 19:25:43Z

1

I think you should not use a switch case if u want to evaluate all possibilities. Here is a way to do what u intended :-

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

edited Dec 7, 2013 at 19:25

answered Dec 7, 2013 at 19:16

Vikram Bhat

6,3063 gold badges22 silver badges19 bronze badges

Comments

Peter Csala · Accepted Answer · 2022-02-20 06:15:46Z

0

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

edited Feb 20, 2022 at 6:15

Peter Csala

23.7k16 gold badges51 silver badges96 bronze badges

answered Feb 19, 2022 at 13:00

Abhijeet kumar prasad

1

1 Comment

Sadra Over a year ago

If you add a short description, your answer will get more attention. Thanks for your contribution!

Collectives™ on Stack Overflow

Algorithm using recursion

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related