Question:
Please help me solve this problem in C++
The Chess Association issued phones to its employees, numbers on which can only be dialed with a knight's move, and the number cannot begin with the number 8 and 0
7 8 9
4 5 6
1 2 3
0
The number N (1 <= N <= 100) is entered, indicating the length of the number.
How many different numbers of a given length can be dialed?
Those. for N = 3 , the variations can be: 1-6-7 1-6-1 2-7-6 , etc.
Answer:
The problem really, if you think about it, comes down to a simple enumeration and multiplication of variations at different stages. Approximate algorithm:
1) You must first compile the so-called "tables of possible moves" for each button, for example, for button 1 we have possible moves for 6, 6, 8 and 8, i.e. for 6 and 8 (two variations), for button 2 we also have two options for the move: on 9 and on 7. I think this is understandable.
2) In the second step, you need to alternately move the knight from each button N times (walk according to the rules of the table above), while displaying the full current path from the very first button. Incrementing at the same time a certain counter of moves.
You can calculate the number of variations of moves in another way, as many have already understood. This is done by simply multiplying the number of variations of moves from each button.
PS Later, I think I will be able to demonstrate the already modified algorithm in action, if you yourself cannot …