Program must be written in C++: The greatest common divisor of integers x and y
ID: 3573830 • Letter: P
Question
Program must be written in C++:
The greatest common divisor of integers x and y is the largest integer that evenly divides both x and y. Write a recursive function gcd that returns the greatest common divisor of x and y. The gcd of x and y is defined recursively as follows. If y is 0 the answer is x; otherwise gcd(x, y) is gcd(y, x%y).
2) Write a recursive program that finds out if n is a Fibonacci number or not. The Fibonacci numbers are 0 1 1 2 3 5 8 13 21 … Y
our program should have the following interface:
Enter a number (enter a negative number to quit): 14 !!!!! Sorry14 is not a Fibonacci number
Enter a number (enter a negative number to quit): 13 Yes, you got it, 13 is a Fibonacci number Enter a number (enter a negative number to quit): 22 !!!!! Sorry 22 is not a Fibonacci number
Enter a number (enter a negative number to quit): 23 !!!!! Sorry 23 is not a Fibonacci number
Enter a number (enter a negative number to quit): 21 Yes, you got it, 21 is a Fibonacci number Enter a number (enter a negative number to quit): -1 (*Thanks – Have a good Day*)
Explanation / Answer
1.
#include <iostream>
using namespace std;
int gcd(int,int); //function prototype
int main()
{
int x,y;
cout << "Enter two positive integers: ";
cin >> x >> y;
cout << " G.C.D of " << x << " & " << y << " is: " << gcd(x,y);
return 0;
}
int gcd(int x, int y) //function definition
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
output:
2.
#include <iostream>
#include <cstdlib>
using namespace std;
bool isFibonacci( int number, int a = 1, int b = 1 )
{
if( number == 0 || number == 1 )
return true;//returning true for 0 and 1 .
int nextFib = a + b; // next number in the sequence
if( nextFib > number )
return false; //if we have passed the tested number, it's not in the fibonacci sequence
else if( nextFib == number )
return true; //if we have a match, the tested number is in the fibonacci sequence
else
isFibonacci( number, b, nextFib );//otherwise, get the next fibonacci number and repeat.
}
int main()
{
int n,i=0;
cout<<" Enter a number (enter a negative number to quit)";
cin>>n;
if(n < 0)
{
cout<<" (*Thanks – Have a good Day*)";
exit(0);
}
else
{
if(isFibonacci(n,1,1) == true)
cout<<"!!!!!Yes, you got it, "<<n<<" is a Fibonacci number ";
else
cout<<"!!!!!Sorry "<<n<<" is not a Fibonacci number";
}
return 0;
}
output:
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.