时间限制 1000 ms
内存限制 64 MB
初始有一个数nn,每过一秒所有大于1的数xx都会分裂成3部分:⌊x/2⌋ , x%2 , ⌊x/2⌋ ( ← 这个符号指floor()取整
问经过足够长的时间后,即所有的数都是0或1的时候,0的个数是多少
一个正整数n,n<=1e12
最终0的个数
最开始没思路,只想到n<=1e12可以排除暴力计算,猜测最终0的个数是可以O(n)得到,开始尝试用数学归纳法碰瓷:
n=12时,12转化为二进制1100,最终结果3个0,转化为二进制0011;
n=5时,5转化为二进制101,最终结果2,转化为二进制10;
n=16时,16转化为二进制数10000,最终结果15,转化为二进制01111。
大胆假设,该规律对所有的n都成立,严格证明不会写…
//二进制运算符不会用,所以是用字符串的方式存二进制数
#include<bits/stdc++.h>
#include<cstring>
using namespace std;
char str[101];
long long Int2Binary(long long num, char* str)
{
int i=0,j,k;
while(num>=1)
{
str[i++]='0'+num%2;
num/=2;
}
int len=strlen(str);
long long nn=1;
long long res=0;
for(i=0;i<len;i++,nn*=2)
{
if(str[i]=='0') res+=nn*1;
}
return res;
}
int main()
{
long long n;
cin >> n;
memset(str,'\0',100);
cout << Int2Binary(n, str) <<endl;
return 0;
}
本文地址:https://blog.csdn.net/qq_45711827/article/details/107237526
如对本文有疑问, 点击进行留言回复!!
【java基础】面试常见问题:类和对象,封装继承多态,final关键字,static关键字,类加载过程,双亲委派模型
荐 Java语言基础之JDK1.8新特性(Lambda表达式、函数式接口、Stream流、新的日期API)
网友评论