第一关：找零钱问题
任务描述
假设有4种硬币，它们的面值分别为2角5分，1角、5分和1分，现在要找给某顾客x分钱，问怎样找零钱才能使给的顾客的硬币个数量少？
相关知识
算法原理
贪心法找零钱的基本思想是：每次都是选择面值不超过需要找给顾客的钱的最大面值的硬币。以上面找零钱的问来说：选出一个面值不超过6角3分的最大面值硬币2角5分找给顾客，然后还要找3角8分；选出一个面值不超过3角8分的最大面值硬币2角5分找给顾客，然后还要找1角3分；选出一个面值不超过1角3分的最大面值硬币1角找给顾客，然后还要找3 分；选出一个面值不超过3分的最大面值硬币1分找给顾客，然后还要找2分；选出一个面值不超过2分的最大面值1分找给顾客，然后还要找1分；最后选出一个面值不超过1分的最大面值硬币1 分找给顾客，这种找硬币的方法实际上就是贪心算法。
编程要求
根据提示，在右侧编辑器编写greedy函数，计算并输出找钱方案。
测试说明
平台会对你编写的代码进行测试：
测试输入： 要找给顾客的零钱，单位：分：63
（注意：63前面的信息实际上是输出）
预期输出：
要找给顾客25分的硬币：2
要找给顾客10分的硬币：1
要找给顾客5分的硬币：0
要找给顾客1分的硬币：3
找给顾客的硬币数最少为：6
# #贪心算法解决找零钱问题
v = [25, 10, 5, 1]
n = [0, 0, 0, 0]
def change():
T = int(input('要找给顾客的零钱，单位：分：'))
greedy(T)
for i in range(len(v)):
print('要找给顾客%d分的硬币：%d' % (v[i], n[i]))
s = 0
for i in n:
s = s + i
print('找给顾客的硬币数最少为：%d' % s)
def greedy(T):
p = 0
for p in range(len(v)):
while T >= v[p]:
T -= v[p]
n[p] += 1
# # please finish this function
if __name__ == "__main__":
change()
# ## 思考题：
# ## 如果v = [12,10,5,1]
# ## 贪心算法能得到正确的解吗？请证明。
# 不能，因为贪心算法下，每次都选择最大的那个硬币，而最大的那个硬币可能是12，
# 而设定输入为63时，易得12*4+10*1+5*1=63总计6枚硬币，贪心算法下的解为8要少。
# 只因12和10之间的差距过小
第二关：哥德巴赫猜想
任务描述
本关任务：编写程序证明哥德巴赫猜想。
编程要求
根据提示，在右侧编辑器补充代码。
测试说明
平台会对你编写的代码进行测试：
测试输入： 90；
预期输出： 7, 83
测试输入： 6；
预期输出： -1, -1
# 设计一个算法，验证哥德巴赫猜想：
# 任何一个充分大的偶数（大于6）总可以表示成两个素数之和.
# 请编写python 程序实现该算法。
def prove(n):
if n <= 6 or n % 2 != 0:
return -1, -1
for i in range(2, n): # 写一个循环，用于找出答案的素数
if sushu(i) and sushu(n - i):
return i, n - i
def sushu(n): # 懒了一下，这里直接写个素数判断的函数
if n >= 2:
for i in range(2, n):
if n % i == 0:
return False
return True
if __name__ == '__main__':
n = int(input())
print("%d, %d" % prove(n))
# 当然你也可以写一个列表用于装所有素数（列表的大小取决于你n的输入值）
# 然后让i在上述列表里遍历，得到答案
第3关：冯诺依曼
任务描述
本关任务：编写一个实现自然数的集合表示形式。
冯•诺依曼不单是一位计算机科学家，也是很有名的数学家，他用集合来定义自然数系统，定义如下： 0 = {} = {} 1 = {0} = {{}} 2 = {0, 1} = {{}, {{}}} 3 = {0, 1, 2} = {{}, {{}}, {{}, {{}}}} …… 请根据上述定义，写出递归函数，由用户输入一个自然数N，输出该自然数对应的集合表示。例如，如输入为2，则输出为{{}, {{}}}。
测试说明
平台会对你编写的代码进行测试：
测试输入：
2
预期输出：
{{}, {{}}}
# ## 请编写代码
n = int(input())
def vonNeumann(n):
sum = '{}' # 注意sum是字符串
if n == 0:
return sum
if n == 1:
return '{' + sum + '}'
else:
for i in range(1, n):
sum = sum + ', ' + vonNeumann(i) # 这里是完成程序的关键，将每次的返回值都归到sum里
return '{' + sum + '}'
print(vonNeumann(n))
参考阅读
您阅读本篇文章共花了：
发表评论