Skip to main content
Code Review

Return to Answer

added 222 characters in body
Source Link
user272752
user272752

Added interest

With the recent posting of a very compact Python solution of the OP's problem, it behooves C to also present its possibilities of concise expression: C here

Added interest

With the recent posting of a very compact Python solution of the OP's problem, it behooves C to also present its possibilities of concise expression: C here

Add "poor man's profiling"...
Source Link
user272752
user272752

Poor man's profiling

Enter number: 832039
..........................514229 ........................196418 ......................75025 ....................28657 ..................10946 ................4181 ..............1597 ............610 ..........233 ........89 ......34 ....13 ..5 2

Simply adding putchar( '.' ); inside the function's while() loop, we can see the effect of recalculating the (shortened) Fibonacci sequence values to find these desired values. And this is the 'ceiling' of only 106 (considering only the first ~30 Fibonacci numbers).

Eventually, a long long will be necessary to go for more Fibonacci numbers. Given the finite maximums of a long and a long long, what are the maximum Fibonacci numbers that can be represented without recourse to more advanced techniques of representing very large integer values? Would it be worthwhile calculating as many of these constants as possible ONE TIME, then having those as a compile time array of values to use for this and other explorations of number theory?

(FYI: There are 182 dots (iterations) in that 'profiling' string, and there should be about 28 more if the function didn't shortcut by skipping 0+1 and 1+1.)

Poor man's profiling

Enter number: 832039
..........................514229 ........................196418 ......................75025 ....................28657 ..................10946 ................4181 ..............1597 ............610 ..........233 ........89 ......34 ....13 ..5 2

Simply adding putchar( '.' ); inside the function's while() loop, we can see the effect of recalculating the (shortened) Fibonacci sequence values to find these desired values. And this is the 'ceiling' of only 106 (considering only the first ~30 Fibonacci numbers).

Eventually, a long long will be necessary to go for more Fibonacci numbers. Given the finite maximums of a long and a long long, what are the maximum Fibonacci numbers that can be represented without recourse to more advanced techniques of representing very large integer values? Would it be worthwhile calculating as many of these constants as possible ONE TIME, then having those as a compile time array of values to use for this and other explorations of number theory?

(FYI: There are 182 dots (iterations) in that 'profiling' string, and there should be about 28 more if the function didn't shortcut by skipping 0+1 and 1+1.)

Source Link
user272752
user272752

Review:

Again, nice looking code that does what it is supposed to do. Well presented and fairly easy to follow. Kudos!

But, the exercise states "in any order", so much of the clerical code (that is correct, too) dealing with heap memory and a linked list is, in fact, a distraction.

Since the exercise is to generate the list of numbers only, the following (distilled from your code) is presented here for your learning and appraisal.

#include <stdio.h>

int find( int n ) {
    if( n == 1 ) return n;

    int f1 = 1, f2 = 2; // tiny shortcut as problem suggests
    while( f1 + f2 <= n ) {
        int fx = f1 + f2;
        f1 = f2;
        f2 = fx;
    }

    return f2;
}

int main( void ) {
    int n = 0;

    for( ;; ) { // infinite loop for testing many numbers
        printf("Enter number: ");
        if( scanf( "%d", &n ) != 1 ) { // check return codes!
            scanf( "%*[^\n]" ); // clear the input buffer. (read scanf doco!)
            continue;
        }

        for( int large; n; n -= large )
            printf( "%d ", large = find( n ) ); // output is all that's required
        puts( "" );
    }

    return 0;
}

Here's an abridged list of some Fibonacci numbers

       0   #01
       1   #02
...
  832040   #31
 1346269   #32 // Bigger than the problem's 1000000 limit

Output:

Enter number: 832039
514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2
Enter number:

Now that we know there are 31 Fibonacci numbers between 0 and 1000000, a simple array of int store[31] would more-than serve to store and print the found values of interest for this exercise.

Were such an array to be populated once at startup (only to the limit of interest for 'single shot' or to the 1000000 limit for multiple queries) determination of the Zeckendorf representation values to be printed would be greatly accelerated.

Your code is very good. A lesson that will be valuable going forward is to only write correct code to meet today's requirements. Some suggest coding in certain (costly) ways "in case the demands change tomorrow." Let tomorrow take care of itself. Take care that the user typing "foo", instead of 15642, doesn't cause your program to collapse in a pool of tears.