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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Как узнать, инициализирован ли указатель? http://www.cyberforum.ru/cpp-beginners/thread327783.html
Появился вопрос, как узнать в C++ инициализирован ли определенный указатель?
C++ Нерабочий ссылочный элемент Подскажите пожалйсто почему в данной программе #include<iostream> using namespace std; struct a {int b,c; }; int e(a, bool&); int main () {setlocale(LC_ALL,"Rus"); http://www.cyberforum.ru/cpp-beginners/thread327763.html
C++ Циклы, массивы, простейшие программы
Доброго времени суток. В программировании не силен. Решил обратиться к людям понимающим в этом вопросе больше. Если кто может помочь буду признателен. Задачи привожу ниже по списку разделов. Циклы: 1. Среди всех n-значных чисел (n = 1,2,3,4) указать те, сумма цифр которых равна данному числу k. 2. Натуральное число М называется совершенным, если оно равно сумме всех своих делителей,...
C++ Удалить элементы из структуры
Дали вот такое задание на С++ 1. сделать Структура "Владелец автомобиля": - Фамилия, имя, отчество; - Номер автомобиля; - Номер техпаспорта; - Отделение регистрации ГАИ. 2. Удалить элемент с указанным номером авто, 3. добавить 2 элемента перед элементом с указанным именем. первое я сделал без проблем а вот во вторым и третьим не разберусь никак
C++ error LNK2001 http://www.cyberforum.ru/cpp-beginners/thread327728.html
беда, совсем беда. день тяжелый, мозг не работает. в общем пример из книжки. непосредственно мейн.цпп //_011.cpp #include <iostream> using std::cout; using std::endl; #include <iomanip>
C++ Что означает строчка ??? Что озночает строчка double *x = new double; Заранее спасибо подробнее

Показать сообщение отдельно
vaselo
19 / 19 / 1
Регистрация: 17.10.2010
Сообщений: 247
30.06.2011, 21:55  [ТС]     Прокомментируйте, пожалуйста рекурсию
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'; 
}
что такое в ифах в рекурсивной ф-ции? нифига не вьезжаю
 
Текущее время: 19:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru