dfs 划分数字

流照君发布于 2019-03-16 14:34， 1538 次点击

题目描述
将一个数字n，分成若干m份，每份不可为空。
注意，任意2个方案不可用相同，不考虑顺序
比如：n =6  ,m =3
1 1 4
1 4 1
4 1 1
这3个是一个方案。

输入
给n ，给m
n<100, m<6
输出
输出多少分法
大佬帮忙看一下我的代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,count1=0;
void dfs(int n,int num,int last)
{
    if(n<0||num<0)
    return;
    if(num==0&&n==0)
    {
    count1++;
    cout<<"wrf"<<endl;
    }
    for(int i=last;i<=n;i++)
    {
            n=n-i;
            dfs(n,num-1,i);
    }
}
int main()
{
    cin>>n>>m;
    dfs(n,m,1);
    cout<<count1<<endl;
    return 0;
}

请教一下为什么我输入6 3 输出 1
不应该输出3 吗？？

只有本站会员才能查看附件，请登录

5 回复

流照君2019-03-16 22:55

重新改了一点，但还是不行无法解决那个疑问
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,count1=0;
void dfs(int n,int num,int last)
{
    //cout<<n<<" "<<num<<endl;
    if(n<0||num<0)
    {
        return ;
    }
        if(num==0&&n==0)
            {
            count1++;
             return;
            }
    for(int i=last;i<=n;i++)
    {
            n=n-i;
            num=num-1;
            //cout<<n<<" "<<num<<" "<<i<<endl;
            dfs(n,num,i);
    }
}
int main()
{
    cin>>n>>m;
    dfs(n,m,1);
    cout<<count1<<endl;
    return 0;
}

流照君2019-03-16 22:56

求大佬前来指点？？？

rjsp2019-03-18 08:45

总觉得
    {
            n=n-i;
            dfs(n,num-1,i);
    }
不对，应该是
    {
            dfs(n-i,num-1,i);
    }

lyb6612019-03-18 19:30

直观上看，递归函数计算机也会懵。怎么操作？总应该有求和的计算吧！
当然也可能我是错的。
身边就一个手机，没法验证。

[此贴子已经被作者于2019-3-18 19:31编辑过]

jklqwe1112019-03-18 23:21

程序代码：

#include<iostream>
using namespace std;

int main()
{
   int n,m,count=0;
   int &cn=count;
   void dfs(int m,int n,int k,int &cn);

    cin>>m>>n;

    dfs(m-n,m-n,n,cn);
     cout<<cn<<endl;

    return 0;

}
void dfs(int m,int n,int k,int &cn)
{
    for(int i=m<n?m:n;i>0&&i*k>=m;--i)
    {
         if(m==i)++cn;
         else if(k>=0) dfs(m-i,i,k-1,cn);
      }
}