python3刷TK题库 1012: 外币兑换（求最值，find min and/or max）

spearous (40)in #acm • 7 years ago (edited)

这算是第一个涉及一个比较重要的算法的题目。这一类题目会要求你给出一个数组中的最值，即给出最大值或最小值或两个都要求给出。如果延伸一下，还可以求前n个最大值和前n个最小值。因此这是一个很基础的算法。首先看一下理论结果，然后看一下有没有什么python库函数可以直接调用，最后看一下求前n个最值的方法。

理论上讲

你想找出最大值最小值，至少要遍历一遍所有的数字才可以。这样，时间复杂度就是O(N)，不可能再优化。然后是比较次数的问题。如果找一次最大值遍历一次，再找一次最小值再遍历一次，一共是2N次比较。然后如果想改进比较次数，那么就要从能否把这两次遍历合二为一入手。结果当然是可以。最佳比较次数是(3/2)N。对于最佳比较次数，我们可以这么想：
首先把所有数字分成2个一组的形式，这样一共有N/2组。然后在组内有a和b两个数，另有max和min做临时变量，那么可以这样操作：
1 比较a和b （假设a>b）
2 比较a和max，如果a>max，那么a是最大值，更新max；否则max是最大值；
3 比较b和min，如果b<min, 那么b是最小值，更新min；否则min是最小值；
这样在每个组内找出最大和最小值需要3次比较，所以整体上需要(3/2)N次比较。

python3库函数

在python3标准库中，提供了一些函数调用，可以用来找出一组数（list）中的最值。

c = [-10,-5,0,5,3,10,15,-20,25]

print (min(c)) #返回最小值
print (max(c)) #返回最大值
print (c.index(min(c)))  # 返回最小值的位置
print (c.index(max(c))) # 返回最大值的位置

对于字典的求最值也可以用max()和min()，可以参见参考文献5，6.

求前n个最值

如果只是调用python3库函数的话，可以直接使用heapq模块里的nlargest()和nsmallest()。比如：

import heapq
nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
print(heapq.nlargest(3, nums)) # Prints [42, 37, 23]
print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2]

当然，他们也可以取出某个复杂数据结构中的某一个成员的最大或者最小值，只需要指定是哪个成员。比如：

portfolio = [
    {'name': 'IBM', 'shares': 100, 'price': 91.1},
    {'name': 'AAPL', 'shares': 50, 'price': 543.22},
    {'name': 'FB', 'shares': 200, 'price': 21.09},
    {'name': 'HPQ', 'shares': 35, 'price': 31.75},
    {'name': 'YHOO', 'shares': 45, 'price': 16.35},
    {'name': 'ACME', 'shares': 75, 'price': 115.65}
]
cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price'])

对于这两个函数，在库里是通过堆排序来实现的。
我们需要根据不同的场合来选用合适的函数。比如，如果只要求取出最大或者最小，则min()或者max()是比较好用的；或者如果需要取出前k个数值，并且k比总量小，那么nlargest()或者nsmallest()是比较好用的；而当k接近总量时，直接排序再使用切片来取用前k个，是比较好用的：

sorted(items)[:N]
sorted(items)[-N:]

http://tk.hustoj.com/problem.php?id=1012

1012: 外币兑换
时间限制: 1 Sec 内存限制: 32 MB
提交: 2683 解决: 1790
[提交][状态][讨论版][命题人:外部导入][下载1元][20kb]
题目描述
小明刚从美国回来，发现手上还有一些未用完的美金，于是想去银行兑换成人民币。可是听说最近人民币将会升值，并从金融机构得到了接下来十二个月可能的美元对人民币汇率，现在，小明想要在接下来一年中把美金都兑换成人民币，请问最多能得到多少人民币？
输入
输入的第一行是一个实数N（1.00<=N<=100.00），表示小明现有的美金数量。
接下来一行，包含12个实数ai，表示接下来十二个月的美元对人民币汇率。
输出
输出一个小数R，表示小明最多能获得的人民币数量，结果保留两位小数。
样例输入
46.91
6.31 6.32 6.61 6.65 5.55 5.63 6.82 6.42 6.40 5.62 6.78 5.60
样例输出
319.93

我的python3程序应该是没错的，但一直不能通过，因此列在这里作参考而已：

dollar=float(input())
if (dollar >= 1 and dollar =< 100):
    US_to_CN=input()
    for i in range(0,12):
        ratio.append(float(US_to_CN.split(' ')[i]))
    print("{:.2f}".format(max(ratio)*dollar))

参考资料：

#cn #cn-reader #tk #python

7 years ago in #acm by spearous (40)

$0.00