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

Обход доски шахматным конем - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Меню для программы http://www.cyberforum.ru/cpp-beginners/thread263405.html
Подскажите пожалуйста как сделать в консольной программе на c++ главное меню вверху (файл, справка, об авторе и тд...)
C++ Массив Подскажите пожалуйста как реализовать на С вот такой фрагмент: Если элемент встречается в массиве 3к раз(число кратное трем), то продолжать работу и когда находится элемент который встречается не... http://www.cyberforum.ru/cpp-beginners/thread263404.html
Уравнения! C++
Подскажите как правильно написать эти уравнения? Вот всё что я осилил... X вместо а. void ysl1 (float X, float *tab) { tab = X * ((cos (X) + 14) / (sin (X) + 7)); }
Точка на плоскости. C++
!!!!!!!!!!!!!!!!!!!!!!!!!!!
C++ преобразование *argv[] http://www.cyberforum.ru/cpp-beginners/thread263385.html
Всем привет. Смысл задачи такой. Запускаю программу с параметром "с.txt" на который указывает *argv. Как сделать так, чтобы *argv указывал не на "c.txt" а на "c.out.txt". Естественно имя файла может...
C++ Найти сумму нечетных элементов. Постановка задачи. Решить указанные в варианте задачи, используя основные операторы языка С++. При решении задачи, использовать все типы циклов (for, while, do while). 1. Дана последовательность... подробнее

Показать сообщение отдельно
olleg90
34 / 34 / 6
Регистрация: 06.01.2011
Сообщений: 90
26.03.2011, 19:37  [ТС]
Два способа решения!
способ номер (эвристика) один за основу взято Правило Варнсдорфа
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
#include <stdio.h>
#include <iostream>
#define M 30
int numberOfSteps(int x, int y, int A[M][M]);
void printArray(int A[M][M]);
int offset[8][2];
 
int main()
{
    setlocale(LC_CTYPE,"");
    int A[M][M];
    int steps[8];
    int x=3, y=3, count=1, idx=0;
    std::cout<<"введите х"<<std::endl;
    std::cin>>x;
    std::cout<<"введите y"<<std::endl;
    std::cin>>y;
 
    offset[0][0]= 2; offset[0][1]= 1; 
    offset[1][0]= 2; offset[1][1]=-1; 
    offset[2][0]= 1; offset[2][1]= 2;
    offset[3][0]= 1; offset[3][1]=-2; 
    offset[4][0]=-1; offset[4][1]= 2; 
    offset[5][0]=-1; offset[5][1]=-2;
    offset[6][0]=-2; offset[6][1]= 1; 
    offset[7][0]=-2; offset[7][1]=-1;
    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            A[i][j]=0;    
        }
    }
    A[x][y]=count;
    
    do {
        for(int k=0; k<8; k++) {
            steps[k]=numberOfSteps(x+offset[k][0], y+offset[k][1], A);
        }
        for(int k=0; k<8; k++) {
            if(steps[k]>0) {
                idx = k;
                break;
            }
            if(k==7) {
                for(int i=0; i<8; i++) {
                    if(steps[i]==0) {
                        A[x+offset[i][0]][y+offset[i][1]]=++count;
                    }
                }
                printArray(A);
                return 0;    
            }
        }
        for(int k=0; k<8; k++) {
            if(steps[k]<steps[idx] && steps[k]>0) {
                idx = k;
            }
        }
        
        x += offset[idx][0]; 
        y += offset[idx][1]; 
        A[x][y]=++count;
        
    } while(true);
    return 0;
}
 
int numberOfSteps(int x, int y, int A[M][M])
{
    if((x<0 || x>=M || y<0 || y>=M || A[x][y]!=0)) {
        return -1;
    }
    int count=0;
    for(int k=0; k<8; k++) {
        int xn=x+offset[k][0];
        int yn=y+offset[k][1];
        if(xn>=0 && xn<M && yn>=0 && yn<M && A[xn][yn]==0) {
            count++;
        }
    }
    return count;
}
 
void printArray(int A[M][M])
{
    for(int i=0;i<M;i++) {
        for(int j=0;j<M;j++) {
            printf("%4d",A[i][j]);
        }
        printf("\n");
    }    
     system("pause");
}
способ номер два Через рекурсию с откатом
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;
}
 
 
 
/*главная функция*/
void main() 
{
setlocale (LC_ALL,"");
 
int i,nrows,ncols,sy,sx,**desc = NULL;
time_t start,end;
//вводим данные
cout<<"Введите размерность доски (от 2 до 8) :"<<endl
 <<"по оси \"X\"\t"; cin>>size_x;
cout<<"по оси \"Y\"\t";cin>>size_y;
if(size_x>8||size_x<2||size_y>8||size_y<2)
{cout<<"Неверный размер";system("pause");return;}
//проверяем размерность
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");
}
сам спросил сам ответил

Добавлено через 7 минут
На wiki нашел следующее :
"В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня."
ребята подскажите кто ни будь как можно через графы решить а то что то не пойму гамильтонов путь и цикл )
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru