寒假程序设计与算法设计训练补充练习：求解递归函数

例题1：POJ1664 放苹果

POJ1664 放苹果

我的AC代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define LL long long

LL schemes(int m, int n) {
	if (0 == m || 1 == n)
		return 1;
	if (n > m)
		return schemes(m, m);
	else
		return schemes(m - n, n) + schemes(m, n - 1);
}

int main() {
	int t, m, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d %d", &m, &n);
		printf("%lld\n", schemes(m, n));
	}
	return 0;
}

第二篇：求解递归数据

例题2：POJ 2013 Symmetric Order

POJ 2013 Symmetric Order

我的AC代码1：借助栈与队列

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

int main() {
	int n, kase = 1;
	while (cin >> n && n) {
		stack<string> nameStack;
		queue<string> nameQueue;
		for (int i = 0; i < n; ++i) {
			string name;
			cin >> name;
			if (i & 1)
				nameStack.push(name);
			else
				nameQueue.push(name);
		}
		cout << "SET " << kase++ << endl;
		while (!nameQueue.empty()) {
			cout << nameQueue.front() << endl;
			nameQueue.pop();
		}
		while (!nameStack.empty()) {
			cout << nameStack.top() << endl;
			nameStack.pop();
		}
	}
	return 0;
}

例题3：POJ 2083 Fractal

POJ 2083 Fractal

我的AC代码：

#include <iostream>
#include <cstring>
using namespace std;

char mp[731][731];
int a[8] = { 0, 1, 3, 9, 27, 81, 243, 729 };
void getMaze(int n, int x, int y) {
	if (1 == n) {
		mp[x][y] = 'X';
		return;
	}
	else {
		getMaze(n - 1, x, y);// 左上角
		getMaze(n - 1, x + a[n - 1], y + a[n - 1]);// 中间
		getMaze(n - 1, x + 2 * a[n - 1], y);// 右上角
		getMaze(n - 1, x, y + 2 * a[n - 1]);// 左下角
		getMaze(n - 1, x + 2 * a[n - 1], y + 2 * a[n - 1]);// 右下角
	}
}

int main() {
	int n;
	while (cin >> n && -1 != n) {
		for (int i = 0; i < 731; ++i)
			for (int j = 0; j < 731; ++j)
				mp[i][j] = ' ';
		getMaze(n, 1, 1);
		for (int i = 1; i <= a[n]; ++i) {
			for (int j = 1; j <= a[n]; ++j)
				cout << mp[i][j];
			cout << endl;
		}
		cout << "-" << endl;
	}
	return 0;
}