题解 | Times 17-牛客假日团队赛3J题
J-Times 17_牛客假日团队赛3
https://ac.nowcoder.com/acm/contest/945/J
题目描述
After realizing that there is much money to be made in software development, Farmer John has launched a small side business writing short programs for clients in the local farming industry.
Farmer John's first programming task seems quite simple to him -- almost too simple: his client wants him to write a program that takes a number N as input, and prints 17 times N as output. Farmer John has just finished writing this simple program when the client calls him up in a panic and informs him that the input and output both must be expressed as binary numbers, and that these might be quite large.
Please help Farmer John complete his programming task. Given an input number N, written in binary with at most 1000 digits, please write out the binary representation of 17 times N.
输入描述:
* Line 1: The binary representation of N (at most 1000 digits).
输出描述:
* Line 1: The binary representation of N times 17.
示例1
输入
10110111
输出
110000100111
说明
OUTPUT DETAILS:The binary numberis equal to
in decimal form.
is
in binary format.
解答
一开始正常的想法是将二进制转化为十进制，乘以17之后再换回2进制，但是发现由于二进制有1000位，转化为十进制没有能装下的类型，马上放弃这个想法。
然后分析二进制数，乘以
可以看成乘以
，而乘以
则可以简单的在后面加上
个
完成。如二进制的
乘以结果是
,再加上可以得到结果
对于二进制的加法，我用了模拟手算加法，进位用temp记录，注意string里面的是字符类型char。
#include<iostream>
using namespace std;
int main(){
string n_binary;
cin>>n_binary;
string result_binary=n_binary+"0000";//乘以17可以先乘上16在加上本身
n_binary="0000"+n_binary;//补足位数进行模拟手算
int len=result_binary.length();
int temp=0;//记录进位
for(int i=len-1;i>0;i--){//模拟手算加法
if((n_binary[i]-'0')+(result_binary[i]-'0')+temp<2){//不够进位
result_binary[i]=(n_binary[i]-'0')+(result_binary[i]-'0')+temp+'0';
temp=0;
}
else{
result_binary[i]=(n_binary[i]-'0')+(result_binary[i]-'0')+temp+'0'-2;
temp=1;
}
}
if(temp==1){//如果最高位有进位需要在前面补'1',而进位之后第二位变为'0'
result_binary[0]='0';
result_binary="1"+result_binary;
}
cout<<result_binary<<endl;
return 0;
} 来源：Jolin123
