变成1
题目 变成1
思路分析
位数不超过10^6 说明是高精度问题
还是一样 用容器进行模拟
string读入 逆序存储
如何判断是奇数偶数 其实就是取出最低位（最右） 也就是容器里的第一个元素
判断它是0还是1
若为奇数 就得进行加法
对于二进制的高精度加法
实质与十进制一样 只要修改%10 /10 为%2 /2即可
在原本的模板基础上 发现第二个加数可以不要
因为只有第一次计算时为1 其他时候都为0 那我不妨将t初始化成1 直接省去第二个加数
然后发现 二进制的加1 实际上就是将后面的连续的1变成0 然后最后一个0变成1
也就是只有当t=1的时候才要进行翻转 当t=0时 前面的位数都可以保持不变
那不妨直接在原容器里面进行修改 而不是重新拷贝一份结果
那么就得到
for(int i=0;i<q.size();i++)
{
t+=q[i];
q[i]=t%2;
t/=2;
if(!t)
break;
}
当然 也存在进位的情况 当循环结束了 t若还存在 就得pushback一个1
若为偶数
就除以2
二进制的除以2其实就相当于10进制的除以10
当最后一位为0时 其实就是往右边划掉一位
那就是要把容器里的第一个元素pop掉
但是vector没有从前面删元素的操作
所以改用deque 使用它的pop_front（）
当然别忘了在每次加1和删0的操作后进行计数
步骤模拟如下
代码实现
#include<bits/stdc++.h>
using namespace std;
int n;
deque<int> q;
string s;
int main()
{
cin>>s;
for(int i=s.size()-1;i>=0;i--)
q.push_back(s[i]-'0');
int cnt=0;
while(q.size()>1)
{
int lowbit=q.front();
if(lowbit%2)
{
int t=1;
for(int i=0;i<q.size();i++)
{
t+=q[i];
q[i]=t%2;
t/=2;
if(!t)
break;
}
if(t)
q.push_back(1);
cnt++;
}
else
{
q.pop_front();
cnt++;
}
}
cout<<cnt;
return 0;
}
💬 评论