扯淡党党部

pku 1906这道题题干非常简短也没有什么歧义，要说读题难度吗 长难句勉强算一个好了

这个题看似非常唬人

输入的是多组19位数字（就是64位整数）

输出的光sample里就出现了717897987691852588770249这样恐怖的23位数（超越long long的范围了）

因此光从数据上看对超大数的使用首先要做准备

其次是子集问题 这道题的讨论很多但是明显那些提出用全排列的小朋友只有超时的命运

回想起以前做过的一道幂集题 当时为了穷举一个集合的所有子集我用了二进制的表示方法

比如集合有元素{1,2,3,4,5,6,7,…..} 那么有同长度的二进制数….00000001就表示一个只含有a的子集 对其进行加法运算就可以得到….00000010，….00000011，….00000100等等 进而穷举出所有子集和

当时用这个算法没有考虑这种顺序的特点，现在看来有这样的对应

00000001：1=1

00000010：2=2

00000011：1，2=3

00000100：3 =3

00000101：1，3=4

00000110：2，3=5

…….

易见他们是按递增顺序排列的 正好与题目要求相符合

因此编程就很容易啦

把输入数据化成二进制 根据二进制的每个为1的位置找出相应的3的幂 输出 解决

代码如下：

#include <iostream>

using namespace std;

#define N 64
#define M 100

int main()
{
unsigned long long binary[N],n,temp;
int i,k,j,bignum[M];
while (cin)
{
cin>>n;
memset(binary,0,sizeof(binary));
if (n==0) break;
if (n==1)
{
cout<<”{ }”<<endl;
continue;
}
n–;
for (i=0;i<N;i++)
{
if (n!=0)
{
binary[i]=(n%2);
n=n/2;

}
}
k=0;memset(bignum,0,sizeof(bignum));bignum[0]=1;
for (i=0;i<N;i++) if (binary[i]>0 ) k++;
cout<<”{ “;
for (i=0;i<N;i++)
{
if (binary[i]>0)
{
for (j=M-1;j>=0;j–)
{
if (bignum[j]>0)
for (j;j>=0;j–)
cout<<bignum[j];
}
if (k>1)
{
cout<<”, “;
k–;
}
else
{
cout<<” }\n”;
break;
}
}
for (j=0;j<M;j++)
bignum[j]=bignum[j]*3;
for (j=0;j<M-1;j++)
if (bignum[j]>=10)
{
bignum[j+1]=bignum[j]/10+bignum[j+1];
bignum[j]=bignum[j]%10;
}

}
}
return 0;
}

总结：

1 超大数的处理简单必要

2 最好有认识常用数据类型的范围

3 要注意编译器不同所能使用的数据类型不同 比如long long可以用__int64代替 等等

4 注意0的处理 在这面因为0没有处理好 走了不少弯路

over

补充：

尝试改了下程序 当输入19个9的时候 输出的最大数字为31位 因此将M修改为32

结果提交后发现memory和time没有变化 看来后台数据比较善良 不知道是否每个超大数题都这样

~ by mcluxun on 三月 2, 2008.