尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

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

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题, 主题待开源···

站点信息

文章总数目: 298
已运行时间: 991

问题描述

给定一个正整数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(分钟)

n:19(分钟)

n:20(分钟)

n:21(分钟)

n:22(分钟)

n:23(分钟)

网上查的代码!

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


评论区

Twikoo giscus