国家集训队2000论文集 张一飞论文(3)

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

【附录】

[1].

摘自《郑板桥集》第206页，全诗如下：

题画竹 四十年来画竹枝 日间挥写夜间思 冗繁削尽留清瘦 画到生时是熟时

[2].

见参考文献[2]。

在后面的分析中可以看到，调用粗体部分程序段的总次数是

nijin

[3].

??Ci?0j?0??2i?0i?2n?1

故算法的时间复杂度为O(2n+1)=O(2n)。 [4].

也可以直接采用数学方法推导公式1。但我认为，这比本文中使用的方法更难掌握。在参考文献[1]中，给出了一个形式上更简单的计算公式，但这个公式的设计也颇有难度。参考文献[1]中给出的公式是：

F(m,t)?[F(m?1,t?1)?F(m?1,t)]?t边界条件：F(1,1)?1,F(1,t)?0(t?0)n

n个数的序关系数是：?F(n,i)i?1

[5].

本文中所有程序的运行环境均为Pentium 100MHz，BP7.0编译。

如果我们边读数据边规划，就只要保存V[i-1]和V[i]，而没有必要定义长度为M的数组V。这样，算法的空间复杂度降到了O(1)。

[7].

公式6可进一步化简：

MaxF[i]?max{MaxF[i?1],F[i?1]}?max{MaxF[i?1],MaxFV[i?1]*V[i?1]}MaxF[i]/V[i?1]?max{MaxF[i?1],MaxFV[i?1]*V[i?1]}/V[i?1]?max{MaxF[i?1]/V[i?1],MaxFV[i?1]*V[i?1]/V[i?1]}?max{MaxF[i?1]/V[i?1],MaxFV[i?1]}?MaxFV[i?1]MaxFV[i]?max{MaxFV[i?1],MaxF[i]/V[i?1]}?MaxF[i]/V[i?1]MaxF[i]?max{MaxF[i?1],MaxFV[i?1]*V[i?1]}?max{MaxF[i?1],MaxF[i?1]/V[i?2]*V[i?1]}[6].

第 11 页

冗繁削尽留清瘦——浅谈信息的充分利用 张一飞

这样可以得到如下递推关系式：

MaxF[i]?max{MaxF[i?1],MaxF[i?1]/V[i?2]*V[i?1]}

在源程序Pro_2.pas中，给出了这个公式的算法2-4。算法2-4的时空复杂度同算法2-3，只是形式上更加简单。

[8].

值得说明的是，采用二分法求乘幂，并不是最充分利用已知信息的方法。例如，采用二分法计算i15需要6次乘法，而实际上，我们只需5次乘法即可。

p[1]=i;

p[2]=p[1]*p[1] p[3]=p[2]*p[1] p[6]=p[3]*p[3] p[9]=p[6]*p[3] p[15]=p[9]*p[6]

要得到求乘幂的最优方案，需要耗费大量的时间 (见参考文献[3])。由于二分法的计算次数，与最优的次数非常接近，因此，本文选择了二分法。

[9].

我们只需保存已算出的1m,2m,…4999m的值即可。当然，还可以进一步优化空间复杂度，详见程序Pro_3.pas。

第 12 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库国家集训队2000论文集 张一飞论文(3)在线全文阅读。