主题：第72次编程比赛结果
雨中飞燕 [专家分：18980] 发布于 2008-09-23 12:07:00
我浏览一次后，还没打算编译测试前，已经决定好了谁是冠军了，
因为除了那一份代码有测试的价值外，其它的我已经没有兴趣去试验了
不过，有点可惜的是，冠军的代码和我自己的代码效率差别不大
偶也想看看n<=30有15%左右提升，n>39有一倍提升的代码，能发上来看看吗？
顺便可以的话你说明你优化了些什么
PS.前两天有点忙，搞得忘记来结帖了。。。
最后更新于：2008-09-23 12:09:00
回复列表 （共24个回复）
沙发
JackieRasy [专家分：3050] 发布于 2008-09-23 12:38:00
我都忘记了要输出了。晕
板凳
boxertony [专家分：23030] 发布于 2008-09-23 16:40:00
我的优化就是加入了对各数字个数的范围的限制，但是效果不大。不过如果作弊的话，限定每个数字个数的最大值为10（实际上对于10进制所有的89个水仙花数数字个数最多的就是9个2，此时n=34），速度倒是可以得到很大的提升，呵呵。
当我设置radix=32，n=28时，这个慢啊，运算了7个小时，楞没出结果。
3 楼
boxertony [专家分：23030] 发布于 2008-09-23 16:41:00
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <conio.h>
#include <windows.h>
#include <algorithm>
#include <functional>
#include <stack>
#define MAX_RADIX 37
#define MAX_POWER 61
#define MAX_SIZE 100 // 第0个结点用于存放数据的结点个数
int nPowerOfN[MAX_RADIX][MAX_POWER][MAX_SIZE]; //
// dest[] = src[] * m
inline void MultiplyN(int dest[], int src[], int m, int radix)
{
assert(m >= 0);
if(m == 0)
{
dest[0] = 1;
dest[1] = 0;
return;
}
int carry = 0;
int temp;
dest[0] = src[0];
for(int i=1; i<=src[0]; ++i)
{
temp = src[i] * m + carry;
carry = temp / radix;
dest[i] = temp - carry * radix;
}
while(carry > 0)
{
temp = carry;
carry = temp / radix;
dest[i++] = temp - carry * radix;
++dest[0];
}
}
// dest[] = dest[] + src[]
inline void Add(int dest[], int src[], int radix)
{
int carry = 0;
int temp;
int len_d, len_s, min_len;
len_s = src[0];
len_d = dest[0];
if(len_s > len_d)
{
min_len = len_d;
dest[0] = len_s;
}
else
{
min_len = len_s;
dest[0] = len_d;
}
for(int i=1; i<=min_len; ++i)
{
temp = dest[i] + src[i] + carry;
carry = temp>=radix?1:0;
dest[i] = temp - carry * radix;
}
for(; i<=len_s; ++i)
{
temp = src[i] + carry;
carry = temp>=radix?1:0;
dest[i] = temp - carry * radix;
}
for(; i<=len_d; ++i)
{
temp = dest[i] + carry;
if(temp >= radix)
{
carry = 1;
dest[i] = temp - radix;
}
else
{
carry = 0;
dest[i] = temp;
break;
}
}
if(carry > 0)
{
dest[i] = carry;
++dest[0];
}
}
// dest[] = dest[] + m
void Add(int dest[], int m, int radix)
{
int carry = m;
int temp;
for(int i=1; i<=dest[0]; ++i)
{
temp = dest[i] + carry;
if(temp >= radix)
{
carry = 1;
dest[i] = temp - radix;
}
else
{
carry = 0;
dest[i] = temp;
break;
}
}
if(carry > 0)
{
dest[i] = carry;
++dest[0];
}
}
4 楼
boxertony [专家分：23030] 发布于 2008-09-23 16:42:00
// 假定dest[]总是大于等于src[]
// dest[] = dest[] - src[]
inline void sub(int dest[], int src[], int radix)
{
int carry = 0;
int temp;
for(int i=1; i<=src[0]; ++i)
{
temp = dest[i] - src[i] + carry;
carry = temp<0?-1:0;
dest[i] = temp - carry * radix;
}
for(; i<=dest[0]; ++i)
{
temp = dest[i] + carry;
if(temp < 0)
{
dest[i] = temp + radix;
}
else
{
dest[i] = temp;
break;
}
// carry = temp<0?-1:0;
// dest[i] = temp - carry * radix;
}
assert(i<=dest[0]+1);
// 去掉高位无效0
if(i > dest[0])
{
while(!dest[--i])
;
if(!i)
i = 1;
dest[0] = i;
}
}
// 预先求取某个进制下所有数字的各次幂的值
void Init(int n, int radix)
{
int i, j;
for(j=0; j<=n; ++j)
{
nPowerOfN[0][j][0] = 1;
nPowerOfN[1][j][0] = 1;
nPowerOfN[1][j][1] = 1;
}
for(i=2; i<=radix; ++i)
{
nPowerOfN[i][0][0] = 1;
nPowerOfN[i][0][1] = 1;
}
for(i=2; i<=radix; ++i)
{
for(j=1; j<=n; ++j)
{
MultiplyN(nPowerOfN[i][j], nPowerOfN[i][j-1], i, radix);
}
}
}
// 输出水仙花数
void Output(int sum[], int radix)
{
for(int i=sum[0]; i>=1; --i)
{
if(sum[i] < 10)
printf("%d", sum[i]);
else
printf("%C", 'a'+sum[i]-10);
}
printf("\n");
}
int cmp(int a[], int b[])
{
if(a[0] != b[0])
return a[0] - b[0];
for(int i=a[0]; i>=1; --i)
if(a[i] != b[i])
return a[i]-b[i];
return 0;
}
5 楼
boxertony [专家分：23030] 发布于 2008-09-23 16:48:00
inline int GetMaxK(int n, int b, int left, int radix, int sum[])
{
int tmp[MAX_SIZE];
int m = 0;
memcpy(tmp, nPowerOfN[radix][n], sizeof(int)*MAX_SIZE);
if(cmp(tmp, sum) <= 0)
m = 0;
else
{
int *p = nPowerOfN[b][n];
sub(tmp, sum, radix);
if(cmp(tmp, p) <=0 )
m = 0;
else
{
int len1 = tmp[0];
int len2 = p[0];
int value1, value2;
if(len1-len2 < 3)
{
value1 = tmp[len1];
for(int i=len1-1; i>=len2-2; --i)
{
value1 *= radix;
value1 += tmp[i];
}
value2 = p[len2];
for(i=len2-1; i>=len2-2; --i)
{
value2 *= radix;
value2 += p[i];
}
m = value1 / value2;
if(m > left)
m = left;
}
else
m = left;
}
}
return m;
}
6 楼
boxertony [专家分：23030] 发布于 2008-09-23 16:49:00
inline int GetMinK(int n, int b, int left, int radix, int sum[])
{
int tmp[MAX_SIZE];
int m = 0;
int *r = nPowerOfN[radix][n-1];
if(cmp(r, sum) <= 0)
m = 0;
else
{
int *p = nPowerOfN[b][n];
int *q = nPowerOfN[b-1][n];
int tmp1[MAX_SIZE];
memcpy(tmp, r, sizeof(int)*(r[0]+1)); // tmp[] = radix^(n-1)
sub(tmp, sum, radix); // tmp[] = radix^(n-1)-sum
MultiplyN(tmp1, q, left, radix); // tmp1[] = left*(b-1)^n
if(cmp(tmp, tmp1) <= 0)
m = 0;
else
{
sub(tmp, tmp1, radix); // tmp [] = radix^(n-1)-sum-left*(b-1)^n
memcpy(tmp1, p, sizeof(int)*(p[0]+1)); // tmp1[] = b^n
sub(tmp1, q, radix); // tmp1[] = b^n - (b-1)^n
if(cmp(tmp, tmp1) < 0)
m = 0;
else
{
int len1 = tmp[0];
int len2 = tmp1[0];
int value1, value2;
if(len1-len2 < 3)
{
value1 = tmp[len1];
for(int i=len1-1; i>=len2-2; --i)
{
value1 *= radix;
value1 += tmp[i];
}
value2 = tmp1[len2];
for(i=len2-1; i>=len2-2; --i)
{
value2 *= radix;
value2 += tmp1[i];
}
m = value1 / value2 - 1;
if(m > left)
m = left;
if(m < 0)
m = 0;
}
else
m = left;
}
}
}
return m;
}
// 检查sum[]中存放的是否水仙花数
inline bool CheckNarcissus(int sum[], int n, int end, int radix, int k[])
{
int i;
int count[MAX_RADIX];
if(sum[0] < n || k[sum[1]] == 0)
return false;
memset(count, 0, sizeof(int)*radix);
for(i=1; i<=sum[0]; ++i)
++count[sum[i]];
for(i=radix-1; i>end; --i)
if(count[i] != k[i])
return false;
return true;
}
7 楼
boxertony [专家分：23030] 发布于 2008-09-23 16:49:00
// 求水仙花数
inline void Narcissus(int sum[], int n, int left, int start, int radix, int k[])
{
if(left == 0)
{
if(CheckNarcissus(sum, n, start, radix, k))
{
Output(sum, radix);
}
return;
}
int tmp[MAX_SIZE];
memcpy(tmp, sum, sizeof(int)*(sum[0]+1));
if(start == 1)
{
k[0] = left;
Narcissus(tmp, n, 0, start-2, radix, k);
for(int i=1; i<=left; ++i)
{
k[start] = i;
k[0] = left - i;
Add(tmp, 1, radix);
Narcissus(tmp, n, 0, start-2, radix, k);
}
}
else
{
int maxk, mink;
int *p = nPowerOfN[start][n];
if(start >= radix/2)
{// 计算每一个数字允许的最大个数和最小个数
maxk = GetMaxK(n, start, left, radix, sum);
mink = GetMinK(n, start, left, radix, sum);
}
else
{
maxk = left;
mink = 0;
}
if(mink == 0)
{
Narcissus(tmp, n, left, start-1, radix, k);
}
else
{
MultiplyN(tmp, p, mink, radix);
Add(tmp, sum, radix);
k[start] = mink;
Narcissus(tmp, n, left-mink, start-1, radix, k);
}
for(int i=mink+1; i<=left; ++i)
{
k[start] = i;
Add(tmp, p, radix);
Narcissus(tmp, n, left-i, start-1, radix, k);
}
}
k[start] = 0;
}
int main()
{
int n, radix;
int k[MAX_RADIX] = {0};
int sum[MAX_SIZE] = {1,0};
scanf("%d%d", &n, &radix);
{
memset(sum, 0, sizeof(int)*MAX_SIZE);
sum[0] = 1;
Init(n, radix);
Narcissus(sum, n, n, radix-1, radix, k);
}
return 0;
}
8 楼
AllenRomeo [专家分：0] 发布于 2008-09-23 17:42:00
看不懂啊，能不能指点一下
9 楼
AllenRomeo [专家分：0] 发布于 2008-09-23 17:44:00
inline void MultiplyN(int dest[], int src[], int m, int radix)是什么意思
10 楼
天空飞雪 [专家分：960] 发布于 2008-09-23 18:42:00
error C2065: 'GetMinK1' : undeclared identifier？？
我来回复
您所在位置：