lddongdong
2021-10-14 16:39
采纳率: 88.2%
浏览 147

求“最小公倍数”的算法代码,不理解这段代码的思路

问题描述:编写一函数lcm,求两个正整数的最小公倍数。

#include <stdio.h>
void lcm(int* s, int* b)
{
    *s = *s / *b;
}
main(void)
{
    int a, b, t, s;
    scanf("%d%d", &a, &b);
    s = a * b;
    if (a < b)
    {
        t = a; a = b; b = t;
    }
    while (b)
    {
        t = a % b;
        a = b;
        b = t;
    }
    lcm(&s, &a);
    printf("%d", s);
    return 0;
}

int* s是什么呀?为什么要s = *s / *b;啊?下面为什么又要inta,b,t,s;啊?总之全部都看不明白!希望大家帮我解析一下整个代码。非常感谢大家!

  • 好问题 提建议
  • 收藏

4条回答 默认 最新

  • CSDN专家-link 2021-10-14 16:39
    已采纳

    while循环辗转相除法得到a为最大公约数。lcm是求最小公倍数。最小公倍数=两数乘积除以最小公约数。由于s是a * b,即两数乘积,a是最大公约数,lcm函数用指针作为参数,所以需要 * s, * a获得对应的值进行相除。得到的结果记录到s返回,再printf输出

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • lddongdong 2021-10-14 23:15

    就是感觉lcm(&s, &a)中的&a和void lcm(int* s, int* b)中的int* b对不上

    评论
    解决 无用
    打赏 举报
  • 爱晚乏客游 2021-10-15 09:11

    辗转相除法,一个求大公约数的方法,证明方法可以看看度娘,一时半会不好说。


    11行的if可以保证a>b
    下面的while循环就是辗转相除法,循环结束之后a就是最大公约数。
    lcm的作用就是求最小公倍数,这个直接举例来说。比如15和21的最小公倍数,最大公约数为3,最小公倍数就是15x21/3=105。
    原理就是105=3x7x5,15=5x3,21=3x7,公约数为3(所以约去一个3就是最小倍数)。s=s/a=21x15/3=3x5x3x7=3x5x7。

    评论
    解决 无用
    打赏 举报
  • Gaim_ 2021-10-16 11:48

    辗转相除法:辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。

      例如,求(319,377):
      ∵ 319÷377=0(余319)
      ∴(319,377)=(377,319);
      ∵ 377÷319=1(余58)
      ∴(377,319)=(319,58);
      ∵ 319÷58=5(余29)
      ∴ (319,58)=(58,29);
      ∵ 58÷29=2(余0)
      ∴ (58,29)= 29;
      ∴ (319,377)=29。

      用辗转相除法求几个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。最后所得的那个最大公约数,就是所有这些数的最大公约数

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题