C++基础编程 最大公约数问题

题目描述
									
小赛经常沉迷于网络游戏。有一次，他在玩一个打怪升级的游戏，他的角色的初始能力值为a。在接下来的一段时间内，他将会依次遇见n个怪物，每个怪物的防御力为b1,b2,b3,…bn。如果遇到的怪物防御力bi小于等于小赛的当前能力值c，那么他就能轻松打败怪物，并且使得自己的能力值增加bi；如果bi大于c，那他也能打败怪物，但他的能力值只能增加bi与c的最大公约数。那么问题来了，在一系列的锻炼后，小赛的最终能力值为多少？

#include<iostream>
using namespace std;


int greatest_common_divisor(int a, int b)
{
if (a<b)
swap(a, b);
while (b != 0) {
int c = a %b;
a = b;
b = c;
}
return a;
}


int main()
{
long long  n, a;
int b[100000];


while (cin >> n >> a)
{
int i = 0;
while (i < n)
{
cin >> b[i];
i++;
}
i = 0;
while (i < n)
{
if (b[i] <= a)
a = a + b[i];
else
a = a + greatest_common_divisor(a, b[i]);
i++;
}
cout << a<<endl;
}

}

编程笔记:

本题比较基础，最主要的难点在于求出两个数的最大公约数。

求最大公约数的最简单办法是 使用for循环从1到min（a，b）找到所有的公约数。不过这样的方法无用功太多，时间复杂度太高。在当min（a，b）很大时可能会超时。

所以这里介绍一种辗转相除法。

辗转相除法

例1 。求两个正数8251和6105的最大公因数。

（分析：辗转相除→余数为零→得到结果）

解：8251＝6105×1＋2146

显然8251与6105的最大公因数也必是2146的因数，同样6105与2146的公因数也必是8251的因数，所以8251与6105的最大公因数也是6105与2146的最大公因数。

6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

则37为8251与6105的最大公因数。

以上我们求最大公因数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。

1． 为什么用这个算法能得到两个数的最大公因数？

利用辗转相除法求最大公因数的步骤如下：

第一步：用较大的数m除以较小的数n得到一个商q₀和一个余数r₀；

第二步：若r₀＝0，则n为m，n的最大公因数；若r₀≠0，则用除数n除以余数r₀得到一个商q₁和一个余数r₁；

第三步：若r₁＝0，则r₁为m，n的最大公因数；若r₁≠0，则用除数r₀除以余数r₁得到一个商q₂和一个余数r₂；

……

依次计算直至r_n＝0，此时所得到的r_n－1即为所求的最大公因数。

其c++代码实现 就是代码中的函数：

int greatest_common_divisor(int a, int b)

参考资料；

http://blog.csdn.net/thisispan/article/details/7458182

最后

以上就是瘦瘦花瓣为你收集整理的C++基础编程 最大公约数问题的全部内容，希望文章能够帮你解决C++基础编程 最大公约数问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。