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

[p51x]

И? Где в условии N > 1?

[niggainsoul]

Тему по ссылке видел. Ответа там не нашел.
Сделал unsigned long long - не помогло

[Serge_Bliznykov]

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

И? Где в условии N > 1?

больше или равно 1.

в исходной задаче (см. acmp 471)
сказано "Входной файл INPUT.TXT содержит натуральное число N"
ну и по логике:
"...программу, определяющую количество телефонных номеров длины N ..."
длина у нас всегда положительное число (или ноль, что, впрочем, отсекается ограничением - что на входе натуральное число)

[Serge_Bliznykov]

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

не помогло

при n=1 у Вас ответ 8 ?!

и чему равен ответ при n=100 ?

[niggainsoul]

После изменения условия на if (i != '8') show(string(1, i)); ответ стал 8. При 100 не знаю, долго ждать.

[Serge_Bliznykov]

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

При 100 не знаю, долго ждать.

ну так на acmp.ru задача вывалится по "time limit"...

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

[niggainsoul]

Этот код проходит, но я не очень понимаю его((

#include <iostream>
using namespace std;
void sum(int *a, int *b, int *c, int *n)
{
	int i, t;
	for (i = t = 0; i < *n + 3; i++)
	{
		t += a[i] + b[i];
		c[i] = t % 10;
		t /= 10;
	}
	*n += 3;
	while (!c[*n])
		--*n;
}
int d[20][200][200], s[200], n, i, j, l, m, p[20][5] = { {2,4,6},{2,6,8},{2,7,9},{2,4,8},{3,0,3,9},{0},{3,0,1,7},{2,2,6},{2,1,3},{2,2,4} };
int main()
{
	
	int n;
	for (i = 0; i < 10; i++)
		d[i][0][0] = 1;
	cin >> n;
	for (i = 1; i < n; i++)
		for (j = 0; j < 10; j++)
			for (d[j][i][0] = l = 0; l < p[j][0]; l++)
			{
				m = 100;
				sum(d[j][i], d[p[j][l + 1]][i - 1], d[j][i], &m);
			}
	for (m = 100, i = 1; i < 10; i++)
		if (i != 8)

			sum(s, d[i][n - 1], s, &m);
	for (i = m; i >= 0; i--)
		cout << s[i];
	return 0;
}

[niggainsoul]

Проще повеситься

[Аватар]

Проще повеситься

Само собой, только веревка или заменитель нужен и даже без мыла. И мозги не нужно включать, почти. А тут нужно и очень )

[val_nnm]

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp11
{
    class Program
    {
        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 }, //Список кнопок откуда можно попасть на кнопку 4

            new int[] { }, //Список кнопок откуда можно попасть на кнопку 5
            new int[] { 1,7 }, //Список кнопок откуда можно попасть на кнопку 6
            new int[] { 2,6 }, //Список кнопок откуда можно попасть на кнопку 7
            new int[] { 1,3 }, //Список кнопок откуда можно попасть на кнопку 8
            new int[] { 2,4 }, //Список кнопок откуда можно попасть на кнопку 9
        };
        // Расположение кнопок на клавиатуре
        //
        //      1 2 3
        //      4 5 6
        //      7 8 9
        //        0
        //
        static void Main(string[] args)
        {
            
            //В переменной Current находиться количество способов которыми можно попасть на данную кноку на текущем шаге
            long[] current = new long[10] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; //Список разрешённых для старта цифр (если 1 то соответсвующая цифра разрешена для старта)
            int n = 6;

            for (int i=2;i<=n;i++)
            {
                long[] next = new long[10];
                for (int j = 0; j < 10; j++)

                    //Расчитываем сколько различных вариантв номеров длиной i цифр может заканчиваться цифрой j
                    foreach (var t in AvailableSteps[j])
                        next[j] += current[t];
                current = next;
            }
            Console.WriteLine(current.Sum());
            Console.ReadLine();
        }
    }
}