学步园

1. 全排列

思路1：递归分治（基于交换）

#include <stdio.h>

void perm(int* a, int start, int end);
void swap(int& m, int& n);
void output(const int* a, int size);

int main() {
	int a[5] = {1, 2, 3, 4, 5};
	perm(a, 0, 5);
	return 0;
}

void perm(int* a, int start, int end) {
	if(start == end - 1) {
		output(a, end);
	} else {
		for(int i = start; i < end; ++i) {
			swap(a[start], a[i]);
			perm(a, start + 1, end);
			swap(a[start], a[i]);	
		}
	}
}

void swap(int& m, int& n) {
	int t = m;
	m = n;
	n = t;
}

void output(const int* a, int size) {
	static int count;
	printf("%3d: ", ++count);
	for(int i = 0; i < size; ++i) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

思路2：剪枝回溯

#include <stdio.h> 

void perm(int* data, int* buf, int start, int end);
void output(const int* a, int size);

int main() {
	int data[5] = {1, 2, 3, 4, 5};
	int buf[5] = {0};
	perm(data, buf, 0, 5);
	return 0;
}

void perm(int* data, int* buf, int start, int end) {
	if(start == end) {
		output(buf, end);
	} else {
		for(int i = 0; i < end; i++) {
			if(!data[i]) continue;

			buf[start] = data[i];
			data[i] = 0;
			perm(data, buf, start + 1, end);
			data[i] = buf[start];
		}
	}
}

void output(const int* a, int size) {
	static int count;
	printf("%3d: ", ++count);
	for(int i = 0; i < size; ++i) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

2. 汉诺塔

#include <stdio.h>

void hanoi(int n, char a, char b, char c);
void move(int n, char from, char to);

int main() {
	hanoi(5, 'A', 'B', 'C');
	return 0;
}

void hanoi(int n, char a, char b, char c) {
	if(n > 0) {
		hanoi(n - 1, a, c, b);
		move(n, a, b);
		hanoi(n - 1, c, b, a);
	}
}

void move(int n, char from, char to) {
	static int step;
	printf("Step %3d: No.%d %c -> %c.\n", ++step, n, from, to);
}