第一题：设计一个递归算法，从自然数1、2、…、m中任取k个数的所有组合

#include<iostream>
#include<vector>
using namespace std;
vector<int> putInf;//每一种可能的方案
vector<vector<int>> ans;//存储可行方案  !!!(多结果的记录）


//vector<vector<int>>&
void combination(int m,int k)//m自然数个数，k，取k个数
{
	if (m == k)
	{
		for (int i = m; i > 0; i--)
		{
			putInf.push_back(i);
		}
		ans.push_back(putInf);
		for (int i = 0; i < m; i++)
		{
			putInf.pop_back();
		}
	}
	else if (k == 0)
	{
		ans.push_back(putInf);
	}
	else
	{
		putInf.push_back(m);//选中第m个数
		combination(m - 1, k - 1);//第m个数在组合中 递归
		putInf.pop_back();//还原到结点处

		combination(m - 1, k);//第m个数不在组合中
	}	
}

int main()
{
	int m, k,j=1;//num记录共有多少种组合数
	cout << "从1~m个自然数中选择k个数，请输入吗m，k" << endl;
	cin >> m >> k;
	combination(m, k);
	cout << "共" << ans.size() << "种方案\n具体方案如下如下:\n" << endl;
	for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); it++) {
		cout << "第" << j++ << "种方案, 结果为 " << endl;
		for (int i = 0; i < it->size(); i++) {
			cout << (*it)[i]  << "  ";
		}
		cout << endl;
	}
	return 0;
}

第二题：已知Ackerman函数定义如下： (1) 写出递归算法； (2)利用栈，写出非递归算法；

 

 

//注意对于ackman函数，输出值增长速度非常快，仅是对于(4,3)的输出已大得不能准确计算
#include<iostream>
#include<stack>

using namespace std;

//递归算法  按照公式输入即可
int akm1(int m, int n)
{
	if (m == 0)
		return n + 1;
	else if (n == 0)
		return akm1(m - 1, 1);
	else
		return akm1(m - 1, akm1(m, n - 1));
}

//非递归算法 线性递归转化为非递归
//始终保持n在计算位，将m入栈
int akm2(int m, int n)
{
	stack<int> s;
	s.push(m);
	while (!s.empty())
	{
		m = s.top();
		s.pop();
		if (m == 0)//m=0,akm(m,n)=n+1
		{
			n++;
		}
		else if (n == 0)//m!=0,n=0, akm(m,n)=akm(m-1,1)
		{
			s.push(m - 1);
			n = 1;
		}
		else//m!=0, n!=0, akm(m,n)=  
		{
			s.push(m - 1);
			s.push(m);
			n--;
		}
	}
	return n;
}

int main()
{
	int m, n;
	cout << "请输入m，n" << endl;
	cin >> m >> n;
	cout << "递归算法结果为："<<akm1(m, n) << endl;
	cout << "非递归算法结果为：" << akm2(m, n) << endl;
	return 0;
}

第三题：写一个判断两个广义表相等的递归算法

 

#include<iostream>
using namespace std;

template <class Type> class GenList;
template <class Type> class GenListNode {//广义表节点定义
    friend class Genlist;
private:
    int utype;       //=0/1/2
    GenListNode <Type>* tlink;     //指向同级的下一个结点 
    union {      //联合 
        int ref;    Type value;   //utype=0，在ref计数，utype=1，在value中储存值 
        GenListNode <Type>* hlink;     //utype=2储存子表头节点 
    } info;
public:
    GenListNode() { info.utype(0), tlink(NULL), info.ref(0); }
    GenListNode(GenListNode<Type>* p)
    {
        utype = p->utype;  tlink = p->tlink;  info = p->info;
    }
};
template <class Type> class GenList {
private:
    GenListNode <Type>* first;
    bool Equal(GenListNode<Type>* s, GenListNode<Type>* t);
};

template<class Type>
bool GenList<Type>::Equal(GenListNode<Type>* s, GenListNode<Type>* t)
{
    if (s != NULL && t != NULL)//两广义表均不为空
    {
        if (s->info.ref == t->info.ref)
        {
            s = s->tlink; t = t->tlink;
            while (s != NULL && t != NULL)//依次比较
            {
                if ((s->utype == 1 && t->utype == 1 && s->info.value == t->info.value) || (s->utype == 2 && t->type == 2 && Equal(s->info.hlink, t->info.hlink)))//若储存子表，递归比较
                {
                    s = s->tlink; t = t->tlink;
                }//当前节点相等则后移
                else  return false;
            }
            if (s == NULL && t == NULL)return true;//完成全循环则相等
        }
        else return false;
    }
    else if (s == NULL && t == NULL) return true;//都为空表，相等
    else return false;//一个空一个不空，不相等
}

 

 第四题： 皇后问题：

用 n 行 n 列的矩阵表示一个国际象棋棋盘，若两个皇后位于同一行、同一列、同一对角线上（包括下图所示的各主对角线和次对角线），则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。请给出解决这个问题的递归算法。

//2021.10.31
//递归解决n皇后问题
//思路：先写出合法判断的条件，之后按照空间树求解，在节点处调用递归，注意求解后结果的保存与记录数值的还原

#include <iostream>
#include <vector>
using namespace std;
#define N 256
int n;//记录n皇后值
vector<int> putInf;//每一行皇后的置放位置情况
int used[N] = { 0 };//每一列只能有一个皇后，记录每一列的状态
vector<vector<int>> ans;//存储可行方案  !!!(多结果的记录）
int curRow = 0;//当前待放皇后的行数

bool judgeLegalPut(int& curRow, int col) {//判断在curRow行的col列放置皇后是否合法
	for (int i = curRow - 1; i >= 0; i--) {
		//在queueAssign中已经排除了皇后处于同一行及同一列的情况
		//因此在这里只需要判断皇后是否成斜线即可
		if (curRow - i == abs(col - putInf[i])) {
			//当前位置与之前的皇后处于同一斜线上
			return false;
		}
	}
	return true;
}

void queensAssign(int curRow) {//一般递归函数输入都带有记录当前进度的数
	if (curRow >= n) {//完成n行遍历，递归结束，收集结果
		ans.push_back(putInf);
		return;
	}
	//i : 当前行皇后准备放的列数
	for (int i = 0; i < n; ++i) {//curRow行i列的位置
		if (used[i]) continue;//位置被使用过，直接跳过  排除了两皇后处于同一列的情况
		if (judgeLegalPut(curRow, i)) {
			//当前位置置放与之前不冲突 将皇后加入
			used[i] = true;
			putInf.push_back(i);
			queensAssign(curRow + 1);
			//在之前的递归中，已经得到了这种情况下的完整解并储存
			//一次要把used数组与putInf还原到上一步（即空间树的上一个分叉处），以便下一个分支的求解
			used[i] = false;
			putInf.pop_back();
		}
	}
}


void printChessBoard(vector<int>& vec) {//输出模拟棋盘
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j != vec[i])
				cout << "○";
			else
				cout << "●";
		}cout << endl;
	}cout << endl;
}

int main() {
	cout << "请输入n皇后问题的规模" << endl;
	cin >> n;
	queensAssign(0);
	int j = 1;
	cout << n << "皇后问题,共"<<ans.size()<<"种方案\n具体方案如下如下:\n" << endl;
	for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end();it++) {
		cout << "第" << j++ << "种放置方案, 皇后被放于 " << endl;
		for (int i = 0; i < it->size(); i++) {
			cout << (*it)[i] + 1 << "  ";
		}cout << "列" << endl;
		cout << endl << "棋盘布局如下↓" << endl;
		printChessBoard(*it);
	}
	return 0;
}