gcd的使用：完成对1/1+1/2+1/3+…+1/n的和的算法编写

今天闲着无聊写了个算法，要完成的目的是：求出1/1+1/2+1/3+…+1/n的和。废话不多说，代码在这儿：

#include <stdc++.h>
using namespace std;
int a, b = 1, c = 1;
int d=1,e,g;
int gcd(int a,int b) {
  int f=0;
  while (b) {
    f = a%b;
    a = b;
    b = f;
  }
  return a;
}
int main() {
  int gcd(int, int);
  cin >> a ;
  for (int i = 1; i < a;++i) {
    d = d*(b + 1);//确定分母
    if (i > 1) {
      c = c*(b + 1) + e;
    }
    else c = c*(b + 1) + b;//确定分子
    e = d;
    ++b;		
  }
  g = gcd(c, d);
  c = c / g;
  d = d / g;
  printf("%d\n", c);
  printf("——\n");
  printf("%d", d);
  system("pause");
}

首先让我们来理清一下思路，平时我们在运算1/1+1/2+1/3时是不是先把它们的分母化成一样，怎么化呢？就是前一项的分母乘以后一项的分母，后一项的分母乘以前一项的分母，转换成代码就是：

d = d*(b + 1);//确定分母

因为我们永远是从1/1开始加的，所以第一项的分母一定是1，第二项的分母呢一定是前一项再加1，所以就是d*(b+1),然后将新的分母的值储存起来。

解决完分母再解决分子，分子较分母会困难一点，我们在运算的时候是不是前一项的分子乘以后一项的分母，后一项的分子乘以前一项的分母，那么代码就是：

if (i > 1) {
  c = c*(b + 1) + e;
}
else c = c*(b + 1) + b;//确定分子
e = d;

解决完分母分子后还有一件事我们要完成，那就是约分，约分就是找到他们的最大公因数，普遍的方法呢就是用碾转相除法，解释一下：如果要找出a,b的最大公因数，那么我们就只要先让a除以b，我们会得到一个余数，然后再让b除以余数，我们又会得到一个余数，接着让上一次得到的余数除以这一次得到的余数我们就又会得到一个余数，直到余数为0后我们最后得出来的值就是最大公约数，转换成代码就是：

int gcd(int a,int b) {
  int f=0;
  while (b) {
    f = a%b;
    a = b;
    b = f;
  }
  return a;
}

到这里我们算法就写完了，让我们随便来运行一下；

 

可以看到答案是正确的。