《阶梯式程序设计数的计算教程》由会员分享，可在线阅读，更多相关《阶梯式程序设计数的计算教程（13页珍藏版）》请在金锄头文库上搜索。
1、,阶梯式程序设计-数的计算,数的计算(count) 题目要求 我们要求找出具有下列性质数的个数(包含输入的自然数n): 先输入一个自然数n(n=1000),然后对此自然数按照如下方法进行处理: . 不作任何处理; . 在它的左边加上一个自然数,但该自然数不能超过原数的一半; . 加上数后,继续按此规则进行处理,直到不能再加自然数为止. 样例: 输入: 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 输出: 6,根据问题描述中的处理方法，对自然数n，可在它的左边加上一个自然数，但该自然数不能超过原数的一半：由题意描述，n加上数后，继续按此规则进行处理，直到不能再加自
2、然数为止。很多同学不理解题意，不妨先看样例。我们把依次产生的数据放到集合S中。 n=6 s=6 在n的左边可添加1，2，3，因此可产生新数16，26，36， S=6，16，26，36 对于这个结果大家都很容易得到了，接下来对数据16，26，36怎么扩展，是本题的重点，也是本题的难点。 在处理方法描述中，并没有对“原数”做出明确定义，怎么办? 先猜想，再通过样例验证。,思辩,(1)猜想 原数=n 由16可产生新数116，216，316；26可产生新数126，226，326：36可产生新数136，236，336。但在样例中116，216，316，226，326，236，336均没有出现，猜想失败。
3、 原数=新产生的数(如16，26，36) 则由16可产生新数116，216，316，416，516，616，716，816，同样，和样例比较，并不吻合，猜想也失败。 原数=n左边已添加的数据(如16中的1，26中的2，36中的3) 因为要求左边可添加的自然数不能超过原数的一半，数据16无法产生新数；数据26可产生新数126(左边添加1)；数据36可产生新数136(左边添加1)。S=6,16,26,36,126,136)。 126，136能否继续扩展?根据猜想，数据126是在6的左边添加了12，则可继续扩展出1126，2126，3126，4126，5126，6126，与样例不符，猜想同样失败。,
4、原数=n左边最近一次添加的数据 类似前面的分析，我们从S=6,16,26,36,126,136开始。 因为126中最近一次添加的是1，因此无法产生新数：同理136也无法产生新数。 集合S扩展结束，与样例完全吻合。 (2)理论验证 根据问题描述中的处理方法 ，要使程序能够终止，原数应该在n的基础上不断变小，否则自然数的添加会无法终止，而只有猜想符合这一要求。如n=100，可扩展出: 50100，2550100，122550100，6122550100，36122550100，136122550100。 在这里，原数依次为100，50，25，12，6，3，l，是逐渐变小的。当原数为1的时候终止扩展
5、。 很多同学喜欢一拿到题目，就凭主观臆想急着编程。俗话说“磨刀不误砍柴工”，前面的分析虽然花费了一定的时间，但它能使程序目标明确、意图清晰，何乐而不为?,分析到这步，很多同学感觉程序没有问题了。观察数据规模，n=1000，取n=1000， 则可产生数据1371531621252505001000(1000-500-250-125-62-31-15-7-3-1)，怎样表示这些数据? 可以采用高精度数。 再看试题要求：只需输出满足条件的数据个数即可。因此，能否把问题再简化? 根据变化规则，我们每次关心的只是最近一次添加的自然数，因此，可以只记录生成数据的个数，而忽略数据本身。这样，程序就简单多了。
6、,算法1 (1)数据结构 s：longint； 记录满足条件的数据个数 n：mteger； 表示原数 (2)算法描述：(用j记录数据个数) 输入数据n，s=0 s=s+1，n左边可添加的自然数为1n/2 依次设置原数为1n/2，执行语句 程序模拟： 假定n=2，符合要求的数为，12。 n=2,s=1n左边可添加的自然数为1，s=s+1=2 程序结束。 假定n=10，符合要求的数为10,110,210,1210,310,1310,410，1410,2410,12410,510,1510,2510,12510，共14个。,#include #include long s; int n; int c
7、hange(long n) int i; s+; /* 每出现一个数，累加器加1 */ for(i=1;i=n/2;i+) change(i); /*左边添加不超过原数一半的自然数，作为新原数*/ int main() double start,end; scanf(“%d“, ,换一个角度看问题，通过前面的分析，我们可以发现这样一个事实，对于任意自然数n，它能扩展出的数据个数受限于1n/2所能扩展出的数据个数。用f(n)表示自然数n所能扩展的数据总个数，则f(n)的值与f(1),f(2),f(n/2)的取值有关。 由前面的分析已知f(1)=1，f(2)=2，f(10)=14，假定n=50，则
8、当在50的左边添加自然数10时，可扩展出的数据总数为14，当在50的左边添加自然数2时，可扩展出的数据总数为2， 当在50的左边添加自然数1时，可扩展出的数据总数为1。能否用f(1),f(2),f(n/2)来表示f(n)? 猜想 : f(n)= f(1),f(2),f(n/2) 验证： 若n=2，则f(2)=f(1),错误。问题在于忽略了处理规则，f(n)存在初始值1：因此，修正递推表达式： f(3)=1+f(1)=2 f(4)=1+f(1)+f(2)=4 f(5)= 1+f(1)+f(2)=4 f(10)=1+f(1)+f(2)+f(3)+f(4)+f(5)=1+1+2+2+4+4=14 n
9、的最大值为t000，因此，时间和空间都能承受。,思辩,#include #include long long f10001; int n,i,j; int main() double start,end; scanf(“%d“, ,【进阶】,我们还可以进一步思考，从循环结构中发现可以将部分和逐一求出，用sum(i)代表从h(1)到h(i)的累加和，这样可以省出重复求每一个f(n-1)的时间。 由前面的分析, 可以得到: h(i)=1+sum( i /2 ) sum(i)=sum(i-1)+h(i);,思辩,#include #include long long h10001,sum10001; int n,i,j; int main() double start,end; scanf(“%d“, ,【提高】,谢谢观赏,谢谢观赏,2014-01,
