C++编程:折半查找与辗转相除法实现

需积分: 9 5 下载量 57 浏览量 更新于2024-07-28 收藏 81KB DOC 举报
"C++程序实例,包括折半查找法和辗转相除法求最大公约数与公倍数" 在给定的C++程序实例中,我们有两个不同的主题:折半查找法(Binary Search)和辗转相除法(Euclidean Algorithm)。 首先,折半查找法是一种在已排序的数组中查找特定元素的有效方法。在这个实例中,程序接收一个排序好的整数数组和一个待查找的数值。它通过设置两个指针,`low` 和 `high`,来划定搜索范围。在每次循环中,计算中间值 `mid`,然后根据待查找的数值 `x` 与中间值的比较结果来更新搜索区间。如果 `x` 大于 `mid`,则将搜索区间移到 `mid` 的右边;反之,如果 `x` 小于 `mid`,则搜索区间移到左边。如果找到目标值,返回其索引;否则,在找不到时返回 -1。这种方法的时间复杂度为 O(log n),因为每次迭代都将搜索范围减半。 接下来,第二个程序涉及的是辗转相除法,这是一种古老的求解两个正整数最大公约数(Greatest Common Divisor, GCD)的方法。首先,用户输入两个整数 `m` 和 `n`。程序通过不断用较小的数去除较大的数,直到余数为0,此时较小的数即为最大公约数。同时,两个原始数的乘积除以最大公约数得到最小公倍数(Least Common Multiple, LCM)。这种方法在《九章算术》中已有记载,被称为“更相减损”法。对于给定的52317和75569这两个数,使用辗转相除法,我们可以快速地找到它们的最大公约数。 辗转相除法的基本步骤如下: 1. 如果 `m > n`,则交换 `m` 和 `n`,确保 `m <= n`。 2. 使用 `m` 除以 `n` 得到余数 `r`。 3. 如果 `r` 为0,则 `n` 是最大公约数。 4. 如果 `r` 不为0,重复步骤2和3,用 `n` 除以 `r`,更新 `m` 和 `n`。 因此,通过这个程序,我们可以轻松地找出任意两个整数的最大公约数和最小公倍数。 这两个C++程序展示了数据搜索和数论算法在实际编程中的应用。折半查找法用于高效地定位有序数组中的元素,而辗转相除法则是求解整数最大公约数的经典算法。这些基础知识对于理解算法和数据结构以及优化代码性能至关重要。