当前位置: 代码迷 >> J2SE >> 一道java算法题
  详细解决方案

一道java算法题

热度:161   发布时间:2016-04-23 20:23:36.0
求助一道java算法题
要求实现一个简单功能:
public static void pailie(int length);
在函数中做以下事情:
根据输入的长度,每个循环计数器(i,j,k...)在0,1中选择,进行for循环打印
比如pailie(3) 则
执行:
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
for(int k=0; k<2; k++) {
System.out.println(i + " / " + j + " / " + k);
}
}
}
打印的结果为:
0 / 0 / 0
0 / 0 / 1
0 / 1 / 0
0 / 1 / 1
1 / 0 / 0
1 / 0 / 1
1 / 1 / 0
1 / 1 / 1

谢谢各位!
------解决方案--------------------
这是递归的一个实现,也可以循环遍历数组a实现
楼主慢慢看吧


 public static void pailie(int length) {
        int a[]   = new int [length];//记录当前应该输出的值
        pp(length,a);
    }
    public static void pp(int length,int a[]) {
        if(length>0){
            for (int i = 0; i < 2; i++) {
                a[length-1]=i;
                pp(length-1,a);
            }
        }else{
            //pp(0)的时候输出所有值
            System.out.print(a[a.length-1]);
            for(int i = a.length-2; i >=0; i--){
                System.out.print( " / " + a[i] );
            }
            System.out.println();
        }
    }




------解决方案--------------------
幂集问题么?老掉牙了。解决“排列组合问题”一类问题,其釜底抽薪的办法就是弄懂解空间树:




import java.util.Scanner;

public class Pailie {
public static void pailie(int length){
combineAllDfs(0, new int[length]);
}
public static void printOne(int[] array){
System.out.print(array[0]);
for(int i=1;i<array.length;i++){
System.out.print(" / "+array[i]);
}
System.out.println();
}
public static void combineAllDfs(int level,int[] array){
if(level==array.length-1){
printOne(array);
array[level]=1;
printOne(array);
        array[level]=0;
}else{
//递归左子树
combineAllDfs(level+1, array);
array[level]=1;
//递归右子树
combineAllDfs(level+1, array);
//回溯
array[level]=0;
}
}

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
pailie(n);
}
}



另外,还有:全排列(包括字典序)、C(M,N)(可打表)、A(M,N)三个问题,希望lz练习一下,弄懂之后,排列组合算是入门了。
  相关解决方案