RECURSION C++ We are interested in computing the maximum number of pidgeys we co

Question

RECURSION C++

We are interested in computing the maximum number of pidgeys we could evolve given a certain number of candies because each evolution is worth 500 experience points. There is no simple mathematical formula where you can plug in the number of candy you have and calculate the number of pidgeys you can evolve, because transferring enough pidgeotto eventually results in enough candy to evolve more pidgeys. However, we can solve this problem with a recursive program.

Here is an example solution if you had 140 candies:

You could use 132 of those candies to evolve 11 pidgeys (11*12=132) leaving you with 8 candy leftover.

Those 11 evolutions give you 11 more candies, for a total of 19 candy.

Transferring the 11 pidgeotto you evolved gives you 11 more candies, for a total of 30 candy.

Repeat the process with the 30 candy.

You could use 24 of those candies to evolve 2 pidgeys (2*12=24) leaving you with 6 candy leftover.

Those 2 evolutions give you 2 more candies, for a total of 8 candy.

Transferring the 2 pidgeotto you evolved gives you 2 more candies, for a total of 10 candy.

10 candy is not enough to evolve, so that's it for evolution! But if there were 12 or more we'd repeat the process.

You have evolved a total of 13 pidgeys. Note that there are other evolution sequences that will result in the same total number of evolutions.

Write a program with a recursive function that takes as input the number of pidgey candy that you have. The function should return how many pidgey you could evolve, using the rules and procedure stated above.

Explanation / Answer

//C++ program

#include<iostream>

using namespace std;

int Evolution(int candy){

if(candy<12)return 0;

int evolution = candy/12;

return evolution+Evolution(candy%12+2*evolution);

}

int main(){

int candy;

cout<<"enter candy : ";

cin>>candy;

cout<<"pidgeys : "<<Evolution(candy);

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.