算法设计(第12章)

以八、 /* 以八、十六进制输出 */
} ???? 是对应的带符号短整数。 输出结果是八进制整数 十六进制整数
2
3.9 计算某个表达式的值。 通用程序清单如下： stdio.h” #include ”stdio.h stdio.h void main() { ?????? x; 计算表达式值存入x x=( 表达式 )；/* 计算表达式值存入x */ printf(”% printf( %？\n”,x); ,x); } ?????? 表达式对应的数据类型符(需事先判断) ？ 表达式为整型，则为d 表达式为实型，则为f 3
第七章习题答疑（二）
折半查找法在排序数组中查找某个数。 上课时已有提示。 7.13 字符串连接(b[]中字符串连接到a[]中字符串后) 设：a[10]=”12 ,b[]=”abc 12”, abc” 12 abc (1)找到a串的’\0’的下标（i=2） ’ (2)j=0; 当型循环（b[j]!=’\0’） ’\ ’ a[i]=b[j],i++,j++ (3)a[i]=’\0’ \ 7.15 字符串复制(b[]中字符串复制到a[]中) 设：a[10]=”12”,b[]=”abc” (1)i=0; 当型循环（b[i]!=’\0’） a[i]=b[i],i++ (2)a[i]=’\0’ 7.9
18
第十章习题答疑（一）
输入3个整数，按照由小到大顺序输出。 int x,y,z,*px=&x,*py=&y,*pz=&x; 用以前的程序，其中的x、y、z换成*px、*py、*pz 10.3 输入10个整数存入一维数组a[10]，将其中最小数与第1 个数交换，最大数与最后一个数交换。 要求编3个函数： 10 10 输入10个整数、交换、输出交换后的10个整数。 输入函数： void in(int *p,int n) 输出函数： void out(int *p,int n) 交换函数： void change(int *p,int n) 其中寻找最大最小数的方法： int *q,*max,*min; for (max=min=p,q=p+1;q<p+n;q++) { if(*max<*q) max=q; if(*min>*q) min=q; } 19 交换的方法：*p和*min，*(p+n-1)和*max 10.1

开课院系
信息科学技术学院
通选课领域
是否属于艺术与美育
否
平台课性质
平台课类型
授课语言
中文
教材
《计算概论》（第2版）,许卓群、李文新、罗英伟、汪小林,清华大学出版社,2009,2；
《程序设计基础（第2版）》,吴文虎,清华大学出版社,2005,
参考书
2；
教学大纲
本课程是所有新入学的本科一年级学生学习计算机科学与技术的第一门课程。本课程总括了计算机学科的知识体系，是计算机学科的入门基础。通过本课程的学习，不但可以使学生掌握计算机的基本工作原理以及程序设计的基本原理和方法，为后续课程的学习创造条件；而且可以让学生真正理解计算的本质，提高学生的抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
操作系统的功能和作用，文件系统的概念和使用。
第8章 程序设计 - 入门篇（课堂讲授4学时）
程序设计的要素和过程，高级程序设计语言的特点，C语言程序示例及程序规范。
第9章 程序设计 - 基本框架（课堂讲授6学时，习题课2学时）
变量、常量、数据类型和表达式；指令流的控制；控制台输入和输出。
第10章 程序设计 - 数组和结构（课堂讲授8学时，习题课2学时）
本课程课时安排为5学时/周，共90学时，包括课堂教授和上机，不同的教学班级，可以根据实际的需要适当调整课堂讲授和上机的学时分配。课程教学的环节包括：教师课堂讲授，学生在线实践及教师、助教现场辅导，学生利用网络课件和网络资源自学，学生课后作业和小组合作，教师、助教网络答疑和网络讨论等。作为计算机基础教育的第一门课程，我们尤其注重实验教学内容的改革和建设，强调学生真正动手编程训练。除了传统的教学方式方法之外，我们尤其注重实践能力和创新能力的培养，设计了多种有特色的教学方法和教学手段，包括在线实践、多层次的教学辅导、在线考试、与大学生程序设计竞赛相结合、定期的教学交流与讨论等。

比较对象，若 k 与中间元素相等，则查找成功；若 k 小于中间元素，则在中间元
算 法 设
计
素的左半区继续查找；若 k 大于中间记录，则在中间元素的右半区继续查找。不
与 分
析
断重复上述过程，直到查找成功，或查找区间为空，查找失败。
（ 第
版 ）
k
清 华
大
学
[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] （mid=(1+n)/2）
Page 4
3
7.1.2 一个简单的例子——俄式乘法
【问题】俄式乘法（russian multiplication）用来计算两个正整数 n 和 m 的乘积
，运算规则：如果 n 是偶数，计算 n/2×2m；如果 n 是奇数，计算(n-1)/2×2m＋
m；当 n 等于 1 时，返回 m 的值。
算
法
俄式乘法的优点？
与 分 析
2. 测试查找区间［low，high］是否存在，若不存在，则查找失败，返回 0；
（ 第
3. 取中间点 mid = (low+high)/2; 比较 k 与 rmid，有以下三种情况：
版 ）
3.1 若 k < rmid，则 high = mid - 1；查找在左半区进行，转步骤2；
清 华
3.2 若 k > rmid，则 low = mid + 1；查找在右半区进行，转步骤2；
Page 12
7.2.2 选择问题
【想法】假定轴值的最终位置是 s，则： （1）若 k=s，则 rs 就是第 k 小元素； （2）若 k<s，则第 k 小元素一定在序列 r1 ~ rs-1 中； （3）若 k>s，则第 k 小元素一定在序列 rs+1 ~ rn 中。

9
How to Study Algorithm？
“Sometimes we have experiences, and sometimes not. Therefore, the better way is to learn more."
10
1.1 算法与程序
算法：是满足下述性质的指令序列。
输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行 每条指令的时间也有限。
1） 第一种解法：
输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[ ],m[ ],s[ ] 1. void chicken_question(int n,int &k,int g[ ],int m[ ],int s[ ]) 2. { int a,b,c; 4. k = 0; 5. for (a=0;a<=n;a++) 6. for (b=0;b<=n;b++) 7. for (c=0;c<=n;c++) { 8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. }}}
矩阵。
数组 T：表示售货员的路线，依次存放旅行路线中的城 市编号。
售货员的每一条路线，对应于城市编号的一个排列。
n 个城市共有 n! 个排列，采用穷举法逐一计算每一条路线的费 用，从中找出费用最小的路线，便可求出问题的解。