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

последовательность ходов коня - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Тривиальный move конструктор http://www.cyberforum.ru/cpp-beginners/thread1049043.html
Всем привет. Вобщем пишу код используя классы некой библиотеки, полагаясь, что в будущем разработчики добавят move-конструкторы в эти классы. Следовательно сейчас используются определенные компилятором по-умолчанию move-конструкторы (тобишь тривиальные). Вопрос: тривиальный move-конструктор генерируется пустым (получается тогда нету никакой выгоды в скорости) или тупо почленно перемещает...
C++ Указатель на структуру Выбивает ошибку: scalar object requires one element in initializer #include <QtGlobal> #include <iostream> #include <cmath> #include <climits> #include <windows.h> #include <ctime> #include <cstring> #include <clocale> #include <time.h> http://www.cyberforum.ru/cpp-beginners/thread1049039.html
C++ как в c++ проверить пренадлежит ли переменная определенному типу?
Например, что бы если пользователь ввел не число а символ, то в консоль выводилось сообщение об ошибке.
тяжёлая программа, поднапрягите мозги:) ( необходимо составить тяжёлый алгоритм ) C++
итак, писать самому лень, поэтому просто скопирую задачу Условие: Для школьного пикника двум классам 11 «А» и 11 «Б» было поручено закупить N продуктов. Помогите ребятам определить, какой класс какие продукты закупает, так, чтобы закупленные классами наборы продуктов, отличались по суммарной их стоимости на минимально возможную величину. Формат входных данных: Вводится N- общее количество...
C++ квадратное уравнение http://www.cyberforum.ru/cpp-beginners/thread1049024.html
Обработка исключительных ситуаций Функция вычисляет корень квадратного уравнения ax2+bx+c=0
C++ Определить и вывести на экран количество предложений в произведении, а также сами предложения В-общем, есть такая задача:С клавиатуры вводится строка символов, представляющая собой некоторый отрывок литературного произведения. Определить и вывести на экран количество предложений в нем, а также сами предложения. И есть вот такой вот код, найденный в интернете(немного изменённый мной): #include <iostream> using namespace std; int main() { char str, s = " "; int count =... подробнее

Показать сообщение отдельно
Ботью
 Аватар для Ботью
3 / 3 / 0
Регистрация: 12.09.2012
Сообщений: 90
19.12.2013, 23:12     последовательность ходов коня
доброго времени суток, есть задача:
"Разработать программу, решающую задачу о ходе коня. Дана доска размером n x n (n<=10). На поле с координатами x0, y0 помещается конь (правила перемещения этой фигуры как в шахматах). Задача заключается в поиске последовательности ходов (если она существует), при которой конь точно один раз побывает на всех полях доски (обойдет доску), т. е. нужно вычислить n2-1 ходов. Полученную в качестве результата последовательность ходов отобразить на экране."

я нашел некоторое подобие этой задачи, но ни в какую не могу подогнать под свое условие, может кто помочь?
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
//глобальные константы, определяющие размерность массива board
const int hor = 8, ver = 8;
//прототип функции для вывода массива, имитирующего шахматную доску, на экран   
void printBoard(int[][ver]);  
using namespace std;
 
int main()
{
   //выделяем память для массива, эмитирующего шахматную доску
   int board[hor][ver] = {0};                        
   //описываем этими двумя массивами варианты ходов конем на доске(их всего восемь от 0 до 7)
   int horizontal[hor] = { 2, 1,-1,-2,-2,-1, 1, 2};  
   int vertical[ver] =   {-1,-2,-2,-1, 1, 2, 2, 1};
   //массив доступности ходов конем  
   int accessibility[hor][ver] = {{2,3,4,4,4,4,3,2}, 
                                  {3,4,6,6,6,6,4,3},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {3,4,6,6,6,6,4,3},
                                  {2,3,4,4,4,4,3,2}};
   //переменные, запоминающие текущие координаты нахождения коня
   int currentRow, currentColumn;
   //переменная, определяющая вариант хода конем(от 0 до 7)                    
   int moveNumber;
   //счетчик ходов конем                                   
   int counter = 0;                                  
 
   //предложение ввода координаты нахождения коня по горизонтали
   cout << "Enter a horizontal coordinate(0 - 7): "; 
   //сохранение введенных данных в переменной
   cin >> currentRow;
   //ввод координаты по вертикали                                
   cout << "Enter a vertical coordinate(0 - 7): "; 
   //сохранение данных ввода  
   cin >> currentColumn;                             
   
   //переменные currentRow и currentColumn модифицируються для изменения доступностей, поэтому сохраняем их
   int mainRow = currentRow, mainColumn = currentColumn;
   //переменные для записи координат следующего хода конем 
   int Row, Column; 
   
   //начинаем поиск решения
   for(int i = 1; i <= 64; i++)                      
   {
      board[mainRow][mainColumn] = ++counter;
      
      //делаем равным максимально возможной доступности
      int minAccessibility = 8;
      //временные переменные для исследования субдоступностей  
      int minA = 8, minB = 8;  
      
      //уменьшение доступности на единицу клеток, расположенных в одном ходу от выбранной
      for(moveNumber = 0; moveNumber <= 7; moveNumber++) 
      {
         //запоминаем положение коня на доске перед модификацией для изменения доступностей
         currentRow = mainRow;      
         currentColumn = mainColumn;
         
         //исследуем доступность всех возможных ходов не выходящих за границы доски
         currentRow += horizontal[moveNumber];  
         currentColumn += vertical[moveNumber];
         
         //не выходит ли за границы доски
         if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7) 
         {
            //уменьшаем доступность всех клеток в одном ходу
            accessibility[currentRow][currentColumn]--;  
            
            //если доступность больше, то меняем на меньшую
            if(minAccessibility > accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               //нашли минимальную доступность и ее координаты
               minAccessibility = accessibility[currentRow][currentColumn];  
               
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0)  
               {
                  //подготовили координаты к ходу на эту клетку
                  Row = currentRow;  
                  Column = currentColumn;
               }
               //временных переменные для нахождения минимальной доступности у тех, что меньше
               int RowA = currentRow, ColumnA = currentColumn; 
               
               for(int moveA = 0; moveA <= 7; moveA++)
               {
                  RowA += horizontal[moveA];
                  ColumnA += vertical[moveA];
                  
                  if(RowA >= 0 && RowA <= 7 && ColumnA >= 0 && ColumnA <= 7)
                  {
                     if(minA >= accessibility[RowA][ColumnA] && board[RowA][ColumnA] == 0)
                        //наименьшая доступность следующего хода
                        minA = accessibility[RowA][ColumnA]; 
                  }
               }
            }
   
            //если доступности равны
            if(minAccessibility == accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               minAccessibility = accessibility[currentRow][currentColumn];
               
               //временных переменные для нахождения минимальной доступности у тех, что равны
               int RowB = currentRow, ColumnB = currentColumn; 
               
               for(int moveB = 0; moveB <= 7; moveB++)
               {
                  RowB += horizontal[moveB];
                  ColumnB += vertical[moveB];
                  
                  if(RowB >= 0 && RowB <= 7 && ColumnB >= 0 && ColumnB <= 7)
                  {
                     if(minB >= accessibility[RowB][ColumnB] && board[RowB][ColumnB] == 0)
                        //наименьшая доступность следующего хода
                        minB = accessibility[RowB][ColumnB]; 
                  }
               }
   
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0 && minB < minA)  
               {
                  //изменяем подготовленные для следующего хода координаты в случае, если доступность следующего хода меньше
                  Row = currentRow;       
                  Column = currentColumn;
               }
            }
         }
      }
   
      mainRow = Row;
      mainColumn = Column;
   }
   
   //вызов функции для печати массива, моделирующего шахматную доску
   printBoard(board);                                
   system ("pause void");
   return 0;
}
   
//вывод массива, печатающего шахматную доску, на экран
void printBoard(int array[][ver])   
{
   cout << endl;
   for(int j = 0; j < ver; j++)
   {
      for(int i = 0; i < hor; i++)
         cout << setw(4) << array[i][j];
         
      cout << endl << endl;
   }
}
Добавлено через 1 час 6 минут
мои попытки привели вот к такому вот коду, он запускается, но падает в неизвестном мне месте циклов
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "stdafx.h"
#include <iostream>
#include <iomanip>
 
//прототип функции для вывода массива, имитирующего шахматную доску, на экран   
void printBoard(int **arr, int , int);  
using namespace std;
 
int main()
{
    int hor,ver;
    cout<<"Enter N\t\t";
    do {
    cin>>hor;
    }while(hor<1&&hor>10);
    ver=hor;
   //выделяем память для массива, эмитирующего шахматную доску
   int **board=new int*[hor];
   for(int i=0;i<hor;i++)
       board[i]=new int [ver];                      
   //описываем этими двумя массивами варианты ходов конем на доске(их всего восемь от 0 до 7)
   int horizontal[8]={ 2, 1,-1,-2,-2,-1, 1, 2};  
   int vertical[8]=   {-1,-2,-2,-1, 1, 2, 2, 1};
   //массив доступности ходов конем  
   
   int **accessibility=new int*[hor];
   for(int i=0;i<hor;i++)
       accessibility[i]=new int[ver];
   for(int i =0;i<hor;i++)
   {
       for(int j=0; j< ver; j++)
       {
           if(i==0||i==ver-1)
           {
               if(j==0||j==ver-1) accessibility[i][j]=2;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=3;
               else accessibility[i][j]=4;}
           }
           if(i==1||i==ver-2)
           {
               if(j==0||j==ver-1) accessibility[i][j]=3;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=4;
               else accessibility[i][j]=6;}
           }
           else if(i!=0&&i!=1&&i!=ver-1&&i!=ver-2)
           {
               if(j==0||j==ver-1) accessibility[i][j]=4;
               else{
               if(j==1||j==ver-2) accessibility[i][j]=6;
               else if(i!=2||i!=3||i!=4||i!=6)accessibility[i][j]=8;}
 
           }
       }
   }
       
       
       /* = 
                                 {{2,3,4,4,4,4,3,2}, 
                                  {3,4,6,6,6,6,4,3},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {4,6,8,8,8,8,6,4},
                                  {3,4,6,6,6,6,4,3},
                                  {2,3,4,4,4,4,3,2}};*/
   //переменные, запоминающие текущие координаты нахождения коня
   printBoard(accessibility, hor,ver);
   int currentRow, currentColumn;
   //переменная, определяющая вариант хода конем(от 0 до 7)                    
   int moveNumber;
   //счетчик ходов конем                                   
   int counter = 0;                                  
 
   //предложение ввода координаты нахождения коня по горизонтали
   cout << "Enter a horizontal coordinate(0 - 7): "; 
   //сохранение введенных данных в переменной
   cin >> currentRow;
   //ввод координаты по вертикали                                
   cout << "Enter a vertical coordinate(0 - 7): "; 
   //сохранение данных ввода  
   cin >> currentColumn;                             
   
   //переменные currentRow и currentColumn модифицируються для изменения доступностей, поэтому сохраняем их
   int mainRow = currentRow, mainColumn = currentColumn;
   //переменные для записи координат следующего хода конем 
   int Row, Column; 
   
   //начинаем поиск решения
   for(int i = 1; i <= hor*hor; i++)                      
   {
      board[mainRow][mainColumn] = ++counter;
      
      //делаем равным максимально возможной доступности
      int minAccessibility = 8;
      //временные переменные для исследования субдоступностей  
      int minA = 8, minB = 8;  
      
      //уменьшение доступности на единицу клеток, расположенных в одном ходу от выбранной
      for(moveNumber = 0; moveNumber < 8; moveNumber++) 
      {
         //запоминаем положение коня на доске перед модификацией для изменения доступностей
         currentRow = mainRow;      
         currentColumn = mainColumn;
         
         //исследуем доступность всех возможных ходов не выходящих за границы доски
         currentRow += horizontal[moveNumber];  
         currentColumn += vertical[moveNumber];
         
         //не выходит ли за границы доски
         if(currentRow >= 0 && currentRow <= 7 && currentColumn >= 0 && currentColumn <= 7) 
         {
            //уменьшаем доступность всех клеток в одном ходу
            accessibility[currentRow][currentColumn]--;  
            
            //если доступность больше, то меняем на меньшую
            if(minAccessibility > accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               //нашли минимальную доступность и ее координаты
               minAccessibility = accessibility[currentRow][currentColumn];  
               
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0)  
               {
                  //подготовили координаты к ходу на эту клетку
                  Row = currentRow;  
                  Column = currentColumn;
               }
               //временных переменные для нахождения минимальной доступности у тех, что меньше
               int RowA = currentRow, ColumnA = currentColumn; 
               
               for(int moveA = 0; moveA < 8; moveA++)
               {
                  RowA += horizontal[moveA];
                  ColumnA += vertical[moveA];
                  
                  if(RowA >= 0 && RowA < 8 && ColumnA >= 0 && ColumnA <8 )
                  {
                     if(minA >= accessibility[RowA][ColumnA] && board[RowA][ColumnA] == 0)
                        //наименьшая доступность следующего хода
                        minA = accessibility[RowA][ColumnA]; 
                  }
               }
            }
   
            //если доступности равны
            if(minAccessibility == accessibility[currentRow][currentColumn] && board[currentRow][currentColumn] == 0)  
            {
               minAccessibility = accessibility[currentRow][currentColumn];
               
               //временных переменные для нахождения минимальной доступности у тех, что равны
               int RowB = currentRow, ColumnB = currentColumn; 
               
               for(int moveB = 0; moveB <8; moveB++)
               {
                  RowB += horizontal[moveB];
                  ColumnB += vertical[moveB];
                  
                  if(RowB >= 0 && RowB <hor && ColumnB >= 0 && ColumnB <hor)
                  {
                     if(minB >= accessibility[RowB][ColumnB] && board[RowB][ColumnB] == 0)
                        //наименьшая доступность следующего хода
                        minB = accessibility[RowB][ColumnB]; 
                  }
               }
   
               //если не ходили на нее еще то делаем на нее ход
               if(board[currentRow][currentColumn] == 0 && minB < minA)  
               {
                  //изменяем подготовленные для следующего хода координаты в случае, если доступность следующего хода меньше
                  Row = currentRow;       
                  Column = currentColumn;
               }
            }
         }
      }
   
      mainRow = Row;
      mainColumn = Column;
   }
   
   //вызов функции для печати массива, моделирующего шахматную доску
   printBoard(board, ver, hor);                                
   system ("pause void");
   return 0;
}
   
//вывод массива, печатающего шахматную доску, на экран
void printBoard(int **array, int ver, int hor)   
{
   cout << endl;
   for(int j = 0; j < ver; j++)
   {
      for(int i = 0; i < hor; i++)
         cout << setw(4) << array[i][j];
         
      cout << endl << endl;
   }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 01:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru