生成真值组合【Java实现】
/**
*问题描述：给定 n个布尔变量，打印所有真值组合。
*例如， n = 2时，所有真值组合为 (true, false),(true, true),(false, true),(false, false).
*
*算法的基本思路：
*使用一个长度为 n的数组存储着 n个布尔变量；位 1表示 true ,位 0表示 false,
*生成每一个真值元组，实际上是生成一个由 0和 1表示的数组。
*
*生成每一个真值元组的方法：从零开始，逐次加一。
*比如000 -> 001 -> 010 -> 011 -> 100 -> 101 -> 110 -> 111
*
*具体算法：
*每次都从最低位开始，将最低位作【置一】处理：
*①如果最低位是 0，则置 1即可【不进位】；
*②如果最低位为 1，则置 0；由于有进位，进一步将次低位作【置一】处理。
*直至某一位由 0置 1为止【不进位】。
*
*例如： 011 :
*①最低位为1，置 0，并进位；
*②次低位为1，置 0，并进位；
*③次次低位为 0，置 1。结果为 100
*
*
*技巧：
*①由于这里只涉及置 1或置 0，实际上就是置 true或置 false，
*因此，可以直接在数组里存储布尔值，并不必要在 1,0和 true, false之间转换。
*
*②设置一个结束标识变量 endflag，当 1..1 -> 0..0时设置为 true
*
*/
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Combination {
private boolean[] combination ;
private long count;
private boolean endflag;
public Combination(int n) {
if (n <= 0)
throw new IllegalArgumentException("参数必须为正整数");
if (combination == null) {
combination = new boolean[n];
count = 0;
endflag = false;
}
}
/**
* 求解问题，打印所有的真值组合结果。
*
*/
public void solution()
{
System.out.println("n = " + combination.length + " ***** 所有真值组合： ");
do {
System.out.println(getOneTuple());
count++;
increOne();
} while(!terminate());
System.out.println("真值组合数： " + count);
}
/**
* 逐次加一，生成每一个真值元组
*
*/
private void increOne()
{
int i;
for (i=0; i < combination.length; i++) {
// 若为 0，则置 1，结束。
if (combination[i] == false) {
combination[i] = true;
break;
}
else {
// 若为 1，则置 0，并通过 i++转至次低位进行相同处理
combination[i] = false;
}
}
// 由 1..1 -> 0..0时,设置 endflag = true;
if (i == combination.length) { endflag = true; }
}
/**
* 根据整数数组表示生成的真值元组，转化为布尔数组表示生成的真值元组。
*
*/
private String getOneTuple()
{
StringBuilder tuple = new StringBuilder("(");
for (int i=0; i < combination.length; i++) {
tuple.append(combination[i]);
tuple.append(",");
}
// 删除多余的逗号
tuple.deleteCharAt(tuple.length()-1);
tuple.append(")");
return tuple.toString();
}
/**
* 终止条件：结束标识符 endflag = true;
*
*/
private boolean terminate()
{
return endflag == true;
}
public static void main(String[] args) {
BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
try {
String s = null;
while ((s = stdin.readLine()).matches("[1-9][0-9]*")) {
int n = Integer.parseInt(s);
System.out.println("n = " + n);
Combination c = new Combination(n);
c.solution();
}
} catch (IOException e) {
e.printStackTrace();
} catch (Exception e) {
System.out.println(e.getMessage());
e.printStackTrace();
}
//Combination c = new Combination(3);
// c.solution();
}
}
算法分析：
总的运行时间由两部分组成：置一处理时间 和 判断结束时间。
T(n) = setBit(n) + judgeEnd(n)
其中： judgeEnd(n) = 2^n，因为从 0..0 -> 1..1 -> 0..0每次变换做一个简单的比较操作，endflag == true，总共花时 2^n
下面计算 setBit(n) :
n = 1 时 0 -> 1setBit(1) = 1;
n = 2 时 00-> 01 -> 10 -> 11setBit(2) = 121 【置位次数：1+2+1】
n = 3 时 000 –> 001 -> 010 -> 011 -> 100 -> 101 -> 110 -> 111setBit(3) = 1213121
n = 4 时 0000 -> 0001 -> 0010 -> 0011 -> 0100 -> 0101 -> 0110 -> 0111 -> 1000 -> 1001 -> .. -> 1111 setBit(4) = 121312141213121
归纳可得：
setBit(n) = n + 2setBit(n-1)setBit(1) = 1 ； 解得： setBit(n) = O(n^2)
故 T(n) = 2^n
更多相关文章
- 字体图标的引入和通过媒体查询改变导航样式
- HTML样式和常用选择器
- 字体图标的引用和自定义样式/媒体查询的使用
- 数据库的CURD操作、PDO本质与原理的学习
- CSS之伪类选择器和简单盒子简单案例
- 伪类选择器与盒模型常用属性
- 伪类选择器-结构伪类、根据位置选择匹配
- 7.4——常用标签与应用场景之表格与单元格
- css伪类选择器和盒模型