首页 > 编程资源分享区 > C/C++测试题 > 一道c++竞赛题
2005
12-29

一道c++竞赛题

已知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
7 12 19
输出:
  1
源程序:
#include<iostream>
#include<math.h>
  const int N=21;
  using namespace std;
  int issushu(long num)
  {
      for(long i=2;i<=sqrt(num);i++)
      if(num%i==0)
           return 0;
      return 1;
  }
long totalsum(long a[],int n)
{
    long sum=0;
    for(int i=0;i<n;i++)
      sum+=a;
    return sum;
}
int main()
{
    cout<<endl<<”please input the number(0~20) of the numlist and the choose numbers:”;
    int num=0,k=0;
    cin>>num>>k;
    cout<<”please input “<<num<<” listnum:”;
    long num1[N],num2[N];
    for(int i=0;i<num;i++)
        cin>>n um1;
    long num3=0,count=0;
    for(int j=0;j<k;j++)
       num2[j]=num1[j];
    num3=totalsum(num2,k);
    if(issushu(num3))
    count++;
    int m=0;
    long data=0;
    for(int n=0;n<k;n++)
    {
        data=num2[n];
      for(m=k;m<num;m++)
      {
           num2[n]=num1[m];
           num3=totalsum(num2,k);
           if(issushu(num3))
               count++;
      }
      num2[n]=data;
    }
    cout<<endl<<”the kinds number is:”<<count<<endl;
    return 0;
}


留下一个回复