(算法)精确表示小数
算法 表示 小数 精确
2023-09-14 09:00:35 时间
题目:
给定一个正整数n,求1/n的小数表示,如:
1/2=0.5
1/3=0.(3)
1/6=0.1(6)
1/7=0.(142857)
其中括号表示小数中的循环部分。
思路:
考虑一下除法运算的过程:
当余数与之前运算出现重复时,那么说明循环已经开始,因此可以通过hash表来记录余数对应的位置。
被除数 除数 余数 商
1 7 1 0
1*10 7 3 1
3*10 7 2 4
2*10 7 6 2
6*10 7 4 8
4*10 7 5 5
5*10 7 1 7
1*10 7 3 1
3*10 7 2 4
2*10 7 6 2
6*10 7 4 8
4*10 7 5 5
5*10 7 1 7
代码:
#include<iostream> #include<map> #include<sstream> using namespace std; string decimalRepresent(int n){ map<int,int> mp; int num=10; int residue=1; string multi; int idx=0; while(mp.find(residue)==mp.end()){ if(residue==0){ stringstream ss; string tmp; ss<<1.0/n; ss>>tmp; return tmp; } mp[residue]=idx; stringstream sstr; string str; sstr<<num/n; sstr>>str; multi=multi+str; idx++; residue=num%n; num=residue*10; } string result="0."+multi.substr(0,mp[residue])+"("+multi.substr(mp[residue])+")"; return result; } int main(){ int n; while(cin>>n){ cout<<"The result of 1/"<<n<<": "<<endl; cout<<decimalRepresent(n)<<endl; } return 0; }
相关文章
- ☆打卡算法☆LeetCode 218. 天际线问题 算法解析
- 算法基础课 - 并查集笔记
- SDUT算法分析与设计机测
- [Unity算法]斜抛运动[通俗易懂]
- KDD2022 | 基于图表示的推荐算法教程
- 前端工程师leetcode算法面试必备-二分搜索算法(中)
- 谷歌的变种murmurHash算法
- murmurhash算法_hash function
- 指派问题匈牙利算法例题_匈牙利算法matlab代码
- 时间轮算法
- hanoi塔问题如下图所示_hanoi塔问题最经典的算法
- 算法0基础刷题——组合数
- ICCV 2021 | 字节跳动提出面向GAN压缩的在线多粒度蒸馏算法,算力降至1/46
- [随笔]文件系统上存储哈希对象:哈希算法以及目录结构对性能的影响
- 算法-表示数值的字符串详解编程语言
- Facebook新算法:360度摄影不再感觉头晕
- 顾险峰教授:解读医学影像配准的基本算法
- MySQL中的哈希算法简介与应用(mysql中hash)
- PHP数据结构算法三元组Triplet
- 冒泡排序算法原理及JAVA实现代码
- 扩展KMP算法(ExtendKMP)