Problema Ciorilor

Problemă:

Pe n copaci așezați în cerc se află n-1 ciori, maxim una pe fiecare copac. Dându-se o configurație inițială și una finală a ciorilor și știind că la un moment dat o singură cioară poate zbura de pe copacul ei pe cel liber, să se scrie un program care să determine o secvență de zboruri pentru a ajunge la configurația finală.

Implementare:

Cod Sursa C++

// CioriCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
#define MAX 10
 
int initial[MAX];
int final[MAX];
int n;
 
int CopacLiber()
{
	int i = 0;
	while (initial[i] != 0)
		i++;
	return i;
}
 
int Copac(int c)
{
	int i = 0;
	while (initial[i] != c)
		i++;
	return i;
}
 
void Zboara(int s, int d)
{
	printf("Cioara %d zboara de pe copacul %d pe %d!\n", \
		initial[s], s + 1, d + 1);
	initial[d] = initial[s];
	initial[s] = 0;
}
 
void main()
{
	int i, k;
	cout << "n=";
	cin >> n;
	printf("Introduceti configuratia initiala (0 pt. liber): \n");
	for (i = 0; i < n; i++)
	{
		printf("initial[%d] = ", i + 1); 
		cin >> initial[i];
	}
	printf("Introduceti configuratia finala (0 pt. liber):\n");
	for(i = 0; i<n; i++)
	{
		printf("final[%d] = ", i + 1); 
		cin>>final[i];
	}
	for (i = 0; i < n;i++)
	if (final[i] && initial[i] != final[i])
	{
		if (initial[i])
		{
			k = CopacLiber();
			Zboara(i, k);
		}
		k = Copac(final[i]);
		Zboara(k, i);
	}
	system("pause");
}

Rezultat