Assignment 3 Problem A Fibonacci sequence Solution

Description:




The Fibonacci sequence is defined as follows:

Fn+1 = Fn + Fn-­‐1

with F0=0 and F1=1. Here we take F0=1 and F1=2. The first 10 Fibonacci numbers will be:




1, 2, 3, 5, 8, 13, 21, 34, 55, 89




Input:




The first line will be an integer T (1<=T<=100), which is the number of test cases. For each test case, there will be an integer n (1<=n<=109) means the upper bound of the numbers.




Output:




For each test case, print all the Fibonacci numbers which is not more than n in ascending order.




Sample Input:




2

6

13




Sample Output:




1

2

3

5

1

2




3

5

8

13



Problem B: Zeckendorf’s theorem version 1




Description:




There is a well known magical trick in which you have 10 cards with long lists of ordered but otherwise random-­‐looking numbers. You ask someone to think of a number between 1 and 100, then to tell you on which cards this number can be found (it may be several ones). Magically (assuming you can add in your head) you can tell which is the number.




This trick is based on what is known as Fibonacci numbers and Zeckendorf’s theorem.




Fibonacci numbers are defined as follows:

Fn+1 = Fn + Fn-­‐1

with F0=0 and F1=1. For the purpose of the magical trick, we’ll take F0=1 and F1=2.

The first 10 Fibonacci numbers will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89




(the 11th one is of course bigger than 100). In the trick, the first number on each card is one of these Fibonacci numbers.




Zeckendorf’s theorem states that every positive integer can be decomposed into a unique sum of non-­‐consecutive Fibonacci numbers. If you print each number between 1 and 100 on each card that starts with a Fibonacci number from that sum, you just have to add up the first numbers of the card to get the number chosen by the user.




Write a function that stores the first 10 Fibonacci numbers in an array fib and gets the above list, assuming that fib[0] is initialized to 1 and fib[1] initialized to 2.




Write the Zeckendorf decomposition of ANY number between 1 and 100. To decompose a number, you find the greatest Fibonacci number smaller (or equal) to the number, subtract it from the number and iterate. This will tell you on which cards the number should appear.




Input:




The first line will be an integer T (1<=T<=150), which is the number of test cases. For each test case, the first line will be an integer n (1<=n<=100) means the number to decompose.




Output:




For each test case, output cards in ascending order, separated by a space.

For number not in range [1, 100], output “Invalid Number”




Sample Input:




5

-­‐1




101

1

10


40




Sample Output:




Invalid Number




Invalid Number




1

2 8

1 5 34


Problem C: Zeckendorf’s theorem version 2




Description:




There is a well known magical trick in which you have 10 cards with long lists of ordered but otherwise random-­‐looking numbers. You ask someone to think of a number between 1 and 100, then to tell you on which cards this number can be found (it may be several ones). Magically (assuming you can add in your head) you can tell which is the number.




This trick is based on what is known as Fibonacci numbers and Zeckendorf’s theorem.




Fibonacci numbers are defined as follows:

Fn+1 = Fn + Fn-­‐1

with F0=0 and F1=1. For the purpose of the magical trick, we’ll take F0=1 and F1=2.

The first 10 Fibonacci numbers will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89




(the 11th one is of course bigger than 100). In the trick, the first number on each card is one of these Fibonacci numbers.




Zeckendorf’s theorem states that every positive integer can be decomposed into a unique sum of non-­‐consecutive Fibonacci numbers. If you print each number between 1 and 100 on each card that starts with a Fibonacci number from that sum, you just have to add up the first numbers of the card to get the number chosen by the user.




Write a function that stores the first 10 Fibonacci numbers in an array fib and gets the above list, assuming that fib[0] is initialized to 1 and fib[1] initialized to 2.




Write the Zeckendorf decomposition of ANY number between 1 and 100. To decompose a number, you find the greatest Fibonacci number smaller (or equal) to the number, subtract it from the number and iterate. This will tell you on which cards the number should appear.




What you need to do is to print the contents of cards with a upper bound, for example, if the upper bound is n, you just need to work on numbers in range [1, n].




Input:




The first line will be an integer T (1<=T<=150), which is the number of test cases. For each test case, there will be an integer n (1<=n<=100) means the upper bound of the numbers.




Output:




For each test case, output numbers in cards in ascending order, separated by a space.




You should only print the cards with at least one number.




Sample Input:




2

10




20




Sample Output:




Card #1: 1 4 6 9

Card #2: 2 7 10

Card #3: 3 4

Card #4: 5 6 7

Card #5: 8 9 10

Card #1: 1 4 6 9 12 14 17 19

Card #2: 2 7 10 15 20

Card #3: 3 4 11 12 16 17




Card #4: 5 6 7 18 19 20

Card #5: 8 9 10 11 12

Card #6: 13 14 15 16 17 18 19 20






















































































































































Page 5