核桃的数量

一、题目分析

　　这道题目意思很容易明白，解题方法也很简单，就是求三个整数（三个小组的加班人数）的最小公倍数。

二、最小公倍数介绍

　　最小公倍数（Least Common Multiple，缩写 L.C.M.），如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数，b 为 a 的因数，对于两个整数来说，指该两数共有倍数中最小的一个。

　　计算最小公倍数时，通常会借助最大公约数来辅助计算，计算公式如下：

最小公倍数 = 两数的乘积 / 最大公约（因）数

三、最大公约（因）数介绍

　　最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b 的最大公约数记为 (a，b)，同样的，a，b，c 的最大公约数记为 (a，b，c) ，多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。本题我使用的是辗转相除法，下面详细介绍这个算法：

　　设两数为 a、b(a>b)，使用辗转相除法求 a 和 b 最大公约数 (a，b) 的步骤如下：

用 a 除 b，得 a÷b=q......r(0≤r)；
若 r=0，则 (a，b)=b；
若 r≠0，则令 a=b，b=r，返回第一步。

　　实现该算法的程序设计如下：

 1 /*********************************************************************************************************
 2 ** 函数功能 ：得到两个整数的最小公倍数 
 3 ** 函数说明 ：最小公倍数 = 两数的乘积 / 最大公约（因）数，使用辗转相除法求两个整数的最大公约数
 4 ** 入口参数 ：a，b；两个整数 
 5 ** 出口参数 ：两个整数的最小公倍数 
 6 *********************************************************************************************************/
 7 int GreatestCommonDivisor(int a,int b)
 8 {
 9     return a%b==0?b:GreatestCommonDivisor(b,a%b); //辗转相除法 
10 }

四、算法设计

　　先求 a 和 b 的最小公倍数 ab，再求 ab 和 c 的最小公倍数 abc。

五、程序设计

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 //函数声明 
 6 int GreatestCommonDivisor(int a,int b); //得到两个整数的最小公倍数  
 7 
 8 //主函数 
 9 int main()
10 {
11     int a,b,c; //分别用于记录三个小组加班的人数
12     cin>>a>>b>>c; //输入三个整数（三个小组加班的人数） 
13     
14     int ab,abc; //ab：a 和 b 的最小公倍数；abc：ab 和 c 的最小公倍数 
15     ab=a*b/GreatestCommonDivisor(a,b); //得到a 和 b 的最小公倍数
16     abc=ab*c/GreatestCommonDivisor(ab,c); //得到 ab 和 c 的最小公倍数
17     
18     cout<<abc; //输出三个整数的最小公倍数（每袋核桃的数量） 
19     
20     return 0;
21 }
22 
23 /*********************************************************************************************************
24 ** 函数功能 ：得到两个整数的最小公倍数 
25 ** 函数说明 ：最小公倍数 = 两数的乘积 / 最大公约（因）数，使用辗转相除法求两个整数的最大公约数
26 ** 入口参数 ：a，b；两个整数 
27 ** 出口参数 ：两个整数的最小公倍数 
28 *********************************************************************************************************/
29 int GreatestCommonDivisor(int a,int b)
30 {
31     return a%b==0?b:GreatestCommonDivisor(b,a%b); //辗转相除法 
32 }