ACM入门题（一）
程序员文章站
2022-05-22 09:57:38
...
question:
用给定的几种钱币凑成某个钱数，一般而言有多重方式。例如，给定了6中钱币面值为2,5,10,20,50，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者用1个5元、1个10元等，显然，最少需要2个钱币，草能凑成15元
destination:
给定输入若干互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。若凑不了，则输出'impossible'
My code:
def main():
input_num= input("input your num:")
input_num = int(input_num)
#158
type_list = input("input your type list:")
#[2,5,10,20,50,100]
type_list = sorted(type_list, reverse=True)
for i in range(len(type_list)):
type_list[i] = int(type_list[i])
#-----------------------------------------------1---------------------------------------------------
if input_num >= type_list[0]:
num0 = int(input_num/type_list[0])
res0 = int(input_num%type_list[0])
# -----------------------------------------------1.2---------------------------------------------------
if res0 >= type_list[1]:
num1 = int(res0/type_list[1])
res1 = int(res0%type_list[1])
if res1 >= type_list[2]:
num2 = int(res1/type_list[2])
res2 = int(res1%type_list[2])
if res2 >= type_list[3]:
num3 = int(res2/type_list[3])
res3 = int(res2%type_list[3])
if res3 >= type_list[4]:
num4 = int(res3/type_list[4])
res4 = int(res3%type_list[4])
if res4 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[1], num2, type_list[2], num3, type_list[3], num4, type_list[4])
else:
if res3 == 0:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[1], num2, type_list[2], num3, type_list[3])
else:
return 'impossible'
elif res2 >= type_list[4]:
num3 = int(res2 / type_list[4])
res3 = int(res2 % type_list[4])
if res3 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1], num2, type_list[2], num3, type_list[4])
else:
if res2 == 0:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1], num2, type_list[2])
else:
return 'impossible'
elif res1 >= type_list[3]:
num2 = int(res1 / type_list[3])
res2 = int(res1 % type_list[3])
if res2 >= type_list[4]:
num3 = int(res2 / type_list[4])
res3 = int(res2 % type_list[4])
if res3 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1], num2, type_list[3], num3, type_list[4])
else:
if res2 == 0:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1], num2, type_list[3])
else:
return 'impossible'
elif res1 >= type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[1])
else:
return 'impossible'
# -----------------------------------------------1.3---------------------------------------------------
elif res0 >= type_list[2]:
num1 = int(res0/type_list[2])
res1 = int(res0%type_list[2])
if res1 >= type_list[3]:
num2 = int(res1/type_list[3])
res2 = int(res1%type_list[3])
if res2 >= type_list[4]:
num3 = int(res2/type_list[4])
res3 = int(res2%type_list[4])
if res3 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[2], num2, type_list[3], num3, type_list[4])
else:
if res2 == 0:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[2], num2, type_list[3])
else:
return 'impossible'
elif res1 >= type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[2], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[0], num1, type_list[2])
else:
return 'impossible'
# -----------------------------------------------1.3---------------------------------------------------
elif res0 >= type_list[3]:
num1 = int(res0 / type_list[3])
res1 = int(res0 % type_list[3])
if res1 >= type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[3], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[3])
else:
return 'impossible'
# -----------------------------------------------1.4---------------------------------------------------
elif res0 >= type_list[4]:
num1 = int(res0 / type_list[4])
res1 = int(res0 % type_list[4])
if res1 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d' % (num0, type_list[0], num1, type_list[4])
# -----------------------------------------------1.5---------------------------------------------------
else:
if res0 == 0:
return 'least need %d 个 %d' % (num0, type_list[0])
else:
return 'impossible'
# -----------------------------------------------2---------------------------------------------------
elif input_num >= type_list[1]:
num0 = int(input_num/type_list[1])
res0 = int(input_num%type_list[1])
if res0 >= type_list[2]:
num1 = int(res0/type_list[2])
res1 = int(res0%type_list[2])
if res1 >= type_list[3]:
num2 = int(res1/type_list[3])
res2 = int(res1%type_list[3])
if res2 >= type_list[4]:
num3 = int(res2/type_list[4])
res3 = int(res2%type_list[4])
if res3 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[1], num1, type_list[2], num2, type_list[3], num3, type_list[4])
else:
if res2 == 0:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[2], num2, type_list[3])
else:
return 'impossible'
elif res1 > type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[2], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[2])
else:
return 'impossible'
elif res0 >= type_list[3]:
num1 = int(res0 / type_list[3])
res1 = int(res0 % type_list[3])
if res1 >= type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[3], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[3])
else:
return 'impossible'
elif res0 >= type_list[4]:
num1 = int(res0 / type_list[4])
res1 = int(res0 % type_list[4])
if res1 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[1], num1, type_list[4])
else:
if res0 == 0:
return 'least need %d 个 %d' % (
num0, type_list[1])
else:
return 'impossible'
# -----------------------------------------------3---------------------------------------------------
elif input_num >= type_list[2]:
num0 = int(input_num / type_list[2])
res0 = int(input_num % type_list[2])
if res0 >= type_list[3]:
num1 = int(res0 / type_list[3])
res1 = int(res0 % type_list[3])
if res1 >= type_list[4]:
num2 = int(res1 / type_list[4])
res2 = int(res1 % type_list[4])
if res2 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d; %d 个 %d' % (num0, type_list[2], num1, type_list[3], num2, type_list[4])
else:
if res1 == 0:
return 'least need %d 个 %d; %d 个 %d' % (num0, type_list[2], num1, type_list[3])
else:
return 'impossible'
elif res0 >= type_list[4]:
num1 = int(res0 / type_list[4])
res1 = int(res0 % type_list[4])
if res1 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d' % (
num0, type_list[2], num1, type_list[4])
else:
if res0 == 0:
return 'least need %d 个 %d' % (
num0, type_list[2])
else:
return 'impossible'
# -----------------------------------------------3---------------------------------------------------
elif input_num >= type_list[3]:
num0 = int(input_num / type_list[3])
res0 = int(input_num % type_list[3])
if res0 >= type_list[4]:
num1 = int(res0 / type_list[4])
res1 = int(res0 % type_list[4])
if res1 > 0:
return 'impossible'
else:
return 'least need %d 个 %d; %d 个 %d' % (num0, type_list[3], num1, type_list[4])
else:
if res0 == 0:
return 'least need %d 个 %d' % (num0, type_list[3])
else:
return 'impossible'
# -----------------------------------------------4---------------------------------------------------
elif input_num >= type_list[4]:
num0 = int(input_num / type_list[4])
res0 = int(input_num % type_list[4])
if res0 > 0:
return 'impossible'
else:
res = num0
return 'least need %d 个 %d' % (res, type_list[4])
# -----------------------------------------------5---------------------------------------------------
else:
return 'impossible'
if __name__ == '__main__':
result = main()
print(result)
input & output:
get:
1.从input输入的数据类型为str，要先做转int处理
2.一开始直接在对最后数据type_list[4]与上一步余数进行判断，else则为零，未考虑到已经被数组上一位整除的情况，导致输出为Impossible；后在每一次对type_list[4]与上一步余数进行判断后的else中再次对上一步余数进行是否为零的判断，再输出即可
note:
1.本程序默认输入为长度为5的数组，对于输入为10元以上的纸币尚且没想到可行的方法(若载输入时每种面值钱币间增加空格，则在转换成int数据时报错，求大神指导)