首页 > 代码库 > hihocoder1311 二进制小数
hihocoder1311 二进制小数
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定一个十进制小数X，判断X的二进制表示是否是有限确定的。
例如0.5的二进制表示是0.1，0.75的二进制表示是0.11，0.3没有确定有限的二进制表示。
输入
第一行包含一个整数 T (1 ≤ T ≤ 10)，表示测试数据的组数。
以下T行每行包含一个十进制小数 X (0 < X < 1)。 X一定是以"0."开头，小数部分不超过100位。
输出
对于每组输入，输出 X 的二进制表示或者NO(如果 X 没有确定有限的二进制表示）。
样例输入
3
0.5
0.75
0.3
样例输出
0.1
0.11
NO
题意：十进制小数转二进制，输出二进制小数，无限循环则输出NO
题解：二进制小数，高精度乘法加个特判即可，这里还用到了hash
#include <bits/stdc++.h>using namespace std;map<int, int>mp;string s, ans;int BKDRHash(string s){ long long seed=131; long long hash=0; int i = 0; while(i<s.size()&&s[i]) hash=hash*seed+(s[i++]); return (hash & 0x7FFFFFFF);}string Multiply(string s,int x){//模版 reverse(s.begin(),s.end()); int cmp=0; for(int i=0;i<s.size();i++){ cmp=(s[i]-‘0‘)*x+cmp; s[i]=(cmp%10+‘0‘); cmp/=10; } while(cmp){ s+=(cmp%10+‘0‘); cmp/=10; } reverse(s.begin(),s.end()); return s;}bool f(string s){ int i; for(i=0;i<s.size();i++) if(s[i] != ‘0‘) break; if(i>=s.size()) return 1; return 0;}int main(){ int T, flag, l; cin>>T; while(T--){ cin>>s; int i = s.size()-1; while(i>=0&&s[i]==‘0‘) i--; if(i>=0&&s[i]!=‘5‘) { cout<<"NO"<<endl; continue; } ans = "";mp.clear(); flag = 0; s.erase(0,2); l = s.size(); while(mp[BKDRHash(s)] == 0){ mp[BKDRHash(s)] = 1; s = Multiply(s, 2); if(f(s)){ flag = 1; break; } if(s.size() != l) s.erase(0, 1), ans += ‘1‘; else ans += ‘0‘; } if(flag == 1) cout<<"0."<<ans<<endl; else cout<<"NO"<<endl; } return 0;}
hihocoder1311 二进制小数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。