实验项目一：基础算法设计.docx

《算法设计与分析》实验报告
实验项目（一）基础算法设计
专业、班级

学 号

姓 名

实验时间

实验地点

指导教师

教学目标
使学生掌握“算法设计与分析”中的基本原理、基本技术和方法，提升计算机问题求解的水平。熟练掌握编程中常见问题的求解策略，培养学生对算法复杂性进行正确分析的能力。
（1）掌握编程求解问题的常用算法策略。
（2）熟练强化深入计算机求解问题的过程。
（3）增强理论结合实际能力，增强获得理论联系实际问题的能力。
（4）培养系统分析能力和团队协作能力。
一、实验目的及要求
（1）练习算法基本工具和优化技巧的使用；
（2）巩固和掌握算法的常用基本技巧。
二、实验设备（环境）及要求
使用C/C++语言，Visual Studio 2开发环境，Windows系列操作系统环境
三、成绩评定
题号
题型
能力
分值
成绩
备注
①
设计题
设计分析
10

②
设计题
设计分析
20

③
设计题
设计分析
20

④
设计题
解决问题
20

⑤
设计题
解决问题
20

⑥
报告格式
10

总成绩

四、实验内容与步骤
1、广场上有一队士兵，如果排成10列纵队，最后剩下a个人(0 a 9)如果排成
9列纵队，最后剩下b个人(0 b 8)如果排成8列纵队，最后剩下c个人(0 c
7)……如果排成2列纵队，最后剩下j个人(0 j 1)计算并输出广场上士兵的
最少可能人数，分别用蛮力法和数学建模方法求解。
提示:
数学建模方法参见“中国剩余定理”。
蛮力法：*include<iostream>using namespace std;int{
main()
int i = 19;while (true){
if
5 == 4
{
(i % 10 == 9 && i % 9 == 8 && i % 8 == 7 && i % 7 == 6 && i % 6
&& i % 4 == 3 && i % 3 == 2 && i % 2 == 1)
cout << "This number is : " << i << endl;break;
}
i++;
}
}
33 C:\WiNDOWS\system32\cmd.exe
广场上I一兵的最少有：2519请接任意健缝续一 一一

==5 &&

2、给定一个正整数n,
输出如下
“之字形，，
方阵。
1
2
6
7
15
16
28
29
3
5
8
14
17
27
30
43
4
9
13
18
26
31
42
44
10
12
19
25
32
41
45
54
11
20
24
33
40
46
53
55
21
23
34
39
47
52
56
61
22
35
38
48
51
57
60
62
36
37
49
50
58
59
63
64
选作：输入任意的两个正整数m
和n(n
n),
构造
m
n “之字形”
3 5矩阵：

1
2 6
7
12

3
5 8
11
13

4
9 10
14
15

例：8 8方阵。
为
矩阵，
以下示例

*include<iostream>using namespace std;void main()
{
int n,i,j,m,k;
int a[1][1] = {0};
cout<<"please input n:cin>>n;
k=0;〃标记
i=0,j=0;
m=1;
a[0][0]=m;
while(m<n*n)
{
switch(k)
{
case 0://向右或向下
if(i+j<n-1){
j++;
m++;
a[i][j]=m;
k=(k+1)%4;
}

else
L
m++;
a[i][j]=m;
k=(k+1)%4;
break;
case 1://向左下
while(i+1<n&&j-1>=0)
|
i++,j--;
m++;
a[i][j]=m;
k=(k+1)%4;
break;
case 2://向下或向右
if(i+j<n-1)
{i++;
m++;
a[i][j]=m;
k=(k+1)%4;
else
{j++;
m++;
a[i][j]=m;
k=(k+1)%4;
break;
case 3://向右上
while(i-1>=0&&j+1<n)
i--,j++;
m++;
a[i][j]=m;
k=(k+1)%4;
break;

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%5d",a[i][j]);
}
cout<<endl;
}

C:\WI NDOWSVsytTemd. exe

ase
input
n:8

1
2
6

15
16
28
29
3
5
8
14
17
27
30
43
4
9
13
18
26
31
42
44
ID
12
19
25
32
41
45
54
11
20
24
33
40
46
53
55
21
23
34
39
47
52
56
61
22
35
38
48
51
57
60
02
35
37
49
50
58
59
63
54
请按任意键绿续.一.

3、用1、2、3、4、5、6、7、8、9这9个数字，填入 中使等式
成立，每个数字恰好只用一次。
以下是所有的7个答案供参考：12 483 = 579.6 18297 = 534627 198
=5346、
28157 = 4396、 39186 = 7254、42138 = 5796、
48159 = 7632
*include<stdio.h>
*include<string.h>
bool go(int *, bool map[]){
while (*)
{
if (map[* % 10]) return false;
map[* % 10] = true;
* /= 10;
}return true;
}bool check(int *, int y, int z){
bool map[10];

if (z >9999) return false;
memset(map, 0, sizeof(map)); map[0] = true;
return go(*, map) && go(y, map) && go(z, map);
}
int main()
{
for (int * = 10; *<= 98; *++)
{
for (int y = 102; y<= 987; y++)
{
int z = * * y;
if (check(*, y, z)) printf("%d * %d = %d\n", *, y, z);
}}
return 0;
4、
}
四 C:\WI NDOW£\sym d.este
12 非 483
5796
IS 琳 297
5346
27 * 198
5346
25 * 157
4396
39 * 186
7254
42 * 138
5796
4S * 159
7632
请按任意键继续.，.
给定一个正整数n,计算有多少个不同的连续自然数段，其中自然数的个数至少

为2,其和恰为n。
例如，当n = 27时，有3个不同的长度大于等于2的连续自然数段的和恰为 27: 2 + 3 + 4 + 5 + 6、+87 + 9 + 10 13 + 14 而单独的 27 则不算。
*include<iostream>
*include<math.h>
using namespace std;
void Print(int a,int b,int押印连续的 a 到 b
{
while(a<b){
cout<<a<<"+";
a++;
}
cout<<b<<"="<<n<<endl;
}
void main()
{
int a,n;
double b;
cout<<"输入正整数n:";
cin>>n;

for(a=1;a<=n/2;a++)
{
b=(-1.0+sqrt(1.0-4.0*(a-a*a-2.0*n)))/2.0;
if(b==int(b)) //判断b是否为整数Print(a,b,n);
}
}
宜 'C:\SOLDER\Debu
圃人正整数n：27
2+3+4+5+6+7=27
J+9+10=27
13+14=27
Press any key to cont inue
5、一个整数nn 30可以有多种分划，分划的整数之和为n,在不区分分划出各整数的次序时，字典序递减输出n的各详细分划方案和分划总数。
例如n = 6程序输出为：
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
2 1 1 1 1
1 1 1 1 1 1
total = 11
*include <iostream>
*include <cstdio>
*include <cstring>

*include <cstdlib>
*include <cctype>
*include <cmath>
*include <algorithm>
*include <set>
*include <map>
*include <queue>
*include <stack>*include <vector>using namespace std;
int a[35],total=0,n;
void output(int m)
{
printf("%d=",n);
for(int i=1;i<=m-1;i++)
printf("%d+",a[i]);
printf("%d\n",a[m]);
total++;
return ;
}
void dfs(int k,int m)
{
int i,j;
for(i=1;i<=k/2;i++)
{
if(i>=a[m-1])
{
a[m]=i;
a[m+1]=k-i;
output(m+1);
dfs(k-i,m+1);
}
}
}
int main()
{
memset(a,0,sizeof(a));
scanf("%d",&n);dfs(n,1);
printf("total=%d\n",total);
return 0;
}