算法与编程

实 验 报 告 班级：10083412 姓名：储飞 学号：10081235 指导老师：朱芳

第一题

一、题目：

一、题目：统计字母的使用频率

二、目的与要求

1． 目的：

通过编写程序统计字母的使用频率，培养学生综合利用C语言进行程序设计的能力，熟悉字符串的操作方法，加强函数的运用，提高软件系统分析能力和程序文档建立、归纳总结的能力。

2． 基本要求：

1）要求用C语言编程，在Visual C++环境下调试完成；

2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；

3）要求应用本课所讲授的程序设计语言知识来解决问题

三、设计方法和基本原理

1． 课题功能描述

本程序的功能，就是要统计英文字母的使用频率。

2． 问题详细描述

为统计英文字母的使用频率，输入一个不包括空格的由英文字母组成的字符串，长度不超过200个字符。统计26个英文字母的使用频率，不区分大小写。最后按使用频率从大到小输出字母（小写字母）和使用频率（出现的次数）。

3． 问题的解决方案

按照程序要求，本程序应采用模块化设计方法,设计几个功能模块。例如（仅供参考）：

l 将字符串中的大写字母转换为小写字母

l 统计输入的字符串中字母的使用频率

l 按使用频率从大到小进行排序

主函数中控制输入、函数调用和输出。

四、主要技术问题的描述

根据三的分析，主要问题在于：

1) 为统计字母的使用频率，定义一个长度为26的int数组存放所统计的各个字母的使用频率。

2) 在统计字母的使用频率时，不要使用if语句或switch语句，利用字母的ASCII码与数组元素下标之间的关系来求得。

3) 按使用频率从大到小进行排序时，建议使用指针数组更为方便。

五、创新要求

实现程序功能后，可进行创新设计：

1) 使用多文件，即主函数和各个函数分别存放在不同的.c文件中，在头文件中进行函数原型声明。

2) 读入一篇英文文档，并对其进行字母频率分析。

二、设计思路（流程图）

首先，从屏幕读取一段字母，字符数小于200。为了便于统计，先把字符串中的大写字母转换为小写字母，所以我先建立了一个转换函数，逐个判断字符串中的字符是否为大写字母，若为大写字母则转换为小写字母并通过指针赋给原字符。接下来要统计字母使用频率，根据题目要求，我使用ASCII码来统计每个字母的使用频率，我以“a——97”为基准，其他的字母通过与97相减的差来代表各自频率。最后是相应字母和频率的排序，我采用了冒泡排序，在排列频率的同时对相应频率对应的字母也进行了排序，然后输出结果。

三、程序源代码及相关说明

/*************************************************

第一题：统计字母的使用频率

班级：10083412

姓名：储飞 学号：10081235

2011.6

*************************************************/

#include<stdio.h>

/*************************************************

函数:zhuan

功能：判断字母并将大写字母转换为小写字母后返回

入口参数:字符指针

出口参数：相应的小写字母

*************************************************/

void zhuan(char *p)

{

for(;*p!='\0';p++)

if(*p>='A'&&*p<='Z')

*p+=32;

}

/*************************************************

main函数

*************************************************/

void main()

{

int a[26],i,n,c=0,j,t;

char w[200],*q,z[27]={'a','b','c','d','e','f','g','h','i','j',

'k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'},tt;

for(i=0;i<26;i++)

a[i]=0;

printf("请输入一串连续字符：");

gets(w);

zhuan(w); //调用转换函数，将大写字母转换为小写字母

q=w;

for(;*q!='\0';q++){

n=*q-97; //字母ASCII码相对‘a’(97)的大小

a[n]+=1; //各字母出现次数

}

for(i=0;i<25;i++) //使用冒泡排序对频率进行排序

for(j=0;j<25-i;j++){

if(a[j]<a[j+1]){

t=a[j+1];

a[j+1]=a[j];

a[j]=t;

tt=z[j+1]; //同时对频率对应字母进行排序

z[j+1]=z[j];

z[j]=tt;

}

}

printf("字母 频率（出现次数）\n"); //输出结果

for(i=0;i<26;i++)

printf("%c %i\n",z[i],a[i]);

}

四、实验心得

通过这次“统计字母频率”算法编程的实习，我学习并掌握了函数的调用、形参为指针或数组的传递方法以及读取文件数据的方法。但是由于在一开始没有想到好的对字母排序的方法导致了走了很多弯路，对于题目中要求的指针数组使用起来还不是很有把握，所以选择了比较保守的冒泡排序。

第二题

一、题目

题2.指示灯控制

问题描述：

N盏灯排成一排，从1到N按顺序依次编号。有N个人也从1到N依次编号。第一个人（1号）将灯全部关闭。第二个人（2号）将凡是2和2的倍数的灯打开。第三个人（3号）将凡是3和3的倍数的灯做相反的处理（如果该灯为打开的，则将它关闭；如果该灯为关闭的，则将它打开）。以后的人都和3号一样，将凡是与自己编号相同的灯，以及是自己编号倍数的灯做相反处理。请编写程序实现。要求：程序中要显示每一个人所做工作的过程，例如：当第i个人操作时，则显示将i和i的倍数的灯做相反的处理过程；当第N个人操作之后，显示灯的最后状态。（建议：采用图形法，显示每一盏灯，并为每一盏灯加边框，用不同的颜色显示开灯或关灯）。

例如：当输入N为7时；

当第一个人操作时

则输出结果为：

第1盏灯是黑的

第2盏灯是黑的

第3盏灯是黑的

第4盏灯是黑的

第5盏灯是黑的

第6盏灯是黑的

第7盏灯是黑的

当第二个人操作时

则输出结果为：

第1盏灯是黑的

第2盏灯是亮的

第3盏灯是黑的

第4盏灯是亮的

第5盏灯是黑的

第6盏灯是亮的

第7盏灯是黑的

当第三个人操作时

则输出结果为：

第1盏灯是黑的

第2盏灯是亮的

第3盏灯是亮的

第4盏灯是亮的

第5盏灯是黑的

第6盏灯是黑的

第7盏灯是黑的

? ? ?

当第七个人操作时

则输出结果为：

第1盏灯是黑的

第2盏灯是亮的

第3盏灯是亮的

第4盏灯是黑的

第5盏灯是亮的

第6盏灯是亮的

第7盏灯是亮的

二、设计思路（流程图）

我首先想的就是如何表示灯是亮的和黑的，于是我想到的用SWITCH语句，并定义当值为0时灯黑，当值为1时灯亮。但是这又产生了一个问题，如何对灯进行反操作，我采用了指针，并定义了一个一维数组来存放每盏灯的状态，这样每次改变某个数组元素的值都可以保留到下一次判断。至于如何判断对哪盏灯进行操作，我采用取余数的方法，如果余数为0，则说明该灯数为基数的倍数，则对它进行反操作，但是对于第一个人来说，他的灯全都是黑的，所以第一个人的结果不放在输出函数中输出，而是在主函数中先直接给出，而输出函数则从第二个人的结果开始判断并输出。

三、程序源代码及相关说明

/************************************************* 第二题：指示灯控制

班级：10083412

姓名：储飞 学号：10081235

2011.6

*************************************************/

#include<stdio.h>

#define N 100000 //宏定义一个值给N

/*************************************************

函数:shu

功能：对每一盏灯是否进行相反操作进行判断并输出相应状态

入口参数:字符指针

出口参数：void

*************************************************/

void shu(int *p,int n,int i) //定义形参指针

{

int j;

for(j=1;j<=n;j++,p++){

if((j%i)==0){ //判断是否对灯进行相反操作

if((*p-1)==0)

*p=0;

else

*p=1;

}

switch(*p){

case 0:printf(" 第%3i盏灯是黑的○\n",j);break;

case 1:printf(" 第%3i盏灯是亮的●\n",j);break;

default:printf("ERROR!\n");

}

}

}

/*************************************************

main函数

*************************************************/

void main()

{

int n,i,a[N],*p,c;

printf("图形含义：●——灯亮；○——灯灭\n");

printf("请输入人数n：");

scanf("%i",&n); //输入n

for(i=0;i<n;i++) //将数组a的前n个数初始化为；a数组是用来判断灯是黑还是亮的

a[i]=0;

c=0; //表明第一个人的灯都是黑的

printf("第 1个人操作时，则输出：\n\n"); //第一个人的时候灯都是黑的

for(i=1;i<=n;i++)

} { switch(c){ case 0:printf(" 第%3i盏灯是黑的○\n",i);break; case 1:printf(" 第%3i盏灯是亮的●\n",i);break; default:printf("ERROR!\n"); } } for(i=2;i<=n;i++) //从第二个人开始对灯进行操作 { printf("第%3i个人操作时，则输出：\n\n",i); shu(a,n,i); //调用输出函数 }

四、实验心得

通过这次“指示灯控制”算法编程的实习，我学习并更加熟练地掌握了函数的调用、数组及循环体的使用，在变成过程中也遇到了很多问题，在不断解决问题的过程中，我学到了更多。

第三题

一、题目

一、题目：序列小游戏

二、目的与要求

1． 目的：

（1）让学生体会到鸽巢原理（或抽屉原理）的乐趣并使学生更加系统地理解和掌握C语言的函数间参数传递方法、数组和指针的应用等编程技巧。培养学生综合利用C语言进行科学计算，使学生将所学知识转化为分析和设计简单实际问题的能力，学会查资料和工具书。

（2）提高学生建立程序文档、归纳总结的能力。

2． 基本要求：

（1）要求用C语言编程，在Visual C++环境下调试完成；

（2）要求按照程序功能分成几个功能模块来实现，各个功能模块分别使用函数来完成；

（3）要求应用本课所讲授的程序设计语言知识来解决问题.

三、设计方法和基本原理

1． 课题功能描述

任意给定5个数字，其中必定存在3个数字已经有序（或者升序，或者降序），找出这5个数字中最长的升序或降序序列。

例如：1，7，5，3，9。则{1，7，9}，{1，5，9}，{1，3，9}都是最长的升序序列；

而{7，5，3}是最长的降序序列。

再如：1，3，2，5，7。最长的升序序列为{1，3，5，7}和{1，2，5，7}。

2． 问题的解决方案：

自动生成各种可能的序列，对于5个数字所有可能的序列为： {0,1,2,3}、{0,1,2,4}、{0,1,3,4}、{0,2,3,4}、{1,2,3,4}

{0,1,2}、{0,1,3}、{0,2,3}、{1,2,3}

{0,1,4}、{0,2,4}、{1,2,4}

{1,3,4}

{2,3,4}、{0,3,4}

考察各种可能的序列是否升序或是降序，若是则打印；

四、创新要求

在基本要求达到后，进行创新设计，10个数据，必定会有至少4个数据已经有序（或升序或降序），找出最长的升序或降序序列。

二、设计思路（流程图）

一开始，我想定义一个数组，然后对数组中每位数字的大小进行比较，并统计出本次排列中含有几个数字，然后将结果存放到一个二维数组中的某一行，再进行下一次比较，最后将数组中包含数字最多的升序数组或降序数组输出。但在设计的时候发现这样设计的循环体很复杂，而且极易出错，所以我就采用了很死板的

方法——逐个比较，即把大于等于三个数的数组按可能的升序和降序进行比较，输出。但是输出的只是可能情况中包含数字最多的那种情况。

三、程序源代码及相关说明

/*************************************************

第三题：鸽笼原理

班级：10083412

姓名：储飞 学号：10081235

2011.6

*************************************************/

#include<stdio.h>

/*************************************************

函数:sheng

功能：将五个数字中可能的升序输出

入口参数:五个整形数

出口参数：最长升序

*************************************************/

void sheng(int a,int b,int c,int d,int e)

{

int n=5;

if(a<b&&b<c&&c<d&&d<e) //如果五个数本身成升序，则直接输出 {

printf("{%d,%d,%d,%d,%d}",a,b,c,d,e);

return;

}

if(a<b&&b<c&&c<d) //当只有四个数字存在升序时，按情况进行比较 {

printf("{%d,%d,%d,%d} ",a,b,c,d);

n=4;

}

if(a<b&&b<c&&c<e)

{

printf("{%d,%d,%d,%d} ",a,b,c,e);

n=4;

}

if(a<b&&b<d&&d<e)

{

printf("{%d,%d,%d,%d} ",a,b,d,e);

n=4;

}

if(a<c&&c<d&&d<e)

{

printf("{%d,%d,%d,%d} ",a,c,d,e);

n=4;

}

if(b<c&&c<d&&d<e)

{

printf("{%d,%d,%d,%d} ",b,c,d,e);

n=4;

}

if(n==4)return; //当有4个数字的数组时，则停止后面的比较 if(a<b&&b<c) //考虑只有三个数字的情况

{

printf("{%d,%d,%d} ",a,b,c);

n=3;

}

if(a<b&&b<d)

{

printf("{%d,%d,%d} ",a,b,d);

n=3;

}

if(a<b&&b<e)

{

printf("{%d,%d,%d} ",a,b,e);

n=3;

}

if(a<c&&c<d)

{

printf("{%d,%d,%d} ",a,c,d);

n=3;

}

if(a<c&&c<e)

{

printf("{%d,%d,%d} ",a,c,e);

n=3;

}

if(a<d&&d<e)

{

printf("{%d,%d,%d} ",a,d,e);

n=3;

}

if(b<c&&c<d)

{

printf("{%d,%d,%d} ",b,c,d);

n=3;

}

if(b<c&&c<e)

{

printf("{%d,%d,%d} ",b,c,e);

n=3;

}

if(b<d&&d<e)

{

printf("{%d,%d,%d} ",b,d,e);

n=3;

}

if(c<d&&d<e)

{

printf("{%d,%d,%d} ",c,d,e);

n=3;

}

if(n==3)return; //当有3个数字的数组时，则停止后面的比较 return;

}

/*************************************************

函数:jiang

功能：将五个数字中可能的降序输出

入口参数:五个整形数

出口参数：最长降序

*************************************************/

void jiang(int a,int b,int c,int d,int e)

{

int n=5;

if(a>b&&b>c&&c>d&&d>e) //如果五个数字本身成降序，则直接输出 {

printf("{%d,%d,%d,%d,%d}",a,b,c,d,e);

return;

}

if(a>b&&b>c&&c>d) //考虑四个数字的情况 {

printf("{%d,%d,%d,%d} ",a,b,c,d);

n=4;

}

if(a>b&&b>c&&c>e)

{

printf("{%d,%d,%d,%d} ",a,b,c,e);

n=4;

}

if(a>b&&b>d&&d>e)

{

printf("{%d,%d,%d,%d} ",a,b,d,e);

n=4;

}

if(a>c&&c>d&&d>e)

{

printf("{%d,%d,%d,%d} ",a,c,d,e);

n=4;

}

if(b>c&&c>d&&d>e)

{

printf("{%d,%d,%d,%d} ",b,c,d,e);

n=4;

}

if(n==4)return; //当有4个数字的数组时，则停止后面的比较 if(a>b&&b>c) //考虑三个数字的情况 {

printf("{%d,%d,%d} ",a,b,c);

n=3;

}

if(a>b&&b>d)

{

printf("{%d,%d,%d} ",a,b,d);

n=3;

}

if(a>b&&b>e)

{

printf("{%d,%d,%d} ",a,b,e);

n=3;

}

if(a>c&&c>d)

{

printf("{%d,%d,%d} ",a,c,d);

n=3;

}

if(a>c&&c>e)

{

printf("{%d,%d,%d} ",a,c,e);

n=3;

}

if(a>d&&d>e)

{

printf("{%d,%d,%d} ",a,d,e);

n=3;

}

if(b>c&&c>d)

{

printf("{%d,%d,%d} ",b,c,d);

n=3;

}

if(b>c&&c>e)

{

printf("{%d,%d,%d} ",b,c,e);

n=3;

}

if(b>d&&d>e)

{

printf("{%d,%d,%d} ",b,d,e);

n=3;

}

if(c>d&&d>e)

{

printf("{%d,%d,%d} ",c,d,e);

n=3;

}

if(n==3)return; //当有3个数字的数组时，则停止后面的比较 return;

}

/*************************************************

main函数

*************************************************/

void main()

{

int a,b,c,d,e;

printf("请输入五个不相同的整数，逗号隔开\n"); //输入五个数据

scanf("%d,%d,%d,%d,%d",&a,&b,&c,&d,&e); printf("最长升序序列为：");

sheng(a,b,c,d,e); //调用升序排列函数 printf("\n");

printf("最长降序序列为：");

jiang(a,b,c,d,e); //调用降序排列函数 printf("\n");

}

四、实验心得

由于想不出好的办法，用了很死板的方法，造成了程序的冗长。

第四题

一、题目

题7. 约瑟夫问题

[基本要求]

有1至 N编号的N 个人按顺时针方向围坐一圈，每人持有一个密码（正整数），一开始以正整数m作为报数上限值，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的报数上限值，从他的顺时针方向上的下一个人开始重新报数，如此下去，直至所有的人全部出列为止，要求产生记录出列顺序的表。如N = 7，每个人的密码依次是：3，1，7，2，4，8，4，m的值为20，则出列顺序为6，1，4，7，2，3，5。所有人用一个循环单链表表示，表中每个结点代表一个人，按出列次序依次将结点从循环单链表中删除，并按顺序存放在一个单链表中，链表的每个结点包括三个字段：code代表密码，no代表人的编号，link是指向下一个结点的指针。在主函数中，用堆分配的方法建立Josephus对象。循环展开对问题的求解。

扩展：在n个人的Josephus问题中，如果事先知道每个人的密码，求处于哪个位置，获胜的概率最大？

二、设计思路（流程图）

定义结构体，根据题意建立链表，再定义两个结构体指针，在报到密码所指的人时就将他排除，然后再次循环执行前面的行为直到所有人都排除为止。

三、程序源代码及相关说明

/*************************************************

第七题：约瑟夫问题

班级：10083412

姓名：储飞 学号：10081235

2011.6

*************************************************/

#include<stdio.h>

#define N 10000 //宏定义人数

typedef struct Student //定义结构变量,用typedef简化一些复杂的类型声明 {

int mima;

int no;

struct Student* next;

}cir;

void main()

{

int m,n,i,j;

cir s[N],*p,*q; //定义数组和结构体指针 printf("请输入总人数n:\n");

scanf("%d",&n);

for(i=0;i<n;i++)

{

printf("请输入第%d个人的密码:\n",i+1);

scanf("%d",&s[i].mima);

s[i].no=i+1; //学生编号从1开始

s[i].next=&s[i+1]; //指向下一个节点

}

s[n-1].next=&s[0]; //最后一个指向第一个节点 printf("请输入m值:\n");

scanf("%d",&m);

p=q=&s[0]; //指针指向第一个节点

printf("则出列顺序为:");

for(i=0;i<n;i++)

{

for(j=1;j<m;j++) //从1报数到m

{

p=q;

q=q->next;

}

printf("%d ",q->no); //输出此人序号

m=q->mima; //将他的密码赋给m

p->next=q->next; //将此人从队伍中去除

q=q->next;

}

}

四、实验心得

通过本题，自学了一下链表的相关知识，已经可以掌握一点基本的使用方法了，希望可以有进一步的探索。