一道笔试题，求思路

nemopang 2011-08-29 11:32:15

朋友给我出了道他们公司的一道笔试题，我想了许久，没想出来，请教各位

大家可以用自己熟悉的语言写写，求思路：

一个袋子装有5个球，每个球都标注了编号：1、2、3、4、5
一个人只往往袋子取一次，每次取的数量不等。

问有多少种组合？每个组合是？

...全文

1794 61 打赏收藏转发到动态举报

写回复

用AI写文章

61 条回复

切换为时间正序

请发表友善的回复…

发表回复

w835369950 2011-10-04

打赏
举报

看了这个方法，假如可以的话也很麻烦啊，试试下



#include<stdio.h>

#include<math.h>

void main()

{

 int num,i, n;

 for(num=1;num<=31;num++)

 {

 n=num;

 printf("\n");

 for(i=4;i>=0;i--)

 {

if(n>=pow(2,i)){

 n=n-pow(2,i);

 printf("%d ",i+1);

 }

 }

 }

}

w835369950 2011-10-04

打赏
举报

//嗯嗯，想到优化的方法了，如下：
#include<stdio.h>
#include<math.h>
void main()
{
int num,i, n;
for(num=1;num<=31;num++)
{
n=num;
printf("\n");
for(i=4;i>=0;i--)
{
if(n>=pow(2,i)){
n=n-pow(2,i);
printf("%d ",i+1);
}
}
}
}
//另外怎么插入源代码的，没看到有插入源代码那个图标呢，是什么图标也没有

w835369950 2011-10-04

打赏
举报

//不知道如何优化代码，求高人指点
#include<stdio.h>

void main()
{
int i,j,k,l,m,n;
for(j=0;j<2;j++)
for(k=0;k<2;k++)
for(l=0;l<2;l++)
for(m=0;m<2;m++)
for(n=0;n<2;n++)
{
if(j==1)
printf("5");
if(k==1)
printf("4");
if(1==l)
printf("3");
if(m==1)
printf("2");
if(n==1)
printf("1");
printf("\n");
}
}

yj327243832a 2011-09-29

打赏
举报

A51+A52+A53+A54+A55
对么

we_sky2008 2011-09-29

打赏
举报

再给出一种解法：



#include<iostream>

#include<algorithm>



using namespace std;



/****

开一个数组，其下标表示1到m个数，数组元素的值为0表示其下标   

代表的数被选中，为1则没选中。

****/

void combine_next_perm(const int *first, const int *last, int cnt)

{

    if (first == last)

        return;

    

    int len = last - first;  

    int *p = new int[len];

    int i;



    for (i = 0; i < cnt; ++i)

    {

        p[i] = 0;

    }

    for (; i < len; ++i)

    {

        p[i] = 1;

    }

    cout<<"从"<<len<<"中选取"<<cnt<<"个"<<endl;

    do

    {

        for (i = 0; i < len; ++i)

        {

            if (0 == p[i])

            {

                cout<<first[i]<<' ';

            }

        }

        cout<<endl;

    }while (next_permutation(p, p + len));

    

    delete[]p;

}





int main()

{

    int a[] = {1, 2, 3, 4, 5};

    int i;



    for (i = 1; i <= sizeof(a) / sizeof(a[0]); ++i)

    {

        combine_next_perm(a, a + sizeof(a) / sizeof(a[0]), i);

    }



	system("pause");

	return 0;

}

we_sky2008 2011-09-29

打赏
举报

下面这个是回溯法



//回溯法

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>



void func(int src[], int size)

{

    int i, j;

    int cnt = 0;

    int *table = (int *)malloc(sizeof(int) * size);

    

    if (NULL == table)

        return;

    

    for (i = 1; i <= size; ++i)

    {

        int cur = 0;

        table[0] = -1;

        printf("从中选取%d个出来\n", i);

        while (cur >= 0)

        {

            table[cur] += 1;

            

            if (table[cur] < (size - (i - cur - 1)))

            {

                if (i - 1 == cur)

                {

                    for (j = 0; j < i; ++j)

                    {

                        printf("%d ", src[table[j]]);

                    }

                    printf("\n");



                    ++cnt;

                }

                else

                {

                    cur += 1;

                    table[cur] = table[cur - 1];

                }

            }

            else

            {

                cur -= 1;

            }

            

        }

    }

    

    free(table);

    

    printf("共有%d中组合\n", cnt);

}



int main()

{

    int src[] = {1, 2, 3, 4, 5};



    func(src, sizeof(src) / sizeof(src[0]));



    system("pause");

    return 0;

}

we_sky2008 2011-09-29

打赏
举报

在8楼我给出的是用递归求解的，其实也可以用位操作和回溯法



//bit位操作

#include<stdio.h>

#include<stdlib.h>



void func(int src[], int size)

{

    int cnt = 0;

    int total = 1 << size;

    int i, j;

    

    printf("共有%d种组合\n", total - 1);

    for (i = 1; i < total; ++i)

    {

        for (j = 0; j < size; ++j)

        {

            if (i & (1 << j))

            {

                printf("%d ", src[j]);

            }

        }

        printf("\n");

    }

}



int main()

{

    int src[] = {1, 2, 3, 4, 5};



    func(src, sizeof(src) / sizeof(src[0]));



    system("pause");

    return 0;

}

床上等您 2011-09-28

打赏
举报

是排列组合。。。。
C(5,1) + C(5,2) + C(5,3) .......数学计算方法。

martinblade 2011-09-28

打赏
举报

难道不正是我高中学的排列组合？

daojiao_one 2011-09-09

打赏
举报

好贴，围观

a_sum_of_money 2011-09-09

打赏
举报

2的5次方

原来缘来 2011-09-08

打赏
举报

2的5次方-1

牙痴 2011-09-08

打赏
举报

以前看到的一个通过位运算的

public class ZuHe {

private static String[] set = {"1","2","3","4","5"};

public static int nextN(int n){
return (n+(n&(-n))) | ((n^(n+(n&(-n))))/(n&(-n)))>>2;
}

public static void print(String[] set,int c){
int i=0;
int k;
while( (k=1<<i)<=c ){
if( (c&k)!=0 ){
System.out.print(set[i]);
}
i++;
}
}

public static void subSet(String[] set,int n){
int i=1;
while(i<=n){
int c = (1<<i) - 1;
while( c<=(1<<n)-1 ){
print(set,c);
System.out.println();
c = nextN(c);
}
i++;
}
}

public static void main(String[] args) {
subSet(set,5);
}

}

jernymy 2011-09-08

打赏
举报

支持8楼的

孤独小剑 2011-09-08

打赏
举报

没那么复杂吧，一个5位的数，共计2^5个情况。

zhang271123288 2011-09-08

打赏
举报

好吧，路过，来拿分的

awen12345678 2011-09-07

打赏
举报

不是排列组合吗？ C(5,1)+c(52)+....c(5,5)。

c(m,n), 表示从m个物件中随即选取n个物件的组合数（本来应该是用数学公式符号表示，书写太麻烦就这样表示了）。

回去看看数学书，会有的。

孤独小剑 2011-09-07

打赏
举报

[Quote=引用 26 楼 hsli001 的回复:]

引用 18 楼 techray 的回复:

看可不可以不取
可以2^n
不可以2^n-1
取法就是列子集，按取得个数列出来就行
或者按照某个球取不取列出来，可以用位运算

2^n = C50+C51+C52+C53+C54+C55
[/Quote]
按位运算，取为1不取为0，然后就是2^n-1个了