算法学习笔记之数学基础

例1（最小公倍数与最大公约数）

计算最小公倍数

公式：
LCM(A,B) = A*B/GCD(A,B)

A与B的最小公倍数等于A*B除以A与B的最大公约数

计算最大公约数：辗转相除法

原理：设A与B的最大公约数为x，则A是x的倍数，B也是x的倍数，令A=ax，B=bx，A/B取整为c，则A-cB=(a-bc)x。即A与B的余数也是x的倍数

 int gcd(int a, int b)
 {
     int temp;
     while(b != 0)
     {
         temp = a % b;
         a = b;
         b = temp;
     }
     retrun a;
 }

例2（找规律）

寻找个位数的循环

例3（找规律）

F(n)%3 = (F(n-1)+F(n-2))%3 = F(n-1)%3+F(n-2) %3

可以通过上面的公式找循环：

n	1	2	3	4	5	6	7	8	9
f(n)%3	1	2	0	2	2	1	0	1	1

例4（快速幂）

快速幂递归代码

 int power(int a, int n)
 {
     int ans;
     if(n==0) ans = 1; // 结束条件
     else
     {
         ans = power(a*a, n/2)  // 递归调用
         if(n%2==1) ans*=a;  // n为奇数
     }
     return ans;
 }

快速幂循环代码

 int power(int a, int n)
 {
     int ans = 1;
     while(n)
     {
         if(n%2) ans = ans*a; // 奇数情况
         a = a*a; // 底数平方
         n=n/2; // 指数减半
     }
     return ans;
 }

例5（二分查找）

前提：数据有序

二分循环代码

 int BiSearch(int a[], int n, int x)
 {
     int left=1, right=n-1;
     while(left<=right)      // 注意=不能少
     {
         int middle = (left+right)/2;    // 整数除法
         
         if(a[middle] == x)    // 找到了
             return middle;
         if(x > a[middle])    // 如果比中值大
             left=middle+1;
         else                 // 如果比中值小
             right = middle-1;
     }
     return -1;
 }

二分递归代码

 int BiSearch(int a[], int x, int left, int right)
 {
     if(left > right)
         return -1;
     else
     {
         int mid = (left+right)/2;
         if(a[mid] == x)
             return mid;
         else if(x > a[mid])
             return BiSearch(a, x, mid+1, right)
         else if(x < a[mid])
             return BiSearch(a, x, left, mid-1)
     }
 }

例6（二分小数）

参考代码

 #include<iostream>
 #include<cmath>
 using namespace std;
 
 double Y;
 
 
 double f(double x)
 {
     return 8*pow(x, 4.0) + 7 * pow(x, 3.0) + 2*pow(x, 2.0) + 3*x + 6;
 }
 
 int main()
 {
     int t;
     double left, right, mid;
     scanf("%d", &t);
     while(t--)
     {
         scanf("%lf", &Y);
         if (f(0) <= Y && Y <= f(100))
         {
             left = 0;
             right = 100;
             while(right - left > 1e-6)
             {
                 mid = (left + right) / 2;
                 double ans = f(mid);
                 if (ans > Y)
                     right = mid - 1e-7;
                 else 
                     left = mid + 1e-7; 
             }
             printf("%.4f\n", (left+right)/2);
         }
         else
             printf("No solution!\n");
     }
     return 0;
 }