ACAG 0x02-8 非递归实现组合型枚举

之所以专门来写这道题的博客，是因为感觉从最根本处了解到了递归的机器实现。

主要的就是两个指令——Call和Ret。

Call指令会将返回地址入栈（系统栈），然后跳转到$address$位置的语句。

Ret指令就是返回指令(Return)，将返回地址出栈，并跳转到该位置继续执行。

综上，就可以得到组合型枚举的非递归实现了。

#include<bits/stdc++.h>

using namespace std;

int n,m,top,address;

int sta[100010];

vector <int> v;

void Call(int x,int ret_addr) {

	int old_top=top;

	sta[++top]=x;

	sta[++top]=ret_addr;

	sta[++top]=old_top;

	return;

}

int Ret() {

	int ret_addr=sta[top-1];

	top=sta[top];

	return ret_addr;

}

void Recursive() {

	Call(1,0);

	while(top)  {

		int x=sta[top-2];

		switch(address) {

			case 0:

				if(v.size()>m||v.size()+(n-x+1)<m) {

					address=Ret();

					continue;

				}

				if(x==n+1) {

					for(int i=0;i<v.size();i++) {

						printf("%d ",v[i]);

					}

					printf("\n");

					address=Ret();

					continue;

				}

				v.push_back(x);

				Call(x+1,1);

				address=0;

				continue;

			case 1:

				v.pop_back();

				Call(x+1,2);

				address=0;

				continue;

			case 2:

				address=Ret();

				continue;

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	Recursive();

	return 0;

}

巴特西

ACAG 0x02-8 非递归实现组合型枚举

ACAG 0x02-8 非递归实现组合型枚举

最新文章

热门文章