强化复习之常用算法.ppt

强化复习之常用算法 2020 3 26 1 10进制整数m转换为n进制 j 0 while m 0 a j m n m m n 2020 3 26 2 最大公约数 辗转相除法 r m n while r 0 m n n r r m n 2020 3 26 3 素数判断 2020 3 26 4 for i 2 isqrt m m为素数 二分法求根 2020 3 26 5 while fabs b a eps h a b 2 if f h 0 break if f a f h 0 b h elsea h 牛顿法求根 2020 3 26 6 x1 3 do x0 x1 x1 x0 f x0 f1 x0 while fabs x1 x0 eps 3 弦切法求根 2020 3 26 7 x1 3 do x0 x1 x1 x0 b x0 f b f x0 f x0 while fabs x1 x0 eps 字符图形 2020 3 26 8 for i 1 i 行数 i for j 1 j 第i行首字符位置 j printf for j 1 j 第i行字符个数 j printf a i j printf n 变形 1 如果图形是左对齐 则第二行可删去 2 如果图形不是左对齐 首先左对齐 再计算相关参数 冒泡排序 升序 2020 3 26 9 for i 0 ia j 1 交换a j a j 1 变形 1 降序 2 每一轮求最小者 3 当某一轮已有序 终止排序过程 4 效率最低的排序 5 每一轮只比较一次 被比较的两个数始终相邻 选择排序 升序 2020 3 26 10 for i 0 ia j 交换a i a j 每轮和同一个数比较 插入排序 升序 2020 3 26 11 for i 0 im break if i n 1 a n 1 m elsefor j n 1 j i i a j a j 1 a i m 归并排序 升序 2020 3 26 12 while ib j c k b j else c k a i c k b j if i n for i j 1 i m i c k b i elsefor j i 1 j n j c k a j a升序 b升序 c升序 n m 二维数组排序 降序 main ints t l no 30 j k p 30 floata 30 6 for j 0 j 30 j p j j 序号赋初值 for j 0 j 30 j scanf d 第J个人的平均分 30个学生5门成绩 30个学生的编号 30个学生的成绩排序 根据平均成绩排序 for j 0 j 29 j 变形的选择排序 l j 每轮只交换一次 for k j 1 k 30 k if a p l 5 a p k 5 l k t p j p j p l p l t for k 0 k 30 k for j 0 j 6 j printf 4d 4 1f no p k a p k j printf n 字符串排序 10个串 每个串小于10个字符 include string h main chara 100 str 10 sp inti k char temp sp a 难点 for i 0 i 10 i printf Inputastring 9character gets sp str i sp sp 10 10个字符串都放在数组a中每个串的首地址放在字符指针数组str中 aaa bbb ccc 降序排列 for k 0 k 9 k for i k 1 i 10 i if strcmp str i str k 0 temp str i str i str k str k temp 尽量少用strcpy for i 0 i 10 i puts str i str 0 指向最大的串 str 1 指向第二大的串 二分查找 假设a升序 方法1 left 0 right n 1 p 0 while right left mid right left 2 if a mid m p 1 break 找到 if a mid m left mid elseright mid if p 找到 else 没找到 2 3 9 10 12 15 17 19 100 left right mid 二分查找 假设a升序 方法2 递归算法intfind intleft intright intm intmid mid right left 2 if a mid m return1 找到 if left right return0 没找到 if a mid m find mid right m lsefind left mid m 求鞍点 行上最大列上最小 for p 1 i 0 imin p 0 break 注意 1 n n矩阵主要边线的方程 2 矩阵的输入和输出 a m n 矩阵乘法 for i 0 i n i for j 0 j n j c i j 0 for k 0 k n k c i j a i k b k j 扩展 1 矩阵转置 b i j a j i 2 矩阵加法 c i j a i j b i j b a c i j 长整数加 乘 for d 0 i n i 0 i for j m j 0 j c k a i b j d if c k 10 d c k 10 c k c k 10 k a b c 梯形法求积分 方法1 函数名不是形参h b a n for s f a f b 2 i 1 i n i s f a i h s s h a b i a i h f1 h f2 h f2 h f1 f2 f3 h 梯形法求积分 方法2 函数名是形参floatinteger float f floata floatb intn floath s inti h b a n for s f a f b 2 i 1 i n i s f a i h s s h 1 矩形法求定积分 2 辛普森法求定积分 指向函数的指针变量 方法1 t x k 1 s 0 while fabs t eps s t t t x k 方法2 t x s 0 k 1 while fabs t eps s t m 1 n 1 k for i 1 i k i m m i n n x t m n m n t 扩展 回文数 m为字符串 p 1 left 0 right strlen m while left right if m left m right p 0 a b c b a left right m 回文数 m为数 a m n 0 while a 0 n n 10 a 10 a a 10 if m n 回文数 m 12321m 12345 回文数 指针法 main chars 81 pi pj inti j n gets s pi s n strlen s pj s n 或while s 0 pj s while pi pj a b c b a pi pj 魔方 n2个数放在n n矩阵中 使行和 列和 对角线上数字和都相等 求一行字符串中单词个数 以 结束 word 0 n 0 while s 0 if s s s s s s 最长单词 include string h main intword 0 n 0 len 0 lenmax 0 i 0 charstr 10 strmax s gets s 最长单词 while s 0 if s len str i s if word 0 n word 1 else word 0 str i 0 i 0 if len lenmax strcpy strmax str lenmax len len 0 puts strmax 最长串 改错 include stdio h chara 100 intn i big f t testword intj k charc s 26 j i k 0 while a i a 最长串 改错 main intn 1 do n a n getchar while a n getchar big 0 j 1 while i a 最长串 改错 include stdio h main inti maxlen len charinline 10 100 maxline 100 FILE fp if fp fopen myf1 out ow NULL EXIT 1 for i 0 i 10 i gets inline i fprintf fp s n inline i 最长串 改错 maxlen 0 for i 0 imaxlen strcpy maxline inline i maxlen len fprintf fp maxstringis s nmaclen d n maxline maxlen fclose fp strlenth charp intlen len 0 while p len 0 len 链表的建立 建立链表 返回链表头指针 当链表的值域为 999时 建立链表过程结束 输出变量 h指向链表头 输入变量 q指向新分配结点 辅助变量 p指向链表尾 主要思路 1 p next q 2 p q 3 scanf d p q q p p q 40 p 40 q 说明 1 主函数改为子函数 返回链表头指针 structstudent creat return h 2 用typedefstructstudent REC 可把q structstudent malloc sizeof structstudent 缩写为