| Problem description | | Progress |
|
Темы:
recursion
Write a program with a recursive function to calculate the factorial.
Input
The first line contains a natural number N ( N<=12 ).
Imprint
Print the factorial of the number.
Examples
| # |
Input |
Output |
| 1 |
1 |
1 |
| 2 |
2 |
2 |
| |
![]()
|
|
Темы:
recursion
Write a program with a recursive function to calculate the sum of bits in a natural number.
Input
The first line contains a natural number N ( N<=109 ).
Imprint
Print the sum of the bits.
Examples
| # |
Input |
Output |
| 1 |
16 |
1 |
| 2 |
7 |
3 |
| |
![]()
|
|
Темы:
recursion
Write a program with a recursive function to calculate the product of bits in a natural number.
Input
The first line contains a natural number N ( N<=109 ).
Imprint
Output the product of bits.
Examples
| # |
Input |
Output |
| 1 |
16 |
0 |
| 2 |
7 |
1 |
| |
![]()
|
|
Темы:
recursion
Given a string containing only English letters (uppercase and lowercase). Add symbol ‘*’ (asterisk) between letters (you don't need to add "*" character before the first letter and after the last one).
Input
A string of non-zero length is entered. It is also known that the string length does not exceed 1000 characters.
Output
Output the string that will result after adding the characters '*'.
Examples
| # |
Input |
Output |
| 1 |
LItBeoFLcSGBOFQxMHoIuDDWcqcVgkcRoAeocXO |
L*I*t*B*e*o*F*L*c*S*G*B*O*F*Q*x*M*H*o*I*u*D*D*W *c*q*c*V*g*k*c*R*o*A*e*o*c*X*O |
| |
![]()
|
|
Темы:
recursion
You are given a string containing numbers and English letters (uppercase and lowercase). Find and display the number of digits.
Input
A string of non-zero length is entered. It is also known that the string length does not exceed 1000 characters.
Output
Print the number of digits present in the string.
Examples
| # |
Input |
Output |
| 1 |
74kz31n8pn26f2iv10c7u8x356gl73jlka67i929z08i5mnn35h0n |
28 |
| |
![]()
|
|
Темы:
recursion
Given a string containing only decimal digits. Write a program that uses recursion to find the largest digit.
When solving this problem, it is forbidden to use cycles and the word max.
Input
A string of non-zero length is entered. It is also known that the length of the string does not exceed 1000 characters and the string contains only decimal digits.
Output
Print the maximum digit that occurs in the input string.
Examples
| # |
Input |
Output |
| 1 |
11111111 |
1 |
| |
![]()
|
|
Темы:
recursion
Write a program containing a recursive function that solves the problem of finding the sum of numbers from 1 to n (n <= 100)
You cannot use cycles and the formula for the sum of an arithmetic progression in the program
The main program must contain initial data input, function call and response output
The input to the program is a number n
Examples
| |
![]()
|
|
Темы:
recursion
Given a natural number n, calculate the sum of all its natural divisors, including 1 and the number itself. Write the solution as a RECURSIVE function with one parameter. The main program must contain initial data input, function call and output response
Forbidden to use loops in the program
Examples
| |
![]()
|
|
Темы:
recursion
Write a program containing a recursive function that solves the problem of raising x to a natural power n.
The main program must contain the input of initial data, the call of the function and the output of the result
It is forbidden to use the built-in functions (and operations) of exponentiation, as well as cycles
The input to the program is two numbers x and n
Examples
| |
![]()
|
|
Темы:
recursion
Write a recursive function that selects squares of integers from a given sequence and prints them in reverse order. Using an array to store a sequence is not allowed. Loops are not allowed.
The main program must contain a function call and a result output
Input: The input lines contain integers, one per line. The last line contains the number 0.
Output: The program must print the elements of the resulting sequence, which are squares of integers, in reverse order on one line, separated by spaces. If there are none, the program should print the number 0.
Examples
| # |
Input |
Output |
| 1 |
1
2
3
4
0 |
4 1 |
| |
![]()
|
|
Темы:
recursion
Write a recursive function that calculates the sum of the elements of a sequence of integers given not its input. The input ends with the number 0. The main program must contain a function call and a result output. Loops are not allowed
Input: The input lines contain integers, one per line. The last line contains the number 0.
Output: The program should output a single number – the sum of all elements of the sequence.
Examples
| # |
Input |
Output |
| 1 |
1
2
3
0 |
6 |
| |
![]()
|
|
Темы:
recursion
Write a recursive function that calculates the maximum value from a sequence of integers given not its input. The input ends with the number 0. The main program must contain a function call and a result output. Loops are not allowed
Input: The input lines contain integers, one in each line. The last line contains the number 0.
Output: The program should output a single number – the maximum value of all elements of the sequence (not counting the number 0).
Examples
| # |
Input |
Output |
| 1 |
1
3
2
0 |
3 |
| |
![]()
|
|
Темы:
recursion
GCD and Euclid's algorithm
Two numbers are given. Find their greatest common divisor.
Input data: Enter two natural numbers not exceeding 10^9, (record 10^9 means "10 to the 9th power", that is, 1000000000).< /div>
Output: Print the GCD of the entered numbers
| |
![]()
|
|
Темы:
recursion
In the theory of computability, an important role is played by the Ackermann function A(m,n), defined as follows:
You are given two non-negative integers m and n, each on a separate line. Print A(m,n).
Examples
| |
![]()
|
|
Темы:
recursion
Function f with natural arguments and values is defined like this:
f(0) = 0
f(1) = 1
f(2n) = f(n)
f(2n + 1) = f(n) + f(n + 1)
Compose a program to calculate f(n) given n.
Input
Given a single number n (1 ≤ n ≤ 1018).
Output
| |
![]()
|
|
Темы:
recursion
Described a recursive function with three parameters F(a, b, c):
F(a, b, c) = 1 if a ≤ 0 or b ≤ 0 or c≤ 0;
F(a, b, c) = F(20, 20, 20) if a > 20 or b > 20 or c > 20;
F(a, b, c) = F(a, b, c-1) + F(a, b-1, c-1) - F(a, b-1, c), if a < b and b < c;
F(a, b, c) = F(a-1, b, c) + F(a-1, b-1, c) + F(a-1, b, c-1 ) - F(a-1, b-1, c-1), in all other cases.
Input
Input contains three integers a, b, c - function parameters F (-104 ≤ a,b,c ≤104).
Output
In response, display the value of the function F(a, b, c).
Examples
| # |
Input |
Output |
| 1 |
1 1 1 |
2 |
| 2 |
2 2 2 |
4 |
| 3 |
10 4 6 |
523 |
| 4 |
50 50 50 |
1048576 |
| |
![]()
|
|
Темы:
recursion
Depth walk
Given an nxn chessboard. Let the knight stand on the cell (1,1). It is necessary to find such a sequence of moves of the knight, in which he visits each square of the board exactly once.
Input
The input to the program is a natural number n (n ≤ 8).
Output
If the bypass is impossible, then output 0 to the output file, if possible, then 1, and on the next lines print the matrix nn, illustrating the order of the bypass. It is not necessary to align numbers by columns.
Note. The speed of the recursive program in this problem essentially depends on the order in which the variants of the knight's move from the next cell will be considered. One good order is to place all eight options "in a circle".
| Input |
Output |
| 3 |
0 |
| 5 |
1
1 20 17 12 3
16 11 2 7 18
21 24 19 4 13
10 15 6 23 8
25 22 9 14 5
|
| |
![]()
|
|
Темы:
recursion
It is required to display all different representations of a natural number N as a sum of natural numbers. Representations that differ from each other in the order of terms are not different.
Input
The input string contains an integer N (2 ≤ N ≤ 40).
Output
In your answer, output all different representations of the number N without repetitions as a sum one at a time on a separate line. Both the terms and the sums themselves can follow in any order.
Examples
| # |
Input |
Output |
| 1 |
4 |
|
| 2 |
5 |
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
1 4
5
|
| |
![]()
|
|
Темы:
recursion
A ladder is a set of cubes, in which each of the upper ones
layer contains fewer cubes than the previous one.
---
| |
---------
| | | | |
-----------
| | | | | |
-----------------
| | | | | | | | |
-----------------
Count the number of ladders that can be built with N cubes.
Input
The input file contains the number N (1<=N<=100).
Output
Output the desired number of ladders into the output file.
Example
Example input file
3
Example output file
2
| |
![]()
|
|
Темы:
recursion
In the Enchanted Land, coins of denominations A1, A2,..., AM are used. The magic man came to the store and found that he had exactly two coins of each denomination. He needs to pay the amount N. Write a program to determine if he can pay without change.
Input
At the input of the program first comes the number N (1 <= N <= 109), then the number M (1 <= M <= 15) and then M pairwise distinct numbers A1 , A2,..., AM (1 <= Ai <= 109 ).
Imprint
First print K - the number of coins that the Magic Man will have to give if he can pay the specified amount without change. Then print K numbers that define the values of the coins. If there are several solutions, print the variant in which the Magic Man gives the smallest possible number of coins. If there are several such options, print any of them.
If you cannot do without change, then print a single number 0. If the Magic Man does not have enough money to pay the specified amount, print a single number -1 (minus one).
| Input |
Output |
100 6
11 20 30 40 11 99
| 3
40 30 30
|
| |
![]()
|
|
Темы:
recursion
It is known that any natural number can be represented as the sum of at most four squares of natural numbers. Vasya decided to come up with a similar statement for cubes - he wants to know how many cubes are enough to represent any number. His first working hypothesis is eight.
It turned out that almost all the numbers that Vasya could come up with can be represented as a sum of no more than eight cubes. However, the number 239, for example, does not allow such a representation. Now Vasya wants to find some other such numbers, and also, perhaps, some pattern in the representations of all other numbers, in order to put forward a hypothesis about the form of all numbers that are not represented as the sum of eight cubes.
Help Vasya write a program that would check if it is possible to represent a given natural number as a sum of no more than eight cubes of natural numbers, and if possible, find some such representation.
Input
A natural number is entered N <= 2*109.
Imprint
It is required to print no more than eight natural numbers, whose cubes add up to N. If the required representation does not exist, then the word IMPOSSIBLE.
should be output to the output file
Examples
| # |
Input |
Output |
| 1 |
239 |
IMPOSSIBLE |
| 2 |
17 |
2 2 1 |
| |
![]()
|
|
Темы:
recursion
The number N is entered. Generate in anti-lexicographic order all sequences of length N (1≤N≤9) consisting of the numbers 3, 4, 5, in which the number of triples does not exceed two.
In "anti-lexicographic" means "in reverse order of lexigographic" (see example).
In "lexicographical order" means that if two sequences coincide at the first X places, but differ at the X+1 place, then the one in which the number at the X+1 place is less should go first.
In the anti-lexicographic, respectively, vice versa.
Examples
| # |
Input |
Output |
| 1 |
3 |
5 5 5
5 5 4
5 5 3
5 4 5
5 4 4
5 4 3
5 3 5
5 3 4
5 3 3
4 5 5
4 5 4
4 5 3
4 4 5
4 4 4
4 4 3
4 3 5
4 3 4
4 3 3
3 5 5
3 5 4
3 5 3
3 4 5
3 4 4
3 4 3
3 3 5
3 3 4
|
| |
![]()
|
|
Темы:
recursion
In the alphabet of the language of the tribe «tumba-yumba» four letters: "K", "L", "M" and "N". We need to display all possible words consisting of n letters that contain at least two identical letters, not necessarily adjacent. The program should not build other words that do not match the condition.
| Input |
Output |
| 2 |
KK
LL
MM
NN
|
(c) K.Yu. Polyakov
| |
![]()
|
Темы:
recursion
In the alphabet of the language of the tribe «tumba-yumba» four letters: "K", "L", "M" and "N". It is necessary to display on the screen all possible words consisting of K letters, in which there are at least two identical letters standing side by side. Count the number of such words. The program should not build other words that do not match the condition.
| Input |
Output |
| 3 |
KKK
KKL
KKM
KKN
KLL
KMM
KNN
LKK
LLK
LLL
LLM
LN
LMM
LNN
MKK
MLL
MMK
MML
MMM
MMN
MNN
NKK
NLL
NMM
NNK
NNL
NNM
NNN
28 |
(c) K.Yu. Polyakov
| |
![]()
|
|
Темы:
recursion
In the alphabet of the language of the tribe «Tumba-Yumba» four letters: "K", "L", "M" and "N". We need to display all possible words consisting of n letters (n > 1) in which the second letter is «K». Count the number of such words.
Examples
| # |
Input |
Output |
| 1 |
2 |
KK
LK
MK
NK
4 |
(c) K.Yu. Polyakov
| |
![]()
|
|
Темы:
recursion
Write a recursive function that counts the number of even digits of the given number.
The main program must contain the input of initial data, the call of the function and the output of the result
Loops are not allowed
Input: The input string contains one natural number N .
Output: The program should output the number of even digits of the entered number.
Examples
| # |
Input |
Output |
| 1 |
123456 |
3 |
| 2 |
13579 |
0 |
| |
![]()
|
|
Темы:
recursion
Write a program containing a recursive function that given a natural number n, prints all numbers from n to 1. The main program must contain input of initial data (a number n) and a function call.
Examples
| # |
Input |
Output |
| 1 |
6 |
6 5 4 3 2 1 |
| |
![]()
|
|
Темы:
recursion
Vasya and Petya went to dig potatoes. At the end of the day they dug up N sacks of potatoes weighing W1, W2, ... WN. How can they divide the sacks of potatoes among themselves so that the mass difference is minimal.
Input
On the first line the number N is written – number of bags (1 ≤ N ≤ 18). The second line lists the masses of bags W1, W2 , … WN (1 ≤ Wi ≤ 105).
Output
On a single line, print one non-negative integer – the minimum possible difference between the masses of two heaps with bags.
| Input |
Output |
5
5 3 5 7 8
| 2 |
| |
![]()
|
|
Темы:
recursion
Number N is entered. Generate in lexicographic order all sequences of length N, consisting of numbers 2, 4, 5, in which the number of twos does not exceed 2.
In "lexicographical order" means that if two sequences coincide at the first X places, but differ at the X+1 place, then the one in which the number at the X+1 place is less should go first.
1≤N≤9
Examples
| # |
Input |
Output |
| 1 |
3 |
2 2 4
2 2 5
2 4 2
2 4 4
2 4 5
2 5 2
2 5 4
2 5 5
4 2 2
4 2 4
4 2 5
4 4 2
4 4 4
4 4 5
4 5 2
4 5 4
4 5 5
5 2 2
5 2 4
5 2 5
5 4 2
5 4 4
5 4 5
5 5 2
5 5 4
5 5 5
|
| |
![]()
|
|
Темы:
recursion
Puzzle “Towers of Hanoi” consists of three rods, numbered 1, 2, 3. A pyramid of n disks of different diameters is put on rod 1 in ascending order of diameter. The disks can be transferred from one rod to another one at a time, while the disk cannot be placed on a disk of a smaller diameter. It is necessary to transfer the entire pyramid from rod 1 to rod 3 in the minimum number of transfers.
Write a program that solves a puzzle; for a given number of disks n prints a sequence of permutations in the format a b c, where a — number of the shifted disk, b — the number of the rod from which this disk is removed, c — the number of the rod on which this disc is put.
For example, line 1 2 3 means moving disc number 1 from pin 2 to pin 3. One command is printed on one line. The disks are numbered from 1 to n in order of increasing diameter.
Input
Enter a natural number n ( 0 < n < 11).
Output
The program should display the minimum (in terms of the number of operations performed) way of rearranging the pyramid from the given number of disks.
Examples
| # |
Input |
Output |
| 1 |
2 |
1 1 2
2 1 3
1 2 3
|
| |
![]()
|
Темы:
recursion
Raising to a power is faster than n multiplications! To do this, use the following recurrence relations:
\(a^n=(a^2)^{n/2},\ for \ even \ n, \\ a^n=a \cdot a^{n-1 },\ for \ odd \ n.\)
Implement the fast exponentiation algorithm. If you do everything right, then the complexity of your algorithm will be O(logn) .
Input
The program receives a real number a and an integer n as input. Each number on a separate line.
Imprint
Output \(a^n\).
Examples
| # |
Input |
Output |
| 1 |
2
7 |
128 |
| 2 |
1.00001
100000 |
2.71827 |
| |
![]()
|
|
Темы:
recursion
Print all valid bracket expressions of length N, consisting of parentheses and square brackets.
Input
The first line contains a single number N. \(1 <= N <= 14\), N is even.
Output
Each expression is displayed on a separate line.
Examples
| # |
Input |
Output |
| 1 |
2 |
()
[]
|
| 2 |
4 |
(())
[[]]
[()]
()[]
[]()
()()
([])
[][]
|
| |
![]()
|
|
Темы:
Bust
recursion
Two-pan balances and a set of weights are given. An object weighing K grams is placed on the left side of the scale. Is it possible to bring the scales to a state of equilibrium, and if so, determine for each scale pan which weights need to be placed on it for this. Available weights are allowed to be placed on any of the scales (each weight is available only in one copy, some weights may not be used).
Input
Entered first K — the weight of the item placed on the left bowl (1≤K≤50). Next, the total number of weights N (1≤N≤10) is recorded. Next, N different natural numbers are written, not exceeding 50, — weights.
Imprint
On the first line print the weights of the weights to be placed on the left scale pan, on the second line print — weights to be placed on the right bowl. If no weights need to be placed on some bowl — print the number 0 in this line. If it is impossible to balance the scales with the help of these weights, print the single number –1. If there are several options, print any of them.
Examples
| # |
Input |
Output |
| 1 |
5
2
3 5
| 0
5 |
| 2 |
5
3
6 3 4
| 4
36 |
| 3 |
5
1
2 |
-1 |
| |
![]()
|
|
Темы:
recursion
Partitions
Given a natural number N. Consider its partition into natural terms. Two partitions that differ only in the order of the terms will be considered as one, so we can assume that the terms in the partition are ordered in non-increasing order.
Input
A single number N is given. (N ≤ 40)
Imprint
It is necessary to print all partitions of the number N into natural terms in lexicographic order.
Examples
| # |
Input |
Output |
| 1 |
5 |
1 1 1 1 1
2 1 1 1
2 2 1
3 1 1
3 2
4 1
5 |
| |
![]()
|
|
Темы:
Depth walk
recursion
It is required to calculate the area of a room in a square maze.
Input
The first line of enters the number N – maze size (3 <= N <= 10). The following N lines contain a maze (‘.’ – empty cell, ‘*’ – wall). And finally, the last line contains two numbers – the number of the row and column of the cell located in the room whose area is to be calculated. It is guaranteed that this cell is empty and that the labyrinth is surrounded by walls on all sides.
Imprint
It is required to print a single number – the number of empty cells in this room.
Examples
| # |
Input |
Output |
| 1 |
5
*****
**..*
*.*.*
*..**
*****
24
|
3 |
| |
![]()
|
|
Темы:
recursion
In some other world today is December 31st. Grandfather Kokovanya decided to cook a multi-dimensional burger that Daryon loves so much. A L level burger (L is an integer greater than or equal to 0) is being prepared in the following way:
- Level zero burger is a patty.
- Burger with level
L (L >= 1) is a bun, burger with level (L-1), cutlet, burger with another level (L-1) and another bun, stacked vertically in this order, counting from the bottom.
For example, a level 1 burger and a level 2 burger look like BKKKB and BBKKKBKBKKKBB (rotated 90 degrees), where B and K denote a bun and cutlet.
The burger that grandfather Kokovanya will cook is a level N burger. Daryona always eats only X layers of the bottom of the burger (a layer is a patty or a bun). How many meatballs will she eat?
Input
The program receives as input 2 numbers separated by a space: N and X.
Imprint
Output the number of cutlets in the bottom X layers, counting from the bottom of the N layer burger.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
2 7 |
4 |
In the bottom 7 layers of the second level burger ( BBKKKBKBKKKBB) there are 4 burgers. |
| 2 |
1 1 |
0 |
|
| 3 |
50 4321098765432109 |
2160549382716056 |
A level 50 burger is quite thick, so much so that the number of layers does not fit into a 32-bit integer. |
| |
![]()
|
|
Темы:
recursion
Little Grisha has learned to perform two operations with any number: add 3 to the number and add 5 to the number. But, unfortunately, he still does not know that in this way he cannot get any number from the number 1. Help Grisha understand whether he can get the number N from the number 1 or not.
Input
The program takes as input a natural number N (N <= 200).
Output
Print the word YES if the number N can be obtained from the number 1, or NO - otherwise.
Note
The number 1 can always be obtained without doing anything.
Examples
| # |
Input |
Output |
| 1 |
5 |
NO |
| 2 |
1 |
YES |
| |
![]()
|