一、 回溯思想

例题
P517 十进制转二进制
P287 【例47.2】 转进制

回溯

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

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

如何使用回溯：

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

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

三、例题与练习

递归与先进后出

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

例如

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*2 + r，r是余数，利用这个公式就可以依次求得每一步的r，反过来输出就成了二进制。

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

n	n/2	n%2
13	6	1
6	3	0
3	1	1
1	0

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

练习

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

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

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

 输入样例：13

 输出样例：1101

样例代码

#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

样例代码：

#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;
}