Question

我想问一下这道递归题目怎么做的？？？

就是给你一个数组 数组的个数小于50个 然后给你一个数 如果数组中的一个或几个的和等于给的数 那么输出YES 要不然的话就输出NO

讲一下大致的思路就好 最好浅显一点 我刚学算法 就会一些简单的递归题目

Answer 1

人家要求的是和，而不是存不存在这样的数！
题都没看明白就瞎写`

Answer 2

这个用递归？ 我怎么感觉跟排序算法基本差不多呢。
cnt=数组个数；
x[]为数组；
y为目标数；
int temp;
int count=0;//计数器
for(i=0;i<cnt;i++)
{
if(x[i]>y)
{
continue;
}
temp=0;
for(j=i;j<cnt;j++)
{
temp += x[j];
if(temp==y)
{
printf("YES\n");
count++;
}
elseif(temp>y)
{
break;
}
}
}

if(count<1)
{
printf("No");
}

自己凭感觉写的，没测。

Answer 3

//arry为数组首地址，length为数组长度，index为索引的偏移量，value为要寻找的数。
//鉴于你的要求，只要有一个或几个等于value则输出yes。那么只要找到一个等于value就应当输出value，没有必要找到所有value的位置。
bool fun(int *arry,int length,int index,int value)
{
if (value == *(arry+index))
{
return true;
}
if (length == index)
{
return false;
}
return fun(arry,length,++index,value);
}

Answer 4

std::find_if();即可。

Answer 5

比如数组是1到10，还要有个等容量的数组用来标记状态。目标数 21
则先遍历一遍，如果有，则函数完成，标记找到的数；
否则遍历数组，寻找目标数-数组[i].
每次寻找成功必须标记使用的数
这种算法效率可能比较低~
……
下面是完整代码：
#include<iostream>
using namespace std;
bool fun(int *arr,int *state,int n,int tar);
void show(int *arr,int *state,int n,int tar);
void main(){
char ch,pre='#';
int i=0,num,a[12],s[12];
for(i=0;i<12;i++)
a[i]=i+1,s[i]=0;
printf("请输入:\n");
cin>>num;
if (fun(a,s,12,num)){
show(a,s,12,num);
}

}
bool fun(int *arr,int *state,int n,int tar){
int i;
for(i=0;i<n;i++){
if(!state[i]){
state[i]=1;
if(arr[i]==tar)
return true;
state[i]=0;
}
}
for(i=0;i<n;i++){
if(!state[i]){
state[i]=1;
if(fun(arr,state,n,tar-arr[i]))
return true;
state[i]=0;
}
}
return false;
}
void show(int *arr,int *state,int n,int tar){
int i;
printf("%d=",tar);
for(i=0;i<n;i++){
if(state[i])
printf("%d ",arr[i]);
}
}