《阅读程序写结果之提高篇(c语言版)》由会员分享，可在线阅读，更多相关《阅读程序写结果之提高篇(c语言版)（6页珍藏版）》请在金锄头文库上搜索。
1、苏州工业园区星海实验中学 -第 1 页 共 6 页读程序写结果之提高篇“读程序写结果” 有时会考查选手经典算法的掌握情况及数学知识的应用能力。 这类题， 要求选手有较高的综合素质。下面共同探讨一下这两个方面： 技巧七：计算经典问题的重现技巧七：计算经典问题的重现 同一个问题，考虑的角度不一样，往往可以写出风格完全不一样，甚至算法完全不同 的程序，结果却是相同的：殊途同归。 正因为这样，有些经典问题经常会被拿出来“重写” 。在读程序时，应该善于把刚刚看 到的“程序”与自己脑海里的信息进行匹配。 一旦找到自己已有信息里类似、甚至相同的问题时，面对的问题也就迎刃而解。 这些经典问题有：素数、排序、约
2、瑟夫问题、杨辉三角、最大公约数（辗转相除法） 、 高精度计算、二分法、求最短路径、拓扑排序、关键路径、欧拉回路、哈密顿回路、最小生 成树、搜索问题等等。 选例十二 NOIP2007 提高组第三题 1#include 2#include 3#include “math.h“ 4int main() 5 6int a151=0; 7int i,j,t,t2,n=50; 8for (i=2;i #include char ch=q,A,S,O,R,T,E,X,A,M,P,L,E; int n=12; void shift(int k, int n) char v; int j; v=chk; j=k
3、+k; while (j0; k-) shift(k,n); /* 建堆 */ printf(“No.1: “); for(k=1; k0; k-) tmp=ch1; ch1=chk; chk=tmp; shift(1,k-1); int main() int k; hpsrt(); printf(“No.2: “); for(k=1; k0; k-) shift(k,n);：典型的建堆语句本例即输出建立最大堆后的状态，及从小到大堆排序后的结果： No.1: XTORSEAAMPLE No.2:AAEELMOPRSTX 要注意的是，下标为 0 的对象（即 q） ，没有参与操作。技巧八：巧用数学
4、知识推理技巧八：巧用数学知识推理 有些程序，我们粗读一遍就可以知道其循环执行的次数非人工模拟能够忍受，或根本就 没法模拟，这时应该想一想能否运用数学知识，推理得出程序执行的结果。当然，这要求选 手要有扎实的数学功底。 选例十四 NOIP2002 提高组第三题 #include #include int main() double d1,d2,x,min; min=10000;x=3; while (x #include long g(long k) if (k = kk， 则原问题的解为：)(kg=)(kfmod 2005。苏州工业园区星海实验中学 -第 5 页 共 6 页)(kf是个齐次递归
5、数列，其通项公式的特征方程为：200320022+=xx。该方程有两根：2003、-1，所以，)(kf的通项公式为：kkbakf) 1(2003)(+=，其中a、b为常数。1从递归公式里，我们可知0)0(=f、1) 1 (=f，代到)(kf的通项公式，有：=+=+=1) 1(2003) 1 (0) 1(2003)0(1100bafbaf解得中20041=a、20041=b。所以，)(kf的通项公式为：) 1(2003(20041) 1(20041200320041)(kkkkkf=为了下面的推导，先介绍一个定理：2令m是正整数。若)(modmba，)(modmdc，那么)(modmdbca+及
6、)(modmbdac。根据该定理，继续推导如下：)(kg=)(kfmod 2005。2005mod) 1(2003(20041(kk=2005mod) 1()22005() 12005(1(kk=2005mod) 1()2(1(kk=2005mod)12() 1(1(=kk2005mod)12() 1(1=+kk将 k=2005 代入得2005mod)12() 1()2005(200512005=+g2005mod) 12(2005=为了计算这个值，我们先介绍欧拉定理：欧拉函数(n)是指小于或等于 n 的正整数中与 n 互质的数的个数。1参考文献： 离散数学及其应用P313 求解常系数线性齐次
7、递推关系 2参考文献： 离散数学及其应用P118定理 7苏州工业园区星海实验中学 -第 6 页 共 6 页若整数n的因式分解式为：nmnnpmppnL2121=，则有(n)=) 1() 12() 11(2111211pmpppmppnmnnLL欧拉定理欧拉定理 对于互质的整数a和n，则有)(mod1(n)na有了欧位定理，我们可以进行如下推导：16004004) 1401() 15(4015)5*401()2005(1111=故有)2005(mod121600同理，素数 401 的欧位函数为：3400) 1401(401)401(11=故有)401(mod12400（1）同理可得：)5(mod
8、124由上面介绍过的定理，可得：)5(mod1)5(mod111222444LL也即可得：)5(mod12)2(4001004=（2）由（1） 、 （2）可得)5*401(mod12400，即)2005(mod12400所以有：2005mod22005mod2540016002005+=322005mod22005mod)2*2*2(554001600=综上所述，本题输出结果为：31小结：经典重现要求选手能掌握大量的经典算法，数学推理却要求选手具有广博扎实 的数学基础。若重现的经典没学习过，或缺少必要的数学基础及推理能力，这类题是很难解 决的。这类题对要求比较高，选手必须在日常学习过程中，注意积累，并锻炼自己的思维能 力。3欧拉定理，当 n 为素数时，其实就是费马小定理。
