主题：第72次编程比赛结果
雨中飞燕 [专家分：18980] 发布于 2008-09-23 12:07:00
我浏览一次后，还没打算编译测试前，已经决定好了谁是冠军了，
因为除了那一份代码有测试的价值外，其它的我已经没有兴趣去试验了
不过，有点可惜的是，冠军的代码和我自己的代码效率差别不大
偶也想看看n<=30有15%左右提升，n>39有一倍提升的代码，能发上来看看吗？
顺便可以的话你说明你优化了些什么
PS.前两天有点忙，搞得忘记来结帖了。。。
最后更新于：2008-09-23 12:09:00
回复列表 （共24个回复）
11 楼
天空飞雪 [专家分：960] 发布于 2008-09-23 18:45:00
这个程序最大能算到多少？n,k的最多能取多少？
12 楼
雨中飞燕 [专家分：18980] 发布于 2008-09-23 18:59:00
>> 我的优化就是加入了对各数字个数的范围的限制
这得有数学上的证明才行，不过正式比赛的话实在没有办法剪枝的话，偶也喜欢用此下策。。。
13 楼
boxertony [专家分：23030] 发布于 2008-09-23 20:11:00
[quote]>> 我的优化就是加入了对各数字个数的范围的限制
这得有数学上的证明才行，不过正式比赛的话实在没有办法剪枝的话，偶也喜欢用此下策。。。[/quote]
我的两个函数GetMinK和GetMaxK的范围限制在数学上是可以证明的。
14 楼
boxertony [专家分：23030] 发布于 2008-09-23 20:13:00
[quote]inline void MultiplyN(int dest[], int src[], int m, int radix)是什么意思[/quote]
就是计算src[]中存放的大数与普通整数m的乘积啊。radix就是进制
15 楼
boxertony [专家分：23030] 发布于 2008-09-23 20:18:00
to 天空飞雪:
1. GetMinK1写错了，应为GetMinK
2. 计算范围与n和k值有关。当取最大进制36时，1小时之内也许能计算到18~20（没计算过，太慢了）
取进制10时，可以在7分钟内找出所有的89个水仙花数（最大的是39位的）
16 楼
boxertony [专家分：23030] 发布于 2008-09-23 20:28:00
算法如下：
假设求n位的水仙花数（以10进制为例），那么该数只可能有0~9这10个数字。每个数字在该水仙花数当中的个数和显然就是n。假设用k[i]表示数字i在该数中出现的个数，则有：
Sigma(k[i]) = n。因此该水仙花数的值N为：
N = k[0]*0^n + k[1]*1^n + k[2]*2^n + ... + k[9]*9^n
通过循环取得每个数字的可能出现的个数k[i]，就可以计算出某个N值，然后分解这个N值，并统计其中每个数字的个数T[i]，如果跟对应的k[i]值全部相等，则说明该N就是水仙花数。
由于当位数大于9时int类型无法表示，所以需要进行大数运算。
17 楼
雨中飞燕 [专家分：18980] 发布于 2008-09-23 22:15:00
[quote][quote]>> 我的优化就是加入了对各数字个数的范围的限制
这得有数学上的证明才行，不过正式比赛的话实在没有办法剪枝的话，偶也喜欢用此下策。。。[/quote]
我的两个函数GetMinK和GetMaxK的范围限制在数学上是可以证明的。[/quote]
我说的是你所谓的对“数字个数”比如2出现的次数的限制
这个证明了吗？？
18 楼
boxertony [专家分：23030] 发布于 2008-09-23 23:06:00
[quote][quote][quote]>> 我的优化就是加入了对各数字个数的范围的限制
这得有数学上的证明才行，不过正式比赛的话实在没有办法剪枝的话，偶也喜欢用此下策。。。[/quote]
我的两个函数GetMinK和GetMaxK的范围限制在数学上是可以证明的。[/quote]
我说的是你所谓的对“数字个数”比如2出现的次数的限制
这个证明了吗？？[/quote]
GetMink和GetMaxK就是为了对数字个数进行限制的呀，这个从数学上证明应该是没有问题的。正因为这样，所以范围比较宽，因而效果不明显
19 楼
JackieRasy [专家分：3050] 发布于 2008-09-24 14:04:00
我看了boxertony的程序，不是很明白，再去理解一下。
支持boxertony的冠军，实至名归！
20 楼
fenix124 [专家分：70] 发布于 2008-09-24 21:03:00
这次错过了。刚刚看了下题，想到一个方法。宽搜
节点定义的方式是
struct node
{
int currentvalue;//扩展到当前位的值
int sum;//扩展到当前位的各位数的n次方和
};
初始化的时候，把一位的情况放到队列里面（不包括0），然后扩展一个节点后面添加位数0---k-1.
剪枝条件为current*k > sum+(k-1)^n;
实现方式非常简单，不知道效率怎么样。
我来回复
您所在位置：