JZTXT

编程题算法总结

发布时间 2023-08-14 14:55:35作者: __Zed

求最大公约数 最小公倍数

最大公约数

辗转相除法

大的a除小的b，得到余数如果是0，那么b就是最大公约数，否则就取余数做那个小的，本来的b就成了大的继续操作。

    int n,m;
    //辗转相除法,ab最大公约数 = ab余数和b的最大公约数
    int yu,a,b;
    a = n>m?n:m;
    b = n>m?m:n;
    while(1)
    {
      yu = a % b;
      if(yu == 0) break;
      a = b;
      b = yu; //已经是余数了，一定比b小
    }
 //b就是

更相减损法

大的a 小的b，a-b=0就找到了，否则a = a-b循环

    int a,b;
    int cal = a*b;
    //更相减损法 ,a = a-b
    while(a!=b)
    {
      if(a>b)
      a = a-b;
      else b = b-a;
    }
 //b就是

最小公倍数

偷懒法

先求最大公约数，由最大公约* 最小公倍数 = a* b

迭乘法

最小公倍数一定是其中某个数的n倍


    int a,b;
    int cal = a*b;
    int i = 1;
    //迭乘法求最小公倍数
    while(a*i%b!=0)
    {
      i++;
    }
//a*i就是

正序数组插值

    int arr[10],x;
    //正序数组和要插入的值
    int i = 8;
    while(i>=0&&arr[i]>x)  //注意从后面开始遍历，移动到后面的那个
    {
        arr[i+1] = arr[i];
        i--;
    }
    arr[i+1] = x;
    for (int i = 0; i < 10; i++)
    {
        printf("%d\n",arr[i]); //打印输出
    }