【NOIP普及组】 选数
|
💐The Begin💐点点关注，收藏不迷路💐
|
已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34。
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。
输入
键盘输入，格式为：
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000）
输出
屏幕输出，格式为：
一个整数（满足条件的种数）。
样例输入
4 3
3 7 12 19
样例输出
1
C 语言实现的代码：
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// 判断一个数是否为素数
bool isPrime(int num) {
// 如果小于 2 不是素数
if (num < 2) return false;
// 2 和 3 是素数
if (num == 2 || num == 3) return true;
// 能被 2 或 3 整除不是素数
if (num % 2 == 0 || num % 3 == 0) return false;
int i = 5;
int w = 2;
// 从 5 开始用特定方式判断是否为素数
while (i * i <= num) {
// 如果能被 i 整除不是素数
if (num % i == 0) return false;
i += w;
w = 6 - w;
}
return true;
}
int main() {
int n, k;
// 输入整数个数 n 和要选的个数 k
scanf("%d %d", &n, &k);
int arr[20];
for (int i = 0; i < n; i++) {
// 输入 n 个整数
scanf("%d", &arr[i]);
}
int count = 0;
// 生成所有可能的组合
for (int i = 0; i < (1 << n); i++) {
int selectedCount = 0;
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
// 当前位被选中，计数加一，累加和
selectedCount++;
sum += arr[j];
}
}
if (selectedCount == k && isPrime(sum)) {
// 如果选中的个数等于 k 且和为素数，计数加一
count++;
}
}
// 输出满足条件的种数
printf("%d\n", count);
return 0;
}
以下是对这段 C 语言代码的解析：
一、整体功能概述
这段代码的目的是计算从给定的n个整数中任选k个整数相加，其和为素数的组合数。
二、函数解析
-
isPrime函数：- 这个函数用于判断一个整数是否为素数。
- 首先处理小于 2 的情况，小于 2 的数不是素数，直接返回
false。 - 接着判断 2 和 3 是素数，直接返回
true。 - 对于大于 3 的数，先判断是否能被 2 或 3 整除，如果能则不是素数，返回
false。 - 然后从 5 开始，使用一种特定的方式进行判断，通过循环不断尝试可能的因子，直到尝试的数的平方大于要判断的数为止。如果在这个过程中发现能整除的情况，就返回
false，否则返回true。
-
main函数：- 输入部分：
- 首先从标准输入读取整数个数
n和要选的个数k。 - 接着使用一个循环读取
n个整数并存入数组arr中。
- 首先从标准输入读取整数个数
- 计数部分：
- 初始化计数变量
count为 0。 - 通过一个循环遍历从 0 到
(1 << n) - 1的所有整数，这个循环实际上是在生成所有可能的组合。因为对于n个元素，总共有2^n种不同的选取方式，每一种选取方式可以用一个n位的二进制数表示，其中每一位对应一个元素，如果该位为 1 则表示选取该元素，为 0 则表示不选取。 - 在这个循环内部，对于每一个整数
i，使用两个变量selectedCount和sum分别记录当前组合中被选中的元素个数和它们的和。通过遍历数组arr，如果i的二进制表示中对应位置为 1，则将该位置的元素加入和中，并增加选中元素的个数。 - 如果选中的元素个数等于
k并且这个和是素数（通过调用isPrime函数判断），则增加计数变量count。
- 初始化计数变量
- 输出部分：
- 最后将满足条件的组合数输出到标准输出。
- 输入部分：
三、时间复杂度和空间复杂度分析
- 时间复杂度：
isPrime函数的时间复杂度近似为 O ( n ) O(\sqrt{n}) O(n)，其中n是要判断的整数。main函数中的外层循环遍历所有可能的组合，时间复杂度为 O ( 2 n ) O(2^n) O(2n)，其中n是输入的整数个数。内层循环遍历输入的数组，时间复杂度为 O ( n ) O(n) O(n)。因此总体时间复杂度为 O ( 2 n ∗ n ) O(2^n * n) O(2n∗n)加上判断素数的时间复杂度，近似为 O ( 2 n ∗ n + 2 n ∗ m ) O(2^n * n + 2^n *\sqrt{m}) O(2n∗n+2n∗m)，其中m是可能的最大和，通常远小于 2 n ∗ n 2^n * n 2n∗n，所以总体时间复杂度可以近似为 O ( 2 n ∗ n ) O(2^n * n) O(2n∗n)。
- 空间复杂度：
- 主要的空间消耗来自存储输入的整数数组
arr，空间复杂度为 O ( n ) O(n) O(n)，其中n是输入的整数个数。
- 主要的空间消耗来自存储输入的整数数组
C++实现的代码：
#include <iostream>
#include <vector>
#include <cmath>
// 判断一个数是否为素数
bool isPrime(int num) {
// 如果小于 2 不是素数
if (num < 2) return false;
// 2 和 3 是素数
if (num == 2 || num == 3) return true;
// 能被 2 或 3 整除不是素数
if (num % 2 == 0 || num % 3 == 0) return false;
int i = 5;
int w = 2;
// 从 5 开始用特定方式判断是否为素数
while (i * i <= num) {
// 如果能被 i 整除不是素数
if (num % i == 0) return false;
i += w;
w = 6 - w;
}
return true;
}
int main() {
int n, k;
// 输入整数个数 n 和要选的个数 k
std::cin >> n >> k;
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
// 输入 n 个整数
std::cin >> arr[i];
}
int count = 0;
// 生成所有可能的组合
for (int i = 0; i < (1 << n); i++) {
int selectedCount = 0;
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
// 当前位被选中，计数加一，累加和
selectedCount++;
sum += arr[j];
}
}
if (selectedCount == k && isPrime(sum)) {
// 如果选中的个数等于 k 且和为素数，计数加一
count++;
}
}
// 输出满足条件的种数
std::cout << count << std::endl;
return 0;
}
Java 实现的代码：
import java.util.Scanner;
class PrimeSumCombination {
// 判断一个数是否为素数
public static boolean isPrime(int num) {
// 如果小于 2 不是素数
if (num < 2) return false;
// 2 和 3 是素数
if (num == 2 || num == 3) return true;
// 能被 2 或 3 整除不是素数
if (num % 2 == 0 || num % 3 == 0) return false;
int i = 5;
int w = 2;
// 从 5 开始用特定方式判断是否为素数
while (i * i <= num) {
// 如果能被 i 整除不是素数
if (num % i == 0) return false;
i += w;
w = 6 - w;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
// 输入整数个数 n
int k = scanner.nextInt();
// 输入要选的个数 k
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
// 输入 n 个整数
arr[i] = scanner.nextInt();
}
int count = 0;
// 生成所有可能的组合
for (int i = 0; i < (1 << n); i++) {
int selectedCount = 0;
int sum = 0;
for (int j = 0; j < n; j++) {
if ((i & (1 << j))!= 0) {
// 当前位被选中，计数加一，累加和
selectedCount++;
sum += arr[j];
}
}
if (selectedCount == k && isPrime(sum)) {
// 如果选中的个数等于 k 且和为素数，计数加一
count++;
}
}
// 输出满足条件的种数
System.out.println(count);
}
}
Python 实现的代码：
def is_prime(num):
# 如果小于 2 不是素数
if num < 2:
return False
# 2 和 3 是素数
if num == 2 or num == 3:
return True
# 能被 2 或 3 整除不是素数
if num % 2 == 0 or num % 3 == 0:
return False
i = 5
w = 2
# 从 5 开始用特定方式判断是否为素数
while i * i <= num:
# 如果能被 i 整除不是素数
if num % i == 0:
return False
i += w
w = 6 - w
return True
n, k = map(int, input().split())
# 输入整数个数 n 和要选的个数 k
arr = list(map(int, input().split()))
# 输入 n 个整数
count = 0
# 生成所有可能的组合
for i in range(1 << n):
selected_count = 0
s = 0
for j in range(n):
if i & (1 << j):
# 当前位被选中，计数加一，累加和
selected_count += 1
s += arr[j]
if selected_count == k and is_prime(s):
# 如果选中的个数等于 k 且和为素数，计数加一
count += 1
print(count)
# 输出满足条件的种数
|
💐The End💐点点关注，收藏不迷路💐
|
