RECURSION ALGORITHMS- EXAMPLES
Before you start solving the tasks, read the lesson on the page: Recursive algorithms
1. Degree calculation Xn
Write a program that uses recursion to solve degrees Xn
Input: The real number x (0.8 ≤ x ≤ 1.2) and the integer n (0 ≤ n ≤ 20) are entered from the standard input.
Output:
1.1
5
Write a value to the standard output Xn zaokruženu na 5 decimala.
Example:
Input:1.1
5
Output:
1.61051Solution: The task is explained in detail on the webpage: Recursion algorithm
2. First and second in the rankings
N participants participated in the athletic competition. At the end of the competition, the results are summarized and a list is formed
in non-increasing order by the number of getting points , from the highest to the lowest number of points scored. Write a program
which determines the number of points of competitors who are first and second on the ranking list.
in non-increasing order by the number of getting points , from the highest to the lowest number of points scored. Write a program
which determines the number of points of competitors who are first and second on the ranking list.
Input:
5
70
95
75
30
99
95
The first line of the standard input contains a natural number N (1 ≤ N ≤ 20000) which represents the number competitors. In each of the next N lines there is an integer from the interval [0, 20000], these numbers represent points of competitors, which are not sorted.
Output:One line of standard output shows the number of points of the first and second competitor on the ranking list.
Example:
Input:5
70
95
75
30
99
Output:
9995
3. Writing numbers inversely and directly
Write a recursive function that prints numbers from 1 to n in inverse and direct order.
4. Adding numbers recursively
Create a function that sums the first n natural numbers recursively. In the main method, enter n and call a recursive function to calculate the sum of those numbers.
5. Number of permutations
Enter an integer n, then determine the number of permutations of n elements, using recursion
6. The Fibonacci array
Enter an integer n and then print the Fibonacci sequence of n elements using recursion. Determine also the sum of all those elements.
7. From decimal to binary form
Write a recursive function that prints the natural number written in decimal form n in binary form in direct order.
Example 1:
Input
22
Output
0000 0000 0001 0110
Example 2:
Input
2147483647
Output
1111 1111 1111 1111
Example 1:
Input
22
Output
0000 0000 0001 0110
Example 2:
Input
2147483647
Output
1111 1111 1111 1111
8. The number of squares cut by the diagonal
|
A rectangle whose width and height are m[cm] and n[cm] respectively is composed of m*n squares whose sides are 1 cm each. Create a program that, using recursion, determines how many squares will be intersected with the main diagonal of that rectangle.
Example: Input 5 3 Output 7 |
Figure 1: Recursive functions: The number of squares cut by the diagonal of the rectangle that contains them
|
Solve the task according to the following algorithm:
- Enter two integers representing the length and width of rectangles a and b
- Divide the rectangle into squares of side 1 cm, so that the rectangle looks like a chessboard with b columns and a rows.
- Determine the coefficient of the diagonal direction as the tangent of the angle (ratio of the width and length of the rectangle b/a)
- Create a recursive function that returns the number of squares cut by the diagonal of the rectangle
- Pass the function the initial value of the length of the rectangle, the maximum value of the ymax coordinate in the first column of the square, as well as the direction coefficient.
- Inside the function, set the passed value for ymax to be ymin now. Determine ymax based on the kednac line ymax = ymin + k*1, where k is the coefficient of the direction transferred as a parameter, and 1 is the length of the side of the square.
- Inside the function, also, determine the smallest integer value less than the minimum and the smallest integer value greater than the maximum ymax,
determine the number of squares cut diagonally only in the current column and add it to the total number of squares cut in the following columns.
This number is obtained by calling the same recursive function again when obtaining the same return value. - Do this calculation under the condition that the number of remaining columns is greater than 1
- In each subsequent call to the recursive function:
- Reduce the remaining number of columns by 1
- the maximum value in the current recursion should become the minimum value ymin for the next recursion
/* Solution in programming language C */
#include < stdio.h>#include < math.h >
int brkv(float n, float ymin, float k)
{
int x;/*the number of intersected squares in the current column*/
int a,b;
float ymax=ymin + k; /*y=k*x*/
a=floor(ymin); /* the first smaller integer */
b=ceil(ymax);/* the first larger integer */
x=b-a;
if(n > 1)
}
int main()int a,b;
float ymax=ymin + k; /*y=k*x*/
a=floor(ymin); /* the first smaller integer */
b=ceil(ymax);/* the first larger integer */
x=b-a;
if(n > 1)
x = x + brkv(n-1, ymax, k); /* What is ymax here will be ymin in the next one */
return x;{
float a,b,k;
scanf("%f%f",&a,&b);
k=b/a; /* coefficient of the direction of the diagonal, i.e., the tangent of the angle that overlaps the diagonal with the side of the rectangle*/
printf("%d",brkv(a,0,k));
return 0;
}scanf("%f%f",&a,&b);
k=b/a; /* coefficient of the direction of the diagonal, i.e., the tangent of the angle that overlaps the diagonal with the side of the rectangle*/
printf("%d",brkv(a,0,k));
return 0;
9. Fast scaling algorithm
Write a recursive function to quickly calculate the power of some number: Xn
Enter an integer n and use the function to calculate the said power.
10. Solitaire
A solitaire of n floors should be whitewashed under the following conditions:
- each floor is painted either white or blue
- there must not be 3 white floors one above the other.