夏季计算机编程实训题

1、上海大学计算机学院 夏季学期 计算机编程实训上海大学 计算机学院夏季学期计算机编程实训题2012年6月25可信计算与软件工程研究室目 录1. 基础题11.1 数据构造及其基本操作11.1.1 动态数组11.1.2 文件11.1.3 结构体21.2 链表及应用41.2.1 阅读并完成单向链表程序41.2.2 单向链表综合程序设计41.2.3 josephus问题52. 规范题62.1 最大公约数和最小公倍数62.2 指数函数值72.3 圆盘找数82.4 回文串92.5 单向链表92.6 正读反写112.7 字符串交换112.8 数组排序122.9 航空售票系统132.10 鞍点152.11 螺旋

2、方阵162.12 三角形个数172.13 水仙花数182.14 统计字符数字空格和其它字符个数192.15 完全数192.16 24点202.17 logistic映射中的周期点212.18 验证3n+1问题222.19 newton迭代法解方程232.20 计算若干个整数的和241. 基础题通过本节基础题的训练，使学生进一步掌握c程序设计的数组、指针、链表和文件操作。所涉及的语法主要包括：c语言中数组、指针、函数、结构体、链表、文件。1.1 数据构造及其基本操作1.1.1 动态数组练习1.1 随机产生n个50100之间的整数，输出其中与平均值最接近的元素的值及下标。【要求】定义函数原型如下的

3、功能函数，并在main函数中调用这些函数测试其功能，源程序文件名为“学号_01.c”。 调用calloc或malloc函数创建动态数组，free释放动态数组说明：标准c语言中，在定义数组时，数组元素个数必须为常量（即在编译时能确定的值）。而本题中的n为变量，是在程序运行时确定的，为了“既不浪费内存空间，又没有最大处理能力的限制”，应采用动态数组（相关标准函数原型在头文件<stdlib.h>中声明）。 void getdata(int *a, int n);功能：设置具有n个元素的数组a的各个元素值，要求元素值取自50至100之间的随机整数（提示：为了获得随机性更好的随机数，请用语句

4、srand(time(null);设置随机数发生器的种子，然后调用原型为int rand();的函数，它产生0rand_max之间的随机整数。需要包含头文件<stdlib.h>和<time.h>）。 void display(int *a, int n);功能：输出数组a的所有元素。 double getaverage(int *a, int n);功能：计算并返回包含n个元素的数组a的平均值。 int getindex1(int *a, int n, double x);功能：获取与x的值最接近的数组元素的最小下标值。 int getindex2(int *a, in

5、t n, double x);功能：获取与x的值最接近的数组元素的最大下标值。1.1.2 文件练习1.2 在文本文件records.txt中已存储学生信息(学生人数不超过n，可以认为#define n 60)，包括学号、姓名、身高三个数据项（数据项之间用字符't'分隔，姓名中可能含有空格字符，每位学生的数据占一行），要求编程从文件中获取学生的学号和身高数据后，按身高从低到高的顺序排序，并输出排序后的学号、姓名、身高表。【要求】首先用windows系统的“记事本”或其他文本编辑软件编辑records.txt文件，每行为学号（整数或数码字符串）、't'、姓名（不超过

6、8个字符）、't'、身高（浮点型数据）、'n'。然后编写程序：定义函数原型如下的功能函数，并在main函数中调用这些函数测试其功能，源程序文件名为“学号_02.c”。 char *fgetline(file *fp, char *str, int n, char delim);功能：从文件fp中读取字符串存入str，读取的字符数不超过n，或遇到delim指定的字符为止，并将该字符换成串结束标志字符。函数返回所读到的字符串，若直接遇到文件结束则返回空地址（null）。 int getrecs(char *filename, struct students *s,

7、int n);功能：从字符串filename为文件名所联系的文件中读取数据到结构体数组s中，最多读取n个元素，返回实际读取的元素个数。 void sort(struct students *s, int n);功能：对结构体数组s按身高从低到高排序。 void display(struct students *s, int n);功能：输出结构体数组s中所有元素的所有数据成员的值。1.1.3 结构体练习1.3 已知头文件seqlist.h给出学生信息顺序表的类型定义和基本函数原型（用于函数声明）；程序文件seqlist.c中给出基本函数定义。(1) 顺序表类型定义typedef struct

8、int id;/* 学号 */char name9;/* 姓名 */double height;/* 身高 */int sex;/* 性别，0为男生，1为女生 */ datatype;#define max 100typedef struct datatype datamax;/* 存放顺序表元素的数组 */int last;/* 表示data中实际存放元素个数 */ seqlist;(2) 基本操作函数的函数原型void initlist(seqlist *lp);/*置一个空表*/void createlist(seqlist *lp);/*建一个学生顺序表*/void sort_id(s

9、eqlist *lp);/*按学号排序*/void error(char *s);/*自定义错误处理函数*/void printlist(seqlist *lp);/*输出学生表*/void save(seqlist *lp, char *strname);/*保存学生顺序表到指定文件*/(3) 要求 阅读源代码文件seqlist.h和seqlist.c（见电子文档），理解顺序表类型seqlist和基本操作函数。 采用多文件结构，另外编写一个程序（文件名为“学号_03.c”），并将seqlist.h和seqlist.c移植到本程序中，完成如下测试：l 从给定的学生信息文件records.txt

10、中读取数据，创建一个包含学生学号、姓名（姓名中可能含有空格字符）、身高、性别的学生信息表；输出学生信息到屏幕；l 对已建立的学生身高信息表按学号从小到大排序，并把结果写入到数据文件中（results.txt）；l 从键盘输入一位学生的相关信息插入到已排序的学生身高信息表中后仍然保持学号的有序性；l 对新的学生身高信息表进行倒置，结果输出在屏幕；l 从键盘输入一个身高值，统计与该身高相同的学生个数并输出在屏幕；l 将原学生表拆分为男生身高信息表和女生身高信息表，分别输出在屏幕上。在程序文件“学号_03.c”需再定义以下5个功能函数：(1) int pause(char *prompt)print

11、f("%s", prompt);return getch();功能：以字符串prompt为提示信息输出，等待用户按任意键，并返回所按键的扫描码（注：getch函数并非标准c语言的函数，一般在windows系列操作系统中的c语言集成开发环境都提供该函数，其原型在<conio.h>头文件中声明）。(2) void insert(seqlist *lp, datatype x);功能：在学号从小到大排序的学生表中插入值为x的学生仍保持学号的有序性。(3) void reverse(seqlist *lp);功能：对lp指向的顺序表进行倒置操作。(4) int coun

12、t(seqlist *lp，double y);功能：统计学生表中身高值为y的学生数并返回。(5) void split(seqlist *lp, seqlist *lpm, seqlist *lpfm);功能：对原lp学生表拆分成男生身高表lpm与女生身高表lpfm。1.2 链表及应用1.2.1 阅读并完成单向链表程序练习2.1 给定程序文件linklist.h和linklist.c及file4.c并将它们按mingw developer studio集成开发环境组织成工程文件ex_04.msp。请阅读、分析程序，并完成file4.c文件中待完成的3个函数的定义（要求将文件名“file4.c

13、”改成“学号_04.c”，并修改工程文件）: int count(struct node head, double height_fm, double height_m);功能：统计head为头结点的学生链表中身高达标（女生身高、男生身高标准依次由第2、3个参数给定）人数并返回。 void split(struct node *head, struct node *hm, struct node *hfm);功能：将head为头结点的学生链表拆分成男生链表hm与女生链表hfm。 void merge(struct node *hm, struct node *hfm, struct node

14、*head);功能：将男生链表hm与女生链表hfm，合并成一条链表head。【思考问题】 头文件中应该编写什么内容，不能编写什么内容？ 头文件中#ifndef #endif的含义是什么，宏linklist_h的作用是什么？ 为什么有些函数的形式参数设计成指针，用于接收链表头结点的地址？而另一些函数却不需要传递地址，即采用单向的值传递？ 链表的增、删、改、查等函数的算法步骤描述。1.2.2 单向链表综合程序设计练习2.2 建一个带头结点的学生信息(学号、姓名、成绩)单向链表，按成绩降序排列，打印输出，并计算及格人数。#define max_size 20typedef struct studen

15、tint stunum, score;char namemax_size;struct student *next;node, *linklist;【要求】采用多文件结构（1个头文件，2个源程序文件），定义功能函数实现 初始化一个空链表； 从键盘输入数据（学号为非正数时结束），创建新结点添加到链表中； 释放所有结点； 输出所有结点的所有数据； 计算并返回链表的结点数； 计算及格（成绩不低于60分）的人数，输出及格率； 将链表分割成及格结点、不及格结点组成的两条链表； 在“学号_05.c”源程序文件中定义主函数，调用上述函数，测试其功能。1.2.3 josephus问题设计一个循环单向链表，求解

16、如下josephus问题，程序文件文件名为“学号_06.c”。有1至 n编号的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）做游戏。游戏开始时，以正整数m作为报数上限值，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将其密码作为新的报数上限值，从其下一个人开始重新报数，如此下去，直至所有的人全部出列为止。要求产生记录出列顺序的表。如n=7，m=20，每个人的密码依次是：3，1，7，2，4，8，4，则出列顺序为6，1，4，7，2，3，5。2. 规范题2.1 最大公约数和最小公倍数问题描述从输入文件中读入两个整数a，b，求最大公约数gcd(a,b)和最小公倍数

17、和lcm(a,b)。 输入输入有若干行，每行有两个整数a和b，(|a|,|b|<65536)。输入直到文件输入结束。输出对每一行测试数据，在一行上先输出“case #:”，其中“#”是测试数据的行编号（从1开始），接着在下面的两行上分别输出这两个整数的最大公约数和最小公倍数。如无最大公因数，则输出“no gcd”；如无最小公倍数，则输出“no lcm”；两组输出数据之间空一行。输入样例 6 110 06 9输出样例case 1:gcd(6,11) = 1lcm(6,11) = 66case 2:no gcdno lcmcase 3:gcd(6,9) = 3lcm(6,9) = 182.2

18、 指数函数值问题描述通过ex的无穷级数展开公式ex= 1+x+x2/2!+x3/3!+x4/4!+计算ex的值。（a）编写一个函数exp1（x），已知x，取无穷级数的前20项计算ex的近似值；（b）编写一个函数exp2（x），已知x，用无穷级数计算ex，当某项的值小于10-6时，则从1到这项之和为ex的近似值；编写程序，从文件中输入一个x值，分别调用函数exp1（x）和exp2（x），并输出ex的近似值。输入输入有若干行，每行有一个实数x，（-10.0x10.0）。输入直到文件输入结束。输出对输入中的每一个实数x，在一行上先输出“e1(x) = ”，其中x以小数点后有3位小数的形式输出，再将用

19、函数exp1（x）计算的值以四舍五入方式保留5位小数输出；同样地，在第二行上先输出“e2(x) = ”，其中x以小数点后有3位小数的形式输出，再将用函数exp2（x）计算的值以四舍五入方式保留5位小数输出。两组输出数据之间空一行。输入样例 61输出样例e1(6.000) = 403.42664e2(6.000) = 403.42871e1(1.000) = 2.71828e2(1.000) = 2.718282.3 圆盘找数问题描述如图找出3个连续数（紧挨着的3个数），它们相加和最大，再找出和数最小的3个数，试编一程序求之。输入输入的第一行有一个整数n，表示测试数据的组数。接下来有n行，每行有

20、若干个整数a1，a2，,am,（-10000a1，a2，, am 10000），他们表示一个圆盘上的m个数，（m1000）。输入直到文件输入结束。输出对输入中每一行表示的圆盘，在一行上先输出“case #:”，其中“#”是测试数据的行编号（从1开始），接着在下面的一行上分别输出这三个相邻数字之和中最大和与最小和，以及取得最大和与最小和对应的那三个相邻数字的第一个数的下标maxindex与minindex。注：数的下标约定从1开始编起。假如这些数不到3个，那么就无法按圆盘方式计算，此时输出“no maximal and minimal!”输入样例 220 1 8 4 13 6 10 15 2 1

21、7 3 19 7 16 8 11 14 9 12 51 -2输出样例case 1:maximum = 42, minimum = 13, maxindex = 12, minindex = 2case 2:no maximal and minimal!2.4 回文串问题描述编写一函数palindrome(char* s)用于判断任一字符串是否是回文（即顺序读与反序读一样，例如“abcba”、“121”等）。输入输入文件有多组测试数据。第一行有一个整数n，它是测试数据组数，（n10）。接下来有n行，每行至多有m个字符，（m1000）。但是，每一行末尾处的换行字符不能作为这一行的内容。输出对每一组

22、测试数据，在一行上输出你的判断结果。若是回文串，则输出“yes!”，否则输出“no！”。（主函数调用判别函数并输出判别结果）。输入样例3abcba121abca输出样例yes!yes!no!2.5 单向链表问题描述编程实现下述功能：编一函数struct node *create()，建立如下形式的单链表，并把每次读入的整数添加到链首。head100-1050 20编写一函数sort（struct node *head），按将无序单链表中的整数data成员按大到小的次序变为有序单链表。主函数调用函数create创建一个单链表，并分别输出排序前和排序后的单链表。输入输入文件有多组测试数据。第一行有

23、一个整数n，它是测试数据组数，（n20）。接下来有n行，每行至多有m个整数，（m1000），整数之间有一个或多个空格。行尾无多余空格。每一行的数据输入结束标志为换行符号。输出对每一组测试数据，先在一行上先输出“case #:”，其中“#”是测试数据的行编号（从1开始），接着的一行上输出“before sorting:”,再在接下来的行上输出排序前的单链表，每行10个结点值；然后在下面的一行上输出“after sorting:”,再在接下来的行上输出排序后的单链表，也是每行10个结点值。输入样例31 3 2 -11 2 1 012 3 4 5 67 8 9 1 2 34 5 67 28 19 0

24、输出样例case 1:before sorting:-1 2 3 1 after sorting:3 2 1 -1 case 2:before sorting:0 1 2 1 after sorting:2 1 1 0 case 3:before sorting:0 19 28 67 5 34 2 1 9 867 5 4 3 12 after sorting:67 67 34 28 19 12 9 8 5 54 3 2 1 02.6 正读反写问题描述顺序读入一串数据，让机器以相反的次序输出所有的数值。例如，读入：abcde，输出：edcba。输入输入的第1行是一个整数n，表示有n组测试数据。接

25、下来有n行，每行表示一组测试数据，这一行由一串字符串构成，字符串中允许出现空格，以回车符作为这一行的结束符。输出对每一字符串表示的数据，在一行上输出对应的逆序字符串。输入样例2abcde12输出样例edcba212.7 字符串交换问题描述交换两个不同长度的字符串指针，分别输出之。要求：用函数调用的方式来实现。主函数中定义两个字符串，然后调用交换函数。如将：x=“i am a good teacher.”与y=“hello good morning .”进行交换。输入输入的第1行是一个整数n，表示有n组测试数据。接下来是n组测试数据的描述，每一组测试数据有2行，他们均由一串字符串构成，字符串中允

26、许出现空格，以回车符作为这一行的结束符。两组测试数据之间有一个空行。输出对输入中的每一组2行测试字符串，先输出“case #:”，其中“#”是测试数据的编号（从1开始），接着按要求在下面的两行上分别输出这两个经过交换过的字符串。输入样例2i am a good teacher.hello good morning .123abcdef输出样例case 1:hello good morning .i am a good teacher.case 2:abcdef1232.8 数组排序问题描述任意给定整数n，及一组由下列公式定义的数组an：a1=25，a2=-25，ai=（ai-1*4627+ai

27、-2*3581）/100%100-50（i=3，4，n）,用选择排序法把a重整为 a1a2an ，输出结果。主函数调用排序函数，排序应尽量减少数据移动的次数。输入输入文件的每一行上有一个整数n，（1n1000），表示你要处理的这一组测试数据是由n个数组成的数组a。输出对输入中的每一个整数n，输出数组a经从小到大排序后的数组，元素之间有一个空格，尾部无多余空格。两组输出数据之间有一个空行。输入样例234输出样例-25 25-25 2 25-25 2 25 372.9 航空售票系统问题描述为一个容器为m个座位飞机的航班之每次飞行分配座位。飞机上分了2个区：吸烟区、无吸烟区，吸烟区座位数为n，无吸烟

28、区座位数为m-n。如果购票人键入了数1，那么程序就在吸烟区给他分配一个座位（座号1n）；如果键入0，程序就在无吸烟区给他分配一个座位（座号n+1m）。分配座位号按从小到大方式进行。输入输入文件中有若干测试数据。每一组测试数据的第一行是两个整数m、n，他们分别是飞机座位数与吸烟区座位数。接下来有若干行，每行有两个整数b、s。这里b=1或0，表示购票人键入的数；s=0表示购票人吸烟区满员后，购票人愿意被分配到无吸烟区的座位；当s不是0时，系统不能将座位进行调整。当b=-1时表示这一组测试数据输入结束。当一行上的两个整数m、n为0时表示文件输入结束。输出然后程序打印出该购票者所得的座号以及座位是在无

29、吸烟区还是在吸烟区。对输入中的每一组测试数据，先输出“case #:”，其中“#”是测试数据的编号（从1开始），接着按要求在下面的行上输出每个购票者的座位信息：分区与座位号。如在吸烟区，那么输出“smoking”, 如在无吸烟区，那么输出“no smocking”。系统不能把已出售座位再分配给别人。当无烟区或吸烟区满员后，信息“next flight leaves 6 hours”。输入样例10 60 11 01 10 00 11 11 01 00 11 1-1 010 40 11 01 10 00 11 11 01 00 11 1-1 00 0输出入样例case 1:no smoking:

30、1smoking: 1smoking: 2no smoking: 2no smoking: 3smoking: 3smoking: 4smoking: 5no smoking: 4smoking: 6case 2:no smoking: 1smoking: 1smoking: 2no smoking: 2no smoking: 3smoking: 3smoking: 4no smoking: 4no smoking: 5next flight leaves 6 hours2.10 鞍点问题描述给定一个n*n矩阵a。矩阵a的鞍点是一个位置（i，j），在该位置上的元素是第i行上的最大数，第j列上的

31、最小数。一个矩阵a也可能没有鞍点。你的任务是找出a的鞍点。输入输入文件的第1行是一个整数t，（1<=t<=20），表示下面有t个矩阵。接下来是t个矩阵的描述。每一个矩阵a由若干行组成，第1行上是一个正整数n, （1<=n<=100），然后有n行，每一行有n个，同一行上两个元素之间有一个或多个空格。两个矩阵描述之间空一行。输入直到文件结束。输出对输入文件中的t个矩阵，输出“yes”或“no”，如果一个矩阵a有鞍点，那么输出“yes”，否则输出“no”。输入样例251 2 3 4 56 7 8 9 1087 45 98 65 378 94 34 67 589 65 88 5

32、0 4921 24 3输出样例noyes2.11 螺旋方阵问题描述下面是一个5*5螺旋方阵。你的任务是按顺时针方向旋进的n*n螺旋方阵。1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9输入输入文件有若干行，每一行上有一个整数n，（1<=n<=100）。 输出对输入文件中的每个整数n，按n行n列的方式输出n*n螺旋方阵，行尾无空格，同一行上两个数之间空一格。两个螺旋方阵之间空一行。输入样例54输出样例1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11

33、 10 91 2 3 412 13 14 511 16 15 610 9 8 72.12 三角形个数问题描述在平面中给出了n个点。这些点任三点不共线，并且每两个点之间都有一条线相连，求三角形的数目。输入输入文件只有一行，这一行有若干个整数，相邻两个整数用一个空格隔开。每个整数n满足（1<=n<=2,000,000）。 输出输出文件有若干行。对输入文件中的每个整数n，输出一行，输出内容是三角形的数目。输入样例3 4 5输出样例14102.13 水仙花数问题描述水仙花数是一个三位数，其各位数字立方和等于数本身。例如，153是一个水仙花数，因为153=。你的任务是判断一个数n是否是水仙花

34、数。输入输入文件有若干行，每一行上有一个整数n，（1<=n<=999）。 输出输出文件有若干行。对输入文件中的每个整数n，在一行上输出“yes”或“no”，如果数n是水仙花数，那么输出“yes”，否则输出“no”。输入样例153100输出样例yesno2.14 统计字符数字空格和其它字符个数问题描述一行字符中有字符、数字、空格及其它字符。你的任务是统计这一行字符串中字符、数字、空格和其它字符的个数。输入输入文件有若干行，每一行上若干个字符组成的字符串。输出输出文件有若干行。对输入文件中的每一行字符串，在一行上输出字符、数字、空格和其它字符的个数之间空一个空格。输入样例123fe*&

35、amp;54 0934jdf *as输出样例3 9 1 24 0 1 12.15 完全数问题描述一个数n如果恰好等于它的真因子之和，那么这个数就称为完全数。例如，6是一个完全数，因为6=1+2+3。你的任务是判断一个数n是否是完全数。输入输入文件有若干行，每一行上有一个整数n，（1<=n<=65535）。 输出输出文件有若干行。对输入文件中的每个整数n，先输出数n，接着空一格后输出“yes”或“no”，如果数n是完全数，那么输出“yes”，否则输出“no”。输入样例369输出样例3 yes6 yes9 no2.16 24点问题描述给定4个不超过10的正整数a，b，c，d（为了降低难

36、度要求不改变其顺序），在其间添加括号及运算符+，-，*，/（浮点数除法）使其结果为24。输入输入数据文件中有若干行，每一行有4个正整数对应一种情形。输出对于每一种情形，要求先输出“case #: ”（其中#为序号），然后输出具体算式(有多种解法时仅需输出一种)，若不可能使计算结果为24，则输出impossible!。【附注】 4个数需要3次算术运算（从4种运算符中可重复地任选3个运算符，共有4364种情形，可用3重循环实现）；添加括号共有5种可能情形(参见下面输出样例)，其中，分别表示某种运算符(a b) c da (b c) d(a b) (c d)a (b c) da b (c d)建议将

37、运算设计成函数，利用指向函数的指针数组对自定义的add(加)，sub(减)，mul(乘)，div(除)函数进行有效地统一管理使用double (*op4)(double, double) = add, sub, mul, div; 若进一步考虑交换a，b，c，d的次序，其全排列共有4!=24种； 还可以考虑可取113之间的整数。输入样例1 2 3 45 1 5 56 8 7 52 3 4 55 5 1 55 5 5 1输出样例case 1: (1+2)+3*4 = 24case 2: 5-(1/5)*5 = 24case 3: (6*8)/(7-5) = 24case 4: 2*(3+4)+5 = 24case 5: 5*5-(1/5) = 24case 6: impossible!2.17 logistic映射中的周期点(1) 概述logistic映射是混沌学中的例子，指的是如下迭代计算其中参数。取便可以进行迭代计算。对于某些给定的参数，这个迭代过程可能收敛到一个点（即满足，该点被称为不动点，或者周期为1的点）此时称迭代的周期为1；而对于某些给