作者：打酱油的伦 | 来源：互联网 | 2023-02-06 05:30
一、对分查找给定一个整数X和A0，A1，A2，，AN-1，后者已排序，求使得AiX的下标i，如果X不在数据中，则返回i-1。分析：首先数据已经排序，那么取中间元素与X进行比较，若相等则返
一、对分查找
给定一个整数X和A0，A1，A2，...，AN-1，后者已排序，求使得Ai=X的下标i，如果X不在数据中，则返回 i=-1 。
分析：首先数据已经排序，那么取中间元素与X进行比较，若相等则返回下标；若不相等则比较其大小以确定搜索区域。
第二种采用递归方法查找。
1 int binarySearch(const ElementType A[], ElementType X, int N)
2 {
3 int left, mid, right;
4 left = 0; right = N-1;
5 while(left <= right)
6 {
7 mid = (left + right)/2;
8 if(X < A[mid])
9 right = mid-1;
10 else
11 if(X > A[mid])
12 left = mid+1;
13 else
14 return mid;
15 }
16 return notFound;
17 }
int binarySearch(const ElementType A[], ElementType X, int left, int right)
{
int left, mid, right;
left = 0; right = N-1;
mid = (left + right)/2;
if(X < A[mid])
right = mid-1;
else
if(X > A[mid])
left = mid+1;
else
return mid;
binarySreach(A, X, left ,right)
return notFound;
}
二、最大公因数，最小公倍数
最小公倍数*最大公因数=因数1*因数2；
欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。
定理：两个整数的最大公约数等于其中较小的那个数和两数的相除后余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。
gcd(a,b) = gcd(b,r) (不妨设a>b 且r=a mod b ,r不为0)
int gcd(int m, int n)
{
int tem;
while(n >0)
{
tem = m % n;
m = n;
n = tem;
}
return m;
}
#include // std::swap for c++ before c++11
#include // std::swap for c++ since c++11
int gcd(int a，int b)
{
if (a < b)
std::swap(a, b);
return b == 0 ? a : gcd(b, a % b);
}
最小公倍数：
int LCM(int a,int b)
{
int temp_lcm;
temp_lcm=a*b/GCD(a,b);//最小公倍数等于两数之积除以最大公约数
return temp_lcm;
}
三、求幂
3.1递归法
long power(long X, unsigned int N)
{
if(N == 0)
return 1;
if(N%2 == 0)
return power(X*X, N/2);
else
return power(X*X, N/2)*X;
}
3.2非递归法（收藏：利用二进制非递归求幂）
其中n为二进制，反转二进制求法：
REVERSE_BINARY(n)
1 while (n > 0)
2 do output (n mod 2)
3 n ← n / 2
6输出011，需要倒序输出为110.
NumberType optimized_pow_n(NumberType x, unsigned int n)
{
NumberType pw = 1;
while (n > 0) {
if (n & 1) // n & 1 等价于 (n % 2) == 1
pw *= x;
x *= x;
n >>= 1; // n >>= 1 等价于 n /= 2
}
return pw;
}
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 
