金币程序题

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

相关推荐

  1. 金币程序

    2024-07-13 16:22:05       22 阅读
  2. 程序高频面试

    2024-07-13 16:22:05       37 阅读
  3. C语言程序10

    2024-07-13 16:22:05       24 阅读
  4. C语言程序10

    2024-07-13 16:22:05       26 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-13 16:22:05       66 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-13 16:22:05       70 阅读
  3. 在Django里面运行非项目文件

    2024-07-13 16:22:05       57 阅读
  4. Python语言-面向对象

    2024-07-13 16:22:05       68 阅读

热门阅读

  1. Docker Compose 启动容器例子

    2024-07-13 16:22:05       20 阅读
  2. vue3下载base64文件

    2024-07-13 16:22:05       22 阅读
  3. 使用 WebSocket 进行实时数据传输

    2024-07-13 16:22:05       22 阅读
  4. Redis中的管道技术

    2024-07-13 16:22:05       19 阅读
  5. C语言学习第一章--分步编译

    2024-07-13 16:22:05       17 阅读
  6. 力扣题解( 最长数对链)

    2024-07-13 16:22:05       20 阅读
  7. 嵌入式单片机项目开发的基本思想分享

    2024-07-13 16:22:05       19 阅读