Programming Practice

快速費氏數列 (fast recursive Fibonacci sequence) 的定義如下:

寫一個 C 語言的程式以讀入一個整數 n,如果 n 大於或等於 0,則使用三種演算法計算 recursive Fibonacci, iterative Fibonacci, 和 fast recursive Fibonacci 及輸出費氏數;直到 n 小於零,則程式終止;同時輸入一個 count 正整數為重複次數,並輸出三種演算法的執行時間。程式執行範例:

Enter n for fib >> 5
Enter the repetitive count: >> 1000000

Recursive Fibonacci: 1000000 time(s), 0.0600000000 seconds
Result: 8

Iterative Fibonacci: 1000000 time(s), 0.0140000000 seconds
Result: 8

Fast recursive Fibonacci: 1000000 time(s), 0.0550000000 seconds
Result: 8

Enter n for fib >> 10
Enter the repetitive count: >> 100000

Recursive Fibonacci: 100000 time(s), 0.0670000000 seconds
Result: 89

Iterative Fibonacci: 100000 time(s), 0.0030000000 seconds
Result: 89

Fast recursive Fibonacci: 100000 time(s), 0.0200000000 seconds
Result: 89

Enter n for fib >> 20
Enter the repetitive count: >> 1000

Recursive Fibonacci: 1000 time(s), 0.0770000000 seconds
Result: 10946

Iterative Fibonacci: 1000 time(s), 0.0000000000 seconds
Result: 10946

Fast recursive Fibonacci: 1000 time(s), 0.0010000000 seconds
Result: 10946

Enter n for fib >> 40
Enter the repetitive count: >> 10

Recursive Fibonacci: 10 time(s), 12.2250000000 seconds
Result: 165580141

Iterative Fibonacci: 10 time(s), 0.0000000000 seconds
Result: 165580141

Fast recursive Fibonacci: 10 time(s), 0.0010000000 seconds
Result: 165580141

Enter n for fib >> 50
Enter the repetitive count: >> 1

Recursive Fibonacci: 1 time(s), 150.0620000000 seconds
Result: -1109825406

Iterative Fibonacci: 1 time(s), 0.0000000000 seconds
Result: -1109825406

Fast recursive Fibonacci: 1 time(s), 0.0000000000 seconds
Result: -1109825406

Enter n for fib >> -1