Брой 26 на Списание Инфоман
 


Национална олимпиада по информатика 2004, Задача 1.3. ЧАШИ

Уловието на задачата може да прочетете тук.

Решение

Задачата на пръв поглед може да се предефинира в граф, където всеки връх е конкретно разположение на топчетата в чашите, а ребрата са между тези върхове, между които може да се премине с едно преместване на топче. В така дефинирания граф трябва да се намери път който минава през колкото се може върхове точно по веднъж. За съжаление подобна задача в общия случай е трудно решима.

Но за нашия граф имаме много специфични ребра и затова трябва да се опитаме да решим задачата абстрахирайки се от теорията на графите. За подобни задачи е подходящо човек да намери подход, който изменя състоянието, като гарантира, че никога две състояния не се повтарят. Ако може да се докаже, че този подход преминава през всички състояния това би решило задачата за пълен брой точки. Друга удобна техника е когато за решаване на по-голямата задача се решават подобни задачи но с по-малък размер.

За решаването на задачата ще използваме рекурсивен подход, включващ две взаимно рекурсивни функции. Първата функция ще кръстим move1, а втората move2. И двете функции ще приемат по 3 параметъра, start, end и balls. Първата функция ще счита че има balls топчета в чаша с номер start и крайния резултат от нейното изпълнение ще бъде, че всички топчета ще бъдат в чаша end, като междувременно топчетата са преминали през всички възможни разположения в чашите от start до end. Обратно move2 ще счита, че всичките balls топчета са в чаша end и ще премести топчетата в чаша номер start, като междувременно те преминат всички положения в чашите от start до end.

Как работят двете функции. Очевидно за start равно на end функциите са изпълнили задачата си. move1 ще работи като редува следнитею две операции:

  1. Преместване на топче от чаша start в чаша start + 1, последвано от преместване на всичко от чаша start + 1 до чаша е end, използвайки функцията move1.
  2. Преместване на топче от чаша start в чаша end, последвано от преместване на всички топчета от чаша end до чаша start + 1, използвайки функцията move2.

Първата стъпка зависи от четността на balls. Ако е нечетно трябва да се започне от стъпка 1, в противен случай от стъпка 2. Двете операции се редуват докато свършат топчетата в чаша start. Крайния ефект е, че топчетата са преминали от чаша start в чаша end, като са преминали през всички състояния. Второто може да се докаже индуктивно, понеже в чаша start са стояли последователно брой топчета от balls до 0, като рекурсивното извикване е премествало останалите топчета по всички възможни начини по другите позиции.

Аналогично ще се дефинира функцията move2. Тя ще редува следните 2 операции.

  1. Преместване на топче от чаша end в чаша end - 1, последвано от преместване на всички топчета от чаша end - 1 до чаша start, чрез рекурсивно извикване на move2.
  2. Преместване на топче от чаша end в чаша start, последвано от преместване на всички топчета от чаша start в чаша end - 1, чрез рекурсивно извикване на move1.

Отново първата стъпка зависи от четността на balls. При нечетно трябва да се почне от стъпка 1, при четно от стъпка 2. Двете операции се редуват докато свършат топчетата в чаша end. Ефекта от изпълнението на функцията е, че всички топчета са преместени от end в start преминавайки всички възможни положения. Второто се доказва индуктивно, подобно на твърдението за move1.

Очевидно извикването на функцият move1(1, n, k), ще реши нашата задача.

Примерна реализация

#include <cstdio>

using namespace std;


const int maxm = 100000;


int moves[maxm][2];
int mc;


void move1(int start, int end, int balls);
void move2(int start, int end, int balls);


int main()
{
	int n, k, i;

	scanf("%d%d", &n, &k);
	move1(1, n, k);

	printf("%d\n", mc);
	for (i = 0; i < mc; i++)
		printf("%d %d\n", moves[i][0], moves[i][1]);

	return 0;
}

void move1(int start, int end, int balls)
{
	int i;

	if (start != end)
	{
		for (i = 1; i <= balls; i++)
		{
			if ((balls + i) % 2)
			{
				moves[mc][0] = start;
				moves[mc++][1] = end;
				move2(start + 1, end, i);
			}
			else
			{
				moves[mc][0] = start;
				moves[mc++][1] = start + 1;
				move1(start + 1, end, i);
			}
		}
	}
}

void move2(int start, int end, int balls)
{
	int i;

	if (start != end)
	{
		for (i = 1; i <= balls; i++)
		{
			if ((balls + i) % 2)
			{
				moves[mc][0] = end;
				moves[mc++][1] = start;
				move1(start, end - 1, i);
			}
			else
			{
				moves[mc][0] = end;
				moves[mc++][1] = end - 1;
				move2(start, end - 1, i);
			}
		}
	}
}

			

Автор: Иван Анев


обратно към брой 26