1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
|
#define SIZE_OF_INTEGER 100
#define BASE_1 2
#define BASE_2 3
#define NUM 2000
ZZ bs(vec_ZZ& a, long beg, long end, ZZ x)
{
long mid;
mid=(beg+end)/2;
if (x==a[mid])
{
cout << a[mid];
return a[mid];
}
else if (beg>end)
{
cout<<a[end]<<" + ";
return a[end];
}
else if (x<a[mid])
{
end=mid-1;
return bs(a,beg,end,x);
}
else if (x>a[mid])
{
beg=mid+1;
return bs(a,beg,end,x);
}
}
ZZ alg(vec_ZZ& a, long s, ZZ num, ZZ count)
{
ZZ num1;
num1=num-bs(a,0,s,num);
if (num1==0)
return count;
else
return alg(a,s,num1,++count);
}
main()
{
ZZ d;
vec_ZZ a,b,c;
a.SetLength(power_long(SIZE_OF_INTEGER,2));
b.SetLength(NUM);
c.SetLength(NUM);
ZZ v;
v=power_ZZ(2,SIZE_OF_INTEGER);
long x=0;
for(long i=0;i<=SIZE_OF_INTEGER;i++)
{
for(long j=0;( d = power_ZZ(BASE_1,i)*power_ZZ(BASE_2,j)) <= v ;j++)
{
a[x]= d;
x++;
}
}
sort(a,x);
ZZ cnt;
cnt=0;
for(long k=0;k<NUM;k++)
{
c[k]=1;
b[k]=rand();
cout<<endl<<b[k]<<" : ";
c[k]=alg(a,x-1,b[k],c[k]);
cnt=cnt+c[k];
}
cout<<endl<<"total no. of terms: "<<cnt<<endl;
cout<<"avg no. of terms= "<<cnt/NUM;
cout << endl;
}
|