尼采般地抒情

公告栏

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


作者:尼采般地抒情

站点信息

文章数目:296 篇
已运行时间:
目录
  1. 问题描述
  2. 问题思路
  3. 代码思路
  4. java 代码实现

尼采般地抒情

尼采般地抒情

公告栏

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


作者:尼采般地抒情

站点信息

文章数目:296 篇
已运行时间:

问题描述

给定一个正整数 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 就是动态数组的初始大小
然后依次利用“吞进来”和“吐出去”尾元素来实现

java 代码实现

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);
    }
}

评论区

Beaudar Twikoo

最新评论

Loading...