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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа не выводит русские слова http://www.cyberforum.ru/cpp-beginners/thread1262048.html
Пытался сделать чтобы например ввел имя и оно тебе потом выведит в cout<<"Вы ввели:"<<text<<""<<endl; место text мое имя. Оно выводит только английские слова а мне нужно чтобы и русские тоже. #include <iostream> using namespace std; int main() { setlocale(LC_ALL,"rus"); cout<<"Введите любой текст: "; char text="";
C++ Диапазон отрицательных чисел. Функция rand() Как задать диапазон случайных чисел чтобы в него входили как положительные так иотрицательные числа к примеру от -100 до 100? http://www.cyberforum.ru/cpp-beginners/thread1262041.html
Как вернуть массив из функции? C++
#include "stdafx.h" #include <iostream> using namespace std; int mass(int n) { int* Mass = new int; //здесь провожу действия с динамическим одномерным массивом размерность n
Дано ax^2+bx+c=0 найти кол во и значение корней C++
Дано ax^2+bx+c=0 найти кол во и значение корней. т.е ввести a,b,c вывести:1)"это не квадратное выражение "-если a=0 2)"нет корней"-если д<0 3)1 корень х=... если д=0 4)2 корня x1 и x2 если д>0 Заранее спасибо!!!
C++ Невозможно обратиться к private -члену http://www.cyberforum.ru/cpp-beginners/thread1262021.html
Подскажите пожалуйста,в чем проблема, из-за создания объекта компилятор выдает ошибку. Класс Base-абстрактный #include "stdafx.h" #include <iostream> #include <string> using namespace std; class Base { protected:
C++ Массив A содержит только два одинаковых числа. Найти эти числа и указать их индексы ошибка Массив А содержит только два одинаковых числа. Найти эти числа и указать их индексы. #include <iostream> const int N = 3; const int M = 3; struct Pair { подробнее

Показать сообщение отдельно
xannn94
0 / 0 / 0
Регистрация: 17.12.2013
Сообщений: 8

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

24.09.2014, 16:21. Просмотров 397. Ответов 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 минут
Мои мысли что делать такие: создать функцию которая записывает в массив возможные ходы(именно функцию,т.к. размер матрицы может быть разнообразен) далее перед каждым ходом делать проверку (узнать количество ходов и сортировать эти ходы(нужно выбрать ход в клетку из которой можно сделать минимальное количество ходов),после сортировки можно ходить. Как то так. Помогите реализвать всё это пожалуйста=)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru