V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
codeInfinty
V2EX  ›  Android

Java 嵌套 for 循环怎么用递归实现?

  •  
  •   codeInfinty · 2017-07-11 09:52:07 +08:00 · 8581 次点击
    这是一个创建于 2452 天前的主题,其中的信息可能已经有所发展或是发生改变。
    int count=0;
    for(int i=0;i<arr.length;i++){
    for(int j1=i+1;j1<arr.length;j1++){
    for(int j2=j1+1;j2<arr.length;j2++){
    for(int j3=j2+1;j3<arr.length;j3++){
    for (int j4 = j3+1; j4 < arr.length; j4++) {
    count++;
    System.out.println(arr[i]+" "+arr[j1]+" "+arr[j2]+" "+arr[j3]+" "+arr[j4]);

    }
    }
    }
    }
    }
    System.out.println(count);
    }
    30 条回复    2017-07-11 23:05:21 +08:00
    sagaxu
        1
    sagaxu  
       2017-07-11 10:03:24 +08:00 via Android   ❤️ 2
    递归展开哪家强,打开百度搜黑马。
    holyghost
        2
    holyghost  
       2017-07-11 10:06:31 +08:00 via iPhone   ❤️ 1
    先处理结束条件并返回
    然后一次只处理一层
    最后尾递归
    sunsulei
        3
    sunsulei  
       2017-07-11 10:11:17 +08:00   ❤️ 4
    不格式化的代码谁会给你看.
    就算有人看了,谁看谁傻...
    xss
        4
    xss  
       2017-07-11 10:14:24 +08:00
    你这个循环还是不要用递归了吧.
    也没多少层. 递归开销要比你这个循环大...
    Lonely
        5
    Lonely  
       2017-07-11 10:30:42 +08:00
    没必要用递归啊
    3pmtea
        6
    3pmtea  
       2017-07-11 11:24:03 +08:00
    recursive combinations
    Chaos11
        7
    Chaos11  
       2017-07-11 11:31:09 +08:00   ❤️ 1
    @holyghost
    ?不先打 230 到 [email protected]
    Ouyangan
        8
    Ouyangan  
       2017-07-11 11:35:05 +08:00
    超过两层循环 , 一般不往下看 , 一律重写 .
    jiangzhuo
        9
    jiangzhuo  
       2017-07-11 11:36:17 +08:00
    qscqesze
        10
    qscqesze  
       2017-07-11 11:36:26 +08:00   ❤️ 1
    int count = 0;

    void dfs(int x,int deep,int sum){
    for(int i=x+1;i<arr.length();i++){
    if(deep==4){
    count++;
    System.out.println(sum+arr[i]);
    }else{
    dfs(i,deep+1,sum+arr[i]);
    }
    }
    }

    void solve(){
    dfs(-1,0,0);
    System.out.println(count);
    }
    holyghost
        11
    holyghost  
       2017-07-11 11:41:00 +08:00
    @Chaos11

    你先打 2300 过来!(楼主打 230
    kzaemrio
        12
    kzaemrio  
       2017-07-11 11:46:12 +08:00   ❤️ 1
    private static int count(int[] array) {
    return count1(array, array.length, 0, 0);
    }

    private static int count1(int[] array, int length, int count, int i0) {
    if (i0 == length) {
    return count;
    }
    count = count2(array, length, count, i0, i0 + 1);
    return count1(array, length, count, i0 + 1);
    }

    private static int count2(int[] array, int length, int count, int i0, int i1) {
    if (i1 == length) {
    return count;
    }
    count = count3(array, length, count, i0, i1, i1 + 1);
    return count2(array, length, count, i0, i1 + 1);
    }

    private static int count3(int[] array, int length, int count, int i0, int i1, int i2) {
    if (i2 == length) {
    return count;
    }
    count = count4(array, length, count, i0, i1, i2, i2 + 1);
    return count3(array, length, count, i0, i1, i2 + 1);
    }

    private static int count4(int[] array, int length, int count, int i0, int i1, int i2, int i3) {
    if (i3 == length) {
    return count;
    }
    count = count5(array, length, count, i0, i1, i2, i3, i3 + 1);
    return count4(array, length, count, i0, i1, i2, i3 + 1);
    }

    private static int count5(int[] array, int length, int count, int i0, int i1, int i2, int i3, int i4) {
    if (i4 == length) {
    return count;
    }
    System.out.println(String.format(
    "%d %d %d %d %d",
    array[i0],
    array[i1],
    array[i2],
    array[i3],
    array[i4]
    ));
    return count5(array, length, count + 1, i0, i1, i2, i3, i4 + 1);
    }
    mosliu
        13
    mosliu  
       2017-07-11 11:49:29 +08:00
    #7 楼正解。。。

    不过应该吧 sum 改成 String 类型。。
    mosliu
        14
    mosliu  
       2017-07-11 11:57:33 +08:00   ❤️ 1
    在#7 上 完善了一下,去除全局。
    public static int dfs(int[] arr,int count,int x,int deep,String before){
    for(int i=x+1;i<arr.length;i++){
    if(deep==4){
    count++;
    System.out.println(before + arr[i]);
    }else{
    count = dfs(arr,count,i,deep+1,before+arr[i]+" ");
    }
    }
    return count;
    }
    public static void solve(int[] arr){
    int count = dfs(arr,0,-1,0,"");
    System.out.println(count);
    }
    Lonely
        15
    Lonely  
       2017-07-11 12:05:43 +08:00
    @Chaos11 这是什么梗
    qien
        16
    qien  
       2017-07-11 12:35:49 +08:00
    不需要递归并且一层循环就能搞定
    只需要非常基础的数论知识
    码农和软件工程师的区别
    dphdjy
        17
    dphdjy  
       2017-07-11 14:17:04 +08:00 via Android
    @qien 请问有何高见
    我能想到的是分组然后把复杂度降低到 2 层循环
    或者用 4 进制单循环表示
    是否还有其他高见?
    mxi1
        18
    mxi1  
       2017-07-11 14:31:12 +08:00
    @Chaos11 233
    qien
        19
    qien  
       2017-07-11 14:46:03 +08:00
    @dphdjy 在模 arr.length 的剩余类上做输出
    maomo
        20
    maomo  
       2017-07-11 15:30:02 +08:00
    可以把这个问题抽象一下:求一个算法,输入模 m 和维度 n,输出所有模 m 下的 n 维向量(a1, a2, ..., an),满足 a1<a2<...<an
    stillsilly
        21
    stillsilly  
       2017-07-11 15:38:26 +08:00
    搜‘数组 排列组合’
    winglight2016
        22
    winglight2016  
       2017-07-11 18:20:02 +08:00
    不格式化的代码没法看
    pagxir
        23
    pagxir  
       2017-07-11 18:45:03 +08:00 via Android
    @qien 你这个,只能得出结果。而 system.out.println 的输出就消失了。
    pagxir
        24
    pagxir  
       2017-07-11 18:49:13 +08:00 via Android
    结果是 C(4,n)
    qien
        25
    qien  
       2017-07-11 18:54:43 +08:00
    @pagxir 狗屁不通,跟 system.out.println 有个 jb 关系
    先搞清楚什么叫模 n 的剩余类再跟我说话
    Lonely
        26
    Lonely  
       2017-07-11 19:10:16 +08:00 via iPhone
    @qien 错了就错了,何必爆粗口?
    pagxir
        27
    pagxir  
       2017-07-11 21:58:36 +08:00
    @Lonely 别人不仅智商厉害,口才更是一绝。
    pagxir
        28
    pagxir  
       2017-07-11 22:14:49 +08:00
    system.out.println 说的是输出顺序。只考虑总组合数,解法当然可以多变。
    pagxir
        29
    pagxir  
       2017-07-11 22:57:58 +08:00
    miao1007
        30
    miao1007  
       2017-07-11 23:05:21 +08:00
    楼主这个是组合排序算法的暴力实现吧,没必要这样搞,真与黑马差距不大了。Groovy 程序设计中,专门讲了用记忆化改善性能,就是你这个的优化版
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   971 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:22 · PVG 04:22 · LAX 13:22 · JFK 16:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.