本文主要是介绍《算法基础》最大公约数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

1、LeetCode——1979. 找出数组的最大公约数

 2、LeetCode——LCP 02. 分式化简

1、LeetCode——1979. 找出数组的最大公约数

给你一个整数数组 nums ，返回数组中最大数和最小数的 最大公约数 。

两个数的 最大公约数 是能够被两个数整除的最大正整数。

思路：先给数组排好序，然后直接求最大值和最小值的最大公约数

代码及详情：

// qsort排序需要的函数
int cmp(const void* a, const void* b){
    return *(int*)a - *(int*)b;
}
// 求最大公约数函数
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
int findGCD(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);
    int min = nums[0];
    int max = nums[numsSize - 1];

    // 迭代法求公约数
    // while(min){
    //     int t = max % min;
    //     max = min;
    //     min = t;
    // }
    // return max;

    return gcd(min,max);
}

 2、LeetCode——LCP 02. 分式化简

有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？

连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。

输入的cont代表连分数的系数（cont[0]代表上图的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。

 思路：将数组从后往前遍历计算，先计算出通分后的分子，在把分子分母颠倒进行下一次循环计算，最后退出循环时再手动颠倒以下分子分母的位置。

代码及详情：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 // 就是即将要加的整数乘以分母再加上分子，等到加下一个元素的时候，再颠倒一下分子和分母。 
 // 当然了，最后一次执行，分子和分母没有颠倒，所以最后再颠倒一次
int* fraction(int* cont, int contSize, int* returnSize){
    int* ans = (int*)malloc(sizeof(int) * 2);
    int c = 1;  // 分子
    int d = cont[contSize - 1];  // 分母
    for(int i = contSize - 1; i > 0; i--){
        // 计算出同分后的分子，也就是下一次的分母
        c = cont[i - 1] * d + c;
        // 颠倒分母分子
        int temp = c;
        c = d;
        d = temp;
    }
    ans[0] = d;
    ans[1] = c;
    *returnSize = 2;
    return ans;
}

文首图片素材取自博客《算法零基础100讲》(第14讲) 最小公倍数_英雄哪里出来的博客-CSDN博客

这篇关于《算法基础》最大公约数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！