kingnle
kingnle
采纳率16.7%
2016-11-30 01:35

关于递归求解问题求教.寻找递归大神!

已采纳

【问题描述】
  已知一个一维数组A1..N,又已知一整数M。 如能使数组A中任意几个元素之和等于M,则输出YES,反之则为NO。(要求用递归函数编写程序)
【输入样例】
  5
  1 2 3 4 5
  12
【输出样例】
  YES

我的想法是分成两部分,数组中的每一个数都存在选和不选的可能,由此递归。我写了两个递归程序,一个是错的,一个是对的,我不明白错的为什么错了,因为思路和正确的代码是一样的,求大神解答。
--------------------------------------以下是正确的-------------------------------
#include
#include
#include
#include
using namespace std;
int m;
int n,in[100];
int flag=0;
void pd(int in[],int n,int k)
{
if(in[n]==k)
{
flag=1;return ;
}
else if(n==0) return ;
else
{

pd(in,n-1,k);
pd(in,n-1,k-in[n]);
}

}

int main() {

cin>>n;
for(int i=0;i<n;i++)
{
    cin>>in[i];
}
cin>>m;
pd(in,n-1,m);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
return 0;

}
--------------------------------------以下是错误的-------------------------------
#include
#include
#include
#include
using namespace std;
int m;
int n,in[100];
int flag=0;
void pd(int in[],int n,int k,int sum)
{
if(sum==k)
{
flag=1;return ;
}
else if(n==0) return ;
else
{

pd(in,n-1,k,sum);
pd(in,n-1,k,sum+in[n]);
}

}

int main() {

cin>>n;
for(int i=0;i<n;i++)
{
    cin>>in[i];
}
cin>>m;
pd(in,n-1,m,0);
if(flag)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
return 0;

}
---------------------------------------------以上是代码--------------------------
求大神解答,我还想知道这个递归的时间复杂度,不知道该怎么计算,O(n!),O(2^n)?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

3条回答

  • Book1346 Book1346 5年前

    时间复杂度应该是O(2^n),不过这是最坏情况。
    你的程序和正确的那个程序还是由点区别的。
    你用sum和输入的m一直传递进去,一直在比较。你用的是加法
    正确的那个程序传入的是m,并用减法
    主要是核心的这两个递归函数的分析,你的,

     void pd(int in[],int n,int k,int sum)
    {
    //这个判断有点问题,当sum还小于k,但是n此时为1时,往下执行会执行到pd(in,0,k,sum)和pd(in,0,k,sum+in[1])
    //然后这里可以明显看出来sum的递加是加到in[1],那么in[0]还未判断
    //下一步递归,pd(in,0,k,sum+in[1])传进去执行的时候,此时sum=sum+in[1],但是in[0]呢?永远不会执行sum+in[0],因为这里n=0,你已经退出了。
    if(sum==k)
    {
    flag=1;return ;
    }
    //所以你这里要改成n==-1,防止往下执行,导致n为负数,从而出现sum+in[-1]就可以了。
    else if(n==0) return ;
    else
    {   
    pd(in,n-1,k,sum);
    pd(in,n-1,k,sum+in[n]);
    }
    

    下面是正确的那个程序:

     void pd(int in[],int n,int k)
    {
    //他采用的是递减的模式,而且是先判断in[]数组里的元素,所以下面判断用n==0
    //当in[0]==k时候,或者n==0,都表示执行结束,退出了。
    if(in[n]==k)
    {
    flag=1;return ;
    }
    else if(n==0) return ;
    else
    {
    pd(in,n-1,k);
    pd(in,n-1,k-in[n]);
    }
    

    从时间复杂度上,这个正确的最坏情况是O(2^n-1)有小优化。

    点赞 1 评论 复制链接分享
  • zjck1995 zjck1995 5年前

    刚才没用代码格式,重发个

     #include<bits/stdc++.h>
    using namespace std;
    const int N =105;
    int n,m;
    int a[N];
    bool dfs(int now,int sum){
        //数组是0---n-1,比较优雅的代码应该在now==n的时候判断,而不是n-1的时候判断,这个和你在n==0的时候直接退出时一个错误(你的写法可以在n==-1的时候退出)
        if(now==n){
            return sum==m;
        }
        if(dfs(now+1,sum)) return true;
        if(dfs(now+1,sum+a[now])) return true;
        return false;
    }
    int main() {
        while(scanf("%d",&n)==1){
            for(int i=0;i<n;i++) scanf("%d",a+i);
            scanf("%d",&m);
            puts(dfs(0,0)?"YES":"NO");
        }
        return 0;
    }
    
    点赞 1 评论 复制链接分享
  • zjck1995 zjck1995 5年前

    最坏复杂度应该是O(2^n)的
    错误在于:
    if(sum==k)
    {
    flag=1;return ;
    }
    else if(n==0) return ;

    当n==0的时候,你这个程序永远都无法加上a[0]的值,对吗?
    话句话说,当前的sum值并不包括a[n]的值,所以错了。

    试试这个代码

    #include
    using namespace std;
    const int N =105;
    int n,m;
    int a[N];
    bool dfs(int now,int sum){
    //数组是0---n-1,比较优雅的代码应该在now==n的时候判断,而不是n-1的时候判断,这个和你在n==0的时候直接退出时一个错误(你的写法可以在n==-1的时候退出)
    if(now==n){
    return sum==m;
    }
    if(dfs(now+1,sum)) return true;
    if(dfs(now+1,sum+a[now])) return true;
    return false;
    }
    int main() {
    while(scanf("%d",&n)==1){
    for(int i=0;i<n;i++) scanf("%d",a+i);
    scanf("%d",&m);
    puts(dfs(0,0)?"YES":"NO");
    }
    return 0;
    }

    
    
    点赞 1 评论 复制链接分享

相关推荐