高分 有代码 速求解释 1小时解决分数加倍

来源：百度知道 编辑：UC知道 时间：2024/05/26 13:47:32
对于给定的整数N，求出最小的指数E(如果存在)使2^E这个数的前若干位与N相同。注意：N的长度小于2^E的长度的一半。
输入
输入文件包含一些正整数，它们均小于2^31-1。数与数之间用空格(可能不止一个)或空行(可能不止一个)隔开。输入文件末尾可能会有多余的空行。
输出
对于输入文件的每一个数N，依次输出最小的正数E使2^E的前若干位是N(占一行)。如果E不存在，输出"no power of 2"(占一行)。
代码是

就是 要找到前面的数字和给定的数字相同的 2 最小的 的整数次方
而且所输入数字长度小于2^E的长度的一半

举例
输入 1 结果是 7，因为 2 的 7 次方 是 128
输入 2 结果是 8，因为 2 的 8 次方 是 256
输入 10 结果是 20，因为 2 的 20 次方 是 1048576

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

int main()
{

int d,k;
char ai[12];
double l1g=log(10)/log(2);

while(scanf("%s",ai)==1)
{
d=atoi(ai);
k=strlen(ai)+1;

int a;

double l1g2=log(d)/log(2);
double l1g3=log(d+1)/log(2);
while(1)
{
a=int(floor(l1g3+k*l1g)+0.2);
double dd=l1g2+k*l1g;
if(a>=dd)break;

从程序中没有出现输出"no power of 2"的语句,可以知道写这个程序的人已经肯定了题目有解.为什么肯定有解呢,这涉及到的数学知识比较深了,我也不太清楚,据高人说是和丢番图逼近论有关.
反正我们就肯定有解,假设为E.
设N的位数为L，则L=[lgN]+1,这里的[]是取下整,lg是以10为底的对数.
设2^E=10^k*N+P,其中k>0,0<P<10^k
则有10^k*N<2^E<10^k*N+10^k=10^k*(N+1)
以log表示以2为底取对数,两边取2的对数可知
a=k*log10+logN<E<k*log10+log(N+1)=b
要使E存在,必须[a]<[b],因此,可以从L开始枚举k，直到a≠b,就可得到E=[a]+1

好复杂