邯郸网站建设服务报价wordpress空页面模板
昨天，小孩问了我一个python编程竞赛题，我看了一下题目，是一个数列编程的问题，我在想，小学五年级的学生能搞得懂吗？反正我家小孩是没有搞懂，不知道别人家的小孩能不能搞明白。所以我花了一点时间，把编程思路记录下来。第一个方案采样通用的方法，循环处理，但这样的程序时间复杂度与输入的值成正比，然后我又想了第二种方案，采用算式计算的方法，时间复杂度与输入无关。以下是我的分析思路：
国王将金币作为工资，发放给忠诚的骑士。
第一天骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四，五，六天），每天收到三枚金币；之后四天，每天收到四枚金币，依次类推；这种工资发放模式会一直延续下去，当连续N天收到N枚金币后，骑士会在之后的N+1天，每天收到N+1枚金币。【白名单竞赛NOC】
请编写程序计算前M天里，骑士一共获得了多少金币。
【输入格式】输入包含一个正整数M，表示发放金币的天数。
【输出格式】输出一个正整数，即骑士收到的金币数。
【输入样例】
6
【输出样例】
14
分析：
天数： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ......
金币数： 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ......
总数： 1 3 5 8 11 14 18 22 26 30 35 40 45 50 55 ......
可以知道：
第1天收到1枚金币，第二三天每天收到2枚金币，第四五六天每天收到3枚金币，第七八九十天每天收到4枚金币，按这个规律一直持续下去；
每天发放金币的数量的增长规律是：1,2,3,4,5,6，。。。即1枚金币发放1天，2枚金币发放2天，3枚金币发放3天。。。N枚金币发放N天；
所以发放的金币总数量: （假设N枚金币刚好连续发放了N天）
total = 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + ... + N * N
题目需求是：用户输入天数M,输出发放的总的金币数；
所以首先我们要根据天数M，计算出当天发放的金币数N。
我们从上述表格中可以看出：在第1,3,6,10,15，。。。天的时候，当天发放的金币数量是1,2,3,4,5，。。。；并且1枚金币发了1天，2枚金币发了2天，。。。5枚金币刚好发了5天；
所以，我们首先假设用户刚好输入的是1,3,6,10,15，。。。这些天数，然后我们根据这些天数来计算当天应该发放的金币数N；
现在开始找规律：当M=1时：N=1;
当M=3时：M=1+2; N=2;
当M=6时：M=1+2+3; N=3;
当M=10时：M=1+2+3+4; N=4;
当M=15时：M=1+2+3+4+5; N=5;
......
从上述规律可以看出M的值为：M = 1 + 2 + 3 + 4 + 5 + ... + N
这样我们可以使用循环来进行计数累加，当累加值大于等于M时，循环终止，此时计数值即为N。
最后考虑到用户输入的值会小于累加值，在计算总金币数的时候要减掉（M-用户输入）*N的数量。
程序如下：
M = int( input( “请输入一个正整数：” ) )
num = 0
total = 0
for N in range( 1,M ) :
num = num + N
total = total + N * N
if num >= M :
total = total - ( num - M ) * N
break
print( total )
上述程序虽说可以正确输出结果，但是程序运行的时间随着用户输入的数值变大而变长，下面我们换一种方法，使得程序的运行时间与输入无关。
上面的分析我们已经知道：（当用户刚好输入的是1,3,6,10,15，。。。这些天数）
M = 1 + 2 + 3 + 4 + 5 + ... + N = N * ( N + 1 ) / 2
当N1=1时：M1= N1 * ( N1 + 1 ) / 2 = 1;
当N2=2时：M2= N2 * ( N2 + 1 ) / 2 = 3;
当N3=3时：M3= N3 * ( N3 + 1 ) / 2 = 6;
当N4=4时：M4= N4 * ( N4 + 1 ) / 2 = 10;
当N5=5时：M5= N5 * ( N5 + 1 ) / 2 = 15;
......
考虑到等式：M = N * ( N + 1 ) / 2 即：
N*N + N - 2*M = 0 (1)
解方程得：N= ( sqrt( 1 + 8 * M ) - 1 ) / 2
上面分析我们已经知道总金币数：
total = 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4 + ... + N * N
我们用N1,N2,N3,......,NN表示总金币数：
total = N1*N1 + N2*N2 + N3*N3+ N4*N4 + ... + Nn*Nn
用式1代入得：
total = ( 2 * M1 - N1 ) + ( 2 * M2 - N2 ) + ( 2 * M3 - N3 ) + ... + ( 2 * Mn - Nn )
= 2 * ( M1 + M2 + M3 + ... + Mn ) - ( N1 + N2 + N3 + ... + Nn )
N1 + N2 + N3 + ... + Nn 为数列和：1+2+3+4+...+N = N*(N+1)/2 = Mn
M1 + M2 + M3 + ... + Mn 为数列和：1+3+6+10+15+... +Mn = N*(N+1)*(N+2)/6
所以：total = 2 * ( M1 + M2 + M3 + ... + Mn ) - ( N1 + N2 + N3 + ... + Nn )
= 2 * N * ( N + 1 ) * ( N + 2 ) / 6 - N * ( N + 1 ) / 2
= N * ( N + 1 ) * ( 2 * N + 1 ) / 6
= Mn * ( 2 * N + 1 ) / 3
考虑到用户输入的数值M小于Mn , 修正总数为：
total = Mn * ( 2 * N + 1 ) / 3 - ( Mn - M ) * N
= ( 3 * M * N + Mn - Mn * N ) / 3
最后程序如下：
import math
M = int( input( “请输入一个正整数：” ) )
Nf = ( math.sqrt( 1 + 8 * M ) - 1 ) / 2
N = int( Nf )
if Nf > N:
N = N + 1
Mn = N * ( N + 1 ) / 2
total = ( 3 * M * N + Mn - Mn * N ) / 3
print( total )