金币程序题

        昨天，小孩问了我一个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 )