C ++ Recursion

Question

Hello, there is a task

A ladder is a set of cubes, in which each upper layer contains cubes smaller than the previous one. It is required to write a program that calculates the number of ladders that can be built from N cubes.
Input data
The input file INPUT.TXT contains a positive integer N (1 ≤ N ≤ 100) - the number of cubes in the ladder.
Output
In the output file OUTPUT.TXT you need to display the number of ladders that can be built from N cubes.

I encountered Recursion 1 time, I understood what it was, but I don’t know how to approach this task, write in general terms how to organize everything. Thank.

PS I do not ask you to do everything for me completely, the task is not educational (any kind of lab) Here is the link to the original.

And in the task there are not steps, but the number of variations of ladders, that is, if 6 cubes are given, that is, 4 options: 6, 5 + 1.4 + 2.1 + 2 + 3.

To understand recursion, you must first understand recursion.
I need exactly recursion (to master it), and the task is solved by recursion (judging by the title in the original task).

Accepted Answer · 2011-12-28T17:52:14

Here is the recursive function:

int stairs(int n) { int i,out; if(n<=2) return 1; // 1 или 2 кубика можно разложить только 1 способом out=0; for(i=0;i*2<=n;i++) // Меняем i от 0 до половины n { // Отделяем от кучи i кубиков и смотрим сколькими способами их можно разолжить: out += stairs(i); // Если отделили ровно половину, то убираем из подсчета случай, когда n раскладывается на два слоя одинаковой ширины: if(i*2==n) out--; } return out; }

I think you will understand with input-output.

Thanks, it seems to work, I'll try to figure out your code now, for me it looks completely unclear.
and you can still store all the already calculated values of the stairs function, so as not to count it once again

Answer 2 · 2011-12-28T17:05:02

get the number - the number of cubes
call the line counting method
we get the result

in the method itself

took meaning
minus 1 from it
plyusanul to the number of steps
calling ourselves recursively
got the result

Gorets

12k one 15 41

What if the main function is recursive? Or is it nonsense? - username76
yes, it is unlikely that you will succeed =) - Gorets
Immediately make a reservation, my option is wrong according to the conditions of the problem, since it does not consider ALL decomposed ladders (you can just take all the elements minus 1 - the first step, and 1 - the second) - Gorets
Recursive main ()? This is easy: main (int ac, char ** av, char ** ev) {if (ac> 0) {printf ("% d \ n", ac); main (- ac, av, ev); } return 0; } - avp
@ username76 gives me an error - Alisher Yerkimbekov

|

C ++ Recursion

2 answers 2

More articles: