задача на рекурсию

условие:
Все решения должны быть выполнены с помощью рекурсивных функции/функций.
Входные данные должны читаться из текстового файла input.txt.
Результат записываться в текстовый файле output.txt.
На шахматной доске определить поля, в которые может попасть конь за n ходов из указанной позиции.

мысли:
доска есть двумерный массив int board [8][8], изначально заполненный нулями.

из произвольной позиции около центра доски конь может перейти на восемь разных клеток - этот процесс совершает функция.
для каждой получившейся клетки отдельно вызывается та же функция - получаем еще по восемь клеток. итого конь будет в 8^n позициях (n - количество ходов). часть из них выходит за пределы доски - и попросту не учитывается, максимум клеток, куда попадает конь, есть 64 клетки доски.

функция имеет счетчик ходов, достижение которым опр. значения является условием выхода из рекурсии...
перемещение коня в клетку означает заполнение клетки значением счетчика.
вывод результатов: выводятся координаты элементов массива, содержащие значение последнего хода (например, хоров было три - выводятся координаты элементов, содержащих тройку).

baton's picture

	#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's picture

при задании ходов более одного прога падает - "необработанное исключение" или просто выполняет один ход.
первый ход выполняется правильно.

предположений, почему не пашет - нет

vedro-compota's picture

что-то вызывает исключение - то есть ошибку - закомментируйте "опасный" участок и запустите программу - просто выведите рекурсивно сто раз на экран какое-нибудь слово передавая каждый раз в рекурсию счётчик - условие выхода =

i==100 

вы понимаете как это сделать?
сделайте.

_____________
матфак вгу и остальная классика =)

baton's picture

ну... понимаю...
вот пример рабочего кода

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 ();
}

славненько)

_________ _ _ ______
dthcbz фкн вгу and co