PROBLEM SHEET 3

This problem sheet was created by Sir Narasimhan T, Assistant Professor, IT Department LBS College of Engineering, Kasaragod.

The softcopy in .pdf is available here. There is  a bit more in the file.

1)A generalized Fibonacci sequence is a sequence of numbers such that from the third number onwards, each number is the sum of preceding two numbers. An example of generalized Fibonacci sequence is: 2, 5, 7, 12, 19, · · · · · · , but 1, 2, 3, 4, · · · · · · is not. You are to write a program that, given a sequence of numbers, decides whether the sequence is a generalized Fibonacci sequence or not.

2)There are 500 light bulbs (numbered 1 to 500) arranged in a row. Initially they are all OFF. Starting with bulb 2, all even numbered bulbs are turned ON. Next, starting with bulb 3, and visiting every third bulb, it is turned ON if it is OFF, and it is turned OFF if it is ON. This procedure is repeated for every fourth bulb, then every fifth bulb, and so on up to the 500th bulb. Write a C program to determine which bulbs are off at the end of the above exercise.

3)In the Indian currency system, the denominations available are 5, 10, 20, 50, 100, 500 and 2000. To make a sum of 2000, you can use twenty 100 notes or four 500 notes or even a singe 2000 note (and many other combinations are possible). But the last option takes the least number of currency notes. Given the available denominations and the sum (input from user), write a program to make the sum using the available denominations with the least number of currency notes. (Assume the sum is an integer and forget about coins!!!)

4)Write a program that inputs a list of integers and an integer called target, and then prints the pair of elements whose sum is target. A sample input and output is given below.
Input the list
1 6 5 4 2 3 9 12
Input the target
7
The pair of elements that add to 7 are
1     6
5     2
4     3

5)Two players start playing a game. The game board consists of N heaps arranged in a sequence, each containing certain number of coins. The figure shows such a board with 5 heaps.
HEAP 1    HEAP 2    HEAP 3    HEAP 4    HEAP 5
7 coins    2 coins      4 coins      3 coins     5 coins

The two players move alternately from each end. When a player moves, he chooses a heap from either the left end or the right end of the sequence, and removes the selected heap of coins from the sequence. The player should be consistent in the sense that if he chooses to remove heap from left end of sequence, he should continue with left end only. The game is over when the board is exhausted (no coins left). The player who has collected the maximum number of coins wins the game. Write a program to play this game. A sample input and output is shown below:
Input
Enter the number of heaps
5
Enter the number of coins in each heap
7 2 4 3 5
Enter the id (1 or 2) of the player who starts the game
2
Enter L to choose left end or R for right end
L
Output
Player 2 wins with 13 coins
[Player 2 starts with left end and takes off the heap 1. So he has 7 coins. Next player 1 chooses heap 5 from right and gets 5 coins. Next player 2 chooses heap 2 and now has a total of 9 coins. Then player 1 chooses heap 4 and gets 8 coins in total. Finally player 2 chooses heap 3 and has now 13 coins. The game ends now because player 1 has no heap to choose.]

6)Write a program to print the pattern by inputting the number of lines:
1 3 5 7 9
3 5 7 9
5 7 9
7 9
9

7)Write a program to print the pattern by inputting the number of lines:

1
2 6
3 7 10
4 8 11 13
5 9 12 14 15

8)Write a program to print the pattern by inputting the number of lines:

1
1 2 1
1 2 3 2 1
1 2 3 4 3 2 1