刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

题目描述:(注.input()输入函数的括号中不允许添加任何信息)

提示信息:

合数:合数指自然数中除了能被1和本身整除外,还能被其它正整数整除的数。

例如4,4除了能被1和4整除,还可以被2整除。

编程实现:

小明收藏了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

使用微信搜索喵呜刷题,轻松应对考试!

答案:

首先,我们需要读入数字币的个数N、数字币的面值以及要选取的数字币个数K。然后,使用回溯法生成所有可能的选取方式,并计算累加结果中不同结果的个数以及累加结果中不同合数的个数。

解析:

【喵呜刷题小喵解析】:
本题是一道组合数学和编程题,需要用到回溯法来生成所有可能的选取方式,并计算累加结果中不同结果的个数以及累加结果中不同合数的个数。

具体实现步骤如下:

1. 读入数字币的个数N、数字币的面值以及要选取的数字币个数K。

2. 使用回溯法生成所有可能的选取方式,并计算累加结果中不同结果的个数。具体实现可以使用一个哈希表来存储已经出现过的累加结果,每生成一个选取方式,将其累加结果存入哈希表中,最后返回哈希表的长度即为累加结果中不同结果的个数。

3. 对于累加结果中每个结果,判断其是否为合数。可以使用一个哈希表来存储已经出现过的合数,每生成一个选取方式,将其累加结果存入哈希表中,如果累加结果已经出现过,则跳过;否则,判断其是否为合数,如果是合数,则将其存入合数哈希表中。最后返回合数哈希表的长度即为累加结果中不同合数的个数。

注意,在判断一个数是否为合数时,可以预先计算出一个数范围内的所有素数,然后判断该数是否可以被这些素数整除。在本题中,由于数字币的面值最大为1000,因此可以预先计算出1000以内的所有素数,然后判断累加结果是否可以被这些素数整除。

最后,将累加结果中不同结果的个数和累加结果中不同合数的个数输出即可。
创作类型:
原创

本文链接:题目描述:(注.input()输入函数的括号中不允许添加任何信息) 提示信息: 合数:合数指自然数中

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share