我的一道面试题目

面试的人员最后给了我一个题目，我当时傻眼了。他当时问我数学怎么样，我说，“我数学还可以！”。然后他说，要给我一个数学编程的题目做。我说：“会不会很难啊！”。他微笑的说:"很简单！"


题目是这样出的：5个香蕉，4个梨子，3个苹果。如何用程序实现，将这个些水果排列成不同的组合，并用某种语言来实现！

 

 

我找的一些资料：

 

      数学中的组合运算在统计中是十分常见的运算，但用程序输出所有组合的可能性却并不容易。这里介绍一个非常酷的组合算法：（太TM牛逼了）

组合问题：输出从m个数中的任意抽取n个数的组合全部可能序列。

 

[10反转置换法]

 

算法思想：

     (1)  初始化一个m个元素的数组（全部由0，1组成），将前n个初始化为1，后面的为0。这时候就可以输出第一个组合序列了。

     (2)  从前往后找，找到第一个10组合，将其反转成01，然后将这个10组合前面的所有1，全部往左边推 ，即保证其前面的1都在最左边。这时又可以输出一组组合序列了。

     (3)  重复第(2)步，知道找不到10组合位置。这时已经输出了全部的可能序列了。 为什么？你想，（以m=5,n=3为例）一开始是11100，最后就是00111，已经没有10组合了 。

 

//10置换法源代码
public void combination(int m,int n)
{
    char[] totalArray=new char[m];
    //记录排序次数
    int totalSortNum=0;

    //建立 111...100...0
    for(int i=0;i<m;i++){
        if(i<n)
            totalArray[i]='1';
        else
            totalArray[i]='0';
    }
    totalSortNum+=1;
       System.out.println(totalSortNum+"\t"+Arrays.toString(totalArray));

    //"10"反转置换法
    int index=-1;
    while((index=String.valueOf(totalArray).indexOf("10"))!=-1){
        //交换"10"为"01"
        totalArray[index]='0';
        totalArray[index+1]='1';
        //计算刚反转的"10"前面所有的'1'全部移动到最左边
        int count=0;
        for(int i=0;i<index;i++){
            if(totalArray[i]=='1')
                count++;
        }
        for(int j=0;j<index;j++){
            if(j<count)
                totalArray[j]='1';
            else totalArray[j]='0';
        }
        //输出结果
        totalSortNum++;
               System.out.println(totalSortNum+"\t"+Arrays.toString(totalArray));
    }
}

评论

5 楼 w2c2y2 2009-11-02  

liuming 写道

edward32tnt 写道

我觉得是12 个东西 然后减去 香蕉5个  4个梨子  3个苹果  的 排列组合 剩下就是了吧

关键是你怎么把这个“剩下的”的组合输出来。

结果比如是这样的：

香蕉 香蕉 香蕉 香蕉 香蕉 梨子 梨子 梨子 梨子 苹果 苹果 苹果

香蕉 香蕉 香蕉 香蕉 香蕉 梨子 梨子 梨子 苹果 苹果 苹果 梨子

香蕉 香蕉 香蕉 香蕉 梨子 梨子 香蕉 梨子 苹果 苹果 苹果 梨子

4 楼 liuming 2009-11-02  

edward32tnt 写道

我觉得是12 个东西 然后减去 香蕉5个  4个梨子  3个苹果  的 排列组合 剩下就是了吧

关键是你怎么把这个“剩下的”的组合输出来。

3 楼 edward32tnt 2009-10-26  

我觉得是12 个东西 然后减去 香蕉5个  4个梨子  3个苹果  的 排列组合 剩下就是了吧

2 楼 xiao151451664 2009-10-26  

如果是我、
  估计我会给他说我数学不行、

1 楼 presses 2009-10-26  

三层循环可不可以？
int count=1;
for(int banana=0;banana<5;banana++){
    for(int pear=0;pear<4;pear++){
         for(int apple=1;apple<3;apple++){
             log.info(组合:"+count+"banana:"+banana+",pear:"+pear+",apple:"+apple);
             count++;
         }
    }
}