算法实验报告

1、算法实验报告学号_ _姓名_实验一1-1问题描述 打印以下n*n方阵1 2 3 4 5 6 7 24 25 26 27 28 29 823 40 41 42 43 30 922 39 48 49 44 31 1021 38 47 46 45 32 1120 37 36 35 34 33 1219 18 17 16 15 14 13 1-2问题分析 此方正为螺旋方阵，依次存放1到n*n个数，数依次加一，要按顺时针逐圈摆放数据，就使数形成了螺旋形。1-3策略选择用二维数组存放数字，依次摆放1到n*n个数，数依次加一，要按顺时针逐圈分别处理上方，右侧，下方，左侧的数据。1-4模型例21螺旋阵1-5时

2、间及空间复杂度时间复杂度空间复杂度1-6算法描述 124为第一圈，2540为第二圈，i为圈数的控制，下标i<=n/2，（1）i行（上方），从i列到n-i列（2）n+1-i列（右侧），从i行到n-i行（3）n+1-i行（下方），从i列到n-i列（4）i列（左侧），从n+1-i行到ni+1行当n为奇数时中间一个数没有形成圈,所以当为奇数时，要单独赋值为n*n.1-7算法实现#include<iostream>#include <iomanip>using namespace std;void main()int i,j,n,k,a100100=0;cout<&l

3、t;"请输入n:"cin>>n;k=1;for(i=1;i<=n/2;i+)/控制圈数for(j=i;j<=n-i;j+)/上方aij=k;k+;for(j=i;j<=n-i;j+)/右侧 ajn+1-i=k;k+;for(j=n+1-i;j>=i+1;j-)/下方 an+1-ij=k;k+;for(j=n+1-i;j>=i+1;j-)/左侧 aji=k;k+;if(n%2=1)/当n为奇数时中间一个数没有形成圈i=(n+1)/2;aii=n*n;for(int c=1;c<=n;c+)cout << 'n

4、'for(int d=1;d<=n;d+)cout<<setw(6)<<left<<acd<<" "/空6个字符输出1-8测试与说明输入n的值，打印n*n的螺旋矩阵如下1-9总结 对于趣味矩阵的算法实现，首先要观察矩阵的特点，还有规律，而且一般矩阵都使用二维数组。#include <iomanip>cout<<setw(6)<<left<<配合使用实验二2-1问题描述 写出计算ackermann函数ack(m.n)的递归计算函数2-2问题分析对于m>=0.n&

5、gt;=0.ack(m,n)ack(0,n)=n+1;ack(m,0)=ack(m-1,1);ack（m,n）=ack(m-1,ack(m,n-1)2-3策略选择 使用递归算法，不断调用本身实现算法，公式题目已经给出。2-4模型递归调用2-5时间及空间复杂度时间复杂度空间复杂度2-6算法描述当m=0时 返回n+1;当n=0时调用ack(m,0)=ack(m-1,1);当m！=0 &&n！=0时调用自身 ack（m,n）=ack(m-1,ack(m,n-1)2-7算法实现#include <iostream>using namespace std;int akm(in

6、t m,int n)/递归设计 int r,g; if(m=0) r=n+1; else if(n=0) r=akm(m-1,1); else g=akm(m,n-1);r=akm(m-1,g);/两次连着递归 return r; main() int a,b,c,i; while(1) printf("input two numbers a and b (a<4):"); scanf("%d %d",&a,&b); if(a<4)/ 为了防止无限进行下去 c=akm(a,b);/调用函数计算结果 printf("t

7、he result is:%d",c); else printf("输入错误/n");/输入不合法 printf("是否继续(1)yes (2)no:"); scanf("%d",&i); if(i!=1) break; 2-8测试与说明输入a和b，为了防止不断调用，限制a<4输入1继续，2退出2-9总结 更好的理解了递归思想，和使用方法，递归在很大程度上增加了程序了理解性，减少了代码量。实验三3-1问题描述狼找兔子问题：一座山周围有n个洞，顺时针编号为0,1,2,3,4，n-1。一只狼从0号洞开始，顺时针方向

8、计数，每当经过第m个洞时，就进洞找兔子。输入m，n。试问兔子有没有幸免的机会？如果有该藏在哪儿？3-2问题分析 一座山周围有n个洞，顺时针给他编号为0,1,2,3,4，n-1。从0号洞开始，顺时针方向计数，每当经过第m个洞时，问兔子有没有幸免的机会，输出洞的编号3-3策略选择使用标志位标记。n个洞，编号为0,1,2,3,4，n-1。从0号洞开始，顺时针方向计数，每当经过第m个洞时，改标志位为1。第二次到0时说明会重复这个过程，所以不用再循环，如果还有洞的标志位还有有幸免的机会，输出洞的编号3-4模型例17手拉手问题3-5时间及空间复杂度时间复杂度空间复杂度3-6算法描述n个洞，编号为0,1,2

9、,3,4，n-1。从0号洞开始，顺时针方向计数，每当经过第m个洞时，改标志位为1。第二次到0时说明会重复这个过程，所以不用再循环，如果还有洞的标志位还有有幸免的机会，输出洞的编号3-7算法实现#include<iostream>using namespace std;int main() int n,m,i,c;int flag=0; int j=0,k=0; int a50,b50; cout<<"请输入山周围的洞口总数: " cin>>n; cout<<endl<<"请输入狼每次经过洞口的个数: &q

10、uot; cin>>m; cout<<endl<<"洞口号码依次为:" for(i=0;i<n;i+) ai=i; cout<<ai<<" " cout<<endl<<endl<<"狼依次经过的洞口号码为: 0 " b0=1; c=0;while(1)c+=m;if(c>=n)c=c-n;bc=1;cout<<c<<" "if(c=0)break;for(i=0;i<n;i+)

11、if(bi!=1) cout<<endl<<"兔子有幸免的机会"<<endl; cout<<endl<<"兔子可以藏在"<<i<<"洞口中"<<endl;flag=1; if(flag=0)cout<<endl<<"兔子没有幸免的机会" return 0;3-8测试与说明输入洞口数还有每次访问的值则输出所需内容3-9总结 标志位的使用，当为多种可能时候用数组，为两种情况时，使用变量实验四4-1问题

12、描述假设有52张纸牌，现在扑克牌全正面向上，第一轮从第二张开，凡是2的倍数位置上的牌翻为反面；第二轮，凡是3的倍数的位置上，正面的翻为反面，反面翻为正面。依次递推，当翻牌的数量大于104则停止翻牌。统计最后由几张牌翻为正面，和它所对应的位置。4-2问题分析有52张纸牌，开始时扑克牌全正面向上，之后依次依次以2.3.4可以整除的数翻面，翻面超过104次的，则停止翻面，统计最后由几张牌翻为正面，和它所对应的位置。4-3策略选择使用标志位数组来记录他的正反面。4-4模型例26开灯问题4-5时间及空间复杂度时间复杂度空间复杂度4-6算法描述a52为标志位，标志位正反面，每翻过一次求反，正为1反为-1，

13、 循环外层为k2,3,4每次为k的倍数i%k=0则反面ai=-ai控制翻面次数num; ai=1时Cnum+记录为正的个数。4-7算法实现#include<iostream>#include<math.h>using namespace std;void main()int i,k,num=0,Cnum=0,a52;for(i=1;i<=52;i+)ai=1;for(k=2;k+)for(i=1;i<=52;i+)if(i%k=0)ai=-ainum+;if(num>=104)break;if(num>=104)break;for(i=1;i&l

14、t;=52;i+)if(ai=1)Cnum+;cout<<i<<" "cout<<Cnum;4-8测试与说明输出为正面的牌的编号，和他们的个数，一共有26个4-9总结num>=104控制翻面次数时，内外都需要判断，才能准确退出；用 数组作为标志位，正为1反为-1；num>=104实验五5-1问题描述 两个乒乓球队进行分组，各出三人，甲队有A B C 3人，乙队有X Y Z 3人，已经抽签决定比赛名单，有人向队员打听比赛名单，A说她不和X比，C说他不和X和Z比，请编写算法找出3对赛手的名单。5-2问题分析 此问题为信息数字化的题

15、目，根据题中的条件排除组合的可能性，将剩余的结果输出。5-3策略选择i是a的对手;j是b的对手;k是c的对手，对ijk进行赋值，是他满足，互不相同，且A说她不和X比，C说他不和X和Z比，相当于i!='X' && k!='X' && k!='Z'。5-4模型例32警察抓小偷问题5-5时间及空间复杂度时间复杂度空间复杂度5-6算法描述 首先他们的对手不能互相重叠，需要一一对应(i!=j) (i!=k && j!=k)，其次，题中给出的消息得到(i!='X' && k!='X' && k!='Z')，将组合排除，剩下为结果5-7算法实现#include <stdio.h>int main() char i,j,k; / i是a的对手;j是b的对手;k是c的对手 for (i='X'i<='Z'i+) for (j='X'j<='Z'j+) if (i!=j) for (k='X'k<='Z'k+) if (i!=k &&a