分数(蓝桥杯2018第一题)

题目

    1/1+1/2+1/4+1/8+...

    每项是前一项的一半，如果一共有 20项,求这个和是多少，结果用分数表示出来。

    类似：3/2，当然，这只是加了前 2 项而已。分子分母要求互质。

思路

    ②等比数列公式（幂级数），求最大公约数

    ③快速幂运算，求最大公约数

求最大公约数公共代码方法一：

#include <iostream>
using namespace std;
int measure(int x, int y)
{	
	int z = y;
	while(x%y!=0)
	{
		z = x%y;
		cout<<z<<endl;
		x = y;
		y = z;	
	}
	return z;
}

int main()
{
    
    int max = measure(12,5);
    std::cout << max << std::endl;
    return 0;
}

求最大公约数公共代码方法二(递归)：

#include <iostream>
using namespace std;
int measure(int x, int y)
{	
	if(y==0) return x;
	return measure(y,x%y);
}

int main()
{
    
    int max = measure(12,4);
    std::cout << max << std::endl;
    return 0;
}

代码一：使用函数库求幂

#include <iostream>
#include<math.h>
using namespace std;
int main()
{
  long  numerator = pow(2,20)- 1;
  long denominator = pow(2,19);
  cout<<numerator<<"/"<<denominator<<endl;
  return 0;
}

代码二：快速幂运算实现pow()

#include <iostream>
using namespace std;

int measure(int x, int y)
{	
	if(y==0) return x;
	return measure(y,x%y);
}

int pow_f(int base_num,int y){
    int res = 1;
    int x = base_num;
    while(y > 0){
        if(y&1){
            res *= x;
        }
        y>>=1;
        x *=x;
    }
    return res;
    
}

int main()
{
    int gcd = measure(pow_f(2,20)-1,pow_f(2,19));
    if(gcd == 1){
        cout<<pow_f(2,20)-1<<"/"<<pow_f(2,19)<<endl;
    }
    else{
        cout<<(pow_f(2,20)-1) / gcd<<"/"<<pow_f(2,19) / gcd<<endl;
    }
    
    
    return 0;
}