教材与实验书指定例题分析及算法总结

排序算法 排序算法 理论书例题 6 6 或或理论书例题 7 8 补充题完善程序 7 题或或补充题完善程序 12 题 选择排序选择排序 进行 N 1 轮扫描 1 N 1 第 i 轮扫描确定第 i 位 i 从 1 到 N 1 第 i 轮扫描为 第 i 位逐个和后面的第 j 位 j i 1 N 比较 不符合要求顺序则 交换 该轮比较 N i 次 N 1 轮扫描结束 排序完成 选择排序法选择排序法对数组元素进行降序排序降序排序的排序函数 Private Sub sort a As Integer Dim i As Integer j As Integer temp As Integer For i 1 To 9 对于 n 个元素的数组共需排前 n 1 个位置 For j i 1 To 10 排第 i 位置 需将 a i 和后面 n i 个数比较 不符合顺序就交 换 If a i a j Then temp a i 典型两数交换算法 借助辅助变量 temp a i a j a j temp End If Next j Next i End Sub 向后冒泡排序向后冒泡排序 进行 N 1 轮扫描 1 N 1 第 i 轮扫描确定倒数第 i 位 即第 N 1 i 第 i 轮扫描为 1 前面 N i 个数逐个和自己的后紧邻位两两比较 不符合要求顺 序则交换 即 A j 和 A j 1 比较 j 从 1 到 N i 该轮比较 N i 次 N 1 轮扫描结束 排序完成 For i 1 To n 1 对于 n 个元素的数组共需进行 N 1 轮扫描排 n 1 个位置 第 i 轮扫描确定倒数第倒数第 i 位位 即第 N 1 i For j 1 To n i 排倒数第倒数第 i 位位 需将从 a i 前面 n i 个元素 从 a 1 到 a n i 进行 两两相邻比较 不符合顺序要求就交换 If a j n 2 m 除以 n 得余数 r 3 若 r 0 则 n 为求得的最大公约数 算法结束 否则执行 4 4 m n n r 再重复执行 2 例如 求 m 14 n 6 的最大公约数 m n r 14 6 2 6 2 0 m inputBox m 用 inputbox 函数输入两个数 m n 并保证 m n 否则交换 n inputBox n If m n Then t m m n n t r m mod n 第一次 m 除以 n 如果写成补充题完善程序 14 题那样就不需要此次除 法 因为它的 While r 0 在下面 先执行后判断 Do While r 0 当最后一次除法得到的余数 r 为 0 时 循环停止 m n 除数 n 作为新的被除数 m 余数 r 作为新的除数 n 进行下一轮除法 n r r m mod n Loop Print 最大公约数 n 最后一轮除法的除数 n 作为最大公约数 注意与理论书例 题 5 3 和补充题完善程序 14 题的区别 那两程序输出的是 m 区别是因为循环体中 m n n r 语句与 r m mod n 语句 交换了顺序导致 最大公约数函数最大公约数函数 理论书例题 7 3 写法请参考理论书 P134 页和补充题完善程序 14 题的 详细注释详细注释 这两题雷同 采用了最大公约数函数写法 最大公约数函数 递归形式 最大公约数函数 递归形式 写法请参考理论书 P161 页理论书例题 7 11 不太重要 求最大公约数递归函数 Private Function Gcd ByVal X As Long ByVal Y As Long 参数皆为传值方式 Dim R As Long R X Mod Y X 除以 Y If R 0 Then 递归终止条件 得到的余数 r 为 0 时 除数 Y 作为公约数 GCD Gcd Y Else 递归内容 除数 Y 作为新的被除数 X 余数 r 作为新的除数 Y 递归调用函数本身进行下一轮除法 X Y Y R Gcd Gcd X Y End If End Function 实验书 10 4 用最大公约数递归算法求出最大公约数 然后分子分母同除以最大公约数来 约分约分 最小公倍数算法 最小公倍数算法 实验书 9 4 或或理论书例题 7 5 解法一 解法一 最小公倍数最小公倍数 两个整数之积两个整数之积 最大公约数最大公约数 m inputBox m n inputBox n nm n m 求 n 和 m 的乘积赋给 nm 变量 If m n Then t m m n n t r m mod n Do While r 0 m n n r r m mod n Loop Print 最大公约数 n Print 最小公倍数 nm n 用 n 和 m 的乘积除以最大公约数 n 得到最小公倍数 解法二解法二 理论书例题 7 5 Private Function LCM ByVal x As Integer ByVal y As Integer 参数皆为传值方式 Dim m As Long flg As Boolean flg False 公倍数找到标识公倍数找到标识 开始设为假 Do Until flg m m x m 为 x 的倍变量 从 1 倍加起 If m Mod y 0 Then 若 m k 倍 x 能整除 y 则设找到公倍数标识为真 停止循环 flg True 否则继续循环 m k 1 x 再做除法 End If Loop LCM m 能整除 y 的 x 的倍数 m 赋给最小公倍数变量 End Function 另外 实验书 9 4 用控件数组编最大公约数最小公倍数程序 累加与连乘 阶乘算法累加与连乘 阶乘算法 算法说明 累加形式 V V e 连乘形式 V V e 其中 V 是变量 e 是递增表达式 累加和连乘一般通过循环结构来实现 要注意根据问 题确定循环变量的初值 终值或结束条件 更要注意用来表示计数 和 阶乘的变量的初 值 注意 需在执行循环体前对变量 V 赋初值 一般累加时置初值 0 连乘时置初值为 1 累加算法 累加算法 例例 求 1 2 3 100 的累加和 并打印输出 分析 分析 设累加器 S 初值为 0 加数用变量 I 表示 当 I 1 时 累加器 S S I 0 1 1 当 I 2 时 累加器 S S I 1 2 3 当 I 3 时 累加器 S S I 3 3 6 当 I 4 时 累加器 S S I 6 4 10 当 I 100 时 累加器 S S 100 1 2 3 99 100 5050 不难看出 I 的值从 1 变化到 100 的过程中 累加器均执行同一个操作 S S I S S I 的操作执行了 100 次 所以该程序段可写成 Dim I As Integer S As Integer S 0 给累加器 s 赋初值 For S 1 To 100 S S I I 既作为循环变量 又作为加数 Next I Print 1 2 100 S 考虑一下 语句 Print 1 2 100 S 可以放在循环体中吗 当然不可以 连乘 阶乘算法连乘 阶乘算法 理论书 P70 页的例子 5 4 或或理论书 P131 页的例子 7 1 连乘算法的一般做法是定义一个变量 s 作为乘法器即积变量使用 初值为 1 设一个 变量 i 用来保存乘数 举例举例 求阶乘求阶乘 N 的结果的结果 Private Sub Command1 Click Dim n i s n Val InputBox 输入 n s 1 s 为积变量 初值为 1 For i 1 To n 循环 n 次 每次乘以乘数 i 循环变量 i 从 1 到 n s s i Next i Print s 输出积 End Sub 可以参考理论书 P70 页的例子 5 4 求阶乘的算法也可以写成递归形式 递归形式阶乘函数递归形式阶乘函数 理论书 P131 页的例子 7 1 Private Function Fact byval N As Integer As Long 因为在函数中不修改参数 N 可以传值 也可以传址 If N 0 Or N 1 Then 递归结束条件 当 n 0 或 1 直接阶乘函数值 Fact 等于 1 Fact 1 Else n 等于其他值时 采用递归调用函数自身计算 每次乘次小整数阶乘 Fact N Fact N 1 End If End Function 求级数算法 求级数算法 实验书 6 3 或或补充题编程题第 3 题和补充题改错题第 1 题详细注释 连加和连乘算法 特别阶乘算法可以用来求级数求级数 如下面题目 利用下列公式求通项和 S 近似值 规定通项的绝对值 10 6 时结束累加 请参考补充题编程题第 3 题和补充题改错题第 1 题详细注释 另外请参见实验书 6 3 统计算法统计算法 实验书 7 10 如果在编程时需要计算满足某一条件的量有多少个时 就可以采用统计算法 统计算法的 一般做法是定义若干个变量用来作计数器 专门来统计满足相应条件的量 有多少个统计 要求 就定义多少个计数器 在程序设计过程中 分别判断是否满足指定条件 若满足条 件 则指定的计数器加 1 如果计数器太多 而且相互之间有联系时 一般会定义一个计 数器数组 例 在文本框中输入一串字符 统计其中的字母 数字和其他字符的个数 基本思路 基本思路 要统计满足指定要求的字符个数 应定义相应变量 如 n 作为计数器 初值为 0 每找 到符合条件的字符 将指定计数器的值加 1 本题需要定义 3 个计数器 n1 n2 n3 初值为 0 对字符串的字符逐个判断 如果是字 母 n1 加 1 如果是数字 n2 加 1 否则 n3 加 1 Private Sub Command1 Click Dim str As String i As Integer ch As String 1 Dim n1 As Integer n2 As Integer n3 As Integer n1 0 n2 0 n3 0 str Text1 Text For i 1 To Len str 从 str 中取字符处理 循环 str 字符个数 Len str 次 ch Mid str i 1 从 str 中取第 i 个字符 If UCase ch A Then 如果取的是大写字母 n1 n1 1 计数器 n1 加 1 ElseIf ch 0 And ch n 1 Then 如果 i n 1 则前面 for 完整执行完 说明从 2 到 n 1 的平方根都不能 整除 n n 是素数 该条件也可写成 If flag Then MsgBox n 是素数 Else MsgBox n 不是素数 End If End Sub 注意除数到根号 n 即 Sqr n 或 n 2 就可以了 如 Private Function Prime m as Integer As Boolean Dim i Prime True For i 2 To int sqr m If m Mod i 0 Then Prime False Exit For Next i End Function 进制转换算法进制转换算法 实验书实验书 9 7 1 十进制正整数 m 转换为 R 2 16 进制的字符串 思路 将 m 不断除以 r 取余数 商作为新的被除数 m 再做除法 直到商为 0 将余数 反序即得到结果 算法实现 Private Function Tran ByVal m As Integer ByVal r As Integer As String Dim StrDtoR As String n As Integer Do While m o 被除数 m 不为 0 就继续除以 R n m Mod r m 除以 R 得到余数 n m m r m 除以 R 的商作为新的被除数 m If n 9 Then 将余数贴到转化结果字 R 2 16 进制符串 StrDtoR 前面 造成后得到的余数排在前面 反序 StrDtoR Chr 65 n 10 StrDtoR 如果余数超过 9 用字母表示 如 余数 10 转化为 A Else StrDtoR n StrDtoR 如果余数是数字 直接贴 End If Loop Tran StrDtoR End Function 2 R 2 16 进制字符串转换为十进制正整数 思路 R 进制数每位数字乘以权值之和即为十进制数 算法实现 Private Function Tran ByVal s As String ByVal r As Integer As Integer Dim i as Integer n As Integer dec As Integer s UCase Trim s For i 1 To Len s 每次从 R 进制数里面取一个字符处理 If Mid s i 1 A Then 如果字符里有字母转化成 10 进制数 如 A 转化为 10 n Asc Mid s i 1 Asc A 10 Else n Val Mid s i 1 如果字符是数字直接变成数值 End If dec dec n r Len s i 将该字符值 n 乘以该字符 r 进制权值 该字符 r 进制权值 r Len s i Next i Tran dec End Function 字符处理算法 字符处理算法 理论书例题 5 5 或或实验书 6 4 收集逆序输出字符收集逆序输出字符 或或实验书 8 1 加密加密 字符加密字符加密 将输入的原字符串的每个字符按指定的规则进行转换 得到新字符 将每个新字符连接成 新串就可以实现对字符串进行加密 对字符串的每个字符的解密过程与上述相同 只是规则正好与上面的加密规则相反 例 输入一串字母 按以下规则进行加密 将每个原码字母在 A Z A 首尾相连的字母表上 向后移 6 位为译码 如下表所示 原码 ABC XYZ 译码 GHI DEF 1 截取字符串 str 的每个字符