C语言经典回溯算法之解决数的组合问题（详解）

迈不过友情╰ 2023-01-11 01:27 157阅读 0赞

### 文章目录 ###

*   *  一、回溯算法
     *  二、数的组合问题

## 一、回溯算法 ##

**1、回溯法**  
也叫试探法，实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

**2、回溯法解决问题的步骤**  
（1）针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。

（2）确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

## 二、数的组合问题 ##

**1、问题**  
找出从自然数1~n中任取r个数的所有组合。

**2、算法思想**  
按回溯法的思想，将找到的组合从小到大的顺序存放到数组a\[0\],a\[1\],…,a\[r-1\]中，组合中的元素满足以下性质：  
`a[i+1]>a[i]`，后一个数大于前一个数  
`a[i]-i<=n-r+1`，如此

**3、C语言实现数的组合**

#include <stdio.h>
    #define MAX 100
    int a[MAX];
    void comb(int n, int r)
    { 
    	int i, j;
    	i= 0;
    	a[i]= 1;
    	do{ 
    		if(a[i]-i<=n-r+1)  //还可以向前试探 
    		{ 
    			if(i==r-1)  //找到一个组合
    			{ 
    				for(j=0; j<r; j++)  //输出一个组合 
    					printf("%4d", a[j]);
    				printf("\n");
    				a[i]++;
    				continue;
    			} 
    			i++;  //向前试探 
    			a[i]= a[i-1]+1;
    		}
    		else  //开始回溯 
    		{  
    			if(i==0)  //找完全部解
    				return;  //所有解都找到了才返回，结束函数 
    			a[--i]++; 
    		}
    	}while(1);
    } 
    
    void main()
    { 
    	int x, y;
    	printf("请规定截止数和几个数组合（用,分割的整数）：");
    	scanf("%d,%d",&x,&y);
    	printf("自然数1~%d中%d个数的任意组合有：\n", x, y);
    	comb(x, y);
    }

高中学过的“排列组合”我们就知道是组合是不考虑顺序的，所以一眼看去就知道结果是否正确：  
![01][]  
![02][]

参考文献：《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/3713d392037445c7987a321a459f14e7.png
[02]: https://img-blog.csdnimg.cn/20210125185010848.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1ZpZXdpbmZpbml0ZWx5,size_16,color_FFFFFF,t_70