C语言程序设计100例之（32）：组合问题

例32  组合问题

题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1,2,…,n，从中任取r个数。

例如n=5,r=3，所有组合为：123,124,125,134,135,145,234,235,245,345。

输入格式

一行两个自然数n,r(1<n<21,1≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

输入样例

5 3

输出样例

  1  2  3

  1  2  4

  1  2  5

  1  3  4

  1  3  5

  1  4  5

  2  3  4

  2  3  5

  2  4  5

  3  4  5

        （1）编程思路。

        用递归来完成。

        设函数void dfs(int pos,int num)表示为第pos（0≤pos≤r-1）个数取值，取值可以为num~n之一。显然，若r-pos>n-num+1，则后面剩下的数不够，直接剪枝；否则，在num~n中取一个数i（num≤i≤n）赋给a[pos]，继续为下一个位置pos+1取数，即递归调用函数dfs（pos+1,i+1）。

（2）源程序。

#include <stdio.h>

int a[21],n,r;

void dfs(int pos,int num)

{

    if (pos==r)   // 已有r个数

    {

       for (int i=0;i<r;i++)

          printf("%3d",a[i]);

       printf("\n");

       return;

    }

    if(r-pos>n-num+1) return ;

    for(int i=num;i<=n;i++)

    {

        a[pos]=i;

        dfs(pos+1,i+1);

    }

}

int main()

{

    scanf("%d%d",&n,&r);

    dfs(0,1);

    return 0;

}

习题32

32-1  lotto

        本题选自北大oj题库 （http://poj.org/problem?id=2245）

description

in the german lotto you have to select 6 numbers from the set {1,2,...,49}. a popular strategy to play lotto - although it doesn't increase your chance of winning - is to select a subset s containing k (k > 6) of these 49 numbers, and then play several games with choosing numbers only from s. for example, for k=8 and s = {1,2,3,5,8,13,21,34} there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ... [3,5,8,13,21,34].

your job is to write a program that reads in the number k and the set s and then prints all possible games choosing numbers only from s.

input

the input will contain one or more test cases. each test case consists of one line containing several integers separated from each other by spaces. the first integer on the line will be the number k (6 < k < 13). then k integers, specifying the set s, will follow in ascending order. input will be terminated by a value of zero (0) for k.

output

for each test case, print all possible games, each game on one line. the numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. the games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below. the test cases have to be separated from each other by exactly one blank line. do not put a blank line after the last test case.

sample input

7 1 2 3 4 5 6 7

8 1 2 3 5 8 13 21 34

0

sample output

1 2 3 4 5 6

1 2 3 4 5 7

1 2 3 4 6 7

1 2 3 5 6 7

1 2 4 5 6 7

1 3 4 5 6 7

2 3 4 5 6 7

 

1 2 3 5 8 13

1 2 3 5 8 21

1 2 3 5 8 34

1 2 3 5 13 21

1 2 3 5 13 34

1 2 3 5 21 34

1 2 3 8 13 21

1 2 3 8 13 34

1 2 3 8 21 34

1 2 3 13 21 34

1 2 5 8 13 21

1 2 5 8 13 34

1 2 5 8 21 34

1 2 5 13 21 34

1 2 8 13 21 34

1 3 5 8 13 21

1 3 5 8 13 34

1 3 5 8 21 34

1 3 5 13 21 34

1 3 8 13 21 34

1 5 8 13 21 34

2 3 5 8 13 21

2 3 5 8 13 34

2 3 5 8 21 34

2 3 5 13 21 34

2 3 8 13 21 34

2 5 8 13 21 34

3 5 8 13 21 34

        （1）编程思路。

        本题的意思是要在有k个元素的集合s中任意取6个元素，并输出所有这些取值组合。

        设 combine(int take[], int len, int count,int num[])为从具有len个元素的数组num中取出count个元素，并将取出的元素存放在数组a中。

        为求解combine(int take[], int len, int count,int num[])，可以先在len个元素的数组num的后面取第一个元素num[i]放在a[count-1]中，所取的第一个数组元素的下标i可以是len-1,len-2,…,count-1。注意：第一个取的数组元素的下标i不能取count-2，因为后面的要取的元素均会在第一个取的元素的前面，因此最多只能取出0~count-3共count-2个不同的y元素，达不到取count个数的目的。

        在将确定组合的第一个元素num[i]放入数组take后，有两种选择：还未确定组合的其余元素时（count>1，即还需取count-1个元素），继续递归comb(take,i,count-1,num)确定组合的其余元素，即在num[0]~num[i-1]这i个元素中取count-1个数；已确定组合的全部元素时（count==1），输出这个组合。

        （2）源程序。

#include <stdio.h>

void combine(int take[], int len, int count,int num[])

{

    int i,j;

    for (i = len-1; i >= count-1; i--)

    {

       take[count - 1] = num[i];

       if (count >1)

           combine(take, i , count - 1, num);

       else

      {

          for (j = 6-1; j >=0; j--)

          {

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

           }

           printf("\n");

      }

    }

}

int main()

{

       int i,k,num[13],take[6],t;

       while(scanf("%d",&k) && k!= 0)

       {

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

                  scanf("%d",&num[i]);

              for (i=0;i<k/2;i++)

              {

                     t=num[i];

                     num[i]=num[k-i-1];

                     num[k-i-1]=t;

              }

              combine(take,k,6,num);

              printf("\n");

    }

   return 0;

} 

32-2  选数

        本题选自洛谷题库 （https://www.luogu.org/problem/p1036）

题目描述

已知 n 个整数x1 ,x2 ,…,xn，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34。

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

输入格式

键盘输入，格式为：

n,kn,k(1≤n≤20,k<n)

x1 ,x2 ,…,xn (1≤xi ≤5000000)

输出格式

1个整数（满足条件的种数）。

输入样例

4 3

3 7 12 19

输出样例

1

         （1）编程思路。

        编写递归函数void dfs(int pos,int num)完成n个数中取k个数。然后判断每种取值组合的和是否为一个素数。

        （2）源程序。

#include <stdio.h>

#include <math.h>

int a[21],b[22],n,k,cnt=0;

int isprime(int num)

{

    if (num==1) return 0;

    for (int m=2;m<=(int)sqrt((double)num);m++)

        if (num%m==0) return 0;

    return 1;

}

void dfs(int pos,int num)

{

    if (pos==k)   // 已有k个数

    {

       int sum=0;

       for (int i=0;i<k;i++)

          sum+=a[i];

       if (isprime(sum)) cnt++;

       return;

    }

    if(k-pos>n-num+1) return ;

    for(int i=num;i<=n;i++)

    {

        a[pos]=b[i];

        dfs(pos+1,i+1);

    }

}

int main()

{

    scanf("%d%d",&n,&k);

    for (int i=1;i<=n;i++)

        scanf("%d",&b[i]);

    dfs(0,1);

    printf("%d\n",cnt);

    return 0;

}

32-3  加法变乘法

问题描述

我们都知道：1+2+3+ ... + 49 = 1225

现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015

比如：

1+2+3+...+10*11+12+...+27*28+29+...+49 = 2015

就是符合要求的一个答案。

输入格式

输入一个正整数n （n>1225）。

输出格式

若可以将两个不相邻的加号变成乘号使得结果为n，输出两个乘号左边的数字，若解有多种情况，按字典序输出。如果无解，输出“no solution!”。

输入样例

2015

输出样例

10 27

16 24

        （1）编程思路。

        问题实际上是在1~48这个48个数字中任选两个数字。选择了这两个数字后，判断将两个数字后面的加号变成乘号后，表达式的值是否等于给定的n。

        （2）源程序。

#include <stdio.h>

int a[3],n,found=0;

void dfs(int pos,int num)

{

    if (pos==2)

    {

        int t=1225-2*(a[0]+a[1]+1)+a[0]*(a[0]+1)+a[1]*(a[1]+1);

        if (a[1]-a[0]!=1 && t==n)

        {

            printf("%d %d\n",a[0],a[1]);

            found=1;

        }

        return;

    }

    if(2-pos>48-num+1) return ;

    for(int i=num;i<=48;i++)

    {

        a[pos]=i;

        dfs(pos+1,i+1);

    }

}

int main()

{

    scanf("%d",&n);

    dfs(0,1);

    if (found==0) printf("no solution!\n");

    return 0;

}