尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:
目录
  1. 一、递归
    1. 算法特点
    2. 递归和迭代
  2. 二、问题描述
  3. 三、问题思路
  4. 四、代码思路
  5. 五、代码实现

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:

一、递归

算法特点

适用于递归解决的问题通常有两个特点:

  1. 递归性:能将规模为 n 的问题简化为 n-1 的问题,并且规模为 n 的问题和规模为 n-1 的问题性质一样
  2. 可终结性:不能无限递归下去,小到一定程度能够得出结果

eg:前 n 个自然数的和、n 个数之和这两个问题就可以用递归来解决

递归和迭代

递归问题也可以用迭代方式来解决(循环),这过程中,有一些普遍的特点就是:

  1. 递归问题有较好的直觉性
  2. 迭代运行过程中调用太多的栈空间,因而运行效率相对优于递归

二、问题描述

给定一个正整数 n,生成集合 {1,2,3,…n} 的所有子集

三、问题思路

思路一:二进制法

利用二进制是否显现”的转换思路来解决这个问题,一个数字在子集当中就标记为 1 反之标记为 0,就比如 n=3 ,输出: {}{1,0,0}{0,1,0}{0,0,1}{1,1,0}{1,0,1}{0,1,1}{1,1,1}

四、代码思路

思路一:利用动态数组数据结构

输入的 n 就是动态数组的初始大小
然后依次利用“吞进来”和“吐出去”尾元素来实现

五、代码实现

package com.wztlink1013.al._递归法_;
/*
 * 作用:测量代码运行时间
 */
import java.text.SimpleDateFormat;
import java.util.Date;

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");

    public interface Task {
        void execute();
    }

    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始:" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束:" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时:" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}
package com.wztlink1013.al._递归法_;

import java.util.ArrayList;

/**
 * 子集问题
 */
public class SubSetting {
    static ArrayList<Integer> x  = new ArrayList<Integer>();
    static int cnt = 0;
    public static void main(String args[]) {
        int n = 4;
        Times.test("当n = " + n + "时候的耗费时间", new Times.Task() {
            public void execute() {
                Subsetting(n);
            }
        });
    }

    private static void Subsetting(int n) {
        if (n > 0) {
            x.add(0);
            Subsetting(n - 1);
            x.remove(x.size() - 1);
            x.add(1);
            Subsetting(n - 1);
            x.remove(x.size() - 1);
        }else {
            OutputOneSubsetBinary();
            OutputOneSubset();
            System.out.print("\n");
        }
    }

    private static void OutputOneSubset() {
        System.out.printf("; {");
        int k = 0;
        for (int i = x.size() - 1; i >=0; i--) {
            if (x.get(i) == 1) {
                if (k > 0)
                    System.out.printf(",");
                System.out.printf("%d", x.size() - i);
                k++;
            }
        }
        System.out.printf("}");
    }

    private static void OutputOneSubsetBinary() {
        System.out.printf("%010d: ", ++cnt);
        for (int i = x.size() - 1; i >= 0; i--)
            System.out.printf("%d", x.get(i));
    }
}

运行结果:

n:18(分钟)

image.png

n:19(分钟)

image.png

n:20(分钟)

image.png

n:21(分钟)

image.png

n:22(分钟)

image.png

n:23(分钟)

image.png

网上查的代码!

class Main
{
    static void printSubsets(String[] set)
    {
        int n = set.length;
        for (int i = 0; i < (1<<n); i++)
        {
            System.out.print("{ ");
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) > 0)
                    System.out.print(set[j] + " ");
            System.out.println("}");
        }
    }
    public static void main(String[] args)
    {
        String[] set = {"1", "2", "3", "4",
                        "5", "6", "7", "8"};
        printSubsets(set);
    }
}

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/mz8hpp/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...