算法篇之回溯法
算法篇之回溯法
--细说回溯法（细说不是胡说）
算法篇之回溯法
前言
一、什么是回溯法
二、回溯法模型设计
三、常见的回溯算法的分类
1.有固定的起始点
2.任意一个元素都可作为起始点
四、回溯例题求解
1.素数环
2.排列组合
3.自然数的拆分
前言
最近因为复试的原因，对几个算法进行了一定程度的了解，这一篇将详细讲述一下回溯，让大家浅显易懂的明白回溯。
一、什么是回溯法
官方解释：回溯法是一个既带有系统性又带有跳跃性的搜索算法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
通俗来讲：回溯思想其实就是试探思想，有时候我们需要得到问题的解，先从其中某一种情况进行试探，在试探的过程中，一旦发现原来的选择是错误的，那么就退回一步重新选择，然后继续向前试探，反复这样的过程直到求解出问题的解。
二、回溯法模型设计
回溯法一般都有固定的形式，下面给出一般形式
有多组测试数据，每组输入一个n(0输出描述:
每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。样例输入:
6
8
3
0样例输出:
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
Case 3:
No Answer第一行输入整数N（1输出描述:
在1-n中选取m个字符进行全排列，按字典序全部输出,每种排列占一行，每组数据间不需分界。如样例样例输入:
2
3 1
4 2样例输出:
1
2
3
12
13
14
21
23
24
31
32
34
41
42
43
#include
#include
#define maxsize 10
using namespace std;
int a[maxsize];
int vis[maxsize]={0};
int sum=0;
int n,r;
void dfs(int cur)
{int i;if(cur==r+1){sum++;for(i=1;i>T;while(T--){cin>>n;cin>>r;dfs(1);}return 0;
} 3.自然数的拆分
/**
回溯之拆分自然数
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和
当n=7共14种拆分方法：
7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4
total=14
*/
#include
#define maxsize 100001
using namespace std;
int a[maxsize]={1};
int sum=0;
int n;void print(int cur)
{sum++;cout<>n;dfs(n,1);cout<<"sum="<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！