0123训练

T1
经典的全排列问题。
这里采用递归的写法，枚举每一个数字并用vis数组标记有没有出现过，如果长度到了就输出答案并回溯。
Code:

CPP

#include<iostream>
#include<cstring>
using namespace std;
int n,f[11],s[11];
void print(int cnt){
	if(cnt>n){
		for(int i=1;i<=n;i++) cout<<s[i]<<" ";
		cout<<"\n";
		return;
	}
	for(int i=1;i<=n;i++){
		if(!f[i]){
			f[i]=1;
			s[cnt]=i;
			print(cnt+1);
			f[i]=0;
		}
	}
}
int main(){
	while(cin>>n && n){
		memset(f,0,sizeof(f));
		print(1);
	}
	return 0;
}

T2
递归找规律（好像也比较经典）。
如果苹果或盘子只有一个，那就只有一种方案，这是递归的终止条件。
如果x>y，那么就有每个盘子都放一个苹果和不放这个盘子两种情况，答案为两种情况的方案数之和；如果x<y，则无法把盘子全放满，所以可以忽略没放苹果的盘子；如果x==y，那么就有每个盘子都放一个苹果（方案数为1）和有空盘子不放两种情况，答案为两种情况的方案数之和。
按这些推理就可以写出递归函数了。
Code:

CPP

#include<iostream>
using namespace std;
int t,n,m;
int f(int x,int y){
	if(x==1 || y==1) return 1;
	if(x>y) return f(x-y,y)+f(x,y-1);
	if(x==y) return 1+f(x,y-1);
	if(x<y) return f(x,x);
}
int main(){
	cin>>t;
	while(t--){
		cin>>m>>n;
		cout<<f(m,n)<<endl;
	}
	return 0;
}

T3
极致的暴搜，完全不用脑子。
Code:

CPP

#include<iostream>
#include<cstring> 
using namespace std;
int n,arr[1001],vis[1001];
void dfs(int x){
	vis[x]++;
	if(vis[x]==2){
		cout<<x<<" ";
		return;
	}
	dfs(arr[x]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>arr[i];
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof(vis));
		dfs(i);
	}
	return 0;
}

T4
听完机房大佬的讲解后大彻大悟了。
首先，这个图形的长和宽都是

3^{n-1}

，随后，定义

l=3^{n-2}

，目前图形的左上角为

(1,1)

，则每个分型的左上角分别为

(1,1),(1+2l,1),(1,1+2l),(1+2l,1+2l),(1+l,1+l)

。当分型大小为1时，进行特判，把结果存入二维数组。
到这里我和大佬的思路还是一致的，但在递归函数中，我们需要的参数不仅是目前的分型大小，还需要目前的图形的左上角的坐标（我倾向于在函数中计算当前坐标，可能码力不足没调出来）。
Code:

CPP

#include<iostream>
#include<cmath>
using namespace std;
int n;
char G[2001][2001];
void f(int x,int y,int g){
	if(g==1){
		G[x][y]='X';
		return;
	}
	int l=pow(3,g-2);
	f(x,y,g-1);
	f(x+2*l,y,g-1);
	f(x,y+2*l,g-1);
	f(x+2*l,y+2*l,g-1);
	f(x+l,y+l,g-1);
}
int main(){
	while(cin>>n && n!=-1){
		f(1,1,n);
		for(int i=1;i<=pow(3,n-1);i++){
			for(int j=1;j<=pow(3,n-1);j++){
				if(G[i][j]!='X') cout<<" ";
				else cout<<"X";
				G[i][j]=' ';
			}
			cout<<endl;
		}
		cout<<"-\n";
	}
	return 0;
}

文章操作

相关推荐

评论

0123训练