Program must be written in C++: 1) The greatest common divisor of integers x and

Question

Program must be written in C++:

1) 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 … Your 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

2)

code:

#include <iostream>
#include <math.h>
using namespace std;

bool isFibonacciNumber( int num, int a = 1, int b = 1 )
{
if( num == 0 || num == 1 )
return true;
int nextFibNum = a + b;
if( nextFibNum > num )
return false;
else if( nextFibNum == num )
return true;
else
isFibonacciNumber( num, b, nextFibNum );
}

int main()
{
int num=1;
while(num>0)
{
cout<<"Enter a number (enter a negative number to quit):";
cin>>num;
if(num<0)
break;
if(isFibonacciNumber(num))
{
cout<<"Yes, you got it, "<<num<<" is a Fibonacci number ";
}
else
{
cout<<" !!!!! Sorry "<< num<<" is not a Fibonacci number ";
}

}

cout<<num<<"(*Thanks – Have a good Day*)";

return 0;
}

==============================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ fibbo.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Enter a number (enter a negative number to quit):14
!!!!! Sorry 14 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):-1
-1(*Thanks – Have a good Day*)

===================================================

#include <iostream>
using namespace std;

int Gcd(int x, int y);

int main()
{
int x, y;

cout << "Enter X and Y integers: ";
cin >> x >> y;

cout << "GCD of " << x << " & " << y << " is: " << Gcd(x, y);

return 0;
}

int Gcd(int x, int y)
{
if (y != 0)
return Gcd(y, x % y);
else
return x;
}

================================================

output:

akshay@akshay-Inspiron-3537:~/Chegg$ g++ fibbo.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
Enter X and Y integers: 6
12
GCD of 6 & 12 is: 6

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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