培训网站建设报价单,网站app简单做,网站侧边 跟随 样式,网站建设须知昨天#xff0c;小孩问了我一个python编程竞赛题#xff0c;我看了一下题目#xff0c;是一个数列编程的问题#xff0c;我在想#xff0c;小学五年级的学生能搞得懂吗#xff1f;反正我家小孩是没有搞懂#xff0c;不知道别人家的小孩能不能搞明白。所以我花了一点时间… 昨天小孩问了我一个python编程竞赛题我看了一下题目是一个数列编程的问题我在想小学五年级的学生能搞得懂吗反正我家小孩是没有搞懂不知道别人家的小孩能不能搞明白。所以我花了一点时间把编程思路记录下来。第一个方案采样通用的方法循环处理但这样的程序时间复杂度与输入的值成正比然后我又想了第二种方案采用算式计算的方法时间复杂度与输入无关。以下是我的分析思路 国王将金币作为工资发放给忠诚的骑士。
第一天骑士收到一枚金币之后两天第二天和第三天每天收到两枚金币之后三天第四五六天每天收到三枚金币之后四天每天收到四枚金币依次类推这种工资发放模式会一直延续下去当连续N天收到N枚金币后骑士会在之后的N1天每天收到N1枚金币。【白名单竞赛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
现在开始找规律当M1时N1;
当M3时M12; N2;
当M6时M123; N3;
当M10时M1234; N4;
当M15时M12345; N5;
......
从上述规律可以看出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
当N11时M1 N1 * ( N1 1 ) / 2 1;
当N22时M2 N2 * ( N2 1 ) / 2 3;
当N33时M3 N3 * ( N3 1 ) / 2 6;
当N44时M4 N4 * ( N4 1 ) / 2 10;
当N55时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 为数列和1234...N N*(N1)/2 Mn
M1 M2 M3 ... Mn 为数列和1361015... Mn N*(N1)*(N2)/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 )
