全国青少年信息学奥林匹克竞赛（信奥赛）备考实战之循环结构（while循环应用）
实战训练1—求最大公约数
问题描述：
给定两个正整数，求它们的最大公约数。
输入格式：
输入一行，包含两个正整数。
输出格式：
输出一行，包含gcd=+正整数，即这两个正整数的最大公约数。
输入输出样例：
| 输入样例1 | 输出样例1 |
|---|---|
| 6 9 | gcd=3 |
| 输入样例2 | 输出样例2 |
| 48 24 | gcd=24 |
问题分析：
最大公约数（Greatest Common Divisor, GCD），是数学中的一个基本概念，用于描述两个或多个整数共有的最大的那个正整数约数。在数论、代数以及计算机科学等多个领域中，最大公约数都扮演着重要的角色。对于任意两个正整数a和b，如果存在一个正整数d，使得d能够同时整除a和b，即存在整数m和n，使得a = md且b = nd，那么我们就说d是a和b的一个公约数。在所有能够同时整除a和b的正整数中，最大的那一个被称为a和b的最大公约数，记作gcd(a, b)。
求两个整数的最大公约数（Greatest Common Divisor, GCD），辗转相除法（也称欧几里得算法）是一种高效且简洁的解决方案。下面将介绍辗转相除法的基本原理，并通过C++代码实现这一过程，以便更好地理解算法的核心逻辑。辗转相除法的具体步骤为：
1、输入两个整数a和b：假设a和b为非负整数，且a >= b。如果a < b，可以交换a和b的位置，因为最大公约数是对称的，即gcd(a, b) = gcd(b, a)。
2、计算余数：计算a除以b的余数r，即r = a % b。
3、更新数值：如果r不为0，则将a的值更新为b，将b的值更新为r的值
4、重复步骤2和3：直到r为0时停止。此时b的值即为所求的最大公约数。
具体程序代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;//定义两个整数变量a和b
cin>>a>>b;//输入a和b的值
if(a<b){//如果a的值小于b的值则交换a和b
int tmp = a;
a = b;
b = tmp;
}
int r=a%b;//计算a对b取余的值
while(r!=0){//如果余数不为0
a=b;//将a的值更新为b
b=r;//将b的值更新为r
r=a%b;//重新计算a对b的余数
}
cout<<"gcd="<<b<<endl;//输出最大公约数
return 0;
}
如果题目修改为求最小公倍数，又该如何用C++实现呢？
问题分析：求两个或多个整数的最小公倍数，是指能被这些整数同时整除的最小的正整数。与最大公约数（GCD）的关系：最小公倍数与最大公约数之间存在紧密的数学关系。对于任意两个正整数a和b，它们的最小公倍数LCM(a, b)与最大公约数GCD(a, b)的乘积等于a和b的乘积，即：LCM(a, b) * GCD(a, b) = a * b，由此，我们可以推导出计算最小公倍数的一个简便公式：LCM(a, b) = (a * b) / GCD(a, b)，具体实现步骤为：首先输入两个正整数a和b；使用辗转相除算法或其他方法计算a和b的最大公约数；利用上述公式计算LCM，通过a、b和它们的GCD来计算最小公倍数；最后输出计算得到的最小公倍数。具体程序代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;//定义两个整数变量a和b
cin>>a>>b;//输入a和b的值
if(a<b){//如果a的值小于b的值则交换a和b
int tmp = a;
a = b;
b = tmp;
}
int a1=a,b1=b;//求最大公约数时，a和b的值会发生变化，所以将a和b最初的值记录下来，赋值给a1和b1
int r=a%b;//计算a对b取余的值
while(r!=0){//如果余数不为0
a=b;//将a的值更新为b
b=r;//将b的值更新为r
r=a%b;//重新计算a对b的余数
}
cout<<(a1*b1)/b<<endl;//输出最小公倍数49
return 0;
}
实战训练2—斐波那契数列
问题描述：
斐波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。给出一个正整数 k，要求斐波那契数列中第 k 个数是多少。
输入格式：
输入一行，包含一个正整数k（1<=k<=46）。
输出格式：
输出一行，包含一个正整数，表示斐波那契数列中第k个数的大小。
输入输出样例：
| 输入样例1 | 输出样例1 |
|---|---|
| 2 | 1 |
| 输入样例2 | 输出样例2 |
| 20 | 6765 |
问题分析：
根据题意，要计算第k个斐波那契数列的值，首先初始化两个变量来存储斐波那契数列的前两个数fb1、fb2，这两个数的值为1；如果k的值小于等于2，那么直接输出1，因为斐波那契数列的前两个数都是1；对于k大于2的情况时，使用一个计数器变量来控制循环的次数（需要注意，由于已经知道斐波那契数列的前两项值，所以计数器的初始值为3），直到达到所需的斐波那契数位置；在每次循环中，计算下一个斐波那契数，并更新存储前两个数的变量；当计数器达到k时，输出当前的斐波那契数，具体程序代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
int k;//首先定义第k小数变量
cin>>k;//输入k的值；
int fb1=1,fb2=1;//首先定义前两个数变量fb1、fb2，并将这两个数初始化为1
if(k<=2){//如果k的值小于等于2
cout<<1<<endl;//那么直接输出1
}else{//如果k的值大于等于3
int sum = 3;//定义计数器变量sum，记录斐波那契数列计算到第几小
while(sum<=k){//当sum<=k时，则执行循环体
int tmp = fb1+fb2;//计算斐波那契变量的后一个值tmp
fb1 = fb2;//并将fb2值赋值为fb1
fb2 = tmp; //fb2的值赋值为tmp
sum++;//计数器自增运算
}
cout<<fb2<<endl;//输出第k小的斐波那契值
}
return 0;
}