Python挑战100题（21~26）

21、山峰的个数

题目：十一假期,小P出去爬山,爬山的过程中每隔10米他都会记录当前点的海拔高度(以一个浮点数表示),
这些值序列保存在一个由浮点数组成的列表h中。回到家中，小P想研究一下自己经过了几个山峰，请你帮他计算一下，输出结果。
例如：h=[0.9,1.2,1.22,1.1,1.6,0.99], 将这些高度顺序连线，会发现有两个山峰，故输出一个2(序列两端不算山峰)
参考答案：

h=[0.9,1.2,1.22,1.1,1.6,0.99]
count = 0
for i in range(1,len(h)-1):
    if h[i]>h[i-1] and h[i]>h[i+1]:
        count += 1
print(count)

22、三角形形状

题目：给以一个三角形的三边长a,b和c(边长是浮点数),请你判断三角形的形状。
若是锐角三角形，输出R,
若是直角三角形，输出Z，
若是钝角三角形，输出D，
若三边长不能构成三角形，输出W.
提示：
1..若其中有两边相等,则为[等腰三角形]
2.若其中有三边相等,则为[等边三角形]
3.若a的平方+b的平方=c平方,则为[直角三角形]
4.若a的平方+b的平方>c平方,则为[锐角三角形]
5.若a的平方+b的平方<c平方,则为[钝角三角形]
参考答案：

a,b,c = [4,3,5]
a,b,c = sorted([a,b,c])
if a+b>c and c-a<b:
    ab = a*a + b*b
    cc = c*c
    if ab>cc:
        print('R')
    elif ab<cc:
        print('D')
    else:
        print('Z')
else:
    print('W')

23、大幂次运算

题目：给你两个正整数a(0 < a < 100000)和n(0 <= n <=100000000000)，计算(a^n) % 20132013并输出结果
提示：
pow(x,y,z) 函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z
参考答案：

print(pow(a,n,20132013))

更深入：来源http://www.pythontip.com/coding/report_detail/632/

先贴出AC代码如下：

def powAndMod(a,n,mod):

    res = 1
    while n > 0:
        if n%2 == 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res
print powAndMod(a,n,20132013)

代码在前面几个ACer的解题报告里面有一模一样的，我自己也是研究了好一阵子才知道代码的含义。讲解针对于小白，牛人就不用看了。

之前我写了如下代码，先求得a的n次幂，然后对20132013取模。求次幂是用的递归。

-－－－－－－－－－－－－－－－－－
def pow(a,n):
    if n == 0:
        return 1
    else:
        return a*pow(a,n-1)
print pow(a,n)%20132013

提交的结果是超时，要求优化算法，因为a和n的数值很大的时候，递归的次数超过了规定的递归深度。因此只有寻找更好的算法。

算法思想：对于任意a和n求a的n次幂，a^{n可以转化为a}(p+q),其中p+q=n,因此我们只要把a^{n转化为几个适当的p,q,满足a}q * a^p * ....a^x = a^{n，这样可以大大简化算法的复杂度。我们可以先把十进制数n化为二进制数xxxxxxxx(2),如100可以化为1100100(2)，拆分为幂的和为：2、32、64,然后分别算2}2,2^32,264的数值，把它们相乘即可得到2^100。

24、最大连续子序列

题目：给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个连续子序列，使其和最大，输出最大子序列的和。
例如，对于L=[2,-3,3,50]，输出53（分析：很明显，该列表最大连续子序列为[3,50]).
参考答案：

L=[-2 ,6, -8, 5, 4, -7, 2, 6]
i = 0
sum = L[0]
for x in L:
    i += x
    if i > sum:
        sum = i
    elif i < 0:
        i = 0
print(sum)

25、最大非连续子序列

题目：给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个非连续子序列，使其和最大，输出最大子序列的和。
这里非连续子序列的定义是，子序列中任意相邻的两个数在原序列里都不相邻。
例如，对于L=[2,-3,3,50]，输出52（分析：很明显，该列表最大非连续子序列为[2,50]).
参考答案：
动态规划：https://blog.csdn.net/Herishwater/article/details/94546608

L=[2,-3,3,50,-4,1]
n = len(L)
f = list(L)
for i in range(n):
    if i > 0:
        f[i] = max(f[i],f[i-1])
    if i > 1:
        f[i] = max(f[i],f[i-2]+L[i])
print(f[n-1])

**另一个：
**

# 看不懂的解决方案
for i in range(2,len(L)):
    L[i]=max(L[i-2]+L[i],L[i],L[i-2],0)
    L[i-1]=max(L[i-2],L[i-1],0)
print(max(L))

再一个：

L=[2,-3,3,50,-4,1]
b=[0 for i in range(len(L))]
for i in range(len(L)):
    if i==0 or i==1:
        b[0] = L[0]
        b[1] = L[1]
    else:
        b[i] = max(max(b[0:i-1])+L[i],L[i])
print(max(b))

26、Py数

题目：Py从小喜欢奇特的东西，而且天生对数字特别敏感，一次偶然的机会，他发现了一个有趣的四位数2992，
这个数，它的十进制数表示，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22，
同时它的十二进制数表示1894，其四位数字之和也为22，啊哈，真是巧啊。
Py非常喜欢这种四位数，由于他的发现，所以这里我们命名其为Py数。
现在给你一个十进制4位数n，你来判断n是不是Py数，若是，则输出Yes，否则输出No。
如n=2992，则输出Yes； n = 9999，则输出No。
知识补充：

image.png

十六进制的加法：
加减法的进/借位规则为：借一当十六，逢十六进一。

例如：3F+4A，写成竖式，先算F+A，F是十进制中的15，A是十，加起来是二十五，在十六进制中，满十六进一，二十五在十六进制中就是19，所以个位是9，进1，3+4+1=8，最后等于十六进制89。
相关函数：hex() 函数用于将10进制整数转换成16进制，以字符串形式表示。
十二进制：十进制到十二进制的转换可按下面的例子进行：
123456 ÷ 12 = 10288 ... 0 10288 ÷ 12 = 857 ... 4 857 ÷ 12 = 71 ... 5 71 ÷ 12 = 5 ... 11 (B) 5 ÷ 12 = 0 ... 5
将最右排的数从下往上依次写下，即得到123456 = （5B540）12 。

参考答案：

def py(a):
    sum1 = 0
    sum2 = 0
    e = list(str(a))
    for i in range(len(e)):
        sum1 += int(e[i])
    b = hex(a)                 # 换成16进制
    for j in range(2,len(b)):  # 16进制前两位0x表示16进制
        sum2 += int(b[j],16)   # int('39',16)将16进制的数39换算成10进制的数
    L = []
    while a>0:                 # 换成12进制数的集合
        L.append(a % 12)
        a //= 12
    f = sum(L)
    if sum1 == sum2 == f:
        print('Yes')
    else:
        print('No')

a = int(input('请输入需要判断的数a:'))
py(a)

参考二：

a = 0
tmp = n
while tmp:
    a += tmp % 12
    tmp //= 12

b = 0
tmp = n
while tmp:
    b += tmp % 10
    tmp //= 10

c = 0
tmp = n
while tmp:
    c += tmp % 16
    tmp //= 16

if a == b and b == c:
    print("Yes")
else:
    print("No")