分类 算法 下的文章

最大公约数


更相减损术

更相减损术, 出自于中国古代的《九章算术》,是一种求最大公约数的算法。

20161014092205.png

它的原理是:两个正整数a和b(a>b),它们的最大公约数等于a-b的差值c和较小数b的最大公约数。

//更相减损法
int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b -a;
    }
    return a;
}

当两数相差较大是,比如1和100000,那它就要循环99999次。


python练习


其实有很多这样的活动都有一个相同的模式:N 种人物卡片,每次买一包干脆面随机得到一张。当你集齐这 N 种人物时,就会有相应的奖励。 那时候还不懂怎么计算概率,白白给人家送了好多钱,吃了好多干脆面。 现在的任务是,给你一个正整数 N (1 <= N <= 10^4),请你帮我从期望的角度计算平均需要买多少包干脆面才能集齐这 N 种人物。 提醒:由于结果可能不是整数,所以结果只保留到小数点后两位。