算法设计与分析第四章作业
2021/5/20 22:54:42
本文主要是介绍算法设计与分析第四章作业,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法设计与分析第四章作业
(1)
求2+22+222+2222+…+22…22(不考虑精度)
#include <iostream> typedef long long LL; using namespace std; //快速幂 LL FastPower(LL m,LL n){ if(n==0) return 1; LL res=FastPower(m,n>>1); if(n&1) return res*res*m;//奇数就平方再乘以底数 else return res*res;//偶数就平方 } int main(){ LL n; cin>>n; //求和公式 cout<<(20*(FastPower(10,n)-1)-n)/81<<endl; return 0; }
时间复杂度:O(log n);
(7)
有一堆棋子,2枚2枚地数,最后余1枚;3枚3枚地数,最后余2枚;5枚5枚的数,最后余4枚;6枚6枚地数,最后余5枚;只有7枚7枚地数,最后正好数完。求这堆棋子最少有多少棋子。
分析
- 最小公倍数=两整数的乘积÷最大公约数
- 2枚2枚的数,最后余1枚,故该棋子是奇数。
- 棋子个数+1是2,、3、5、6的公倍数,故为5、6的公倍数。
- 5、6的最小公倍数是30。
- 棋子个数是7的公倍数。
综上所知,棋子数n+1是30的公倍数,n是7的公倍数
#include<iostream> using namespace std; //Greatest Common Divisor,GCD //Least Common Multiple, LCM //欧几里得算法:gcd(a,b)=gcd(b,a%b) int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } //算术基本定理得到gcd(a,b)*lcm(a,b)=a*b int lcm(int a,int b){ return a*b/gcd(a,b); } int main(){ int t=lcm(6,lcm(5,lcm(2,3))); while(1){ if((t-1)%7==0){cout<<t<<endl;break;} t*=2; } }
(9)
利用分治法求一组数中最大的两个数和最小的两个数
这篇关于算法设计与分析第四章作业的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01为什么公共事业机构会偏爱 TiDB :TiDB 数据库在某省妇幼健康管理系统的应用
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署