黑马程序员技术交流社区

标题: 来个递归的问题吧！一直没搞明白！求解答！ [打印本页]
作者: 肖建伟    时间: 2014-10-20 20:24
标题: 来个递归的问题吧！一直没搞明白！求解答！
昨天看算法，关于递归呢！有这么个题目，从1,2.。。n中取r个数，r < n，不可重复，有多少种取法。例如，从1，2，3，4，5中取3个数，共有123；124；125；134；135；145；234；235；245；345.这十种取法。程序代码该怎么写？采用for循环的话，递归的思路就是自身引用的for循环，具体到代码怎么写？一直套用的话，不会成一个无限死循环吗？
求高手指点江山！
作者: zhengzhaozhao    时间: 2014-10-20 21:00
package nyist;

import java.util.Arrays;

public class test {
       
        public static boolean flag[] = new boolean[10];
       
        public static void main(String[] args)  {
                Arrays.fill( flag , false );
                dfs( 0, 0 );
        }
        public static void dfs( int id, int index )
        {
                if( id == 3 ) {                       
                        for( int i = 0; i < 5; i++ )
                                if( flag[i] ) System.out.print( i+1 );
                        System.out.println();
                        return ;
                }
                if( index >= 5 ) return ;
               
                for( int i = index ; i < 5; i++ ) {
                        if( flag[i] ) dfs( id, i+1 );
                        else {
                                if( !flag[i] ) {
                                        flag[i] = true;
                                        dfs( id+1, i+1 );
                                        flag[i] = false;
                                }
                        }
                }
        }
}
作者: 想飞的鱼    时间: 2014-10-20 23:01
  1. package com.itheima;

  3. /*
  4. * 需求：从1,2.。。n中取r个数，r < n，不可重复，有多少种取法。
  5. * 例如，从1，2，3，4，5中取3个数，共有123；124；125；134；135；145；234；235；245；345.这十种取法。
  6. */
  7. public class Test11 {
  8.         public static void main(String[] args) {
  9.                 method(5, 3);
  10.         }

  12.         // 共n个数，取出r个
  13.         public static void method(int n, int r) {
  14.                 // 定义数组
  15.                 int[] iarr = new int[n];
  16.                 for (int x = 0; x < n; x++) {
  17.                         iarr[x] = x + 1;
  18.                 }
  19.                 // 判断r的值，并输出符合条件的数字的组合
  20.                 if (r == 1) {
  21.                         method1(iarr, r);
  22.                 } else if (r == 2) {
  23.                         method2(iarr, r);
  24.                 } else {
  25.                         int count = 0;// 定义变量，当pos2往后推一个角标，pos3的初始值也应往后推一个角标
  26.                         // 定义3个指针
  27.                         for (int pos1 = 0; pos1 <= n - r; pos1++) {
  28.                                 for (int pos2 = pos1 + 1; pos2 <= n - r + 1; pos2++, count++) {
  29.                                         for (int pos3 = pos1 + r - 1 + count; pos3 < iarr.length; pos3++) {
  30.                                                 // 输出
  31.                                                 System.out.print(iarr[pos1]);
  32.                                                 for (int x = pos2; x < pos1 + r - 1 + count; x++) {
  33.                                                         System.out.print(iarr[x]);
  34.                                                 }
  35.                                                 System.out.println(iarr[pos3]);
  36.                                         }
  37.                                 }
  38.                                 count = 0;
  39.                         }
  40.                 }
  41.         }

  43.         // 当r==2的时候调用此方法。
  44.         private static void method2(int[] iarr, int r) {
  45.                 for (int pos1 = 0; pos1 < iarr.length - 1; pos1++) {
  46.                         for (int pos2 = pos1 + 1; pos2 < iarr.length; pos2++) {
  47.                                 System.out.print(iarr[pos1]);
  48.                                 System.out.println(iarr[pos2]);
  49.                         }
  50.                 }
  51.         }

  53.         // 当r==1的时候，调用此方法
  54.         private static void method1(int[] iarr, int r) {
  55.                 for (int x = 0; x < iarr.length; x++) {
  56.                         System.out.println(iarr[x]);
  57.                 }
  58.         }
  59. }
复制代码

想了好久，写的不知道是否有点复杂了，是定义了几个指针实现的。希望可以帮到楼主
作者: zhengzhaozhao    时间: 2014-10-21 10:44
public class Main {

        public static void main(String[] args) {               
               
                for( int i = 1; i <= 5; i++ )
                for( int j = i+1; j <= 5; j++ )
                for( int k = j+1; k <= 5; k++ )
                {
                        System.out.print( i+""+j+""+k+",");
                }
        }
}
其实这个题目就只需要这么点代码就可以搞定，开始写的那个递归看不明白就看这个吧，这个我相信没人看不明白



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2