задача на рекурсию
Primary tabs
условие:
Все решения должны быть выполнены с помощью рекурсивных функции/функций.
Входные данные должны читаться из текстового файла input.txt.
Результат записываться в текстовый файле output.txt.
На шахматной доске определить поля, в которые может попасть конь за n ходов из указанной позиции.
мысли:
доска есть двумерный массив int board [8][8], изначально заполненный нулями.
из произвольной позиции около центра доски конь может перейти на восемь разных клеток - этот процесс совершает функция.
для каждой получившейся клетки отдельно вызывается та же функция - получаем еще по восемь клеток. итого конь будет в 8^n позициях (n - количество ходов). часть из них выходит за пределы доски - и попросту не учитывается, максимум клеток, куда попадает конь, есть 64 клетки доски.
функция имеет счетчик ходов, достижение которым опр. значения является условием выхода из рекурсии...
перемещение коня в клетку означает заполнение клетки значением счетчика.
вывод результатов: выводятся координаты элементов массива, содержащие значение последнего хода (например, хоров было три - выводятся координаты элементов, содержащих тройку).
- Log in to post comments
- 9910 reads
baton
Sun, 02/24/2013 - 19:25
Permalink
промежуточный нерабочий результат
#include "stdio.h" #define _USE_MATH_DEFINES #include "math.h" #include "string" #include "conio.h" #include "iostream" #include "time.h" #include "ctime" using std::cout; using std::cin; using std::endl; using namespace std; /* доска есть двумерный массив int board [8][8], изначально заполненный нулями. из произвольной позиции около центра доски конь может перейти на восемь разных клеток - этот процесс совершает функция. для каждой получившейся клетки отдельно вызывается та же функция - получаем еще по восемь клеток. итого конь будетв 8^n позициях (n - количество ходов). часть из них выходит за пределы доски - и попросту не учитывается, максимум клеток, куда попадает конь, есть 64 клетки доски. функция имеет счетчик ходов, достижение которым значения 64 является условием выхода из рекурсии... перемещение коня в клетку означает заполнение клетки значением счетчика. вывод результатов: выводятся координаты элементов массива, содержащие значение последнего хода (например, ходов было три, выводятся координаты элементов, содержащих тройку). */ typedef struct { // наш массив вкупе со счетчиком ходов int board [8][8]; int hod; } D; D hod_konem (int n, D D1, int x, int y){ // рекурсивная функция; х и у в аргументах функции есть координаты старта //memset(D1.board, 0, 64); // заполение нулями - хотя нужно ли? D1.hod++; // счетчик //1 D1.board [(x - 2)][(y + 1)] = D1.hod; /* ход конем вниз на две клетки и на одну клетку вправо; то есть елемент масива на две клетки ниже и клетку левее старта заполняется значением счетчика */ D1.board [(x - 2)][(y - 1)] = D1.hod; // по аналогии - все восем возможных точек, куда перемещается конь //2 D1.board [(x + 2)][(y + 1)] = D1.hod; D1.board [(x + 2)][(y - 1)] = D1.hod; //3 D1.board [(x - 1)][(y + 2)] = D1.hod; D1.board [(x + 1)][(y + 2)] = D1.hod; //4 D1.board [(x - 1)][(y - 2)] = D1.hod; D1.board [(x + 1)][(y - 2)] = D1.hod; if(D1.hod < n){ // если счетчик не превысил количество ходов, // то вызываем рекурсию для каждой из восьми точек if((x-2) >= 0){ // если х не выходит за пределы доски,... if((y + 1) <= 8){ // и у тоже не выходит... hod_konem(n, D1, (x - 2), (y + 1) ); //вызываем для точки с координатами (x-2) и (y+1) рекурсию } if((y - 1) >= 0){ hod_konem(n, D1, (x - 2), (y - 1) ); // по аналогии } }//1 первая пара точек обработана if((x+2) <= 8){ if((y+1) <= 8){ hod_konem(n, D1, (x + 2), (y + 1) ); } if((y-1) >= 0){ hod_konem(n, D1, (x + 2), (y -1) ); } }//2 вторая пара точек.... if ((x - 1) >= 0){ if((y + 2) <= 8){ hod_konem(n, D1, (x - 1), (y + 2) ); } if((y - 2) >= 0){ hod_konem(n, D1, (x - 1), (y - 2) ); } }//3 if ((x + 1) <= 8){ if((y + 2) <= 8){ hod_konem(n, D1, (x + 1), (y + 2) ); } if((y - 2) >= 0){ hod_konem(n, D1, (x + 1), (y - 2) ); } }//4 } return D1; } void Publish(D D3){ // функция вывода на экран координат for(int i = 0; i < 9; i++){ // цикл перебирающий вертикальные координаты доски for(int j = 0; j < 9; j++){ // цикл перебирающий горизонтальные координаты if(D3.board [i][j] == D3.hod){ // если значение рассматриваемого значения равно последнему значению счетчика cout << endl << "координаты точек:"; cout << endl << i << j; // то мы выводим его координаты } } } } void main(){ setlocale(LC_ALL, "Russian"); D D2; // наша шахматная доска D D3; // она же D2.hod = 0; // счетчик ходов в функции hod_konem int x, y, N; cout << "введите количество ходов: "; cin >> N; //количество ходов cout << "введите координаты коня: "; cout << endl; cin >> x; cout << endl; cin >> y; // координаты исходной клетки if (x < 9 && y <9){ D3 = hod_konem (N, D2, x, y); Publish(D3); } else cout << "вы ввели некоректные значения"; getch (); }baton
Sun, 02/24/2013 - 19:26
Permalink
что конкретно не работает
при задании ходов более одного прога падает - "необработанное исключение" или просто выполняет один ход.
первый ход выполняется правильно.
предположений, почему не пашет - нет
vedro-compota
Sun, 02/24/2013 - 22:17
Permalink
что-то вызывает исключение -
что-то вызывает исключение - то есть ошибку - закомментируйте "опасный" участок и запустите программу - просто выведите рекурсивно сто раз на экран какое-нибудь слово передавая каждый раз в рекурсию счётчик - условие выхода =
вы понимаете как это сделать?
сделайте.
_____________
матфак вгу и остальная классика =)
baton
Sun, 02/24/2013 - 22:44
Permalink
100 раз пустить рекурсию с выводом слова
ну... понимаю...
вот пример рабочего кода
void hod_konem (int h){ cout << "мы русские, с нами Бог!"; if(h < 100){ cout << endl << "не в силе Бог, а в правде" << endl; h++; hod_konem (h); } } void main(){ setlocale(LC_ALL, "Russian"); int h = 1; hod_konem(h); getch (); }tata_la
Mon, 02/25/2013 - 21:57
Permalink
славненько)
славненько)
_________ _ _ ______
dthcbz фкн вгу and co