计算思维综合训练 - F. 课堂作业-8-3

时间限制 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