一个面试的题目,请教大家!!!

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

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

我硬是愣了半天!不知道如何入手!请各位大哥们指教!谢谢!!
哎,真受打击!!!

[b]问题补充:[/b]
是排序,例如:
香蕉 香蕉 香蕉 香蕉 香蕉 梨子 梨子 梨子 梨子 苹果 苹果 苹果

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

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

8个回答

排列组合的算法不简单,我这里有一个经典的组合问题的算法思想,给大家分享一下:

求n个数中的m个数的组合。

首先,初始化一个n个元素的数组(全部由0,1组成),将前m个初始化为1,后面的为0。这时候就可以输出第一个组合了。为1的元素的下标所对应的数。

算法开始:从前往后找,找到第一个10组合,将其反转成01,然后将其前面的所有1,全部往左边推,即保证其前面的1都在最左边。然后就可以按照这个01序列来输出一个组合结果了。

而如果找不到10组合,就表示说所有情况都输出了,为什么?你想,(以n=5,m=3为例)一开始是11100,最后就是00111,已经没有10组合了。

(5+4+3)!/5!4!3!

赞成楼上的答案,这是一个排列组合问题,先将所有水果当成一个整体将它排列组合,总共有(5+4+3)!这么多可能,但是我们要排除这5个香蕉,4个梨子,3个苹果的内部排序,因为他们无论怎么排都是一样的,所以要除以(5!4!3!).如果后来者有不同答案,希望能一起分享。

面试官要求那程序实现,我给出一个答案来,看看是否满足你。

void meFun(int banana,int pome,int apple)
{
for(int i=0; i<=banana; i++)
{
for(int j=0; j<=pome; j++)
{
for(int k=0; k<=apple; k++)
{
if(!(i=0 && j=0 && k=0))
{
System.out.println("banana: "+i+" pome: "+j+" apple: "+k);
}
}
}
}
}

在主方法里调用
meFun(5,4,3);
其实面试就是看你有没有这个思考能力,尤其是快速的思考能力,真正的项目中,一个程序逻辑是靠一点一点的调试最后确定的。

不就是三重循环吗?

上面的程序代码错的太离谱了。这是排序吗?
同意一楼的答案,是一个组合问题,从12位置个里面任意取出5个位置放香蕉有C12^5(C是组合,12下标,5上标),然后在从剩下的7个位置里面选择4个位置放梨子有C7^4种。最后的3个位置全部放苹果只有1种。乘法法则: (C12^5) * (C7^4) *1=(5+4+3)!/5!4!3!=27720种排序。

我这有一个全排列代码,我还没有考虑重复元素的全排列,你拿着看看会有帮助

public class Permutation {
public int count=0; //统计总共排列数
public void permutate(String[] array,int i,int j){ //排列递归算法,排列下标从i--j
if(i>j){ //下标i大于j说明已完成一次排列
count++;
for(int k=0;k<array.length;k++){
System.out.print(array[k]+" ");
}
System.out.println();
}else{ //否则分别将i--j的数据与下标为i的位置交换数据,构成前缀,再全排列i+1---j的
for(int x=i;x<array.length;x++){
swap(array,i,x);
permutate(array,i+1,j);
swap(array,x,i); //一种情况完成,要恢复
}
}
}

public void swap(String[] array,int m,int n){
    String t;
        t=array[m];
        array[m]=array[n];
        array[n]=t;
}

public static void main(String[] args){
    String[] test = new String[]{"香蕉","梨子","苹果"};   //测试数据
    Permutation permutation = new Permutation();
    permutation.permutate(test,0,2);   //从下标0--2
    System.out.println("总共有"+permutation.count+"种");
}

}
运行结果:
香蕉 梨子 苹果

香蕉 苹果 梨子

梨子 香蕉 苹果

梨子 苹果 香蕉

苹果 梨子 香蕉

苹果 香蕉 梨子

总共有6种
按照我的算法,若有重复元素,会打印出许多重复的结果,

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));
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!