UVA 1350&&LA 3357 Pinary(递推)

2016-12-02 12:52:09来源:网络收集作者:IT狂人人点击

第七城市


点击打开题目链接



写出前几个pinary数,会发现有1个一位数,1个两位数,2个三位数,3个四位数,5个五位数。。。。 斐波那契数列。可以知道由多少位组成,怎么生成这一序列是个问题?下面是别人的思路:



详细说明:
ans[1]=1 , ans[2]=1 ,ans[3]=2 , ans[4]=3 , ans[5]=5 , ans[6]=8 , ans[7]=13 ,ans[8]=21 ,ans[9]=34
sum[1]=1 , sum[2]=2 ,sum[3]=4 , sum[4]=7 , sum[5]=12 , sum[6]=20 , sum[7]=33 ,sum[8]=54 ,sum[9]=88比如 n=70的情况, 查找到 sum[8]=54=n ,说明“Pinary number”的长度为 9,第 1 个数字是 1, 继续确定余下的 8 位数字
n-=sum[8], n=16 这里要注意 n 另外还要减 1 ,n=15, 因为余下的8位,每一位都可以取 0 ,而如果只有 8位 ,第一位只能取 1
对于 n=15, 查找到 sum[5]=12=n ,说明 长度现在收缩为 6 位, 第 4 个数字是 1,
联系前面得到的 9 位 ,可确定 9位 的前 四 位数字: 1001 . 此时 n-=sum[5], n=3 同样地 n 减 1, 得到 n=2
继续查找, sum[1]=1=n ,说明 长度现在收缩为 2 位, 可确定 前 八 位数字是: 100 100 01
n-=sum[1], n=1 同样地 n 减 1, 得到 n=0 ,于是退出循环,最后空缺的位置都由 0 填充,即 100 100 010 , 序列唯一确定证明: ans[i] = ans[i-1] + ans[i-2] ,ans[i]表示长度为i的“Pinary number”共有多少个
现有一长度为 5 的序列: 10**** , 那长度为 4 的序列为: 10***,
可以看出,长度 5 的序列的第一个星号 如果取 0 ,那么ans[5]=ans[4],因为两者都只剩下 3 个星号
如果长度 5 的序列第一个星号取 1 , 则前4 个数字可确定下来: 1010** ,可以看出ans[5]=ans[3], ans[3]为 10**
故 ans[5]=ans[4]+ans[3] ,得证

[cpp]view
plaincopy#include
#include
usingnamespacestd;
longlongfb[105],sum[105],ans[50];
intmain(intargc,char*argv[])
{
longlongt,i,j,n,m;
sum[1]=fb[1]=fb[2]=1;sum[2]=2;i=3;
while(sum[i-1]<90000005)
{
fb[i]=fb[i-1]+fb[i-2];
sum[i]=fb[i]+sum[i-1];
i++;
}
m=i-1;
cin>>t;
while(t--)
{
cin>>n;
memset(ans,0,sizeof(ans));
while(n>0)
{
for(i=1;iif(nif(n-sum[i-1]==0)i--;
ans[i]=1;
n=n-sum[i-1]-1;
}
for(n=0,i=50;i>=1;i--)
{
if(ans[i])cout<<1,n=1;
elseif(n)cout<<0;
}
cout<}
return0;
}上文来自:/2014th7cj/d/file/p/20161129/o2rvmfkcggi
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台