主题：第54次变成比赛结果
yxs0001 [专家分：9560] 发布于 2007-05-31 14:49:00
姓名 题目true通过 题目2通过 题目1用时 题目2用时
iAkiak TRUE TRUE 0 16
arfi TRUE 0 6750 outtime
System64 TRUE 0 13188 outtime
shen08343 TRUE TRUE 15484 813
poemsea TRUE 0 16047 outtime
小黑骑DK TRUE TRUE 31047 0
wangfangbob 0 TRUE outtime 0
SeZhang 0 TRUE outtime 15
goal00001111 0 TRUE outtime 891
latalata 0 TRUE outtime 13656
xylgg TRUE 0 outtime outtime
leejqy_1 0 0 outtime outtime
maths_dxj TRUE 0 outtime outtime
leejqy_2 0 0 outtime outtime
pysn 0 0 outtime outtime
surgeonlao 0 0 outtime outtime
wuchengwei 0 0 outtime outtime
冠军就是 iAkiak 了，不用记小分了
[size=4][size=3][size=2][color=FF0000]致歉声明：因为本人的偷懒行为，造成了不良影响，特此道歉，请大家谅解[/color][/size][/size][/size]比赛主要比的是算法，iAkiak第一题算法最优（程序出了点问题），第二题算法仅次于小黑骑DK wangfangbob，下次比赛还请iAkiak出题。
最后更新于：2007-06-01 07:45:00
回复列表 （共41个回复）
21 楼
wangfangbob [专家分：380] 发布于 2007-05-31 20:00:00
iAkiak :: solve( 34 ) = 13
iAkiak :: solve( 32 ) = 8
这个貌似有问题
22 楼
雨中飞燕 [专家分：18980] 发布于 2007-05-31 20:04:00
觉得楼主不太懂测试
23 楼
wangfangbob [专家分：380] 发布于 2007-05-31 20:14:00
如果iAkiak :: solve( 32 ) = 8
那么iAkiak :: solve( 34 )一定小于等于10呀
24 楼
iAkiak [专家分：8460] 发布于 2007-05-31 20:18:00
嗯，还是有bug,组合数写错了，再修改：
强烈要求重新测试，我不是冠军～
[code=c]
int c(int m, int n)
{
static int map[33][33];
static bool inited = false;
if (!inited)
{
inited = true;
memset(map, 0xff, sizeof(map));
}
assert(m > 0 && m <= 32);
assert(n >= 0 && n <= m);
if (map[m][n] != -1)
return map[m][n];
int numerator = 1;
int denominator = 1;
int tn = n, tm = m;
while(tn > 0)
{
numerator *= tm, denominator *= tn;
int g = gcd(numerator, denominator);
numerator /= g, denominator /= g;
tm--, tn--;
}
assert(denominator == 1);
return map[m][n] = numerator;
}
[/code]
25 楼
雨中飞燕 [专家分：18980] 发布于 2007-05-31 20:30:00
只测试一个数就决定冠军，真好笑
26 楼
lrn0409 [专家分：130] 发布于 2007-05-31 21:19:00
我也觉的有必要多测试几组数据，综合的考虑。
比如第一题！
m=100,循环1000000
iAkiak ：用时间 51s
maths_dxj：用时间 33s
而m=1024,循环1000000
iAkiak ：用时间 17s
maths_dxj：用时间 23s
27 楼
wangfangbob [专家分：380] 发布于 2007-05-31 23:31:00
嗯,这回iAkiak的solve值和我的在10000000内是一样的
28 楼
maths_dxj [专家分：90] 发布于 2007-06-01 01:03:00
[quote]我也觉的有必要多测试几组数据，综合的考虑。
比如第一题！
m=100,循环1000000
iAkiak ：用时间 51s
maths_dxj：用时间 33s
而m=1024,循环1000000
iAkiak ：用时间 17s
maths_dxj：用时间 23s
[/quote]
//修改了1题，相信运行会很快
int Q(int k)
{
int a = 1,c = 1,d=1,e=1,r;
int temp=1,result=3,cnt=0,i,sum=0;
while(cnt<=k)
{
sum+=a;
sum+=c;
temp = c;
c+=a;
a = temp;
cnt++;
}
int *b=new int[cnt];
for(int j=0;j<cnt;j++)b[j]=0;
temp=k-sum;
while(temp)
{
i=0;
d=1,e=1;
if(temp<=3)
{
if(temp==2)
b[0]=1;
else if(temp==3)
b[1]=1;
break;
}
else
{
while(d<=temp)
{
r=d;
d+=e;
e = r;
i++;
}
temp=temp-d;
b[i]=1;
}
}
for(j=0;j<cnt;j++)
{
if(b[j])
{
result=(result<<1)+3;
}
else
result=(result<<1)+1;
}
return result;
}
//不采用数组，相信会更快了
int C(int N, int n)//组合数
{
int result;
if(0==n||N==n) return 1;
result=C(N-1,n-1)+C(N-1,n);
return result;
}
int solve(int m)
{
int *n_bit = new int[32];
int result=0;
int i = 0,bit=0,j,temp = m,bit1=1;
while(temp>0)
{
n_bit[bit++]=temp&1;
temp=(temp>>1);
}
for(i=bit-1;i>0;i--)
for(j=i-1;2*j>i;j--)
result+=C(i-1,j);
for(i=bit-2;i>=0;i--)
{
if(n_bit[i])
{
for(j=0;2*(bit1+j)<bit&&j<=i;j++)
result+=C(i,j);
bit1++;
}
}
if(2*bit1<bit)result++;
delete[] n_bit;
return result;
}
29 楼
latalata [专家分：60] 发布于 2007-06-01 10:14:00
哎，我的第一题的错误还是没有找出来，如果我的想法是正确的话，那效率应该是比较高的。
我的想法是：对于整数m,先转换成2进制，（位数为Wei_Num）,则1到m所有的A类数是这样构成的:
(1):位数比Wei_Num少的所有A类数；
(2):位数为Wei_Num的A类数.
对于(1),判断从3位到Wei_Num中，每一种位数所存在的A类数，例如位数个数是5,则由5位二进制数组成的A类数个数为:C(3,4)+C(4,4)。
对于(2)，首先判断m本身是否是A类数,设置标记C_0=0,C_1=1(用于存储当前有的0,1的个数)，然后从第2位开始（高到低），遍历每一位，如果当前位为0,则C_0++;
否则，将当前位置为0，C_0,组合求出余下位有多少种A类数的可能。
例如:10010001,找到第一个1时，C_0=2;C_1=1;然后C_0=C_0+1;变成1000****;则由它构成的A类数个数为:C(2,4)+C(3,4)+C(4,4);即是:10000011,10000110,10001100.10001010,10001001,10000110, 10000001,10000010, 10000100,10001000,100000000；计算完成后再复为1,C_0--,C_1++。
程序在16383之前都正确(14位),到16384(15)时就错了,郁闷!大家看看是不是算法有漏洞。
int solve(int m)
{
int count=0;
int i,j,k,temp,C_0,C_1;;
long temp1,temp2;
int Label[33];
int Wei_Num=0,Lef_Num;
while(m)
{
Label[Wei_Num++]=m%2;
m/=2;
}
for(i=0;i<Wei_Num/2;i++)
{
temp=Label[i];
Label[i]=Label[Wei_Num-1-i];
Label[Wei_Num-1-i]=temp;
}
for(i=3;i<Wei_Num;i++)
{
Lef_Num=i-1;
for(j=i/2+1;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0=0;
C_1=0;
for(i=0;i<Wei_Num;i++)
{
if(Label[i]==0)C_0++;
else C_1++;
}
if(C_0>C_1)count++;
C_0=0;
C_1=1;
i=1;
while(i<Wei_Num)
{
if(Label[i]==0)C_0++;
else if(Label[i]==1)
{
Lef_Num=Wei_Num-i-1;
C_0++;
if(C_0>=Wei_Num/2+1)
{
temp1=1;
for(j=1;j<=Lef_Num;j++)
temp1*=2;
count+=temp1;
}
else
{
for(j=Wei_Num/2+1-C_0;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0--;
C_1++;
}
i++;
}
return count;
}
30 楼
maths_dxj [专家分：90] 发布于 2007-06-01 12:46:00
[quote]哎，我的第一题的错误还是没有找出来，如果我的想法是正确的话，那效率应该是比较高的。
我的想法是：对于整数m,先转换成2进制，（位数为Wei_Num）,则1到m所有的A类数是这样构成的:
(1):位数比Wei_Num少的所有A类数；
(2):位数为Wei_Num的A类数.
对于(1),判断从3位到Wei_Num中，每一种位数所存在的A类数，例如位数个数是5,则由5位二进制数组成的A类数个数为:C(3,4)+C(4,4)。
对于(2)，首先判断m本身是否是A类数,设置标记C_0=0,C_1=1(用于存储当前有的0,1的个数)，然后从第2位开始（高到低），遍历每一位，如果当前位为0,则C_0++;
否则，将当前位置为0，C_0,组合求出余下位有多少种A类数的可能。
例如:10010001,找到第一个1时，C_0=2;C_1=1;然后C_0=C_0+1;变成1000****;则由它构成的A类数个数为:C(2,4)+C(3,4)+C(4,4);即是:10000011,10000110,10001100.10001010,10001001,10000110, 10000001,10000010, 10000100,10001000,100000000；计算完成后再复为1,C_0--,C_1++。
程序在16383之前都正确(14位),到16384(15)时就错了,郁闷!大家看看是不是算法有漏洞。
int solve(int m)
{
int count=0;
int i,j,k,temp,C_0,C_1;;
long temp1,temp2;
int Label[33];
int Wei_Num=0,Lef_Num;
while(m)
{
Label[Wei_Num++]=m%2;
m/=2;
}
for(i=0;i<Wei_Num/2;i++)
{
temp=Label[i];
Label[i]=Label[Wei_Num-1-i];
Label[Wei_Num-1-i]=temp;
}
for(i=3;i<Wei_Num;i++)
{
Lef_Num=i-1;
for(j=i/2+1;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0=0;
C_1=0;
for(i=0;i<Wei_Num;i++)
{
if(Label[i]==0)C_0++;
else C_1++;
}
if(C_0>C_1)count++;
C_0=0;
C_1=1;
i=1;
while(i<Wei_Num)
{
if(Label[i]==0)C_0++;
else if(Label[i]==1)
{
Lef_Num=Wei_Num-i-1;
C_0++;
if(C_0>=Wei_Num/2+1)
{
temp1=1;
for(j=1;j<=Lef_Num;j++)
temp1*=2;
count+=temp1;
}
else
{
for(j=Wei_Num/2+1-C_0;j<=Lef_Num;j++)
{
temp1=1;
temp2=1;
for(k=j;k>=1;k--)
{
temp1*=(Lef_Num-k+1);
temp2*=k;
}
count+=temp1/temp2;
}
}
C_0--;
C_1++;
}
i++;
}
return count;
}
[/quote]
我 也是采用组合数的方法来求的 ，也修改了好久，好像在While（i<）{..
}部分和你的不同，我是从高位开始寻找的，遇到1时候，进行相关的组合操作。
恩，有时间在仔细看看你的程序
我来回复
您所在位置：