PDS Lab Section 11 Week 3
Instructors: Satrajit Ghosh and Somak Aditya
Topic: Loops and Iterations
Important information and instructions:
● Only concepts up to Loops and Iterations can be used. No advanced
concept (e.g., functions, arrays, pointers etc.) is allowed.
● No library function except printf and scanf is allowed.
● You must submit exactly one C source file for the question.
● Make sure that your programs match the given sample outputs as
closely as possible.
● Name your file as “A02_ROLLNO.c”
1. A recurrence formula is one that helps us define a sequence of
numbers. Consider the following series (0, 1, 1, 2, 3, 5, 8, 13, 21,
….), which has the recurrence formula of
𝑥𝑛 = 𝑥𝑛−1 + 𝑥𝑛−2
Once we have the first two numbers 0 and 1 (i.e., 𝑥1 = 0, 𝑥2 = 1
), we can generate the entire series with this formula. Write a
program that does the following.
(a)It first asks the user for a single integer (say N) upto which
number the user wants. Using the above formula, and first two
numbers as 0 and 1; calculate the next numbers. First print N
numbers in the sequence. [10 points]
(b) Assume the Nth number is 𝑚. For each number above (say 𝑝),
print 𝑝 number of “*”s; surrounded by (approximately)
(𝑚 − 𝑝)/2. 0 number of “-”s both in left and right. The
number of “-”s in the left and right should differ at most by 1.
Total number spaces and “*”’s should sum to 𝑚. Final printed
pattern would resemble a tree. [25 points]
For example, suppose N=6. The Nth number is 13,
(i) first number is 1, print 6 “-”s, 1 *, then 6 “-”s.
(ii) second number is 2, print 5 “-”s, 2 *, then 6 “-”s.
(iii) third number is 3, print 5 “-”s, 3 *, then 5 “-”s.
(iv) fourth number is 5, print 4 “-”s, 5 *s, then 4 “-”s;
(v) fifth number is 8, print 2 “-”s, 8 *s, then 1 “-”s;
(vi) Last is 13. So, print 13 *s.
(c)Write a program that can take as input any recurrence formula,
where the next number calculation depends on M (up to 3)
previous numbers and a constant.
𝑥𝑛 = 𝑐1 * 𝑥𝑛−1 + 𝑐2 * 𝑥𝑛−2 + 𝑐3 * 𝑥𝑛−3 + 𝑐0
First ask the user to input how many previous numbers are
required. Say M is input. M should be between 1 to 3. Then,
using that, ask the user to input for M + 1 coefficients and first
M numbers of the series. [15 points]
(d) Print the new formula from user input. While printing
(i) ensure that you do not print the variables for which the
coefficient is zero,
(ii) ensure that the relation is well-formatted. There should
not be any dangling “+” in the beginning or the end.
[30 points]
(e)Ask the user of a single integer up to which you should print
the series (say N). Starting from M+1-th number, calculate
each new number and print the series up to N+M-th number.
You need to print the index and the number.
[20 points]
[BONUS] Take two recurrence relations of similar format as Part c.
Suppose one is 𝑥𝑛 = 𝑓(𝑥𝑛−1, 𝑥𝑛−2) and another is 𝑥𝑛 = 𝑔(𝑥𝑛−1, 𝑥𝑛−2).
Define another relation which is 𝑥𝑛 = 𝑓(𝑥𝑛−1, 𝑥𝑛−2)*𝑔(𝑥𝑛−1, 𝑥𝑛−2). Print
the final recurrence formula so that the final recurrence relation is printed
in descending order of degree. Print 10 numbers of the recurrence formula.
[20 points]
-------------- Sample Output 1-------
Enter Value of N? 8
The numbers are: 1, 2, 3, 5, 8, 13, 21, 34
----------------*-----------------
----------------**----------------
---------------***----------------
--------------*****---------------
-------------********-------------
----------*************-----------
------*********************-------
**********************************
Enter any recurrence formula.
Enter how many previous values are considered (upto 3)?
2
Enter coefficient and Enter value of x_0.
Constant Coef: 1
Enter coefficient and Enter value of x_1.
First coef, value: 2 1
Enter coefficient and Enter value of x_2.
Second coef, value: 3 1
The entered recurrence relation is: x_n = 2 * x_n-1 + 3 * x_n-2 + 1.
Enter Value of N? 6
3-rd Number: 6
4-th Number: 16
5-th Number: 51
6-th Number: 151
7-th Number: 456
8-th Number: 1366
-------------- Sample Output 2-------
Enter Value of N?7
The numbers are: 1, 2, 3, 5, 8, 13, 21
----------*----------
---------**----------
---------***---------
--------*****--------
------********-------
----*************----
*********************
Enter any recurrence formula.
Enter how many previous values are considered (upto 3)?
1
Enter coefficient and Enter value of x_0.
Constant Coef: 0
Enter coefficient and Enter value of x_1.
First coef, value: 2 1
The entered recurrence relation is: x_n = 2 * x_n-1 .
Enter Value of N? 6
2-nd Number: 2
3-rd Number: 4
4-th Number: 8
5-th Number: 16
6-th Number: 32
7-th Number: 64
