杭电短学期：算法与编程.doc

1.指示灯控制一.问题描述： N盏灯排成一排，从1到N按顺序依次编号。有N个人也从1到N依次编号。第一个人（1号）将灯全部关闭。第二个人（2号）将凡是2和2的倍数的灯打开。第三个人（3号）将凡是3和3的倍数的灯做相反的处理（如果该灯为打开的，则将它关闭；如果该灯为关闭的，则将它打开）。以后的人都和3号一样，将凡是与自己编号相同的灯，以及是自己编号倍数的灯做相反处理。请编写程序实现。要求：程序中要显示每一个人所做工作的过程，例如：当第i个人操作时，则显示将i和i的倍数的灯做相反的处理过程；当第N个人操作之后，显示灯的最后状态。（建议：采用图形法，显示每一盏灯，并为每一盏灯加边框，用不同的颜色显示开灯或关灯）。 二.功能描述：实现对路灯的控制三.解决方案（流程图）先定义一个函数来实现对指示灯的控制，该函数用到了for循环语句，取余（因为跟倍数有关），还有if语句，定义一个指针*light来存放灯亮灭的情况，并为其分配动态内存。最后在主函数中进行函数调用来完成编程。四.主要函数描述colloc 动态内存分配函数 可分配连续的存储空间free 释放动态分配函数存储空间5. 主要技术问题程序代码#include#includeint main(void) int i,N,*light; void on_off(int n,int k,int p); printf(Enter N:); scanf(%d,&N); if(light=(int *)calloc(N,sizeof(int)=NULL) printf(Not able to allocate memory.n); exit(0); /如果light=0则说明无法分配内存空间，退出 for(i=0;iN;i+) lighti=1;for(i=0;iN;i+) on_off(N,i+1,light); /调用函数on_offfree(light); /释放已分配好的内存空间return 0;void on_off(int n,int k,int p) int j; /j为循环变量 for(j=0;jn;j+) if(j+1)%k=0) pj*=-1; printf(n第%d个人:n,k); for(j=0;jn;j+) printf(第%d盏灯:,j+1); if(pj=-1) printf(黑n); else printf(亮n); 运行结果N=4时第一个人操作时第1盏灯是黑的第2盏灯是黑的第3盏灯是黑的第4盏灯是黑的第二个人操作时第1盏灯是黑的第2盏灯是亮的第3盏灯是黑的第4盏灯是亮的第三个人操作时第1盏灯是黑的第2盏灯是亮的第3盏灯是亮的第4盏灯是亮的第四个人操作时第1盏灯是黑的第2盏灯是亮的第3盏灯是亮的第4盏灯是黑的6. 结论（实验心得）该编程不是很难，用到了指针和数组，for循环和if语句，动态内存分配。编程过程中由于粗心出现了些小问题，不过很容易就检查出来了。时隔一年重新用到C语言来编程不免有些手生，但我相信凭借扎实的编程功底还是可以完成任务的。2.约瑟夫问题一、问题描述编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数， 报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。二.功能描述：游戏淘汰赛，把玩家一个一个淘汰出局。三.解决方案（流程图）为了实现上述程序功能，应以有序循环链表表示集合。为此，需要一个抽抽象数据类型：有序表。有序表的抽象数据类型定义为：ADT LinkList 数据对象：D = ai | ai ElemSet，i = 1, 2, 3, , n, n 0 数据关系：R1 = | ai-1, ai D，ai-1 ai，i = 2, 3, , n 基本操作：void create ( &tail, m, n ) / 创建循环链表操作结果：构造一个有序表并保存各节点信息void run ( &tail, m, n ) / 约瑟夫换的实现初始条件：有序表已经存在操作结果：按顺序输出出列者编号循环链表中节点的定义如下所示：typedef struct LNodeint num; /编号 int code; /密码 struct LNode *next;LNode, *LinkList;四主要技术问题程序代码#includeusing namespace std;typedef struct LNodeint num; /编号 int code; /密码 struct LNode *next;LNode;void create(LNode *&tail, int m, int n) LNode *p, *q; /辅助节点 LNode *head; /头结点 if(n 1) /人数异常, 退出程序 cout Number error! endl; exit(1); if(n = 1) cout 1 = 2 时head = new LNode;p = head;p - num = 1;cin p -code; /输入第一个密码for(int i = 2; i next = q; q - num = i; /写入编号 cin q - code; /输入其余的密码 p = q; /p指向已建链表的最后一个节点 tail = p;tail - next = head; /建立循环链表 void run(LNode *&tail, int m, int n)LNode *p, *q; /辅助节点p = tail;for(int i = 1 ; i = n; i+)for(int j = 1; j next;q = p - next; /q指向出列者cout num; /输出出列者的编号 i n ? cout : cout code; /更新报数上限 p - next = q - next; /p指向出列者的下一人delete q; /删除出列者节点 int main()LNode *tt; /尾节点int m; /报数上限 int n; /人数cout n;cout m;create(tt, m, n);run(tt, m, n);return 0;运行结果：Input the number of people：7Input the first code:203 1 7 2 4 8 46 1 4 7 2 3 5五结论（实验心得）1、 当输入人数为1时，程序出现了意想不到的错误，在程序中加入对非法数据和边缘数据的处理。2、 第一组数据输出正确的出列顺序，但第二组却输出了错误的出列顺序，发现是在对m mod n上当结果为0时没有特殊处理，在程序把这个加速操作删去。3、原来程序是使用全局变量的，但是全局变量不安全，全部改为局部变量。这样一修改后，发现程序在传指针的时候程序崩溃了，想了很久没想到什么原因。后来改成用传引用后程序就能顺利运行，并成为最终这个程序。再后来的时候突然想到了原因，在传指针的时候函数要用指向指针的指针作为形参。 做这个程序是想挑战一下自己的，没想到出了这么多问题，当时很头疼，不过最后还是耐心一个一个的把错误找了出来，这是编的最后一个程序，完成了，很开心。3.处理文件：通信录一.问题描述： 从键盘读入姓名，电话号码和住宅地址，人数要10人以上。输入的符号由英文字母、数字及中文构成。将它们写入一个文件。如果这个文件不存在，就写入新文件。如果文件已存在，就将它们写入该文件。程序可添加新的姓名、电话号码和住宅地址。二.功能描述：对文件进行灵活操作三.解决方案（流程图）（1）如果没有文件名，要求用户输入。（2）打开文件并显示文件的内容（3）将字符串写入文本文件（4）从文本文件读取字符串（5）更新文件的内容四.主要函数描述struct 定义一个结构体存放姓名住址和电话FILE*fp 打开文件fclose 关闭文件五主要技术问题程序代码#include#includestruct tx char name100;char address100;char tel100;void main() FILE*fp; int n;struct tx x;if(fp=fopen(a.txt,w)=NULL)printf(不能打开文件a.txt!);exit(0);printf(人数n=);scanf(%d,&n);while(n0)scanf(%s %s %s,,x.address,x.tel);fprintf(fp,%s %s %sn,,x.address,x.tel);n-;六结论（实验心得）对文件的处理，还是比较得心应手的，不过创新的部分就有点无从下手了。总体不难，用到了结构体。4.单词开头大写一.问题描述：输入一个由多个英文单词组成的句子，两个单词之间包括空格或标点符号，长度不超过200个字符。最后输出这个英文句子使句中每个单词开头第一个字母大写，其他不变。2. 功能描述：从一个英语句子中找出单词，并把单词的首字母变成大写。3. 解决方案（流程图）先判断空格和标点符号的出现，利用空格和标点符号区分单词。然后对字母大小写进行代替。四.主要技术问题程序代码#includevoid main()char a200,*p;printf(Please input a string:n);gets(a);p=a;if(*p=a&*pz|*pZ|