绪论 一、教学对象 计算机科学与技术系新生(第二学期） 二、教学目标 程序设计的重要性 程序设计的基本概念与基本方法 编程解题的思路与典型方法 数学模型简介 算法及算法步骤 程序结构与相应语句 编码与上机调试

三、教学重点 绪论 1. 程序设计的基本概念，基本方法； 2.在 C语言的环境下，学会如何针对问题进行分析，得出数学模型，理出算法并编程实现； 3.有条有理有根有据的编程实践； 4.养成良好的编程风格与习惯； 5.重在思维方法的学习，鼓励创新。

绪论 四、指导思想 1. 立足改革，以培养高素质有创造精神的人才为这门课的教学目标。 2. 以学生为中心，采用与现实生活贴切和具有趣味性的实例进行讲解，有利于调动学生学习的积极性，引导学生主动学习。 3. 强化实践，这门课主张程序设计是高强度的脑力劳动，不是听会的、也不是看会的，而是练会的。引导学生在解题编程的实践中探索其中带规律性的认识。将感性认识升华到理性高度。

绪论 五、学习方法 1.动手动脑，理论指导下的实践 有条有理的实践。 2.在编写大量程序之后，才能感到运用自如。

绪论 六、教学内容安排 1. 简单C程序设计； 2. 分支结构程序设计； 3. 循环结构程序设计； 4. 数组； 5. 函数； 6. 递归及其实现方法 7. 指针； 8. 结构体与链表。

第一讲 简单的C程序设计 1.1 认识C语言程序 1.程序实例 #include <stdio.h> //预编译命令,将标准输入输出函数 //作为头文件包扩到用户源文件中 #include <math.h> //预编译命令,将系统提供的数学函数 //作为头文件包扩到用户源文件中 main( ) //主函数，名为main， { //函数体.开始 float a,b,c; //声明部分.定义变量类型 b=30.0; //执行部分.赋值语句 a=sin(b*3.14159/180); //执行部分.赋值语句 printf(“%f\n”,a); //执行部分.输出语句 } //函数体.结束

第一讲 简单的C程序设计 1.C程序结构 1.2 实例总结 预编译命令 主函数 main( ) { 函数体开始 声明部分 执行部分 } 函数体结束

第一讲 简单的C程序设计 2.变量的类型 整型：int 长整型：long 浮点型：float 双精度型：double 字符型：char 用户自定义类型

第一讲 简单的C程序设计 3.声明的作用 为变量分配内存单元，变量名作为内存单元的符号地址，这件事是在程序编译链接时完成的。 4. 变量 其值可以改变的量，是内存单元的符号地址。 通过符号b可以找到相应的存储单元地址，假设为1000。 语句 b=30.0； 是将值30.0存放在地址为1000的存储单元。

第一讲 简单的C程序设计 5.对变量的赋值 赋值符号“=” <变量>＝<表达式> b = 30.0; // 读作将表达式的值30.0赋给变量b a=sin(b*3.14159/180); // 读作将表达式（正弦函数）的值赋给变量a

第一讲 简单的C程序设计 6.变量赋值特点 （1）先定义，后使用 int d,e,f; 定义三个变量为整数类型 如未定义，则在编译时被查出，认为非法 （2）变量未被赋值前，值为未知 （3）对变量赋值过程是“覆盖”过程，用新值去替换旧 （4）读出变量的值，该变量保持不变 （5）参与表达式运算的所有变量都保持原来的值不变

第一讲 简单的C程序设计 变量赋值过程 d e f 未赋值前 执行d=7 执行 e=d 执行 f=d+e 执行 d=d+1 000 -123497 234316 7 14 8

第一讲 简单的C程序设计 7. 输出语句 printf函数（格式输出函数） 一般形式为 printf(参数1，参数2，参数3，……，参数n） 其中参数1——格式控制 参数2，参数3，……，参数n——输出表列 举例： float a; int b; a = 85.56; b = 100; printf("%f %d", a, b);

第一讲 简单的C程序设计 格式控制是用双引号括起来的字符串，称“转换控制字符串” %f —— 第一个输出表列的格式说明，以小数形式输出单、双精度实数，隐含输出6位小数 %d —— 第二个输出表列的格式说明，以带有符号的十进制形式输出整数（正数不输出符号） 显然，%f是控制实数a的；%d是控制整数b的

第一讲 简单的C程序设计 为了醒目，格式控制项中除格式说明之外可以有 普通字符 例: printf(“a=%f b=%d", a, b); 输出结果为： a=85.560000 b=100 换行符号 例: printf(“a=%f\nb=%d”,a,b); a=85.560000 b=100 域宽和精度 例：printf（”%5.3f”，a）；

第一讲 简单的C程序设计 8. 数学函数 sin(x) x为弧度，double x，double sin(x) cos(x) cos(x) exp(x) ex log(x) logex log10(x) log10x fabs(x) x fmod(x,y) 整除x/y的余数 floor(x) 求不大于x的最大整数 pow(x, y) xy sqrt(x) x1/2

第一讲 简单的C程序设计 9. 算术运算符 ＋ 加 － 减 * 乘 / 除 % 模（取余数）

第一讲 简单的C程序设计 1.3 作业

第二讲 分支结构 我们在日常生活中经常需要处理具有两个分支的问题，例 如，如果明天下雨，则在教室内组织活动，否则去野游。 在C语言中，这类问题需要使用if语句解决，而判断操 作通常使用关系运算符。 关系运算符和关系表达式 > 大于 < 小于 >= 大于等于 <= 小于等于 == 等于 != 不等于

第二讲 分支结构 2.1 掌握if语句的使用方法 【实例】编写程序，判断输入的整数是否为6，若是，显示“Right！”和“Great!”，否则显示“Wrong！”和“Sorry！”。 1．编程思路： 要显示“Right！”和“Great！”，应执行两条语句“printf(”Right！\n“);”和“printf(”Great！\n“);”，要显示“Wrong！”和“Sorry！”，执行两条语句“printf(”Wrong！ \n“);”和“printf(”Sorry！\n“);”。本题需要根据所输入的值（假设赋给a）是否为6来选择执行相应的两条语句。 在C语言中判断a中的值是否为6，使用“if(a==6)”形式。

第二讲 分支结构 本实例的流程图如图所示 开始 输入a值 a==6 显示“Right！” 显示“Great！” 显示“Wrong！” 显示“Sorry！” 结束 假 真

第二讲 分支结构 本实例的N-S流程图如图所示 输入a的值 a==6 显示“Right！” 显示“Great！” 显示“Wrong！” 显示“Sorry！ ”

第二讲 分支结构 2．程序代码： #include <stdio.h> main() { int a=0; printf("Input a:"); scanf("%d",&a); printf("a=%d\n",a); if(a==6) /* if语句开始 */ {printf("Right！\n"); printf("Great！\n"); } else {printf("Wrong！\n"); printf("Sorry！\n");} /* if语句结束 */ }

第二讲 分支结构 3．运行结果： 第1次运行结果： Input a:6<回车> a=6 Right！ Great！ 第2次运行结果： Input a:5<回车> a=5 Wrong！ Sorry！

第二讲 分支结构 4．归纳分析： （1）程序中的“a==6”是关系表达式。 用关系运算符把两个C语言表达式连接起来的表达式称为关系表达式。关系运算的判断结果只有“真”或“假”两种可能，关系成立时为“真”，不成立时为“假”。 关系表达式的值只能是1或0，当关系运算的判断结果为“真”时，关系表达式的值为 1，否则，关系表达式的值为0。例如，当a的值为6时，关系表达式“a==6”的值为1，当a的值为5时，关系表达式“a==6”的值为0。

第二讲 分支结构 （2）程序中的“if(a==6)”是if语句的开始部分。 本例题需要根据“a==6”是否为“真”来选择执行不同的两个输出语句。处理两个分支的问题时常使用if语句。if语句根据其后面括号中表达式的结果，选择执行某个分支程序段。 if语句的一般形式如下： if(表达式) { 语句组1 } else { 语句组2 } “if”和“else”是关键字。当表达式结果为“真”（即不等于0）时，执行语句组1，表达式结果为“假”（即等于0）时，执行语句组2。在语句组1和语句组2中只能选择执行一组，而后执行整个if语句后面的语句。

第二讲 分支结构 （3） C语言中允许程序中的if语句不带else部分。 省略else的if语句一般形式如下： if(表达式) {语句组} 当表达式结果为“真”时，执行语句组，表达式结果为“假”时，不处理。

第二讲 分支结构 2.2学会使用逻辑运算符 处理问题时经常需要同时判断多个条件。例如，在某学生数学和英语成绩中判断是否至少有一门课程是不及格。这时使用逻辑运算符。 逻辑运算符共有三种： && 逻辑与 || 逻辑或 ! 逻辑非 这3个运算符按高到低的优先级顺序是“!”、“&&”、“||” 一般而言，单目运算符优先级较高，赋值运算符优先级低。 算术运算符优先级较高，关系和逻辑运算符优先级较低。

第二讲 分支结构 【实例】编写程序，判断某人的体重是否在50公斤至55公斤之间，若在此范围之内，显示“Ok”，否则显示“No”。 1．编程思路： 先将体重存放在变量w中，要使w的值在50至55范围内，应同时满足“w>=50”和“w<=55”。在C语言中用“w>=50 && w<=55”表示w的值是否同时满足“w>=50”和“w<=55”。 输入体重w的值 w >=50 && w<=55 显示“Ok” 显示“No”

第二讲 分支结构 2．程序代码： #include <stdio.h> main() { float w=0.0; 2．程序代码：  #include <stdio.h> main() { float w=0.0; printf("Input w:"); scanf("%f",&w); printf("w=%.1f\n",w); if(w>=50&&w<=55) printf("Ok\n"); else printf("No\n"); }

第二讲 分支结构 3.运行结果： 第1次运行结果： Input w:53.5<回车> w=53.5 Ok 第2次运行结果： No

第二讲 分支结构 4．归纳分析： 程序中的“w>=50 && w<=55”是逻辑表达式。 用逻辑运算符把两个C语言表达式连接起来的表达式称为逻辑表达式。逻辑运算的判断结果也只有“真”或“假”两种可能，逻辑运算的规则如下： 逻辑与：1&&1=1,其它为0 逻辑或：0||0=0，其它为1 逻辑非：！0为1，！1为0，！2为0，！a为0（当a不为0时） 逻辑表达式的值也只能是1或0，当逻辑运算的判断结果为“真”时，逻辑表达式的值为 1，否则，逻辑表达式的值为0。

第二讲 分支结构 2.3 学会使用嵌套的if语句 有些问题必须在满足某种条件后，再继续分支处理。例如，某单位男职工60岁退休，女职工55岁退休，为了判断某职工是否应退休，首先要判断该职工是男职工还是女职工，然后再根据职工性别判断年龄是否到规定年龄。这时需要使用嵌套的if语句。

第二讲 分支结构 【实例】编写程序，判断若输入的体重大于0且小于200，再判断该体重是否在50公斤至55公斤之间，若在此范围之内，显示“Ok”，否则显示“No”；若所输入的体重不大于0或不小于200，则显示“Data over!”。 1．编程思路： 在上实例中，输入w的值后立刻用if语句实现选择执行“printf(“Ok\n");”或“printf("No\n");”的功能，但由于本题目是在w的值大于0且小于200的情况下，才能执行此if语句，所以在此if语句外面还需要套另一个if语句。

第二讲 分支结构 本实例的程序流程图： 课堂作业：请根据此图画出其N-S流程图。 开始 输入w值 w>0且w<200 显示“Ok” 显示“Data over！” 结束 假 真 w≥50且w≤55 显示“No”

第二讲 分支结构 2．程序代码： main() { float w=0.0; printf("Input w:"); scanf("%f",&w); printf("w=%.1f\n",w); if(w>0 && w<200) /* 外嵌if语句开始 */ if(w>=50 w<=55) /* 内嵌if语句开始 */ printf(“Ok\n"); else printf("No\n");/* 内嵌if语句结束 */ printf("Data over!\n");/* 外嵌if语句结束 */ }

第二讲 分支结构 3．运行结果： 第1次运行结果： Input w:53.5<回车> w=53.5 Ok 第2次运行结果： No 第3次运行结果： Input w:201.7<回车> w=201.7 Data over!

第二讲 分支结构 4．归纳分析： （1）本程序在一个if语句中包含了另一个if语句。 在if语句的语句组1或语句组2中又包含另一个分支结构的if语句称为嵌套的if语句。 （2）本程序中出现了两次else。 C语法规定，在if语句中，若多次出现else，则每一个else总是与前面最近的if配对，所以本例题中第一个else与内嵌的if配对，第二个else与最上面的if配对。程序中由于采用了缩进格式，if与else的配对关系一目了然。

第二讲 分支结构 2.4学会使用if-else if形式的嵌套if语句 【实例】编写程序，求下面分段函数的值，要求x的值从键盘输入。 x+2 (0≤x<5) y= 0 (x<0) x2-3 (5≤x<10) 10 (x≥10)

第二讲 分支结构 1．编程思路： 开始 输入x值 x<0 结束 假 真 显示x和y的值 x<5 x<10 y=x+2

第二讲 分支结构 2．程序代码： #include <stdio.h> main() { float x=0,y=0; printf("Input x:"); scanf("%f",&x); if(x<0) y=0; else if(x<5) y=x+2; if(x<10) y=x*x-3; else y=10; printf("x=%f,y=%f\n",x,y); }

第二讲 分支结构 2.5 switch语句 在日常生活中经常遇到菜单选择操作，例如，用ATM自动取款机取钱时，从菜单中可以选择语种、取款额；用自动服务系统给手机充值时，可以选择查余额还是充值，对本机充值还是对其他号码充值等。这些问题一般使用switch语句解决。 总之，这些问题都是多分支情况。

第二讲 分支结构 【实例】编写程序，在如下菜单中选择一个运算类型，并进行相应的运算。如选择了加法，则进行求和运算。 Please choose + : addition - : subtraction * : multiplication / : division

第二讲 分支结构 1．程序代码： #include <stdio.h> main() {float a=5.0,b=2.0,c=0.0; char sym='\0'; printf("Please choose\n"); printf("+ : addition\n"); printf("- : subtraction\n"); printf("* : multiplication\n"); printf("/ : division\n"); sym=getchar(); printf("%f%c%f=",a,sym,b); /* 显示算式 */

第二讲 分支结构 switch(sym) /* 计算算式 */ {case '+': c=a+b; break; } printf("%f\n",c); /* 显示结果 */

第二讲 分支结构 2．运行结果： Please choose + : addition - : subtraction * : multiplication / : division /<回车> 5.000000/2.000000=2.500000

第二讲 分支结构 3．归纳分析： switch语句的一般形式为： switch(表达式) { case 表达式1: 语句组1 break; … … case 表达式n: 语句组n break; default: 语句组n+1 break; } 其中switch、case、default和break是关键字，所有表达式均为整型或字符型。在表达式1、表达式2、…、表达式n中只能出现常量和运算符，而且每个表达式的值不能相等。

第二讲 分支结构 2.6 条件运算符及其表达式 C语言中条件运算符由“?”和“:”组成，例如“a>b ? a : b”。 条件表达式的一般形式为： 表达式1 ？表达式2 ：表达式3 当表达式1的值为非0时，以表达式2的值作为条件表达式的值，否则，以表达式3的值作为条件表达式的值。例如，当a>b成立时，条件表达式“a>b ? a : b”的值为a中的值，否则为b中的值。 使用条件表达式也可以实现分支结构。

第二讲 分支结构 课堂讨论：谁做的好事？ 忻州师院有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。 A说：不是我。 B说：是C。 C说：是D。 D说：C胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。画出N-S流程图并写出程序。

第二讲 分支结构 1、编程思路： 如何找到该人，一定是“先假设该人是做好事者，然后到每句话中去测试看有几句是真话”。“有三句是真话就确定是该人，否则换下一人再试”。 比如，先假定是A同学，让 thisman='A'; 代入到四句话中 A说：thisman!=‘A’; ‘A’!=‘A’ 假，值为0。 B说：thisman==‘C’; ‘A’==‘C’ 假，值为0。 C说：thisman==‘D’; ‘A’==‘D’ 假，值为0。 D说：thisman!=‘D’; ‘A’!=‘D’ 真，值为1。 显然，不是'A'做的好事（四个关系表达式值的和为1）

第二讲 分支结构 再试B同学，让thisman=‘B’; 代入到四句话中 A说：thisman!=‘A’; ‘B’!=‘A’ 真，值为1。 B说：thisman==‘C’; ‘B’==‘C’ 假，值为0。 C说：thisman==‘D’; ‘B’==‘D’ 假，值为0。 D说：thisman!=‘D’; ‘B’!=‘D’ 真，值为1。 显然，不是'B'所为（四个关系表达式值的和为2）

第二讲 分支结构 再试C同学，让thisman=‘C’; 代入到四句话中 A说：thisman!=‘A’; ‘C’!=‘A’ 真，值为1。 B说：thisman==‘C’; ‘C’==‘C’ 真，值为1。 C说：thisman==‘D’; ‘C’==‘D’ 假，值为0。 D说：thisman!=‘D’; ‘C’!=‘D’ 真，值为1。 显然，就是‘C’做了好事（四个关系表达式值之和为3） 这时，我可以理出头绪，要用所谓枚举法，一个人一个人地去试， 四句话中有三句为真，该人即所求。

第三讲 循环结构 循环结构是程序中一种很重要的结构。其特点是， 在给定条件成立时，反复执行某程序段，直到条件不成立为止。 给定的条件称为循环条件，反复执行的程序段称为循环体。 Ｃ语言提供了三种循环语句，可以组成各种不同形式的循环结构,它们是: ｗｈｉｌｅ语句 ｄｏ－ｗｈｉｌｅ语句 ｆｏｒ语句

第三讲 循环结构 3.1 简单循环 【实例】古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ 1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... 该数列的规律为 a1=1 a2=1 an=an-1+an-2 这里求前20项

第三讲 循环结构 begin a1=1;a2=1; i=3 i<=20 Y N an=a1+a2 end 输出an i=i+1;a1=a2;a2=an;

第三讲 循环结构 a1=1;a2=1;an=0; i<=20 an=a1+a2 i=i+1 a1=a2 a2=an 该题目的N-S流程图 a1=1;a2=1;an=0; i<=20 an=a1+a2 输出an i=i+1 a1=a2 a2=an

第三讲 循环结构 2.程序源代码： 方法一：for循环语句 #include "stdio.h" main( ) { long a1,a2,an;   int i;   a1=a2=1;   for(i=3;i<=20;i++)   { an=a1+a2; printf(“a%d=%ld”,i,an);       a1=a2;     a2=an;   }  } 可否调换？

第三讲 循环结构 方法二：while循环语句 #include "stdio.h" main( ) {  long a1,a2,an;   int i;   a1=a2=1;i=3； while（i<=20）     { an=a1+a2; printf(“a%d=%ld”,i,an);       a1=a2;     a2=an; i++;   }  }

第三讲 循环结构 方法三：do-while循环语句 #include "stdio.h" main( ) {  long a1,a2,an;   int i;   a1=a2=1;i=3； do     { an=a1+a2; printf(“a%d=%ld”,i,an);       a1=a2;     a2=an; i++;   } while（i<=20);  }

第三讲 循环结构 3.归纳分析 （1）for语句格式： for ( 表达式1 ; 表达式2 ; 表达式3 ) {语句} 即：

第三讲 循环结构 For语句执行过程 表达式1 表达式2 表达式3 语 句 Y N

第三讲 循环结构 表达式可以省略，但分号不能省略 a) 省略表达式1 i=1 for ( ；i<=50 ；i++ ) sum=sum+2*i b) 省略表达式2——产生死循环 for ( i=1； ；i++ ) sum=sum+2*i c) 省略表达式3 for ( i=1；i<=50 ；) { sum=sum+2*i; i++;} d) 省略表达式1 , 省略表达式3 for ( ；i<=50 ；) { sum=sum+2*i; i++; }

第三讲 循环结构 表达式1，表达式3可以是： a) 简单的表达式 b)逗号表达式 表达式2 一般是关系表达式或逻辑表达式 例：for ( sum=0 , i=1 ; i<=50 ; i++,i++ ) sum=sum+2*i; 或：for ( sum=0 , i=1 ; i<=50 ; i=i+2 ) sum=sum+2*i

第三讲 循环结构 (2) while语句的一般形式为： while(表达式) {语句；} 计算表达式的值，当值为真(非0)时，执行循环体语句。

第三讲 循环结构 使用while语句应注意以下几点： 2.循环体如包括有一个以上的语句，则必须用{}括起来， 组成复合语句。 3.应注意循环条件的选择以避免死循环,一般需要在循环体中动态改变循环条件的值。

第三讲 循环结构 (3) do-while语句的一般形式为： do 语句； while(表达式)； 其中语句是循环体，表达式是循环条件。 do-while语句的语义是： 先执行循环体语句一次， 再判别表达式的值，若为真(非0)则继续循环，否则终止循环。 do-while语句和while语句的区别在于do-while是先执行后判断，因此do-while至少要执行一次循环体。而while是先判断后执行，如果条件不满足，则一次循环体语句也不执行。

第三讲 循环结构 (4)循环体语句可使用break 和continue语句 break：可以用来从循环体内跳出循环体（提前结束循环） 例:输出100以内能被7整除的数。 int n; for(n=7;n<=100;n++) { if (n%7!=0) continue; printf("%d ",n); }

第三讲 循环结构 练习： 1.有一分数序列：2/1，3/2，5/3，8/5，13/8，21/13...求出这个数列的前20项之和。 2.求1+2!+3!+...+20!的和。 3.用牛顿切线法求x-sin(x)=0在区间（0，π）之间的解。 4.任意输入两个数，求这两个数的最大公约数。 5.从键盘输入一个数判断其是否为素数。

第三讲 循环结构 作业： 求s=a+aa+aaa+aaaa+aa...a的值，其中a是一个数字。例如2+22+222+2222+22222(此时共有5个数相加)，几个数相加由键盘输入控制。 一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？ 求1+2!+3!+...+20!的和 猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少？

第三讲 循环结构 3.2循环的嵌套使用 【实例】 搬砖问题。36块砖，36人搬，男搬4，女搬3，两个小孩抬一砖，要求一次全搬完，问男、女、小孩各若干？ 1.分析: 列方程,得出问题条件: w+m+c=36 4*m+3*w+c/2=36 可以用枚举的方法，让变量w在0~9 、m在0~12 、c在0~36的偶数中取值，形成满足上述条件的w 、m、c的组合

第三讲 循环结构 m=0 m<9 w=0 w<12 c=36-m-w且c%2==0 4*m+3*w+c/2==36 False N-S流程图 m<9 w<12 c=36-m-w且c%2==0 4*m+3*w+c/2==36 输出m、w、c True False w=0 w=w+1;m=m+1; m=0

第三讲 循环结构 2.程序 main（） {int m,w,c; for(m=0;m<9;m++) for(w=0;w<12;w++) {c=36-w-m; if(c%2!=0)continue; if(4*m+3*w+c/2==36) printf(“m=%d,w=%d,c=%d”,m,w,c); }

第三讲 循环结构 练习： 1.输出9*9口诀。 2.判断101-200之间有多少个素数，并输出所有素数。 3.打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个“水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。

第三讲 循环结构 作业： 1.将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。 程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成： (1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。 (2)如果n<>k，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你n, 　重复执行第一步。 (3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。 2.一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3.编程找出1000以内的所有完数。

第三讲 循环结构 课堂讨论： 五位跳水高手将参加十米高台跳水决赛，有好事者让五个人据实力预测比赛结果。 A选手说：B第二，我第三； B选手说：我第二，E第四； C选手说：我第一，D第二； D选手说：C最后，我第三； E选手说：我第四，A第一； 决赛成绩公布之后，每位选手的预测都只说对了一半， 即一对一错，请编程解出比赛的实际名次。

第三讲 循环结构 思路：1 首先是将五个人的预测写成逻辑表达式： 让关系运算符“==”的含义是“是”。 让数字1、2、3、4、5分别表示名次第一、第二，…，第五。 让整型变量A、B、C、D、E分别表示每个选手所得名次。 A选手说：B==2，A==3； B选手说：B==2，E==4； C选手说：C==1，D==2； D选手说：C==5，D==3； E选手说：E==4，A==1；

第三讲 循环结构 2 考虑到每个人说的话是一对一错，即一真一假，比如A说的，若B==2为真，则A==3为假，为真取值为1，为假取值为0，则两个关系表达式之和必为1。 即(B==2)+(A==3)应该是1 我们可以归纳出要同时满足五个人所说的话都符合一半对一半错的条件是 ta=((B==2)+(A==3))==1; 符合A选手的话，则ta为1 tb=((B==2)+(E==4))==1; 符合B选手的话，则tb为1 tc=((C==1)+(D==2))==1; 符合C选手的话，则tc为1 td=((C==5)+(D==3))==1; 符合D选手的话，则td为1 te=((E==4)+(A==1))==1; 符合E选手的话，则te为1

第三讲 循环结构 3.仍然可以用枚举的方法，让变量A、B、C、D、E在1~5中取值，形成满足上述条件且A、B、C、D、E取值均不同的A~E的组合，即是所求。 可以考虑A、B、C、D、E取值均不同的条件为 A *B*C*D*E=120

第三讲 循环结构 For(A=1;A<=5;A++) For(B=1;B<=5;B++) For(C=1;C<=5;C++) For(D=1;D<=5;D++) E=15-(A+B+C+D) True A*B*C*D*E=120 False 求ta、tb、tc、 td、te t=ta+tb+tc+td+te t==5 True False 输出ABCDE

某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析： 第三讲 循环结构 作业: 某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析： 1）A、B至少有一人作案； 2）A、D不可能是同案犯； 3）A、E、F三人中至少有两人参与作案； 4）B、C或同时作案，或与本案无关； 5）C、D中有且仅有一人作案； 6）如果D没有参与作案，则E也不可能参与作案。 试编一程序，将作案人找出来。

第三讲 循环结构 1 案情分析：将案情的每一条写成逻辑表达式，第一条用CC1表示，第二条用CC2表示，…… CC1：A和B至少有一人作案 令A变量表示A作案 B变量表示B作案 A B CC1 0 0 0 1 0 1 0 1 1 1 1 1 显然这是或的关系，因此有CC1=(A||B)

第三讲 循环结构 CC2：A和D不可能是同案犯 可以分析为： A如果是案犯，D一定不是案犯，写成A&&(!D) D如果是案犯，A一定不是案犯，写成D&&(!A) 这两者之间是或的关系，因此有 CC2=!(A&&D) A D A&&D CC2 0 0 1 1 1 1 0 0 0 0 1 0 1 0 1

第三讲 循环结构 CC3：A、E、F中有两人涉嫌作案，分析有三种可能 第一种，A和E作案，（A&&E） 第二种，A和F作案，（A&&F） 第三种，E和F作案，（E&&F） 这三种可能性是或的关系， 因此有 CC3= (A&&E）||（A&&F）||（E&&F)

第三讲 循环结构 CC4：B和C或同时作案，或都与本案无关 第一种情况：同时作案（B && C） CC5：C、D中有且仅有一人作案 CC5=(C && !D)||(D && !C) CC6：如果D没有参与作案，则E也不可能参与作案。 CC6=!D !E=D||!E

第三讲 循环结构 2 采取枚举方法，枚举什么呢？ 枚举组合。 6个人每个人都有作案或不作案两种可能，因此有26种组合，从这些组合中挑出符合6条分析的作案者。 定义6个整数变量，分别表示6个人A，B，C，D，E，F。 枚举每个人的可能性: 让0表示不是罪犯； 让1表示就是罪犯。

第三讲 循环结构 for(A=0;A<=1;A++) for(B=0;B<=1;B++) for(C=0;C<=1;C++) for(D=0;D<=1;D++) for(E=0;E<=1;E++) for(F=0;F<=1;F++) 计算CC1 CC2 CC3 CC4 CC5 CC6 判断这些值是否都为1 True False 输出ABCDEF为1的

第四讲 数组 问题：哪只羊最重？ 中秋佳节，有贵客来到草原，主人要从羊群中选一只肥羊宴请宾客，当然要选最重者。这样就要记录每只羊的重量，如果有成千上万只羊，不可能用一般变量来记录。可以用带有下标的变量，也就是这里要讲的数组。

第四讲 数组 1.程序分析： max=0.0 将记录最重的羊的重量 for(i=0;i<10;i++) 提示输入第i只羊的重量 输入第i只羊的重量sheep[i] max<sheep[i] Yes No max=sheep[i] k=i 输出max和k的值

第四讲 数组 2.程序 main() // 主函数 { float sheep[10]; // 数组，有10个浮点类型元素 float max; // 浮点类型变量，存放最肥羊的重量 int i,k; //整型变量，i用于计数循环，k用于记录最肥羊的号 max = 0.0; // 赋初值0 for ( i=0; i<10; i=i+1 ) // 计数循环 {printf(“请输入羊的重量sheep[%d]=”, i); scanf(“%f”, &(sheep[i])); if ( max < sheep[i] ) {max = sheep[i]; // 让第i只羊为当前最肥羊 k=i;} } printf(“max=%f\n number=%d\n”, max , k);}

第四讲 数组 3.归纳分析 (1)数组的定义 类型说明符 数组名 [ 常量表达式 ] 例： float sheep[10]; 类型说明符 数组名 [ 常量表达式 ] 例： float sheep[10]; int a2001[1000]; 说明 ①数组名的第一个字符应为英文字母； ②用方括号将常量表达式括起； ③常量表达式定义了数组元素的个数；

第四讲 数组 ④数组下标从0开始。如果定义5个元素，是从第0个元素至第4个元素； 例如 int a[5] 定义了5个数组元素如下： a[0], a[1], a[2], a[3], a[4] 这是5个带下标的变量，这5个变量的类型是相同的 ⑤常量表达式中不允许包含变量； 例如 int n; n = 5; int a[n]; 不合法！

第四讲 数组 3 5 4 1 2 0 1 2 3 4 (2)数组初始化 是定义数组完成赋初值的任务 例如 int a[5] = { 3, 5, 4, 1, 2 }; a a[0] = 3; a[1] = 5; a[2] = 4; a[3] = 1; a[4] = 2; 3 5 4 1 2 下标 0 1 2 3 4

第四讲 数组 FF00 00000011 a[0] a FF01 00000000 FF02 00000101 a[1] FF03 (3)数组在内存中分配一段连续的存储空间 地址 内存 变量名 数组名 FF00 00000011 a[0] a FF01 00000000 FF02 00000101 a[1] FF03 00000000 FF04 00000100 a[2] FF05 00000000 FF06 00000001 a[3] 00000000 FF07 FF08 00000010 a[4] 00000000 FF09

第四讲 数组 思考: 1.#include <stdio.h> void main() { int a[4]; // 声明项 printf(“a[0]=%d; a[1]=%d; a[2]=%d; a[3]=%d\n”, a[0], a[1], a[2], a[3]); } 2.其他不变，改变声明项为 int a[4] = { 0, 1, 2, 3 };

第四讲 数组 3.其他不变，改变声明项为 int a[4] = { 3, 8 }; 4.其他不变，改变声明项为 5.其他不变，改变声明项为 int a[4] = { 2, 4, 6, d }; 6.其他不变，改变声明项为 int n=4; int a[n] = { 0, 1, 2, 3 };

第四讲 数组 【实例】将几个数从大到小排序并输出，冒泡排序法 i=1 i=2 i=3 i=4 i=5 i=6 a[1] a[2] a[3] a[4] a[5] a[6] 初始值 1 8 3 2 4 9 比较1和8,调换 1 8 3 2 4 9 比较1和3,调换 8 1 3 2 4 9 比较1和2,调换 8 3 1 2 4 9 比较1和4,调换 8 3 2 1 4 9 比较1和4,调换 8 3 2 4 1 9 1到达位置 8 3 2 4 9 1 比较8和3,不动 8 3 2 4 9 1 比较3和2,不动 8 3 2 4 9 1 比较2和4,调换 8 3 2 4 9 1 比较2和9,调换 8 3 4 2 9 1 2到达位置 8 3 4 9 2 1

第四讲 数组 i=1 i=2 i=3 i=4 i=5 i=6 a[1] a[2] a[3] a[4] a[5] a[6] 中间值 8 3 4 9 2 1 比较8和3,不动 8 3 4 9 2 1 比较3和4,调换 8 3 4 9 2 1 比较3和9,调换 8 4 3 9 2 1 3到达位置 8 4 9 3 2 1 比较8和4,不动 8 4 9 3 2 1 比较4和9,调换 8 4 9 3 2 1 4到达位置 8 9 4 3 2 1 比较8和9,调换 8 9 4 3 2 1 8到达位置 9 8 4 3 2 1

第四讲 数组 从表中可以看出最小的一个数第一遍扫描就交换到a[6] 如果将a[1]视为水底，a[6]视为水面： 最轻的(最小的)一个数 1 最先浮到水面，交换到a[6]; 次轻的 2 第二遍扫描交换到a[5]； 再轻的 3 第三遍扫描交换到a[4]； …依此类推，有6个数，前5个数到位需5遍扫描，第6个最重的数自然落在a[1]中。 因此，6个数只需5遍扫描，即j=n-1, n=6。

第四讲 数组 再看在每遍扫描中，相邻两数组元素的比较次数。 当j=1时，i=1,2,…,n-j。 n=6时，比较5次之后a[6]中有一个最小数到达，这时a[6]不必再参与比较了。 因此在第二遍搜索时，j=2, i=1,2,…,n-j，即i=1,2,3,4。比较4次之后次小的一个数到达了a[5]。 这时a[5]不必再参与比较了。 因此， j=3时，i=1,2,3； j=4时，i=1,2； j=5时，i=1

第四讲 数组 为了表述方便，定义以下3个变量： n —— 待排序的数的个数，这里 n=6 j —— 扫描遍数，j=1,2,…,n-1 i —— 第j遍扫描待比较元素的下标，i=1,2,…,n-j

第四讲 数组 采用两重计数型循环： 步骤1： 将待排序的数据放入数组中； 步骤2： 置j为1； 步骤1： 将待排序的数据放入数组中； 步骤2： 置j为1； 步骤3： 让i从1到n-j，比较a[i]与a[i+1]， 如果 a[i] >= a[i+1]，位置不动； 如果 a[i] < a[i+1]，位置交换， 即 p=a[i]; a[i]=a[i+1]; a[i+1]=p; 步骤3结束后 a[n-j+1]中的数为最小的数 步骤4： 让j=j+1；只要j<n就返回步骤3， 将a[n-j+1]的值排好。当j==n时执行步骤5 步骤5： 输出排序结果

第四讲 数组 2.程序 main() // 主函数 { int i, j, p, a[7]; // 整型变量 for (i=1; i<=6; i=i+1) // 键入6个数，放入a数组中 { printf(“请输入待排序的数a[%d]=”, i); scanf (“%d”, &a[i]); } for ( j=1; j<=5; j=j+1) // 冒泡排序，外层循环 for ( i=1; i<=6-j; i=i+1 ) // 内层循环 { if ( a[i] < a[i+1] ) {p = a[i]; a[i] = a[i+1]; a[i+1] = p;} } for ( i=1; i<=6; i=i+1) // 输出排序结果 printf(“%d\n”, a[i]); }

第四讲 数组 作业： 船长与水手的问题： 有载有50个人的大船，突然触礁，船底撞了一个大窟窿，水不停地涌进船里，船不断下沉。这时，聪明的船长把所有人召集到一起，给每人一个编号，手拉手围成一圈，从1号开始报数，报的数为9时，这个人出列，跳入大海，剩下的人继续围成一圈，后面的人从1开始继续报数，重复上面地步骤,聪明的船长却最后留在了船上。 问:船长是几号才能最后一个跳入大海？

第四讲 数组 讨论问题: 使用筛法求100以内的所有素数 思路 1.想象将100个数看作沙子和小石头子，让小石头子当作素数；让沙子当作非素数。弄一个筛子，只要将沙子筛走，剩下的就是素数了。 2.非素数一定是2、3、4 …… 的倍数。 3.使用数组，让下标就是100以内的数，让数组元素的值作为筛去与否的标志。比如筛去以后让元素值为1。

第四讲 数组 1至100这些自然数可以分为三类： 单位数：仅有一个数1。 素数： 是这样一个数，它大于1，且只有1和它自身这样两个正因数。 素数： 是这样一个数，它大于1，且只有1和它自身这样两个正因数。 合数： 除了1和自身以外，还有其他正因数。 1不是素数，除1以外的自然数，当然只有素数与合数。 筛法实际上是筛去合数，留下素数。 为了提高筛选法效率，注意到： 令n为合数（这里是100），c为n的最小正因数，则据初等数论 只要找到c就可以确认n为合数，将其筛去。

第四讲 数组 for(i=2;i<=100:i++) prim[i]=0; for(i=3;i<=100:i++) a=sqrt(i) for(j=2;j<=a:j++) i%j==0 Yes No prim[i]=1 for(i=2;i<=100;i++) prim[i]==0 Yes No 输出i

第四讲 数组 二维数组 问题：求矩阵a的最大值 1 3 5 a= 7 9 2 4 6 8

第四讲 数组 1．二维数组定义 格式： 类型说明符 数组名[常量表达式] [常量表达式] 格式： 类型说明符 数组名[常量表达式] [常量表达式] 例: int a[2] [3] ={{3,5},{4,1},{2,6}}; 说明： a）每一维的下标从0开始，整个数组元素为：2×3=6个 b）C语言中，二维数组中元素排列的顺序是按行存放。 即：先存放第一行的元素，再存放第二行的元素

第四讲 数组 二维数组在内存中的分配情况 FF00 00000011 a[0][0] a FF01 00000000 FF02 地址 内存 变量名 数组名 FF00 00000011 a[0][0] a FF01 00000000 FF02 00000101 a[0][1] FF03 00000000 FF04 00000100 a[1][0] FF05 00000000 FF06 00000001 a[1][1] 00000000 FF07 FF08 00000010 a[2][0] 00000000 FF09 ……

第四讲 数组 c）可以计算数组元素在数组中的序号 假设 m×n的数组a，计算a[i][j]序号的公式： i×n+j 如3×3数组中:

第四讲 数组 求矩阵a的最大值 1 3 5 a= 7 9 2 4 6 8 问题分析：将矩阵放入二维数组a[3][3]中 1 3 5 a= 7 9 2 4 6 8 问题分析：将矩阵放入二维数组a[3][3]中 首先定义变量max=a[0][0]，max与a[0][1]比较，若发现max<a[0][1]，则将max=a[0][1]，这样max与数组元素逐个比较，最后找到数组中最大的一个。采用二重循环分别对行和列进行控制。 外层控制行标，内层控制列标。

第四讲 数组 作业 1.打印魔方阵： 8 1 6 3 5 7 4 9 2 算法: 1.将1放到第1行的中间。 8 1 6 3 5 7 4 9 2 算法: 1.将1放到第1行的中间。 2.下一个数放在该数的前一行后一列。 3.若该位置已经有数,则放在前一数的正下方。 4.当前数是右上角时,其下一个数放在其下方。 5.若当前是第1行,则其前一行为第n行,若当前列是第n列,则其后一列为第1列。

第五讲 函数 问题：编程求解 我们用函数来编写这个题的程序，参考程序如下： #include <stdio.h> //预编译命令 #define n 6 //定义n为6 #define k 4 //定义k为4 void main() //主函数 {printf("sum of %dth powers of integers from 1 to %d=",k,n ); printf("%d\n",SOP(n,k)); //输出结果,其中SOP(n,k)为被调用函数 }

第五讲 函数 int SOP(m,l) //整型自定义函数,m,l 为形参 int m,l; //形参m,l 为整型变量 { int i,sum=0; //整型变量i,sum for (i=1; i<=m; i=i+1 ) {sum=sum+power( i ,l ); } return (sum) ; } //返回值sum给函数sop(n,k) //以下函数是被函数sop(n,k)调用的函数 int power(p,q) //整型自定义函数 int p,q; //形参p,q 为整型变量 {int i,product=1; for(i=1; i<=q; i=i+1) { product=product*p; } return(product); } //累乘值product返回给power

第五讲 函数 函数的定义格式： <数据类型> <函数名> (<参数表>) 例: int power(p,n) power为函数名，要以英文字母开头。 int是函数值的数据类型，这里是int（整型）。 (p,n)括号中的p,n为函数的形式参数，形式参数也要定义其数据类型。 函数定义的一般格式： <数据类型> <函数名> (<参数表>) <参数说明;> { <说明语句> <执行语句> }

第五讲 函数 形式参数与实在参数 1、形式参数是在定义函数时放在函数名后括号中的参数。在未进行函数调用时，并不对形式参数分配内存单元。在发生函数调用时，立刻给形式参数分配内存单元。调用结束后，释放掉行参所占的内存单元。 2、因此，形参变量属于局部变量，其作用域在它所在的函数体内。 3、在定义函数的时候，必须指定形参变量的类型，如何指定？有二种方法： (1) int power(p,n) int p,n; { …… } (2) int power(int p,int n) { …… } 有些编译系统不认识第（2）种形式

第五讲 函数 4、实在参数是一个具有确定值的表达式。函数在调用时，将实在参数赋给形式参数。 比如，主函数调用SOP(n,k)，这时，n,k为实在参数，n的值为6，k的值为4。在被调用函数定义中，int SOP(m,l)中的m,l为形式参数，在SOP被调用时，系统给m,l这两个形式参数分配了内存单元之后，n的值6赋给m，k的值4赋给l。 实在参数的个数及类型应与形式参数一致。赋值时前后对应关系不会改变。下面画出主函数与SOP函数，调用与被调用时参数传递关系：

第五讲 函数 主函数执行下述语句时， printf(“%d\n”,SOP(n,k)); 传值给被调用函数 int SOP(m,l) n的值6传给m, k的值4传给l。 6和4为实在参数，m和l为形式参数。 被调用函数在其形式参数被赋值之后，开始执行函数体，先是让累加器初始化为0（sum=0），接着进入以i为控制变量的计算循环，i从1变到m（m=6），即累加m次（即6次）。循环体为sum=sum+power(i,l)。当6次循环执行完后，实现的是 注意这里 xl 是由另一个自定义函数power(i,l)实现的。

第五讲 函数 power(i,l)处在SOP(m,l)函数中，表示SOP函数去调用power 函数。其中i,l为实在参数，而int power(p,q)中的p,q为形式参数。 比如，执行SOP(6,4)时，l=4,m=6, 当i=1时， sum=sum+power(1,4) 这里1，4为实在参数，调用power(p,q)，两个形式参数p,q分别被赋以1，4。

i=1: sum = sum + power(i,l) power(1, 4): product = 1*1*1*1 调用 = 0 + 1 = 1 返回 执行 SOP(6,4) l=4 sum=0 i=1: sum = sum + power(i,l) power(1, 4): product = 1*1*1*1 return(1) = 1 SOP(n,k) i=2: sum = sum + power(i,l) = 1 + 16 = 17 调用 返回 执行 power(2, 4): product = 2*2*2*2 return(16) = 16 i=3: sum = sum + power(i,l) = 17 + 81 = 98 调用 返回 执行 power(3, 4): product = 3*3*3*3 return(81) = 81 i=4: sum = sum + power(i,l) = 98 + 256 = 354 调用 返回 执行 power(4, 4): product = 4*4*4*4 return(256) = 256 i=5: sum = sum + power(i,l) = 354 + 625 = 979 调用 返回 执行 power(5, 4): product = 5*5*5*5 return(625) = 625 i=6: sum = sum + power(i,l) = 979 + 1296 = 2275 return (sum) 2275 返回 调用 执行 power(6, 4): produ ct = 6*6*6* return(1296) = 1296 6

第五讲 函数 Main() a函数 b函数 调用b函数 调用a函数 结束 结束 结束

第五讲 函数 例： 求函数f(x)=x3+x+5的值，其中x=y3+y2+5y+6，求当y=1,2,3,4…,100时f(x)的值。

第五讲 函数 作业: 1.设计一个函数,求解1000以内的所有素数.

第六讲 递归及其实现 递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。 我们先从一个最简单的例子导入。 用递归算法求n! 定义：函数 fact(n) = n! fact(n-1) = (n-1)! 则有 fact(n) = n*fact(n-1) 已知 fact(1) = 1

第六讲 递归及其实现 下面我们以3！为例画出了调用和返回的递归示意图 A B fact(3) fact(2) C =3*fact(2) =3*2 =2*1 =1 =6 =2 返回 返回

第六讲 递归及其实现 从图可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。 就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心， 遇到1的阶乘，其值为1，到达了递归的边界。 然后再用fact(n)=n*fact(n-1)这个普遍公式，从里向外倒推回去得到fact(n)的值。 为了把这个问题说得再透彻一点。我们画了如下的流程图：

第六讲 递归及其实现 1 3 2 * ) ＝＝ fact(3) 真 假 调用 fact( 计算 ＝ 返回 ) ) 2

第六讲 递归及其实现 将上图改为下图 ) 假 真 fact(3) 3==1 调用 fact( 2 2==1 1==1 f 返回 act(3)=3*fact(2) fact(1) =1 1

fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6 第六讲 递归及其实现 在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。 为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。 递推是从已知的初始条件出发，逐次去求所需要的阶乘值。 如求3！ 初始条件 fact(1) = 1 fact(2) = 2*fact(1) = 2 fact(3) = 3*fact(2) = 6

第六讲 递归及其实现 这相当于从菜心“推到”外层。而递归算法的出发点不放在 初始条件上，而放在求解的目标上，从所求的未知项出发逐 次调用本身的求解过程，直到递归的边界（即初始条件）。 就本例而言，读者会认为递归算法可能是多余的，费力而不 讨好。但许多实际问题不可能或不容易找到显而易见的递推 关系，这时递归算法就表现出了明显的优越性。 下面我们将会看到，递归算法比较符合人的思维方式，逻 辑性强，可将问题描述得简单扼要，具有良好的可读性，易 于理解，许多看来相当复杂，或难以下手的问题，如果能够 使用递归算法就会使问题变得易于处理。

第六讲 递归及其实现 故事：相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。 A B C

第六讲 递归及其实现 怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。 1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为move 1 from A to C C A B 1

第六讲 递归及其实现 2、在A柱上有二只盘子，1为小盘，2为大盘。 第（1）步将1号盘从A移至B，这是为了让2号盘能移动； 第（2）步将2号盘从A移至C； 第（3）步再将1号盘从B移至C； 这三步记为： move 1 from A to B; move 2 from A to C; move 1 form B to C; C A B 1 3 2

3、在A柱上有3只盘子，从小到大分别为1号，2号，3号 第六讲 递归及其实现 3、在A柱上有3只盘子，从小到大分别为1号，2号，3号 第（1）步将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为 move( 2, A, C, B) 意思是将上面的2只盘子作为整体从A借助C移至B。 第（2）步将3号盘从A移至C，一次到位。记为 move 3 from A to C 第（3）步处于B上的作为一个整体的2只盘子，再移至C。 这一步记为 move( 2, B, A, C) 意思是将2只盘子作为整体从B借助A移至C。

第六讲 递归及其实现 移动过程如下图 A B C 1 3 2

第六讲 递归及其实现 4、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中move(2, A, C, B)实际上是分解为以下三步 第（1）步：move 1 form A to C; 第（2）步：move 2 form A to B; 第（3）步：move 1 form C to B; 经过以上步骤，将1号和2号盘作为整体从A移至B，为3号盘从A移至C创造了条件。同样，3号盘一旦到了C，就要考虑如何实现将1号和2号盘当整体从B移至C的过程了。实际上move(2, B, A, C)也要分解为三步： 第（1）步：move 1 form B to A; 第（2）步：move 2 form B to C; 第（3）步：move 1 form A to C;

第六讲 递归及其实现 5、看move(2, A, C, B)是说要将2只盘自从A搬至B，但没有C是不行的，因为第（1）步就要将1盘从A移到C，给2盘创造条件从A移至B，然后再把1盘从C移至B。看到这里就能明白借助C的含义了。因此，在构思搬移过程的参量时，要把3个柱子都用上。 6、定义搬移函数move(n, A, B, C)，物理意义是将n只盘子从A经B搬到C move(n, A, B, C) 分解为3步 (1)move(n-1, A, C, B)理解为将上面的n-1只盘子作为一个整体从A经C移至B； (2)输出n：A to C，理解将n号盘从A移至C； (3)Move(n-1, B, A, C)理解为将上面的n-1只盘子作为一个整体从B经A移至C。

第六讲 递归及其实现 这里显然是一种递归定义，当解move(n-1, A, C, B)时又可想到，将其分解为3步： 第1步：将上面的n-2只盘子作为一个整体从A经B到C，move(n-2, A, B, C)； 第2步：第n-1号盘子从A直接移至B，即输出n-1:A to B； 第3步：再将上面的n-2只盘子作为一个整体从C经A移至B，move(n-2, C, A, B)；

第六讲 递归 7 返回 move(3,A,B,C) C B move( 2 ,A, , ) A ,C) B, A, 调用 1 C,A C) 输出 1: A to C 2: A to B ,B,C ,A 1: B to A 5 2: B to C 6 3: A to C 1: C to B 3 move (1,C,A,B) move (1,A,B,C) 4

第六讲 递归及其实现 1 2 3 4 5 6 7 B 输出 3: A to C 调用 move(1,C,A,B) 输出： 1: C to move(1,A,B,C) 1: A to C move(2,A,C,B) move(2 ,A,C,B) move(2,B,A,C) move (1,B,C,A) 1: B to A move(1,B,C,A) move(3,A,B,C) 2: 2: B C 1 2 3 4 5 6 7 第六讲 递归及其实现

int step=1 ; //整型全局变量,预置1,步数 void move(int , char ,char,char); //声明要用到的被调用函数 void main() { int n; printf(“请输入盘数n=” ); scanf("%d",&n); printf(“在3根柱子上移%d只盘的步骤为:\n”,n); move(n,'a','b','c');} void move(int m, char p, char q, char r) { if (m==1) {printf("[%d] move 1# from %c to %c\n", step, p,r); step=step+1; } else{move(m-1,p,r,q); printf("[%d] move %d# from %c to %c\n",step, m,p,r); step=step+1; move(m-1,q,p,r); }

第六讲 递归及其实现 该题是2000年全国青少年信息学奥林匹克的一道试题。叙述如下： 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用1，2，…，n编号。规定初始时这队青蛙只能趴在左岸的石头L上，当然是按号排一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有S个石柱，有 y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按号排一个落一个，大的在下，小的在上。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱R，与左岸的石柱L一样 ，允许多个青蛙按号排一个落一个，小的在上，大的在下。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？

第六讲 递归及其实现 思路： 1、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析，化难为易。 2. 定义函数 Jump(S,y) —— 最多可跳过河的青蛙数 其中： S —— 河中柱子数 y —— 荷叶数

第六讲 递归及其实现 3. 先看简单情况，河中无柱子：S=0， Jump(0,y) 当y=1时，Jump(0,1)=2； 说明：河中有一片荷叶，可以过两只青蛙，起始时L上有两只青蛙，1#在2#上面。 第一步：1# 跳到荷叶上； 第二步：2# 从L直接跳至R上； 第三步：1# 再从荷叶跳至R上。 如下图： 1 3 1# L 2# R 左岸 右岸 2

第六讲 递归及其实现 当y=2时， Jump(0,2)=3； 说明：河中有两片荷叶时，可以过3只青蛙。起始时： 1#，2#，3# 3只青蛙落在L上， 5 第一步：1# 从L跳至叶 1上， 1 第二步：2# 从L跳至叶 2上， 叶1 第三步：3# 从L直接跳至R上， L R 第四步：2# 从叶2跳至R上， 第五步：1# 从叶1跳至R上， 3 2 4 叶2 采用归纳法：Jump(0,y)=y+1； 意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数+1。

第六讲 递归及其实现 再看Jump(S, y) 先看一个最简单情况： S=1，y=1。从图上看出需要9步，跳过4只青蛙。 1# 青蛙从 L －> Y； 2# 青蛙从 L －> S； 1# 青蛙从 Y －> S； 3# 青蛙从 L －> Y； 4# 青蛙从 L －> R； 3# 青蛙从 Y －> R； 1# 青蛙从 S －> Y； 2# 青蛙从 S －> R； 1# 青蛙从 Y －> R； 4 3# 3# 6 1 Y 1# 9 R L 1# 3 7 1# 1# 2 S 2# 2# 8 5 4#

第六讲 递归及其实现 用L1 L2 L3 L4表示左岸石柱上落在一起的青蛙的高度位置。 L1 在最上面，L4 在最下面的位置。 引入这个信息就可比较容易地看出对青蛙占位的约束条件。 同理R1 R2 R3 R4也是如此。 对水中石柱S，也分成两个高度位置S1 S2。 对荷叶Y无须分层，因为它只允许一只青蛙落在其上。 t=0为初始时刻，青蛙从小到大落在石柱L上。 t=1为第一步：1#从L跳至荷叶Y上；L上只剩2# 3# 4#。 T=2 为第二步；2#从L跳至石柱S上，处在S2位置上，L上只剩3#和4#。 T=3为第三步，1#从Y跳至S，将Y清空。 这时可看出，S上有1#、2#，L上有3#、4#，好象是原来在L上的4只青蛙，分成了上下两部分，上面的2只通过荷叶y转移到了S上。这一过程是一分为二的过程。即将L上的一队青蛙，分解为两个队，每队各二只，且将上面的二只转移到了S上。这时我们可以考虑形成两个系统，一个是L，Y，R系统，一个是S，Y，R系统。前者二只青蛙号大；后者二只青蛙号小。先跳号大的，再跳号小的。从第五步到第九步可以看出的确是这么做的。

第六讲 递归及其实现 对于LYR系统，相当于Jump(0,1) 对于SYR系统，相当于Jump(0,1) 两个系统之和为2*Jump(0,1)，因此有： Jump(1,1)=2*Jump(0,1)=2*2=4。 现在再看S=2，y=1 Jump(2,1) 我们将河中的两个石柱称作S1和S2，荷 叶叫y， 考虑先将L上的青蛙的一半借助于S2和y 转移到S1上，当然是一半小号的青蛙在 S1上，大的留在L上。 y L R S1 S2

第六讲 递归及其实现 这样 L S1 S2 y R 系统分解为 ： （L S2 y R 系统） + （S1 S2 y R 系统） = 2 * （L S2 y R 系统） = 2 * Jump(1,1) 用归纳法 Jump(S, y)=2*Jump(S-1, y)

第六讲 递归及其实现 main() { int s,y,sum; //整型变量,s为河中石柱数,y为荷叶数 printf("请输入石柱数s=" ); scanf("%d",&s); printf("请输入荷叶数y=" ); scanf("%d",&y); sum=Jump(s,y); //Jump(s,y)为被调用函数 printf(“Jump(%d,%d)=%d\n”,s,y,sum);} int Jump(int r,int z) { int k; if (r==0) {k=z+1; } else{k=2*Jump(r-1,z);} return(k); }

第七讲 指针 指针是C语言中的一个重要概念。掌握指针的用法，可使程序简洁、高效、灵活，但并不难学。 为了了解什么是指针，先看一个小故事 地下工作者阿金接到上级指令，要去寻找打开密电码的密钥，这是一个整数。几经周折，才探知如下线索，密钥藏在一栋三年前就被贴上封条的小楼中。一个风雨交加的夜晚，阿金潜入了小楼，房间很多，不知该进哪一间，正在一筹莫展之际，忽然走廊上的电话铃声响起。艺高人胆大，阿金毫不迟疑，抓起听筒，只听一个陌生人说：“去打开211房间，那里有线索”。阿金疾步上楼，打开211房间，用电筒一照，只见桌上赫然6个大字：地址1000。阿金眼睛一亮，迅速找到1000房间，取出重要数据66，完成了任务。

第七讲 指针 P 1000 66 211 1000 说明： 1、数据藏在一个内存地址单元中，地址是1000。 2、地址1000又由P单元所指认，P单元的地址为211。 3、66的直接地址是1000；66的间接地址是211；211中存的是直接地址1000。 4、称P为指针变量，1000是指针变量的值，实际上是有用数据藏在存储器中的地址。

第七讲 指针 指针变量——用来存放另一变量地址的变量 变量的指针就是变量的地址。 1、指针的概念指针是一种特殊的变量，特殊性表现在类型和值上。 从变量讲，指针也具有变量的三个要素： （1）变量名，这与一般变量取名相同，由英文字符开始。 （2）指针变量的类型，是指针所指向的变量的类型，而不是自身的类型。 （3）指针的值是某个变量的内存地址。

第七讲 指针 从上面的概念可知，指针本身类型是int型，因为任何内存地址都是整型的。但是指针变量的类型却定义成它所指向的变量的类型。 2、指针的定义（说明，先说明后引用） 例如： int *p, *q; // 定义p,q为指向整数类型变量的指针 float *point; // 定义point为指向float型变量的指针 double *pd; // 定义pd为指向double型变量的指针 int (*pa)[10]; // 定义pa为指向int型数组的指针 int (*pu)(); // 定义pu为指向int型函数的指针 int **qq; // 定义qq为指向int型指针的指针 还有指向结构、联合的指针，后面再介绍

第七讲 指针 3、指针赋值 例 int akey; // 定义一个整型变量akey int *p,*q; // 定义p,q为指向整型变量的指针变量 akey=66; // 将66赋给akey p = &akey; //将变量akey的地址赋给p，这时见图1 q = p; // 将p的值赋给q，见图2 p akey &akey 66 &p &akey 图 1 p 变量的地址 akey 变量的地址 图 1 的说明：将 akey 变量的地址赋给指针 p ，意味着让指针 p 指向 akey

第七讲 指针 &a 66 q=p; &a p a &p 图 2 q &q p q 图 2 的说明：当着执行 q=p; 之后， 中所存的 a 变量的 地址值，也就被放到 变量中，意味着让指 针 也指向

第七讲 指针 #include <stdio.h> void main() { int a[5]={0,1,2,3,4}; //定义数组，赋初值 int *p1,*p2; //定义指针变量 p1=&a[1]; //赋值给指针变量，让p1指向a[1] p2=&a[2]; //赋值给指针变量，让p2指向a[2] printf("a[1]=%d;a[2]=%d\n",*p1,*p2); }

第七讲 指针 1 2 3 4 &a[0] &a[1] &a[2] &a[3] &a[4] p1 p2 &a[1] &a[2] &p1 &p2 1 2 3 4 &a[0] &a[1] &a[2] &a[3] &a[4] p1 p2 &a[1] &a[2] &p1 &p2 p1和p2分别指向a[1],a[2]，这里 & —— 取地址运算符 * —— 指针运算符（间接访问运算符） *p1——间接访问p1所指向的内存单元，当然是输出a[1]的值 *p2——间接访问p2所指向的内存单元，当然是输出a[2]的值

第七讲 指针 4、向指针所指向的内存单元赋值 void main() { int akey,b; int *p,*q; akey=66; p=&akey; q=&b; *q=*p; printf(“b=%d\n”,b); printf(“*q=%d\n”,*q); }

第七讲 指针 p &ak ey 66 &akey *q=*p q & b 66 &b

第七讲 指针 5、指针与数组 void main() { int a[5]={1,3,5,7,9}; int *p; int i; p=a; for(i=0;i<5;i=i+1) {printf("a[%d]=%d\n",i,*p); p=p+1; }

第七讲 指针 *(p+3) *(p+4) *(p+2) *(p+1) *p a[1] a[2] a[3] a[4] a[5] 说明 (1) p=a; 这里数组名作为数组的起始地址，即a[0]的地址。 因此 p=a 等效于 p=&a[0]; (2) p=p+1; 如p指向a[0], 则p=p+1之后，p指向a[1] (3) 如果p=a 等效于 p=&a[0]; 则 p=a+4 等效于 p=&a[4]; p p *(p+3) *(p+4) *(p+2) *(p+1) *p a[1] 等效 p+1 p+1 a[2] a[3] p+2 p+2 a[4] a[5]

第七讲 指针 void main() { int a[5]={1,3,5,7,9}; int *p; int i=0; for(p=a;p<a+5;p=p+1) printf("a[%d]=%d\n",i,*p); i=i+1; }

第七讲 指针 数组名是一个常量指针，指向该数组的首地址， 例 void main() { char *p; static char s[] = “abcdefgh”; p=s; while (*p != ‘\0’) { p=p+1; } printf(“字串长度为%d\n”,p-s);

第七讲 指针 s a b c d e f g h \0 s p 图中数组的首地址是s[0]的地址，即&s[0]。s可看作是指向s[0]的指针。s是不会动的，是常量指针。

第八讲 结构体 任务： 我们要作一张登记表，登记排队求职信息，包括：姓名、年龄、性别、电话四个参数。希望便于管理，即可以插入和删除，这时可采用结构类型变量。 struct ST { char name[20]; // 字符串，姓名 int age; // 整数，年龄 char sex; // 字符，性别 long num; // 电话号码 }; // 注意，这里必须有分号 struct ST student1,student2 ;

第八讲 结构体 在定义一个结构体类型时，可以用另一个结构类型来定义其中的成员，即可以嵌套定义。 例：struct date 第八讲 结构体 在定义一个结构体类型时，可以用另一个结构类型来定义其中的成员，即可以嵌套定义。 例：struct date { int month; int day; int year; };  struct person { char name[10]; struct date birthday; long certificate; };

第八讲 结构体 结构体类型变量的引用 引用方式：结构体变量．成员名 对成员变量可以像普通变量一样使用，进行各种运算。 即：worker．name 、 worker．birthday 、 worker．certificate

第八讲 结构体 main () { struct student { long int num; char name[20]; 第八讲 结构体 结构指针 设一个指针变量，用来指向一个结构体变量，此时该变量的值是结构体变量的起始地址。 即：结构指针就是对已经定义的结构变量的一个起始地址 例： main () { struct student { long int num; char name[20]; char sex; float score; };

第八讲 结构体 struct student stu_1; struct student *p; p=&stu_1; 第八讲 结构体 struct student stu_1; struct student *p; p=&stu_1; stu_1.num=10001; strcpy(stu_1.name,"Li Lin"); stu_1.sex='M'; stu_1.score=92.5; printf("No.:%ld\n name:%s\n sex:%c\n score:%4.1f\n", stu_1.num,stu_1.name,stu_1.sex,stu_1.score); printf("\n No.:%ld\n name:%s\n sex:%c\n score:%4.1f\n", (*p).num,(*p).name,(*p).sex,(*p).score); }

第八讲 结构体 注：C语言中，为了使用方便和直观，可以把(*p).num 用p->num来代替 即以下三种形式是等价的： 第八讲 结构体 注：C语言中，为了使用方便和直观，可以把(*p).num 用p->num来代替 即以下三种形式是等价的： a）结构体变量．成员名 b）(*p) ．成员名 c）p->成员名

第八讲 结构体 用指针处理链表 （1）链表的基本概念 第八讲 结构体 用指针处理链表 （1）链表的基本概念 链表是一种重要的数据结构，主要用以实现对数据的动态存储，链表中包含若干个结点( 又可称为元素)，每个结点包含的数据有两部分：一是用户的实际数据，二是下个结点的地址信息，这样，结点都按这个原则“连接”起来，在这种链式结构中，每个结点只有一个“前驱”和一个“后继”，所以，只要知道链中第一个结点的地址，就可以遍访链中的其他结点。

第八讲 结构体 头指针：存储第一个结点的指针变量 （*head） 表头： 由头指针指向的结点，有后继而无前驱 第八讲 结构体 头指针：存储第一个结点的指针变量 （*head） 表头： 由头指针指向的结点，有后继而无前驱 表尾：表的最后一个结点，有前驱而无后继，其下一个的地址信息为空（NULL） 结点的表述：以结构体变量描述： struct student { int num; int score; struct student *next; };

第八讲 结构体 如下所示为典型的单链表结构： 数据 头指针head 指针 40 1 10 2 20 首地址10 首地址40 3 15 第八讲 结构体 如下所示为典型的单链表结构： 数据 头指针head 指针 40 1 10 2 20 首地址10 首地址40 3 15 4 NULL 首地址20 首地址15

第八讲 结构体 链表的建立 例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为10。 第八讲 结构体 链表的建立 例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为10。 head 5 6 8 12 15 null p 10 待插入结点

第八讲 结构体 分析： 考虑将结点p插入链表head中，分如下三种情况： 第八讲 结构体 分析： 考虑将结点p插入链表head中，分如下三种情况： 1、第一种情况，链表还未建成（空链表），待插入结点p实际上是第一个结点。这时必然有head==null。 只要让头指针指向p就可以了。语句为 head = p; p->next = null; 2、第二种情况，链表已建成，待插入结点p的数据要比头结点的数据还要小，这时有p->num <head->num 。 当然p结点要插在head结点前。 3、第三种情况，链表已建成，待插入结点p的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r和q，利用循环比较来找到正确位置。然后将结点p插入到链表中正确的位置。

说明：这种情况下，p结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。13>8，继续比较。 第八讲 结构体 6 head 8 12 null 13 p 15 q r 说明：这种情况下，p结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。13>8，继续比较。

第八讲 结构体 r q 说明：13>12，继续比较。 6 8 12 15 head null 13 p null

语句为：r->next = p; p->next = q; 第八讲 结构体 r q 说明： 13<15，找到了正确的插入位置， 则插入结点p。 语句为：r->next = p; p->next = q; 6 8 12 15 head null 13 p

第八讲 结构体 #include <stdio.h> // 预编译命令 #include <malloc.h> // 内存空间分配 #define null 0 // 定义空指针常量 #define LEN sizeof(struct numST) struct numST { int num; struct numST *next; };

第八讲 结构体 // 被调用函数insert()，两个形参分别表示链表和待插入的结点 void insert (struct numST **phead, struct numST *p) { struct numST *q,*r; if ((*phead)==null) // 第一种情况，链表为空 { *phead = p; // 链表头指向p return; // 完成插入操作，返回 } else // 链表不为空 { // 第二种情况，p结点num值小于链表头结点的num值 if ( (*phead)->num > p->num) { // 将p结点插到链表头部 p->next = *phead;// 将p的next指针指向链表头(*phead) *phead = p; // 将链表头赋值为p return; // 返回 }

第八讲 结构体 // 第三种情况，循环查找正确位置 r = *phead; // r赋值为链表头 第八讲 结构体 // 第三种情况，循环查找正确位置 r = *phead; // r赋值为链表头 q = (*phead)->next; // q赋值为链表的下一个结点 while (q!=null) // 利用循环查找正确位置 { // 判断当前结点num是否小于p结点的num if (q->num < p->num) {r = q; // r赋值为q，即指向q所指的结点 q = q->next;// q指向链表中相邻的下一个结点 } else // 找到了正确的位置 break; // 退出循环 } // 将p结点插入正确的位置 r->next = p; p->next = q; } }

第八讲 结构体 void main() // 主函数开始 { // 函数体开始 第八讲 结构体 void main() // 主函数开始 { // 函数体开始 struct numST *head, *p; // ST型结构指针 head = null;// 分配两个ST结构的内存空间，用于构造链表 head = (struct numST *) malloc(LEN); head->next = (struct numST *) malloc(LEN); // 为链表中的两个结点中的num赋值为5和10 head->num = 5; head->next->num = 10; head->next->next = null; // 链表尾赋值为空 // 构造一个结点p，用于插入链表 p = (struct numST *) malloc(LEN); p->num = 8; p->next = null; insert(&head, p); }

malloc( size ) ——在内存的动态存储区中分配一个长度为size的连续空间。 第八讲 结构体 动态地开辟和释放存储单元的函数 malloc( size ) ——在内存的动态存储区中分配一个长度为size的连续空间。 此函数值是一个指向分配域起始地址的指针。 calloc( n, size ) ——在内存的动态存储区中分配n个长度为size的连续空间 free( ptr ) —— 释放由ptr指向的内存区。 ptr是最近一次调用calloc或malloc函数时返回的值（指针）

第八讲 结构体 例： a）p=(float *)malloc(4); 开辟4个字节的存储空间，并把此地址赋给指针p b）new=(struct work *)malloc(struct work); 开辟一个能容纳结构变量work的空间，并把这个空间的首地址赋给结构指针new