Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)

@Jimm34 · Регистрация: 30.11.2013

Author24 — интернет-сервис помощи студентам

Шахматная фигура «конь» перемещается на 1 клетку по горизонтали и на 2 клетки по
вертикали или на 2 клетки по горизонтали и 1 - по вертикали. «Конь» начинает
свой путь с нижнего левого угла и перемещается по шахматной доске, которая масс n x n
клеток. Определить количество способов, которыми «конь» может дойти до правого верхнего угла доски по к шагов.

_____________________________________________________________
Ребят, не шарю как делать, помогите.

Добавлено через 36 минут
доску я создал вот с конём проблема что бы он ходил

C++

#include<iostream>
using namespace std;
int main()
{
for(int y=0;y<=6;y++)
{
    for(int x=0;x<=6;x++){
        if((x+y)%2==0){//тут только (х+у) и все работает
 
            cout<<"+ ";
        }else cout<<"* ";
    }
cout<<endl;
}
 system ("pause");
return 0;
}

@SlavaSSU · 16.06.2014, 17:18

а кто сказал?

они могут дать тест с ответом, на котором программа неправильно работает?

@Jimm34 · 16.06.2014, 18:44 **[ТС]**

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

а кто сказал?
они могут дать тест с ответом, на котором программа неправильно работает?

Препод сказал) в рятли он даст мне готовую задачу)

@SlavaSSU · 16.06.2014, 18:56

задача то хоть такая?

@Jimm34 · 16.06.2014, 19:17 **[ТС]**

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

задача то хоть такая?

Да условие тоже самое)(за 6 ходов конь не дойдёт от угла до угла нужно как минимум 7) А когда я в задаче ввожу место 6 (7) то способов выдаёт 0.

@SlavaSSU · 16.06.2014, 19:29

за 6 ходов конь доходит от угла до угла!!!
ок, щас спрошу насчет этой задачи на другом форуме.

@Jimm34 · 16.06.2014, 19:47 **[ТС]**

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

за 6 ходов конь доходит от угла до угла!!!
ок, щас спрошу насчет этой задачи на другом форуме.

если за 6 ходов покажи как ты ходил)

@SlavaSSU · 16.06.2014, 20:02

A1 -> C2 -> E3 -> F5 -> H6 -> F7 -> H8, например!!!

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

я написал перебор:

C++ (Qt)

#include <iostream>
 
using namespace std;
 
const int dxh[] = {-2, -2, 2, 2, -1, -1, 1, 1};
const int dyh[] = {-1, 1, -1, 1, -2, 2, -2, 2};
 
bool in(int i, int j, int n, int m)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
int ans = 0;
int n, need;
 
void rec(int i, int j, int k)
{
    if(i < 1 || i > n || j < 1 || j > n)
        return;
    if(k == need)
    {
        if(i == 1 && j == n)
            ans++;
        return;
    }
 
    for(int dir = 0; dir < 8; dir++)
    {
        int ni = i + dxh[dir];
        int nj = j + dyh[dir];
        rec(ni, nj, k + 1);
    }
}
 
int main()
{
    cin >> n >> need;
    rec(n, 1, 0);
    cout << ans << endl;
    return 0;
}

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

@Jimm34 · 16.06.2014, 20:20 **[ТС]**

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

A1 -> C2 -> E3 -> F5 -> H6 -> F7 -> H8, например!!!
я спросил на другом форуме, мне пока не сказали верно или нет, но сказали напиши перебор и сверь ответы.
я написал перебор:

всё таки 7 ходов минималка но в задаче всё равно когда в водишь размер доски 8 и сколько ходов 7 то пишет ответ способов 0

@SlavaSSU · 16.06.2014, 20:22

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

Добавлено через 1 минуту
всё таки 7 ходов минималка но в задаче всё равно когда в водишь размер доски 8 и сколько ходов 7 то пишет ответ способов 0

то что я тебе показал - это 6 ходов(1 клетка стартовая, она за ход не считается).

за 7 ходов нет ни одного способа добраться до угла!

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	16.06.2014, 17:18	21
	а кто сказал? они могут дать тест с ответом, на котором программа неправильно работает? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	16.06.2014, 18:56	23
	задача то хоть такая? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	16.06.2014, 19:29	25
	за 6 ходов конь доходит от угла до угла!!! ок, щас спрошу насчет этой задачи на другом форуме. 0

@Jimm34 1 / 1 / 2 Регистрация: 30.11.2013 Сообщений: 67
	16.06.2014, 19:47 [ТС]	26
	Сообщение от SlavaSSU за 6 ходов конь доходит от угла до угла!!! ок, щас спрошу насчет этой задачи на другом форуме. если за 6 ходов покажи как ты ходил) 0

@Jimm34 1 / 1 / 2 Регистрация: 30.11.2013 Сообщений: 67
	16.06.2014, 20:20 [ТС]	28
	Сообщение от SlavaSSU A1 -> C2 -> E3 -> F5 -> H6 -> F7 -> H8, например!!! я спросил на другом форуме, мне пока не сказали верно или нет, но сказали напиши перебор и сверь ответы. я написал перебор: всё таки 7 ходов минималка но в задаче всё равно когда в водишь размер доски 8 и сколько ходов 7 то пишет ответ способов 0 0

@Jimm34 1 / 1 / 2 Регистрация: 30.11.2013 Сообщений: 67
	16.06.2014, 18:44 [ТС]	22
	Сообщение от SlavaSSU а кто сказал? они могут дать тест с ответом, на котором программа неправильно работает? Препод сказал) в рятли он даст мне готовую задачу) 0

@Jimm34 1 / 1 / 2 Регистрация: 30.11.2013 Сообщений: 67
	16.06.2014, 19:17 [ТС]	24
	Сообщение от SlavaSSU задача то хоть такая? Да условие тоже самое)(за 6 ходов конь не дойдёт от угла до угла нужно как минимум 7) А когда я в задаче ввожу место 6 (7) то способов выдаёт 0. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	16.06.2014, 20:22	29
	если еще раз будешь сдавать ему эту задачу, покажи ему перебор, если он скажет что он правильный(а он правильный!!!) то спроси, знает ли он метод динамического программирования. Добавлено через 1 минуту всё таки 7 ходов минималка но в задаче всё равно когда в водишь размер доски 8 и сколько ходов 7 то пишет ответ способов 0 то что я тебе показал - это 6 ходов(1 клетка стартовая, она за ход не считается). за 7 ходов нет ни одного способа добраться до угла! 1