机器学习爱好者

aabb,3n+1问题,阶乘之和

2019-05-30  本文已影响0人  陨星落云
例题2-1:aabb

输出所有形如aabb的四位完全平方数(即前两位数字相等,后两位数字也相等)。
【分析】
我们枚举所有可能的a a b b ,然后判断它们是否为完全平方数。注意,a 的范围是1〜 9 , 但 b 可以是0。

7744问题(1)

如何判断n 是否为完全平方数?我们用过“开平方”函数,可以先求出它的平方根,然后看它是否为整数,即用一个double型变量m 储存sqrt(n), 然后判断m 是否为整数。判断整数,只需用它和它的整数部分比较即可。完整程序如下:

from math import sqrt

a = 1
while a <= 9:
    a += 1
    b = 0
    while b <= 9:
        n = a*1100 + b*11
        m = sqrt(n)
        #判断m是否为整数
        if round(m) == m:
            print('%d'%n)
        b += 1

注意:round() 方法返回浮点数x的四舍五入值。

round(4.333)
Out[1]: 4

round(4.666)
Out[2]: 5

round(4.888,2)
Out[3]: 4.89

7744问题(2)

另一个思路是枚举平方根x , 从而避免开平方操作。

n = 0
hi = 0
lo = 0 
x = 1
while x <= 100:
    n = x * x
    x += 1
    if n < 1000:
        continue
    hi = int(n / 100)
    lo = n % 100
    #判断枚举的数值是否为aabb
    if (int(hi/10) == hi%10 and int(lo/10) == lo%10):
        print('%d'%n)  
例题2-2:3n+1问题

猜想:对于任意大于1 的自然数n,若n为奇数,则将n变 为 3n+1 , 否则变为n的一半。经过若干次这样的变换,一定会使n变为 1。例如 3→10→5→16→8→4 →2→1。输 入n,输出变换的次数。n \leqslant 10^{9}
样例输入:3
样例输出:7
【分析】
不难发现,程序完成的工作依然是重复性劳动:要么乘3加1 , 要么除以2 , 但和之前程序又不太一样:循环的次数是不确定的,而且 n 也不是 “递增”式的循环。

count = 0
n = int(input('n:'))
while n > 1:
    if n % 2 == 1:
        n= 3*n + 1
    else:
        n /= 2
    count += 1
print('%d'%count)
例题2-3:阶乘之和

输入 n,计 算 S=1 !+2 !+3 !+\cdots+n !

样例输入:10
样例输出:4037913

n = int(input('n:'))
S = 0
i = 1
while i <= n:
    j = 1
    factorial = 1 #factorial为阶乘
    while j <= i:
        factorial *=j
        j+=1
        #print(j,end='')
    #print(factorial)
    S += factorial  
    i+=1
    #print(i)
print('%d'%S)

参考资料:《算法竞赛入门经典》

上一篇 下一篇

猜你喜欢

热点阅读