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次幂，an可以转化为a(p+q),其中p+q=n,因此我们只要把an转化为几个适当的p,q,满足aq * a^p * ....a^x = an，这样可以大大简化算法的复杂度。我们可以先把十进制数n化为二进制数xxxxxxxx(2),如100可以化为1100100(2)，拆分为幂的和为：2、32、64,然后分别算22,232,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")
