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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
xannn94
0 / 0 / 0
Регистрация: 17.12.2013
Сообщений: 8
#1

Оптимизация задачи о ходе шахматного коня - C++

24.09.2014, 16:21. Просмотров 413. Ответов 0
Метки нет (Все метки)

Всем привет. В общем задача была такая:
Написать программу для следующих задач:
1.Нахождение пути шахматного коня(т.е надо чтобы конь прошёл все клетки побывав на каждой 1 раз):
2.Размерность доски должен вводить пользователь.
3.Начальные координаты коня должен вводить пользователь.
4.Программа должна реализоваться рекурсивным способом.

Полностью подходящую программу нашёл на форуме,благодаря комментариям разобрался в ней.

Теперь о проблеме:
Нужно оптимизировать программу с помощью правила Варнсдорфа при обходе доски шахматного коня следует каждый раз
ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько,
то можно выбрать любое из них.


(Просьба не забывать что программа обязательна должна быть рекурсивной,ну и если не сложно комментов по больше оставлять в
программе)
Вот исходник того что есть:

Кликните здесь для просмотра всего текста
C++
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <time.h>
 
using namespace std;
 
#define move_types 8
 
int possible_moves[move_types][2]  = {
        {-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
        {-1,  2}, { 2, -1}, { 1,  2}, { 2,  1}
};
 
int **global;
int size_x, size_y;
int max_moves, back_ret;
 
 
/*Функция проверяет может ли быть сделан ход на клетку с координатами x,y*/
int move_possible(int x, int y)
{
        return x >= 0 && y >= 0 && x < size_x && y < size_y && global[x][y] == 0;
}
 
 
int find_path(int cur_x, int cur_y, int move_num)
{
        int next_x = 0, next_y = 0;
        global[cur_x][cur_y] = move_num;
 
        if(move_num > max_moves)
                return 1;
 
        for(int i = 0; i < move_types; i++)
        {       next_x = cur_x + possible_moves[i][0];
                next_y = cur_y + possible_moves[i][1];
                if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1))
                return 1;
        }
 
        global[cur_x][cur_y] = 0;
        back_ret++;
        move_num++;
        return 0;
}
 
 
 
/*главная функция*/
int main()
{
setlocale (LC_ALL,"");
 
int i,nrows,ncols,sy,sx,**desc = NULL;
time_t start,end;
//вводим данные
cout<<"Введите размерность доски (от 3 до 8) :"<<endl
 <<"по оси \"X\"\t"; cin>>size_x;
cout<<"по оси \"Y\"\t";cin>>size_y;
if(size_x>8||size_x<3||size_y>8||size_y<3)
{cout<<"Неверный размер";system("pause");}
//проверяем размерность
cout<<"Введите начальные координаты:"<<endl
 <<"Координата по оси\"X\"\t";cin>>sx;
cout<<"Координата по оси\"Y\"\t";cin>>sy;
//проверяем координаты
 
 
start=time(NULL);//стартуем
//инициализируем указатель и выделяем память
desc = (int **)malloc(sizeof(int) * size_x);
for(i = 0; i < size_x; ++i)
        desc[i] = (int *)malloc(sizeof(int) * size_y);
 
//инициализируем другие переменные
back_ret = 0;
global = desc;
max_moves = size_x * size_y - 1;
 
//зануляем массив
for(int i = 0; i < size_x; ++i) {
        for(int j = 0; j < size_y; ++j)
                global[i][j] = 0;
}
 
 
//поиск решения
if(find_path(sx, sy, 1)){
 cout<<"___________________________________________"<<endl
  <<"\t***Решение***"<<endl
  <<"___________________________________________"<<endl;
 for(int i = 0; i < size_x; ++i) {
  cout<<endl;
  for(int j = 0; j < size_y; ++j)
    cout<<global[i][j]<<"\t";
    cout<<endl;}
 cout<<"___________________________________________"<<endl;
}
else cout<<"Нет решения"<<endl;
 
 
//освобождаем память
for(i = 0; i < size_x; ++i)
        free(desc[i]);
free(desc);
end=time(NULL);//время конца цикла
 
//время поиска решения
cout<<"время поиска решения "<<difftime(end, start) <<" сек."<<endl;
cout<<"___________________________________________"<<endl;
system("pause");
}


Добавлено через 6 минут
Мои мысли что делать такие: создать функцию которая записывает в массив возможные ходы(именно функцию,т.к. размер матрицы может быть разнообразен) далее перед каждым ходом делать проверку (узнать количество ходов и сортировать эти ходы(нужно выбрать ход в клетку из которой можно сделать минимальное количество ходов),после сортировки можно ходить. Как то так. Помогите реализвать всё это пожалуйста=)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2014, 16:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизация задачи о ходе шахматного коня (C++):

Ошибка в реализации задачи о ходе коня - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; int steps(int MAS, int N, int x, int y, int counter) { switch...

Ходы шахматного коня - C++
Задача заключается в том, чтобы найти минимальное количество ходов для перехода шахматного коня с клетки T1 на клетку T2. Если у кого-то...

Сколько клеток находится под боем шахматного коня - C++
есть задача. http://acm.timus.ru/problem.aspx?space=1&amp;num=1197 написал решение: #include &lt;iostream&gt; using namespace std; int...

Зача про шахматного коня (решить, используя массив) - C++
Помогите пожалуйста решить задачу, на через массив: На шахматной доске NxN в клетке (x1,y1) стоит голодный шахматный конь. Он хочет...

Задача о ходе коня. Опять - C++
Доброе время суток. Мой пост уже второй по этой программе. В прошлый раз меня просили ее сделать более понятной. Ну старался как мог. И...

Путь шахматного коня из одного угла доски в другой за заданное кол-во шагов - C++
Шахматная фигура &quot;конь&quot; перемещается на одну клетку по горизонтали и на две клетки по вертикали или на две клетки по горизонтали и на одну...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.09.2014, 16:21
Привет! Вот еще темы с ответами:

Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей - C++
Найти все пути шахматного коня между двумя заданными полями, не содержащие повторяющихся полей. ПОМОГИТЕЕЕЕ если кто напишет код...

в ходе решения задачи возникли еще вопросы ) - C++
как сделать чтобы массив из 8 элементов разбить на 2 &quot;четверки&quot; и чтобы внутри этих четверок элементы отсортировались по возрастанию ?...

Решение задачи на ветвление (2 коня и шахматная доска) - C++
Поле шахматной доски определяется парой натуральных чисел, каждое которых не превосходит восьми: первое число – номер вертикали (при счете...

Оптимизация Кода задачи - C++
Сама задача: Корабль сначала плыл заданным курсом (север, восток, Юг, запад). Потом его курс был изменен согласно приказу ( вперед,...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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