入门级-搜索与回溯1

# 回溯思想

---

|例题|
|-----|
|[P517  十进制转二进制](http://39.99.183.126:8888/p/517)|
|[P287  【例47.2】 转进制](http://39.99.183.126:8888/p/P287)|

---

## 递归与先进后出

### 1、理解递归函数调用前输出和调用后输出的区别

例如

```c++
void f(int x) {
 if(x > 3) return;
 //cout<<x;  //输出点1
 f(x + 1);
 cout << x; //输出点2
}
int main()
{
 f(1);//f(1)->f(2)->f(3)->f(4)=return
 return 0;
}
```

如果用输出1（注释掉后输出），结果为123
如果用后输出2（注释掉前输出），结果为321

---

##### 2、递归的理解

当f(x)调用f(x+1)的时候，系统是怎么执行呢的？

首先看调用的顺序：

```
f(1) -> f(2) -> f(3) -> f(4) 然后返回
f(1)调用f(2)，在f(2)执行完成，返回后，f(1)才继续往下执行。
```

---

如果用前输出，则：

```
在f(1)调用f(2)之前输出1
在f(2)调用f(3)之前输出2
在f(3)调用f(4)之前输出3
结果为123
```

---

如果用后输出，则：

```
f(1) -> f(2) -> f(3) -> f(4)
f(4)直接返回
f(3)调用f(4)完成，输出3，然后返回
f(2)调用f(3)完成，输出2，然后返回
f(1)调用f(2)完成，输出1，然后返回
结果为321
```

---

### 3、扩展理解

#### 1、后输出的作用

在调用递归函数之后的地方写的代码逻辑，其执行顺序是和递归过程反着的，既先进后出的特性。
这个特性非常关键，是搜索与回溯的核心。

---

### 十进制转二进制

十进制转二进制，对于正整数n，可以定义 $n = a\times 2 + r$，r是余数，利用这个公式就可以依次求得每一步的r，反过来输出就成了二进制。

用表格来描述 $13=(1101)_2$：

|   n   |  n/2  |  n%2  |
| :---: | :---: | :---: |
|  13   |   6   |   1   |
|   6   |   3   |   0   |
|   3   |   1   |   1   |
|   1   |   0   |   1   |

那么这个过程怎么用编程实现呢？要注意输出的顺序是反着的。

---

## 回溯

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。当某个状态明显不满足，就可以退回上一个状态，继续选择别的方向。这种思想就称为回溯。

---

假设每一步的状态为 $X_i$，某一个解（由状态组成的路径）为 $X_1 .. X_n$。 使用回溯法的前提： 如果 $X_1..X_n$ 成立，则 $X_1..X_{n-1}$ 肯定也成立。如果 $X_1..X_n$ 不成立，则 $X_1..X_{n+1}$ 肯定也不成立。

---

如何使用回溯：

当进入下一层前，记录本层的选择，一方面可能下一层的判定要用到，另一方面求解时用到。

当求解完成回退，或某层无解回退时，需要把上一层的记录清除，以便上一层再往下选择。

---

## 三、例题与练习

---
###### 练习

用递归函数实现十进制转二进制。

```
输入格式： 一个正整数n(十进制);

输出格式 ：n的二进制形式

输入样例：13

输出样例：1101
```

---

样例代码

```c++
  #include<iostream>
  using namespace std;
  int n;
  void f(int n)
  {
    if (n == 0)
    {
      return ;
    }
    f(n/2);
    cout << n % 2;
  }
  int main()
  {
    cin >> n;
    f(n);

return 0;
  }
```

---

#### 练习：十进制转任意进制

编写程序，输入十进制数n和要转换的进制m，输出转换结果。

2 <= m <= 36，超出十进制后，10为'A'、11为'B'，12为'C' ... 35为'Z'。

样例输入：

```
54321 16
```

样例输出：

```
D431
```

---

样例代码：

```c++
#include <iostream>
using namespace std;

string s = "0123456789ABCDEFGHIJKLMNOPQRTSTUVWXYZ";
int n, m;
void f(int n)
{
  if (n == 0)
  return;
  f(n / m);
  cout << s[n % m];
}
int main()
{
  cin >> n >> m;
  f(n);

return 0;
}
```