资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

例6.13已知一个一维数组a[1..n](n<25),又已知一整数m。如能使数组a中任意几个

/*
例6.13 已知一个一维数组a1..n,又已知一整数m。
如能使数组a中任意几个元素之和等于m,则输出YES,反之则为NO。
【分析】对于一个已确定的数组a[1..n]和一个确定的数m,
判断能否使数组a中任意几个元素之和等于m,
等价于判断能否从数组a中取任意数使其和为m。
对于a中任意元素a[n]只有取与不取两种情况:

创新互联专注于闽清企业网站建设,响应式网站设计,商城网站制作。闽清网站建设公司,为闽清等地区提供建站服务。全流程定制网站建设,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务

(1)取a[n]:
则此时问题转化为:对于一个已确定的数组a[1..n-1]和一个确定的数m-a[n],
判断能否使数组a[1..n-1]中任意几个元素之和等于m-a[n]。

(2)不取a[n]:
则此时问题转化为:对于一个已确定的数组a[1..n-1]和一个确定的数m,
判断能否使数组a[1..n-1]中任意几个元素之和等于m。

    若用函数sum(n,m)表示能否从数组a[1..n]中取任意数使其和为m,
    只要sum(n-1,m-a[n])和sum(n-1,m)当中有一个值为真,

    则sum(n,m)为真,否则为假。因此,可以用递归来解此题。

递归终止条件为: 
    if (a[n]==m)    sum=true; 
    else if (n==1)  sum=false;

采用全程变量编写程序如下:
*/
#include
using namespace std;
const int max1=51;
int a[max1],n,m;
bool flag;
void sum(int ,int );
int main()
{
cin>>n;
for (int i=1; i<=n; ++i) cin>>a[i];
cin>>m;

flag=false;

sum(n,m);

if (flag)  cout<<"YES"<

}
void sum(int n,int m)
{
if (a[n]==m) flag=true; //利用全局变量falg传递结果
else if (n==1) return; //n=1作为递归边界,不再递归下去
else //进行两种选择
{
sum(n-1,m-a[n]);
sum(n-1,m);
}
}


名称栏目:例6.13已知一个一维数组a[1..n](n<25),又已知一整数m。如能使数组a中任意几个
文章URL:http://cdkjz.cn/article/iegsoj.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220