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

Прокомментируйте, пожалуйста рекурсию - C++

Восстановить пароль Регистрация
 
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
29.06.2011, 19:05     Прокомментируйте, пожалуйста рекурсию #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
void chessknight(int k)
{
   c++; 
   if (k==n*n)    print(); 
   if  ((r[n*x[k]+y[k]+2]==false) && (x[k]<=n-1) && (y[k]<=n-2))
   {
      r[n*x[k]+y[k]+2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]+2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]+1]==false) && (x[k]<=n-2) && (y[k]<=n-1))
   {
      r[n*(x[k]+1)+y[k]+1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]+1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]-1]==false) && (x[k]<=n-2) && (y[k]>=2))
   {
      r[n*(x[k]+1)+y[k]-1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]-1;
      chessknight(k+1);
   } 
   if  ((r[n*x[k]+y[k]-2]==false) && (x[k]<=n-1) && (y[k]>=3))
   {
      r[n*x[k]+y[k]-2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]-2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]-2]==false) && (x[k]>=2) && (y[k]>=3))
   {
      r[n*(x[k]-2)+y[k]-2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]-2;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]-1]==false) && (x[k]>=3) && (y[k]>=2))
   {
      r[n*(x[k]-3)+y[k]-1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]-1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]+1]==false) && (x[k]>=3) && (y[k]<=n-1))
   {
      r[n*(x[k]-3)+y[k]+1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]+1;
      chessknight(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]+2]==false) && (x[k]>=2) && (y[k]<=n-2))
   {
      r[n*(x[k]-2)+y[k]+2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]+2;
      chessknight(k+1);
   }
   r[n*(x[k]-1)+y[k]] = false;
   x[k] = 1;
   y[k] = 0;
   c++;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2011, 19:05     Прокомментируйте, пожалуйста рекурсию
Посмотрите здесь:

прокомментируйте пожалуйста код C++
C++ Прокомментируйте пожалуйста код
Прокомментируйте пожалуйста C++
C++ прокомментируйте пожалуйста программу
прокомментируйте код пожалуйста C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6542 / 3962 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
29.06.2011, 19:18     Прокомментируйте, пожалуйста рекурсию #2
где код взяли там и комментарии ищите, нам-то откуда знать что такое х у r
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
29.06.2011, 19:33  [ТС]     Прокомментируйте, пожалуйста рекурсию #3
x,y -координаты в двумерном массиве.
k - номер шага, я так понял
с - номер решения.
непонятны условия ифов. если это представление како-го то метода, может кто узнает в коде этот метод? понимание кода упроститься.
Bers
Заблокирован
29.06.2011, 20:24     Прокомментируйте, пожалуйста рекурсию #4
нада быть мазохистом, что бы просто так, без особой причины, пытаться впереццо в запись типа:

if ((r[n*x[k]+y[k]-2]==false) && (x[k]<=n-1) && (y[k]>=3))

Тот, кто это писал, похоже ложил с большим прибором на тех, кто после него этот код читать будит.
.4rray
8 / 8 / 0
Регистрация: 15.12.2010
Сообщений: 41
29.06.2011, 20:56     Прокомментируйте, пожалуйста рекурсию #5
Конь может пойти 8 способами. В коде 8 условий.
Значит проверяются свободны ли клетки(8 шт.) в которые он пытается шагнуть.
Но написано как-то через жепь.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
29.06.2011, 20:57     Прокомментируйте, пожалуйста рекурсию #6
Это реализация бэктрекинга (перебор (поиск) с возвратом).
Проверяются все возможные 8 ходов (вверх вправо, вверх влево, вправо вверх и т.д.), если ход есть - делаем следующий, если хода нет - отходим на шаг назад.

Добавлено через 1 минуту

Не по теме:

Цитата Сообщение от .4rray Посмотреть сообщение
Но написано как-то через жепь.
есть немного ))

vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
29.06.2011, 21:48  [ТС]     Прокомментируйте, пожалуйста рекурсию #7
А тут и проверка есть на колличество допустимых ходов? или что такое второе и третье условие в каждом ИФЕ?

Добавлено через 20 минут

Не по теме:

кто знаком с этим алгоритмом???

ValeryLaptev
Эксперт C++
1004 / 783 / 46
Регистрация: 30.04.2011
Сообщений: 1,595
30.06.2011, 09:54     Прокомментируйте, пожалуйста рекурсию #8
Это прога обхода конем всей доски. В самом начале стоит проверка k == n*n - все ли клетки конь обошел. Решение этой задачи можно посмотреть в книге Никлауса Вирта Структуры данных и алгоритмы.
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
30.06.2011, 21:55  [ТС]     Прокомментируйте, пожалуйста рекурсию #9
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
#include "stdafx.h"
#include <Windows.h>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <conio.h>
 
using namespace std;
 
const int n = 8;        //розмірність дошки
 
int x[n*n+1];       //номер горизонталі на k-му кроці, 1<=k<=n^2, 1<=x[k]<=n 
int y[n*n+1];       //номер горизонталі на k-му кроці, 1<=k<=n^2, 1<=y[k]<=n 
bool r[n*n+2];      //r[p[k]]==true = зайнята клітинка з номером p[k]=n*(x[k]-1)+y[k] на k-му кроці, k<=
FILE *f;            //файл для збереження результатів
float time1;        //час початку
float time2;        //час знаходження
int u;              //номер рішення
double c;           //кількість кроків
char fileout[15];   //ім'я файлу для збереження
 
void shag(int k);  //рекурсивна ф-ція
void print();             //друк до файлу
void input();             //введення даних
void output();             
 
int main()
{ 
setlocale(LC_ALL,"Rus");
   input();
   float time1=clock(); 
   u = 0; 
   c = 0;
   r[n*(x[1]-1)+y[1]] = true;
   shag(1);
   output();
   getch(); 
   return 0;
}
 
void shag(int k)
{
   c++; 
   if (k==n*n)    print(); //ЯКЩО ЗРОБИЛИ ДОСТУПНУ КІЛЬКІСТЬ КРОКІВ - ЗБЕРІГАЄМО ДО ФАЙЛУ
   if  ((r[n*x[k]+y[k]+2]==false) && (x[k]<=n-1) && (y[k]<=n-2))            //1
   {
      r[n*x[k]+y[k]+2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]+2;
      shag(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]+1]==false) && (x[k]<=n-2) && (y[k]<=n-1))            //2
   {
      r[n*(x[k]+1)+y[k]+1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]+1;
      shag(k+1);
   }
   if  ((r[n*(x[k]+1)+y[k]-1]==false) && (x[k]<=n-2) && (y[k]>=2))          //3
   {
      r[n*(x[k]+1)+y[k]-1] = true;
      x[k+1] = x[k]+2;
      y[k+1] = y[k]-1;
      shag(k+1);
   } 
   if  ((r[n*x[k]+y[k]-2]==false) && (x[k]<=n-1) && (y[k]>=3))          //4
   {
      r[n*x[k]+y[k]-2] = true;
      x[k+1] = x[k]+1;
      y[k+1] = y[k]-2;
      shag(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]-2]==false) && (x[k]>=2) && (y[k]>=3))            //5
   {
      r[n*(x[k]-2)+y[k]-2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]-2;
      shag(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]-1]==false) && (x[k]>=3) && (y[k]>=2))            //6
   {
      r[n*(x[k]-3)+y[k]-1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]-1;
      shag(k+1);
   }
   if  ((r[n*(x[k]-3)+y[k]+1]==false) && (x[k]>=3) && (y[k]<=n-1))          //7
   {
      r[n*(x[k]-3)+y[k]+1] = true;
      x[k+1] = x[k]-2;
      y[k+1] = y[k]+1;
      shag(k+1);
   }
   if  ((r[n*(x[k]-2)+y[k]+2]==false) && (x[k]>=2) && (y[k]<=n-2))          //8
   {
      r[n*(x[k]-2)+y[k]+2] = true;
      x[k+1] = x[k]-1;
      y[k+1] = y[k]+2;
      shag(k+1);
   }
   r[n*(x[k]-1)+y[k]] = false;
   x[k] = 1;
   y[k] = 0;
   c++;
}
 
void print()
{  
   u++;
   float time2 = clock(); 
   printf("Решение  %6d найдено. Время работы = %3.3f  с\n", u,  (time2-time1)/1000);
   f = fopen(fileout, "a");
   fprintf(f,"Решение № %6d,  шагов = %e,  время = %3.3f s:\n", u, c, (time2-time1)/1000);
   for (int k=1; k<=n*n; k++)  fprintf(f, "%2d  %c%d  %2d\n", k, x[k]+96, y[k], n*(x[k]-1)+y[k]);
   fprintf(f,"\n");
   fclose(f);
}
 
void input()
{
    cout << "Путь обхода конём всех " << n*n <<" клеток шахматной доски размера "<< n <<"x" << n <<".\n Рекурсия\n"; 
    cout<<"\nИспользуется алгоритм, представленный в книге\nНиклауса Вирта 'Алгоритмы+Структуры данных=Программа'\nи правило Варнсдорфа:";
    cout<<"\n\t   'При обходе доски конь следует на то поле,\n\t с которого можно пойти на минимальное число ещё не пройденных полей.";
    cout<<"\n\t Если таких полей несколько, то можно пойти на любое из них'.\n";
   char x0;
   char y0;
   do{
     printf("Введите одну из %d букв: a..%c:   ", n, 96+n);
     cin >> x0;
   }
   while ((x0 <'a')||(x0>96+n)); 
   do
   {
     printf("Введите одну из %d цифр: 1..%c:   ", n, 48+n);
     cin >> y0;
   }
   while ((y0 <'1')||(y0>48+n)); 
   strcpy(fileout, "results ");
   fileout[strlen(fileout)-1]=n+48;
   char v0[] = "  ";
   v0[0] = x0; 
   v0[1] = y0;
   strcpy(fileout+strlen(fileout), v0);
   strcpy(fileout+strlen(fileout), "r.txt");
   time1=clock(); 
   f = fopen(fileout, "w");
   fprintf(f, "Рекурсивная программа поиска путей шахматным конем.\n");
   fprintf(f, "Размер доски %dx%d, %d полей. \n", n, n, n*n);
   fprintf(f, "Конь посещает каждую ячейку всего один раз\n\n");
   fclose(f);
   for (int k=0; k<=n*n; k++) x[k] = 1;
   for (int k=0; k<=n*n; k++) y[k] = 0;
   x[1] = x0-96;
   y[1] = y0-48;
   for (int k=0; k<=n*n; k++) r[k] = false;
}
 
void output()
{
   float time2 = clock(); 
   printf("Время работы  =  %6.3f    с\n",  (time2-time1)/1000); 
   f = fopen(fileout, "a");
   fprintf(f, "Общее время  =  %6.3f    секунд\n",(time2-time1)/1000); 
   if (u==0) fprintf(f, "Нету возможных маршрутов!\n");
   else fprintf(f, "Колличество маршрутов =  %d\n", u);
   fprintf(f, "Всего шагов сделано =  %e\n", c); 
   fclose(f);
   cout << "Сделано всего пробных ходов конём: "  << c <<'\n'; 
   if (u==0) cout << "Решений нет\n"; 
   else cout << "Решения сохранены в файле " << fileout  <<'\n'; 
}
что такое в ифах в рекурсивной ф-ции? нифига не вьезжаю
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2011, 14:14     Прокомментируйте, пожалуйста рекурсию
Еще ссылки по теме:

Прокомментируйте пожалуйста C++
C++ Прокомментируйте пожалуйста программу
C++ Прокомментируйте код, пожалуйста

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

Или воспользуйтесь поиском по форуму:
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
06.07.2011, 14:14  [ТС]     Прокомментируйте, пожалуйста рекурсию #10
C++
1
2
int x[n*n+1];       //номер горизонталі на k-му кроці, 1<=k<=n^2, 1<=x[k]<=n 
int y[n*n+1];       //номер горизонталі на k-му кроці, 1<=k<=n^2, 1<=y[k]<=n
C++
1
if  ((r[n*(x[k]+1)+y[k]+1]==false) && (x[k]<=n-2) && (y[k]<=n-1))
Что за массивы? в них хранится, были ли мы на таком же шагу в той же клеточке? тоесть проверяем, новый ли маршрут ищем? тут попонятнее, пожалуйста

в ифе что такое первое условие? второе - доступность шага, не выход за границу?


помогите, сдавать надо скороо, а у меня и компа нету своего

Добавлено через 30 минут
массивы и есть сама доска, но почему полей по 65? а не по 8. как определяется, не повторяется ли маршрут? а то при работе программы маршрутов может быть до 200 000 штук, как он знает, что не повторяется?

Добавлено через 22 часа 54 минуты
всем спасибо за непомощь, сам справился, оказалось довольно просто! а сегодня все-равно не успел сдать...зато сам разобрался! и стыдно, что отладку не включил и не проследил за ходом алгоритма!
Yandex
Объявления
06.07.2011, 14:14     Прокомментируйте, пожалуйста рекурсию
Ответ Создать тему
Опции темы

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