Задача"Ход конем"

[станислав16]

Помогите решить задачу:
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами,которые бы набирались на кнопочном телефоне
ходом коня.Например,ходом коня набирается телефоном 340-4927.При этом телефонный номер не может начинаться ни с цифры 0,ни с цифры 8.
Клавиатура выглядит так:
789
456
123
0
Напишите программу,определяющую количество телефонных номеров
длины N,набираемых ходом коня.
Входные данные
Во входном файле записано целое число N(1<=N<=100)
Выходные данные
Выведите в выходной файл искомое количество телефонных номеров
Пример входного файла
2
Пример выходного файла
16

[Гром]

Наработки/деньги? С последним вариантом можно сразу ко мне в аську (в профиле).

[станислав16]

А можете написать ее сюда

[Гром]

ICQ 482-373-277

[станислав16]

Я не знаю как туда зайти,напиши сюда

[ВолодимирКіллер]

// Hid Konya.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int main()
{
	int n;
	cin>>n;
	long int r[10000];

	r[0]=1;
	r[1]=2;
	r[2]=3;
	r[3]=4;
	r[4]=5;
	r[5]=6;
	r[6]=7;
	r[7]=9;


	int o1=8,t=0,s=7;
	int sum;

	if (n==1)
		cout<<8;
	else
	{
	for(int i=1;i<=n-1;i++)
	{
	for(int q=t;q<s+1;q++)
		{
			
				if (r[q]=0)
					{
						r[o1]=4;
						r[o1+1]=6;
						o1+=2;
					}
				else
				if (r[q]=1)
					{
						r[o1]=8;
						r[o1+1]=6;
						o1+=2;
					}
				else
				if (r[q]=2)
					{
						r[o1]=7;
						r[o1+1]=9;
						o1+=2;
					}
				else
				if (r[q]=3)
					{
						r[o1]=4;
						r[o1+1]=8;
					o1+=2;
					}
				else
				if (r[q]=4)
					{
						r[o1]=9;
						r[o1+1]=4;
						r[o1+2]=0;
						o1+=3;
					}
				else
				if (r[q]=5)
					{
					}
				else
				if (r[q]=6)
					{
						r[o1]=7;
						r[o1+1]=1;
						r[o1+2]=0;
						o1+=3;
					}
				else
				if (r[q]=7)
					{
						r[o1]=2;
						r[o1+1]=6;
						o1+=2;
					}
				else
				if (r[q]=8)
					{
						r[o1]=1;
						r[o1+1]=3;
						o1+=2;
					}
				else
				if (r[q]=9)
					{
						r[o1]=4;
						r[o1+1]=2;
						o1+=2;
					}
				else
					break;
		}
		sum=o1-s-1;
		t=s+1;
		s=o1;
		o1=s+1;
}
	cout<<sum<<"\n";
	}
	system("pause");
	return 0;
}

[Zerratul]

Ответ написан на языке С++. Я не знаю почему у предыдущего ответа так много кода, даже программа неправильно выдает ответ(сам считал). Задача легко реализуется через графы, схемы(называйте как хотите). Не понимаю зачем рекурсия.
задача:

#include <iostream>
#include <cstdlib>
using namespace std;
int n = 0;
int c = 0;
int h = 0;

int main()
{
    cin >> c;
    h = c - 2;
    n = 16 + 20*h;
    if (c==1){cout << 7 << endl;} else {
    cout << n << endl;}
    system("pause");
    return 0;
}

_____
Код программы нужно выделять (форматировать) тегами [CODE][/CODE] (читать FAQ)
Модератор

[Serge_Bliznykov]

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

Ответ написан на языке С++. Я не знаю почему у предыдущего ответа так много кода, даже программа неправильно выдает ответ(сам считал).

Вы явно что-то считали неправильно.
даже если начать с длины 1.
Правильный ответ: 8 вариантов (а не 7, как у Вас).
Дальше. я подсчитал варианты, у меня получилось так:
n=2 количество=16
n=3 количество=36
n=4 количество=82
n=5 количество=188
n=6 количество=428 (например, список - list_6.txt)
и т.д.
Сравните с тем, что выдаёт ваша программа

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

Не понимаю зачем рекурсия.

в коде выше нет рекурсии. Там есть массив и явно используется метод ДП (динамическое программирование). Это правильный подход, но где допущена ошибка я НЕ возьмусь найти.

[digitalis]

При решении этой задачи следует помнить, я думаю, что в реальной клавиатуре телефона 0 находится в средней колонке (под 2, а не под 1). Движок форума съел впереди стоящий пробел в исходном посте. Иначе решение м.быть неправильным.
34
012
Перед 34 у меня был пробел
Serge А какой может быть ход конем при длине 1 ? Только одна цифра...

[Serge_Bliznykov]

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

При решении этой задачи следует помнить, я думаю, что в реальной клавиатуре телефона 0 находится в средней колонке (под 2, а не под 1).

именно так.
это же очевидно из условия задачи:

Сообщение от станислав16

.Например,ходом коня набирается телефоном 340-4927.

попробуйте ходом коня из "4" перейти на "0", сразу станет понятно, где фактически находится ноль.

789
456
123
 0