[递归] 组合 - 从自然数1,2,...,n中任取r个数的所有组合 | 在一个字符串中任选m个的全部可能 -C语言实现

àì夳堔傛蜴生んèń 2022-05-12 14:58 139阅读 0赞

### 文章目录 ###

*  组合：数字型
 *   *   *   *  方法一
             *  方法二
             *  完整代码
 *  组合：字符型

# 组合：数字型 #

【问题】利用递归方法找出从自然数1,2,…,n中任取r个数的所有组合  
【例如】n=5,r=3，所有组合为：  
![在这里插入图片描述][70]

#### 方法一 ####

【思路】

1.  抽象问题：1,…,n中选r --> f(n,r)
2.  从边界n考虑，n要么取，要么不取 --> f(n,r) = f(n-1, r) + f(n-1, r-1)
3.  退出条件：r==0时，就已经选完了
4.  异常条件：n<r的时候

int a[50]; //存放组合的结果数组
    void f(int n,int r,int m) { 
    	// 从1,...n序列中选r个数字进行组合，当前已选m个数
    	// 【m理解】当前已选择m个数 or 此次选择的数放到a[m]的位置 or 结果数组的最后一位
    	int i;
    
    	if (n<r) return ; //异常条件
    
    	if (r==0) {  //从1,...,n序列中选0个数字进行组合
    		// 打印输出此次组合的结果
    		for (i=0; i<m; i++) printf("%d", a[i]);
    		printf("\n");
    	} else { 
    		// 将n选入数组，赋值到结果数组
    		a[m] = n;
    		f(n-1, r-1, m+1); //已经选了n这个数字-->从1,...,n-1选r-1个
    		//不选n
    		f(n-1, r, m); //n没有选-->从1,...,n-1选r个
    	}
    }

#### 方法二 ####

【代码】

// 从1-n的数字中选r个数字
    // 目前选的一个放入a[m]位置中
    void C(int n, int r, int a[], int m) { 
    	int i;
    	if (r==0) {  //选完了
    		//输出
    		for (i=0; i<m; i++) printf("%d", a[i]);
    		printf("\n");
    	} else { 
    		// 在[r,n]的范围内选一个数字放入a[m]
    		for (i=n; i>=r; i--) { 
    			a[m] = i;
    			C(i-1, r-1, a, m+1);
    		}
    	}
    }

【理解】用树状的形式输出递归树（先序）  
树状的方式类似于这种https://blog.csdn.net/summer\_dew/article/details/82937941  
![在这里插入图片描述][70 1]

#### 完整代码 ####

方法一：

#include<stdio.h>
    
    int a[50];
    
    void f(int n,int r,int m) { 
    	int i;
    
    	if (n<r) return ;
    
    	if (r==0) { 
    		for (i=0; i<m; i++) printf("%d", a[i]);
    		printf("\n");
    	} else { 
    		//选n
    		a[m] = n;
    		f(n-1, r-1, m+1);
    		//不选n
    		f(n-1, r, m);
    	}
    }
    
    int main() { 
    	int n,r;
    	while (1) { 
    		printf("输入n与r，空格分割\n>>> ");
    		scanf("%d%d", &n, &r);
    		f(n, r, 0);
    		printf("\n");
    	}
    	return 0;
    }

方法二：

#include<stdio.h>
    
    // 从1-n的数字中选r个数字
    // 目前选的一个放入a[m]位置中
    void C(int n, int r, int a[], int m) { 
    	int i;
    
    	// 以树状输出递归树
    	/* for (i=0; i<m; i++) { printf(" "); } printf( "C(%d,%d, '" , n,r); for (i=0; i<m; i++) { printf("%d ", a[i]); } printf("', %d)",m ); printf("\n"); */
    
    	if (r==0) {  // 选完了
    		// 输出
    		for (i=0; i<m; i++) printf("%d", a[i]);
    		printf("\n");
    	} else { 
    		// 在[r,n]的范围内选一个数字放入a[m]
    		for (i=n; i>=r; i--) { 
    			a[m] = i;
    			C(i-1, r-1, a, m+1);
    		}
    	}
    }
    
    int main() { 
    	int n,r;
    	int a[50];
    	while (1) { 
    		printf("输入n与r，空格分割\n>>> ");
    		scanf("%d%d", &n, &r);
    		C(n, r, a, 0);
    		printf("\n");
    	}
    	return 0;
    }

# 组合：字符型 #

【问题】从长度为n个字符串str中选出m个元素的可能

【思路】  
![在这里插入图片描述][70 2]

【代码】

char *tmp;	//中间结果
    int top;
    int count;	//种数
    //递归求组合数
    void combination(char *str, int n, int m )
    { 
        if( n < m || m == 0 )    return ;		//case 1：不符合条件，返回
        combination( str+1, n-1, m );			//case 2：不包含当前元素的所有的组合
        tmp[ top++ ] = str[0];					//case 3：包含当前元素
        if( m == 1 ){ 								//case 3.1：截止到当前元素
            printA( tmp, top );
            printf("\n");
            count++;
            top--;
            return;
        }
        combination( str+1, n-1, m-1);				//case 3.2：包含当前元素但尚未截止
        top--;								//返回前恢复top值
    }

【理解】将递归树进行先序输出  
树状的方式类似于这种https://blog.csdn.net/summer\_dew/article/details/82937941  
![在这里插入图片描述][70 3]

【完整代码】

#include<stdio.h>
    #include<stdlib.h>
    
    char *tmp;	//中间结果
    int top;	//
    int count;	//种数
    
    //打印长度为n的数组元素
    void printA(char *str,int n)
    { 
        int i;
        for(i=0;i<n;i++){ 
            printf("%c ",str[i]);
        }
    }
    
    //递归求组合数
    void combination(char *str, int n, int m )
    { 
        if( n < m || m == 0 )    return ;		//case 1：不符合条件，返回
        combination( str+1, n-1, m );			//case 2：不包含当前元素的所有的组合
        tmp[ top++ ] = str[0];					//case 3：包含当前元素
        if( m == 1 ){ 							//case 3.1：截止到当前元素
            printA( tmp, top );
            printf("\n");
            count++;
            top--;
            return;
        }
        combination( str+1, n-1, m-1);		//case 3.2：包含当前元素但尚未截止
        top--;										//返回前恢复top值
    }
    
    int main()
    { 
    
        int n,m;//存放数据的数组，及n和m
    	char *str;
    	printf("输入n与m，用空格隔开\n>>> ");
        scanf("%d%d",&n,&m);
    
        str = (char *) malloc( sizeof(char) * n );
        tmp = (char *) malloc( sizeof(char) * m );
    
    	printf("输入字符串\n>>> ");
    	scanf("%s", str);
    
    	printf("\n%s %d中选取%d个", str, n, m);
        combination( str, n, m );//求数组中所有数的组合
    	printf("总数%d\n", count);
    
    	//记得释放malloc申请来的资源
    	free(str);
    	free(tmp);
    
        return 0;
    }

[70]: /images/20220504/ae452c6d44c945169e35c8d56b41dfcc.png
[70 1]: /images/20220504/c15080c40cfb42f3b749e09965bd6ce9.png
[70 2]: /images/20220504/9cbc51b523c448ffbb49a5bcd7cf1f29.png
[70 3]: /images/20220504/11fdb9f13b064cd7b9b6ba5c4ba40243.png