Код с Паскаля на С++ ( количество телефонных номеров длины N, набираемых ходом коня)

[Serge_Bliznykov]

Сообщение от val_nnm

Если интересно динамическое программирование то вот набросал код.
Правда набросал на C# при желании можно перевести на C++

Вас не смущает то, что программа выдаёт некорректные результаты?

сравните, например, с http://programmersforum.ru/showpost....69&postcount=8

p.s. строчку начальных номеров я изменил в соответствии с условиями задачи.

            long[] current = new long[10] { 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 }; //Список разрешённых для старта цифр (если 1 то соответсвующая цифра разрешена для старта)

ДОБАВЛЕНО
нашёл ошибку.
неверно были заполнены исходные данные по переходам.
Правильно вот так:

        static int[][] AvailableSteps = 
        {
            new int[] { 4,6 }, //Список кнопок откуда можно попасть на кнопку 0
            new int[] { 6,8 }, //Список кнопок откуда можно попасть на кнопку 1
            new int[] { 7,9 }, //Список кнопок откуда можно попасть на кнопку 2
            new int[] { 4,8 }, //Список кнопок откуда можно попасть на кнопку 3
            new int[] { 3,9,0 }, //Список кнопок откуда можно попасть на кнопку 4

            new int[] { }, //Список кнопок откуда можно попасть на кнопку 5
            new int[] { 0,1,7 }, //Список кнопок откуда можно попасть на кнопку 6
            new int[] { 2,6 }, //Список кнопок откуда можно попасть на кнопку 7
            new int[] { 1,3 }, //Список кнопок откуда можно попасть на кнопку 8
            new int[] { 2,4 }, //Список кнопок откуда можно попасть на кнопку 9
        };

всё равно целочисленной разрядности хватает ~n=52, для больших n нужно, наверное, длинную арифметику юзать!

[val_nnm]

Спасибо за замечание.
Действительно я пропустил 2 хода ведущие на кнопку 0.

Да для больших n действительно не хватает разрядности. Но по крайней мере он до 50 считает очень быстро.

[Serge_Bliznykov]

Сообщение от val_nnm

Да для больших n действительно не хватает разрядности. Но по крайней мере он до 50 считает очень быстро.

Это правда.
В этом и есть могущество ДП.
Спасибо за пример!