Олимпиадная задача

#cpp #алгоритм

Помогите решить на с++
шахматная ассоциация выдала своим сотрудникам телефоны, номера на которых можно набирать
только ходом коня, причем номер не может начинаться с цифры 8 и 0
 7 8 9
 4 5 6
 1 2 3
   0

Вводится число N (1 <= N <= 100), обозначающее длину номера
Какое количество разных номеров данной длины можно набрать?
Т.е. для N = 3
вариации могут быть такими: 1-6-7 1-6-1 2-7-6 и т.д.    

Ответы

Ответ 1

Если мне не изменяет логика, то решение должно быть таким. Старался написать максимально
компактно, поэтому не во всех местах понятно идею алгоритма.
#include "iostream"
using namespace std;
int main()
{
    char can_go[10][3]={{4,6,-1},{6,8,-1},{7,9,-1},{4,8,-1},{0,3,9},{-1,-1,-1},{0,1,7},{2,6,-1},{1,3,-1},{2,4,-1}};
    int end_digits[10]={0,1,1,1,1,1,1,1,0,1},temp[10],s,n,i=0,j,l;
    for(cin>>n;i0,
обходим каждый эллемент can_go[j] и добавляем к эллементу массива temp под номером,
равным цифре номера телефона, в которую можем попасть, тоесть can_go[j][l].


Переносим массив temp в end_digits.


Повторяем шаги 2-4 n раз и выводим результат - s.


Ответ 2

Задача на самом деле, если хорошо подумать, сводится к простому перебору и перемножению
вариаций на разных этапах. Приблизительный алгоритм:

1) Нужно предварительно составить так
называемые "таблицы возможных ходов"
для каждой кнопки, например, для
кнопки 1 имеем возможные ходы на 6, 6, 8 и
8, т.е на 6 и 8( две вариации ), для
кнопки 2 имеем также два варианта
хода: на 9 и на 7. Думаю, это понятно.
2) Вторым шагом вам необходимо
поочередно от каждой кнопки ходить
конем N раз( ходить по правилам составленной выше таблицы ), выводя при этом полный
текущий путь от самой первой кнопки.
Инкрементируя при этом определенный
счетчик ходов.

Высчитывать количество вариаций ходов можно и иным способом, как уже многие поняли.
Это делается банальным перемножением количества вариаций ходов от каждой кнопки. 
P.S  Позже, думаю, смогу продемонстрировать уже доработанный алгоритм в действии,
если вы сами не сможете...