Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
15.06.2014, 15:56     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #1
Шахматная фигура «конь» перемещается на 1 клетку по горизонтали и на 2 клетки по
вертикали или на 2 клетки по горизонтали и 1 - по вертикали. «Конь» начинает
свой путь с нижнего левого угла и перемещается по шахматной доске, которая масс n x n
клеток. Определить количество способов, которыми «конь» может дойти до правого верхнего угла доски по к шагов.







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

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2014, 15:56     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
Посмотрите здесь:

С++ Даны два прямоугольника, стороны которых параллельны или перпендикулярны осям координат. Известны координаты левого нижнего угла каждого из них... C++
Перейти из левого нижнего в правый верхний угол массива, двигаясь вверх либо вбок, суммируя элементы через которые идем. Сумма должна быть минимальной C++
Путем перестановок строк и столбцов (целиком) элемент надо переместить в правый верхний угол подмассива (Перевести программу в c++) C++
C++ Путем перестановок строк и столбцов элемент переместить в правый верхний угол подмассива (С Turbo Pascal на C++)
C++ Ход коня по шахматной доске случайным образом
Необходимо организовать движение шашки по шахматной доске C++
C++ Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
15.06.2014, 18:25     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
только тут считает из правого нижнего в левый верхний, но это не важно!

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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 dp[11][11][11];
 
int main()
{
    int n, k;
    cin >> n >> k;
    dp[0][n][n] = 1;
 
    for(int cnt = 0; cnt < k; cnt++)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                for(int dir = 0; dir < 8; dir++)
                {
                    int ni = i + dxh[dir];
                    int nj = j + dyh[dir];
                    if(in(ni, nj, n, n))
                        dp[cnt + 1][ni][nj] += dp[cnt][i][j];
                }
            }
    }
 
    cout << dp[k][1][1] << endl;
    return 0;
}
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
15.06.2014, 19:14  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #3
Шахматная фигура «конь» перемещается на 1 клетку по горизонтали и на 2 клетки по
вертикали или на 2 клетки по горизонтали и 1 - по вертикали. «Конь» начинает
свой путь с нижнего левого угла и перемещается по шахматной доске, которая масс n x n
клеток. Определить количество способов, которыми «конь» может дойти до правого верхнего угла доски по к шагов.

Добавлено через 1 минуту
--------------------------
Помогите доску составил, а движение ни как не выходит.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <conio.h>
using namespace std;
int main()
{
for(int y=0;y<=7;y++)
        {
    for(int x=0;x<=7;x++)
    {
        if((x+y)%2==0)
                {
 
            cout<<"+ ";
        }else cout<<"* ";
        }
cout<<endl;
     }
 system ("pause");
return 0;
 
}
Добавлено через 54 минуты
Есть кто читал это сообщение?
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
15.06.2014, 19:26  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #4
а что в твоей программе (n, k)??

Добавлено через 3 минуты
Цитата Сообщение от SlavaSSU Посмотреть сообщение
1

#
как твоя программа вообще работает?
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 07:07     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
я понял задачу так:
даны n, k;
надо найти количество способов, которыми конь может дойти из левого нижнего угла в правый верхний доски размером n * n, сделав ровно k ходов.
зачем вообще тут рисовать доску - непонятно!
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 08:39  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #6
Цитата Сообщение от SlavaSSU Посмотреть сообщение
ие по шахматной доске коня (с левого нижнего угла в верхний правый угол) / С++ для начинающих
просто я немогу понять что нужно в водить в твою задачу.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 09:04     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
что вводить??? как что, размер поля n и количество ходов k, программа выведет сколькими способами можно дойти из левого нижнего угла в правый верхний ровно за k ходов, если доска имеет размеры n * n
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 09:34  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #8
Цитата Сообщение от SlavaSSU Посмотреть сообщение
что вводить??? как что, размер поля n и количество ходов k, программа выведет сколькими способами можно дойти из левого нижнего угла в правый верхний ровно за k ходов, если доска имеет размеры n * n
сначала я в вёл (n) 8 потом в вёл (k)6 мне выдало 108. Если брать ниже (k)6 то будет всегда ноль.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 10:32     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #9
это значит, что за 5 и менее ходов существует ноль спопсбово добраться! т.е. нельзя добраться из левого нижнего правый верхний! а за 6 ходов можно 108 способами
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 10:44  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #10
Цитата Сообщение от SlavaSSU Посмотреть сообщение
это значит, что за 5 и менее ходов существует ноль спопсбово добраться! т.е. нельзя добраться из левого нижнего правый верхний! а за 6 ходов можно 108 способами

можно добраться за 5 ходов (5 и более способов)( Конь ходит буквой Г если что) только что считал.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 10:46     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #11
ок, напиши мне последовательность клеток, если строки пронумерованы от 1 до 8 сверху вниз, а столбцы от 1 до 8 слева направо, т.е. нижняя леевая клетка имеет координаты (8, 1) а правая верхняя (1, 8)
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 10:52  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #12
Цитата Сообщение от SlavaSSU Посмотреть сообщение
ок, напиши мне последовательность клеток, если строки пронумерованы от 1 до 8 сверху вниз, а столбцы от 1 до 8 слева направо, т.е. нижняя леевая клетка имеет координаты (8, 1) а правая верхняя (1, 8)

B1-D3-D5-E7-G6-H8 первый способ
B1-D2-F3-G5-F5-H8 2 способ
B1-A3-C4-E5-G6-H8 3 способ
B1_c3-D5-F4-G6-H8 4 способ
B1-D2-F3-E5-G6-H8 5 способ
дальше я не считал по способам. Если я правильно понял ты просил это.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 11:04     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #13
почему у тебя везде стартовая клетка B1??? левый нижний угол имеет координаты A1!!!
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 11:08  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #14
Цитата Сообщение от SlavaSSU Посмотреть сообщение
почему у тебя везде стартовая клетка B1??? левый нижний угол имеет координаты A1!!!
конь стоит на клетке B1 в шахматах.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 11:12     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #15
читай свою задачу!!!
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 11:27  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #16
Цитата Сообщение от SlavaSSU Посмотреть сообщение
читай свою задачу!!!
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
Да читал. Много-Много раз очень много раз. Да если конь стоит в А1 то 5 ходов не может быть.

Добавлено через 11 минут
Цитата Сообщение от Jimm34 Посмотреть сообщение
Сообщений: 27
Репутация: 0 (0)
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) / С++ для начинающих
Сообщение от SlavaSSU
читай свою задачу!!!
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
всё равно 108 способов много как то(не на считал я столько)
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 11:34     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #17
я думаю, что эо правильное решение и 108 способв для доски 8*8 и 6 ходов - правильный ответ
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 11:37  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #18
Цитата Сообщение от SlavaSSU Посмотреть сообщение
я думаю, что эо правильное решение и 108 способв для доски 8*8 и 6 ходов - правильный ответ

и последние можешь дописать Коментарии где что делается в программе? (извени за такой штурм мозгов)
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 12:19     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #19
этот решение называется "метод динамического программирования"

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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 dp[11][11][11];
//dp[cnt][i][j] == количество способов добраться до клетки (i, j) ровно за cnt шагов
 
int main()
{
    int n, k;
    cin >> n >> k;
    //количство способв добраться до левой нижней клетки сделав о ходов равно 1
    dp[0][n][1] = 1;
 
    for(int cnt = 0; cnt < k; cnt++)
    {
        //перебрали, сколько шагов сделали
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
            {
                //перебрали клетку в которой стоим
                for(int dir = 0; dir < 8; dir++)
                {
                    //перебрали ход(их 8 штук и они занесены в константу массив где dxh - смещение по строке, dyh - смещение по столбцу
                    int ni = i + dxh[dir];
                    int nj = j + dyh[dir];
                    //теперь (ni, nj) - координаты клетки в которую мы прыгнем
                    //проверка на то, что мы не вышли за пределы доски с помощью функции
                    if(in(ni, nj, n, n))
                    {
                        //вот мы знаем что до клетки (i, j) за cnt шагов можно добраться dp[cnt][i][j] способами
                        //значит до клетки (ni, nj) за cnt + 1 шаг надо увеличить на dp[cnt][i][j]
                        dp[cnt + 1][ni][nj] += dp[cnt][i][j];
                    }
                }
            }
    }
 
    cout << dp[k][1][n] << endl;
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.06.2014, 16:40     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
Еще ссылки по теме:

Заполнение матрицы с левого нижнего угла по диагонали (исправить программу) C++
Пройти по любому разрешенному пути игрового поля от верхнего левого угла до правого нижнего C++
C++ Строка, обегающая весь экран от верхнего левого до нижнего правого угла по строкам слева направо
C++ Передвижение коня по доске и сбор букв
Заполнить матрицу от левого нижнего угла по диагонали: влево - вверх C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Jimm34
1 / 1 / 0
Регистрация: 30.11.2013
Сообщений: 67
16.06.2014, 16:40  [ТС]     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) #20
Всё спасибо)

Добавлено через 3 часа 50 минут
Цитата Сообщение от SlavaSSU Посмотреть сообщение
этот решение называется "метод динамического программирования"

неправильно она работает.Не приняли её. сказали что считаетона не правильно
Yandex
Объявления
16.06.2014, 16:40     Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол)
Ответ Создать тему
Опции темы

Текущее время: 06:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru