《C语言基础教程Lesson14》由会员分享，可在线阅读，更多相关《C语言基础教程Lesson14（20页珍藏版）》请在金锄头文库上搜索。
1、Lesson 14 冒泡排序冒泡排序 递归递归 假设在排序过程中记录序列R1.n的状态为： 第 i 趟冒泡排序 无序序列R1.n-i+1 有序序列 Rn-i+2.n n-i+1 无序序列R1.n-i 有序序列 Rn-i+1.n 比较相邻记录，将关关 键字最大的记录键字最大的记录交换交换 到 n-i+1 的位置上 冒泡排序 #include #include #define NUM 5 void input(int value , int n); void output(int value , int n); void sort(int value , int n); main( ) int v
2、alueNUM; /* 存储待排序的数据数列存储待排序的数据数列 */ input(value, NUM); output(value, NUM); /测试测试 sort(value, NUM); output(value, NUM); void sort(int value , int n) /* 冒泡排序函数冒泡排序函数 */ int i, j, temp; for (i=n-1; i=1; i-) / 控制排序趟数控制排序趟数 for (j=0; jvaluej+1) temp = valuej; valuej = valuej+1; valuej+1 = temp; void inpu
3、t(int value ,int n) int i; printf(“nEnter %d integers:“,n); for (i=0; i1) n! = (n-1)!*n (n-1)! = (n-2)! * (n-1) 1! = 1 递归函数与递归调用递归函数与递归调用 函数中直接或间接的调用自身，这样函函数中直接或间接的调用自身，这样函 数叫递归函数，调用称为递归调用。数叫递归函数，调用称为递归调用。 理解的关键在函数调用过程理解的关键在函数调用过程 void fun1() ; fun1(); ; void fun1() ; fun2(); ; void fun2() ; fun1();
4、 ; 求阶乘函数求阶乘函数 /计算计算n！(n1)，返回值为阶乘的值，返回值为阶乘的值 long f(int n) if( 1 = n) return 1 ; else return n * f(n-1) ; int main() int var; printf(“请输入一个正整数：请输入一个正整数：“) ; scanf(“%d“, printf(“n%d ! = %ldn“, var,f(var); return 0; /调试之，体会递归函数调用过程调试之，体会递归函数调用过程 n:3 3*f(2) 现场 完成计算 输出6 n:2 2*f(1) 现场 返回2 n:1 返回1 编写递归函数的关
5、键编写递归函数的关键 找出递归问题的相同部分找出递归问题的相同部分 递归结束的条件递归结束的条件 需用递归特征：小问题的性质与大问题需用递归特征：小问题的性质与大问题 一样。一样。 递归算法用于解决特定局部问题，不提递归算法用于解决特定局部问题，不提 倡用于软件结构设计。倡用于软件结构设计。 自学自学Hanoi问题。问题。 /用循环求阶乘用循环求阶乘 void main() int i,n,f=1; /* 定义变量定义变量 */ printf(“请输入请输入n的值：的值：n“); scanf(“%d“, i = 1; while(i #define NUM 3 void anagram(int
6、 , int); void print(int ); void main( ) int dNUM; /存储每个全排列存储每个全排列 int i; for (i=0; i=0; i-) printf(“%d“ ,di); void anagram(int d , int n) /* 求解求解n的全排列的全排列 */ int i, j, temp; if (n=1) /* n=1输出输出 */ print(d); return; for (i=0; ihigh) return -1; /* 查找区间为空查找区间为空 */ mid = (low+high)/2; if (valuemid=key)
7、return mid; /* 得到查找的数据位置得到查找的数据位置 */ if (key1 编一程序，从键盘上输入编一程序，从键盘上输入x和和n的值，使用递归函的值，使用递归函 数求数求Pn(x)的值。的值。 作业作业 L14-2.有有100个球，球上印制这个球，球上印制这1-100 的数字（每个球都不同），并且这些球的数字（每个球都不同），并且这些球 采用了特殊材料，只有人正对着球时才采用了特殊材料，只有人正对着球时才 能看清球上的数字，你只有一个人，并能看清球上的数字，你只有一个人，并 且一次只能拿起一个球正面观察其数字，且一次只能拿起一个球正面观察其数字， 那么要将这些球按那么要将这些球按1-100的顺序排序，的顺序排序， 你有什么方法？你有什么方法？
