半条命16吧 关注:393贴子:26,042
  • 5回复贴,共1


IP属地:河南1楼2022-01-14 19:26回复

    这是树,我们要注意的两点是,输出的这一串数中的元素的值是递增的。而且有些数字因为凑不够位数,在某些情况下是不能选的。
    我们还是可以通过dfs的方式来遍历这棵树,但其中包含的参数还需要我们确定。
    定义参数,可以通过定义全局变量的方法,或者是定义到函数里的形参。
    需要的参数:三个数的位置,int [] place, 当前该枚举的位置int k,当前最小可以从哪里枚举,int start


    IP属地:河南2楼2022-01-14 21:01
    回复
      private static int n,m;
      private static int[] place=new int[30];
      关于dfs函数,因为place已经定义成全局变量,那么dfs就只用加两个参数就行了
      private static void dfs(int k,int start){
      //dfs内部还是分两部分来写,一是输出符合要求的案例,二是搜索,我们先看输出样例。
      //当k>m的时候,就会产生一个符合要求的结果
      if(k==m+1){
      for(int i=1;i<=n;i++)
      sout(place[i]+" ");
      sout();
      return;
      }


      IP属地:河南3楼2022-01-14 21:29
      回复
        然后我们开始写搜索部分
        从start开始搜索,直到n
        for(int i=start;i<=n;i++){
        place[k]=i;//将枚举的数字放到place里去,然后下面继续搜索子树
        dfs(k+1,i+1);//继续搜索
        place[k]=0;//还原现场
        }


        IP属地:河南4楼2022-01-14 21:38
        回复
          if(k+n-start<m) return;
          当要枚举的数不足时,直接退出
          此时正在选第k个数,但加上(n-start)(备选的数的数量)仍然小于要求的数


          IP属地:河南5楼2022-01-14 21:42
          收起回复