Can Someone Tell Me If This Is Correct? - Topic

Member

Posts: 14,537

Joined: Feb 13 2007

Gold: 3,241.00

Nov 17 2013 06:34pm

Write a complete C++ program that does the following:
1. The program will contain 3 functions.
a. Fibonacci function which calculates the nth Fibonacci number recursively
b. isPrime function which will check if n is a prime number recursively.
c. findSum function which will find the sum of all the digits recursively.
2. The main program will print out the first 30 fibonacci numbers (first loop), all the
prime number from 1 – 100(second loop). It will then utilize the findSum function
and calculates the sum of the integer 293817234.

#include <iostream>
#include <cmath> // for sqrt
#include <cstdlib> // for rand,min,max
using namespace std;

int findSum(int n){
if(n<10) return n;
else
return n%10 + findSum(n/10);
}

int Fibonacci(int n){
if(n==0) return 0;
if(n==1 || n==2) return 1;
else
return Fibonacci(n-1)+ Fibonacci(n-2); // Forgot to return the function.
}

bool isPrime(int n, int x){
if(x == n) // ONLY when divisor is increased to the point its euqual to n, do we return true, meaning its prime
else
return isPrime(n, x+1); // We can't call isPrime by returning it recursively b/c it will end the function regardless if its not prime
}

int main(){
int n;

cout << "The sum of the digits of 293817234 is ";
cout << findSum(293817234) << endl << endl;

cout << "The first 30 fibonacci numbers are: ";
cout << endl;
for(int i=1; i<=30; i++){
cout << Fibonacci(i) << " ";
}

cout << endl << endl;

cout << "The prime numbers from 1 to 100 are: " << endl;
for(int i=2; i<=100; i++){ //Start loop at 2 because 1 is not prime by definition
if(isPrime(i,2)== true){ // 2 is the argument for x in the definition which is the divisor. CASE SENSITIVE.
cout << i << " "; // Only when isPrime comes out TRUE, which means prime, do we print them out
}
}

return 0;

carteblanche

Member

Posts: 32,925

Joined: Jul 23 2006

Gold: 3,804.50

Nov 17 2013 06:43pm

why dont you just look at your output and see if it's correct? seriously, you should be able to test this yourself

huskerfan113

Member

Posts: 1,177

Joined: Feb 19 2006

Gold: 962.70

Nov 28 2013 02:50am

So... much... recursion...

You should try (just as practice) to come up with some faster ways. For instance, tell your computer to find the fibonacci sequence of 300 rather than 30 and report back if you see the issue I'm mentioning...

(Yep, I know... revived the dead thread to add nothing to it - Couldn't help myself)

KrzaQ2

Member

Posts: 9,803

Joined: Jun 28 2005

Gold: 6.67

Nov 28 2013 06:18pm

Quote (huskerfan113 @ 28 Nov 2013 10:50)

The result of fib(300) is well outside of any modern architecture's normal built-in types (~2.2e62), and because he uses int, integer overflow is undefined behaviour - anything can happen. There's no point in checking that.

huskerfan113

Member

Posts: 1,177

Joined: Feb 19 2006

Gold: 962.70

Nov 28 2013 09:01pm

Quote (KrzaQ2 @ Nov 28 2013 05:18pm)

I 100% agree with you that getting the result of Fibonacci(300) is completely absurd... I wasn't necessarily saying that he should try to find the 300th number in the sequence, just that if he changed his loop to execute until it got to 300 you would quickly see a problem of the recursive approach to solving the Fibonacci sequence problems.

Now, if this assignment was to explore recursion, then what he did is perfectly correct, I was simply suggesting that it would be beneficial as a CS/programming guy to see when recursion is not always the best solution to a problem, regardless of whether it works.

For instance, recursively solving this problem for the first X numbers (until I got bored of waiting) generates the following (again, I'm concerned about runtime, not the right answer. A problem can behave just like this without overflowing data types):

Code

Fibonacci(0): 0 Elapsed Time: 6.9704E-5s
Fibonacci(1): 1 Elapsed Time: 1.4061E-5s
Fibonacci(2): 1 Elapsed Time: 1.3163E-5s
Fibonacci(3): 2 Elapsed Time: 1.436E-5s
Fibonacci(4): 3 Elapsed Time: 1.2564E-5s
Fibonacci(5): 5 Elapsed Time: 1.2864E-5s
Fibonacci(6): 8 Elapsed Time: 1.3762E-5s
Fibonacci(7): 13 Elapsed Time: 1.436E-5s
Fibonacci(8): 21 Elapsed Time: 1.4958E-5s
Fibonacci(9): 34 Elapsed Time: 1.6154E-5s
Fibonacci(10): 55 Elapsed Time: 1.9445E-5s
Fibonacci(11): 89 Elapsed Time: 2.3335E-5s
Fibonacci(12): 144 Elapsed Time: 2.8719E-5s
Fibonacci(13): 233 Elapsed Time: 3.8591E-5s
Fibonacci(14): 377 Elapsed Time: 5.3849E-5s
Fibonacci(15): 610 Elapsed Time: 8.3166E-5s
Fibonacci(16): 987 Elapsed Time: 1.29535E-4s
Fibonacci(17): 1597 Elapsed Time: 1.93555E-4s
Fibonacci(18): 2584 Elapsed Time: 6.5785E-4s
Fibonacci(19): 4181 Elapsed Time: 4.99296E-4s
Fibonacci(20): 6765 Elapsed Time: 5.8037E-5s
Fibonacci(21): 10946 Elapsed Time: 6.7909E-5s
Fibonacci(22): 17711 Elapsed Time: 1.01115E-4s
Fibonacci(23): 28657 Elapsed Time: 1.55562E-4s
Fibonacci(24): 46368 Elapsed Time: 2.49797E-4s
Fibonacci(25): 75025 Elapsed Time: 3.88906E-4s
Fibonacci(26): 121393 Elapsed Time: 7.03323E-4s
Fibonacci(27): 196418 Elapsed Time: 0.001015046s
Fibonacci(28): 317811 Elapsed Time: 0.001630715s
Fibonacci(29): 514229 Elapsed Time: 0.002712474s
Fibonacci(30): 832040 Elapsed Time: 0.004246561s
Fibonacci(31): 1346269 Elapsed Time: 0.007097844s
Fibonacci(32): 2178309 Elapsed Time: 0.011025801s
Fibonacci(33): 3524578 Elapsed Time: 0.017870257s
Fibonacci(34): 5702887 Elapsed Time: 0.029311889s
Fibonacci(35): 9227465 Elapsed Time: 0.047736488s
Fibonacci(36): 14930352 Elapsed Time: 0.075374286s
Fibonacci(37): 24157817 Elapsed Time: 0.122507071s
Fibonacci(38): 39088169 Elapsed Time: 0.196033153s
Fibonacci(39): 63245986 Elapsed Time: 0.320241242s
Fibonacci(40): 102334155 Elapsed Time: 0.517071952s
Fibonacci(41): 165580141 Elapsed Time: 0.834085868s
Fibonacci(42): 267914296 Elapsed Time: 1.34936526s
Fibonacci(43): 433494437 Elapsed Time: 2.174353405s
Fibonacci(44): 701408733 Elapsed Time: 3.516113447s
Fibonacci(45): 1134903170 Elapsed Time: 5.713881123s
Fibonacci(46): 1836311903 Elapsed Time: 9.214309669s
Fibonacci(47): -1323752223 Elapsed Time: 14.961783346s
Fibonacci(48): 512559680 Elapsed Time: 24.175110875s
Fibonacci(49): -811192543 Elapsed Time: 39.177715354s
Fibonacci(50): -298632863 Elapsed Time: 63.278198644s
Fibonacci(51): -1109825406 Elapsed Time: 102.410173498s
Fibonacci(52): -1408458269 Elapsed Time: 165.773999501s

However solving with a different approach yields this:

Code

Fibonacci2(0): 0 Elapsed Time: 8.7056E-5s
Fibonacci2(1): 1 Elapsed Time: 1.8547E-5s
Fibonacci2(2): 1 Elapsed Time: 1.5556E-5s
Fibonacci2(3): 2 Elapsed Time: 1.9445E-5s
Fibonacci2(4): 3 Elapsed Time: 1.8548E-5s
Fibonacci2(5): 5 Elapsed Time: 1.8548E-5s
Fibonacci2(6): 8 Elapsed Time: 1.8548E-5s
Fibonacci2(7): 13 Elapsed Time: 1.9745E-5s
Fibonacci2(8): 21 Elapsed Time: 2.0044E-5s
Fibonacci2(9): 34 Elapsed Time: 1.9445E-5s
Fibonacci2(10): 55 Elapsed Time: 1.9744E-5s
Fibonacci2(11): 89 Elapsed Time: 3.1112E-5s
Fibonacci2(12): 144 Elapsed Time: 2.3335E-5s
Fibonacci2(13): 233 Elapsed Time: 1.9745E-5s
Fibonacci2(14): 377 Elapsed Time: 2.0043E-5s
Fibonacci2(15): 610 Elapsed Time: 2.0343E-5s
Fibonacci2(16): 987 Elapsed Time: 2.5728E-5s
Fibonacci2(17): 1597 Elapsed Time: 2.0044E-5s
Fibonacci2(18): 2584 Elapsed Time: 2.0343E-5s
Fibonacci2(19): 4181 Elapsed Time: 2.0043E-5s
Fibonacci2(20): 6765 Elapsed Time: 2.0044E-5s
Fibonacci2(21): 10946 Elapsed Time: 2.0043E-5s
Fibonacci2(22): 17711 Elapsed Time: 2.0342E-5s
Fibonacci2(23): 28657 Elapsed Time: 2.1539E-5s
Fibonacci2(24): 46368 Elapsed Time: 2.0642E-5s
Fibonacci2(25): 75025 Elapsed Time: 3.7096E-5s
Fibonacci2(26): 121393 Elapsed Time: 2.0642E-5s
Fibonacci2(27): 196418 Elapsed Time: 2.154E-5s
.
.
.
Fibonacci2(296): 5921388823061015893 Elapsed Time: 2.2138E-5s
Fibonacci2(297): 1938697607916024098 Elapsed Time: 2.2138E-5s
Fibonacci2(298): 7860086430977039991 Elapsed Time: 2.154E-5s
Fibonacci2(299): -8647960034816487527 Elapsed Time: 2.2138E-5s
Fibonacci2(300): -787873603839447536 Elapsed Time: 2.1839E-5s

Just trying to help challenge/expand the OP's skills

Go Back To Programming & Development Topic List