4111: 数字币
题目描述
编程实现：
小明收藏了N（2≤N≤25）个数字币，每个数字币上都有一个面值（面值可以重复）。从数字币中任选K（2≤K≤N）个，有多种选法，请将每次选择的数字币上的面值累加，然后解决以下两个问题。
问题1：累加的和中有多少种不同的结果；
问题2：累加的和中有多少个不同的合数。
例如：N=5，K=3，5个数字币上的面值分别为2、1、4、5、3，任选3个数字币，有10种选法，将每种选法上的面值累加：
2+1+4=7、2+1+5=8、2+1+3=6、2+4+5=11、2+4+3=9、2+5+3=10、1+4+5=10、1+4+3=8、1+5+3=9、4+5+3=12。
其中累加的和中有7种不同的结果，分别是7、8、6、11、9、10、12，
累加的和中有5个不同的合数，分别是8、6、9、10、12。
输入
第一行输入一个正整数N（2≤N≤25），表示数字币的个数。
第二行输入N个正整数（1≤正整数≤1000），表示数字币上的面值，正整数之间以一个英文逗号隔开。
第三行输入一个正整数K（2≤K≤N），表示所要选取的数字币个数。
输出
样例输入 复制
5
2,1,4,5,3
3样例输出 复制
7,5提示
本题用遍历法也能做，就是耗时比较长，所以这里就会用到全组合函数combinations。
本题也是体现python在数据处理中的优越性，当我们在程序中遇到需要排列组合的问题时，如果要自己编写程序，往往会非常麻烦，而python中的itertools库就为我们解决了这个小问题。itertools库中的permutations函数可以输出可迭代对象的全排列情况，而combinations函数可以输出可迭代对象的全组合情况。
from itertools import combinations
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
n = int(input())
coins = list(map(int, input().split(',')))
k = int(input())
# 计算每种选法的数字面值之和
sums = set(sum(comb) for comb in combinations(coins, k))
'''
相当于：
sums=set()
for comb in combinations(coins,k):
sums.add(sum(comb))
'''
# 统计不同数字面值之和的个数和不同合数的个数
count_sums = len(sums)
count_primes = sum(1 for s in sums if not is_prime(s))
'''
相当于：
count_primes=0
for s in sums:
if not is_prime(s):
count_primes+=1
'''
# 输出结果
print(count_sums, count_primes, sep=',')
'''
print(str(count_sums)+','+str(count_primes))
'''