111

· · 个人记录

1120: 递归 双色汉诺塔 题目描述 设A、B、C是3个塔座。开始时，在塔座A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着红色，偶数号圆盘着蓝色，如图所示。现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则(1)：每次只能移动1个圆盘； 规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则(3)：任何时刻都不允许将同色圆盘叠在一起； 规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C中任一塔座上。 试设计一个算法，用最少的移动次数将塔座A上的n个圆盘移到塔座B上，并仍按同样顺序叠置。 编程任务：对于给定的正整数n，编程计算最优移动方案。 输入 正整数n。 输出 若干行。每一行由一个正整数k和2个字符c1和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。 样例输入 3 样例输出 1 A B 2 A C 1 B C 3 A B 1 C A 2 C B 1 A B

include<iostream>

using namespace std; void dfs(int n,char a,char b,char c) { if(n==0) return; dfs(n-1,a,c,b); cout<<n<<" "<<a<<" "<<b<<endl; dfs(n-1,c,b,a); } int main() { int n; cin>>n; dfs(n,'A','B','C'); } 1121: 递归 集合的划分 题目描述 设ｓ是一个具有n个元素的集合，ｓ＝｛a1，a2，……，an｝，现将ｓ划分成K个满足下列条件的子集合s1，s2，……，sk ，且满足： 1．si≠φ 2．si∩sj＝φ (1≤i，j≤k i≠j) 3．s1∪s2∪s3∪…∪sk＝ｓ 则称s1，s2，……，sk是集合ｓ的一个划分。它相当于把ｓ集合中的n个元素a1 ，a2，……，an 放入k个（0<k≤n<30）无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，……，an 放入k个无标号盒子中去的划分数s(n，k)。 输入 一行两个整数n、k 输出 一行，一个整数s(n,k) 样例输入 10 6 样例输出 22827

include<iostream>

using namespace std; int n,k; int f(int p,int q) { if(q==1)return 1; else if(p<q)return 0; else return f(p-1,q-1)+q*f(p-1,q); } int main() { cin>>n>>k; cout<<f(n,k); return 0; }

1123: 递归 新汉诺塔 题目描述 设有n个大小不等的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号分别为A、B、C，这个状态称为初始状态。 现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。 移动时有如下要求： •一次只能移一个盘； •不允许把大盘移到小盘上面。 输入 第一行是状态中圆盘总数； 第二到第四行分别是初始状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号； 第五到第七行分别是目标状态中A、B、C柱上圆盘的个数和从上到下每个圆盘的编号。 输出 每行一步移动方案，格式为：move I from P to Q 最后一行输出最少的步数。 样例输入 5 3 3 2 1 2 5 4 0 1 2 3 5 4 3
1 1

样例输出 move 1 from A to B move 2 from A to C move 1 from B to C move 3 from A to B move 1 from C to B move 2 from C to A move 1 from B to C 7

include <iostream>

include <cstring>

using namespace std; int step; char s[4]={' ','A','B','C'}; int xian[64],yuan[64],n; void mov(int c,int b) { int x,l; if (b==yuan[c]) return; x=6-b-yuan[c]; for (l=c-1;l>=1;l--) mov(l,x); cout<<"move "<<c<<" from "<<s[yuan[c]]<<" to "<<s[b]<<endl; yuan[c]=b; step++;

}

int main() { cin>>n; int k,l; for (int i=1;i<=3;i++) { cin>>k; for (int j=1;j<=k;j++) { cin>>l; yuan[l]=i; } } for (int i=1;i<=3;i++) { cin>>k; for (int j=1;j<=k;j++) { cin>>l; xian[l]=i; } } for (int i=n;i>=1;i--) mov(i,xian[i]); cout<<step<<endl; return 0; }