分数(蓝桥杯省赛2018C/C++A组第一题)
2022/2/4 17:12:27
本文主要是介绍分数(蓝桥杯省赛2018C/C++A组第一题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:
1/1+1/2+1/4+1/8+…
每项是前一项的一半,如果一共有20项,求这个和是多少,结果用分数表示出来。
类似:3/2,当然,这只是加了前 2 项而已。分子分母要求互质。
思路:
- 仅题目而言,根据观察得出该分数相加符合等比公式求和,故使用等比公式求和可将原式化简为(2^20 -1) / (2
^19),即可将求和问题转化成幂运算进行求解。 - 题目还要求互质,根据数学知识可转化成最大公约数的问题,求解最大公约数可用辗转相除法就行求解。
代码:
#include<iostream> #include<cmath> using namespace std; //使用辗转相除法求两个数的最大公约数两种方法 int maxgcd(int a,int b){ while(a % b != 0){ int temp = a % b; a = b; b = temp; } return b; } int maxgcd1(int a,int b){ if(a % b == 0) return b; return maxgcd1(b,a%b); } //实现快速指数运算 int pow_f(int x,int y){ int base_x = x; int res = 1; if(y == 0) return res; while(y != 0){ //打印y&1 cout<<(y&1)<<endl; if(y & 1 != 0){ res *= base_x; } y>>=1; base_x*=base_x; } return res; } int main() { long long a = pow(2,20) - 1; long long b = pow(2,19); int c = maxgcd(a,b); cout<<a / c<<"/"<<b / c<<endl; return 0; }
总结:
- 等比公式求和
- 通过辗转相除法求最大公约数的两种方法:
①while循环
②递归 - 求幂运算的两种方法:
①调用库函数cmath
②手动实现快速幂运算
这篇关于分数(蓝桥杯省赛2018C/C++A组第一题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享
- 2024-04-14shell 正则判断字符串内是否含有th-icode9专业技术文章分享