3.3栈与递归的实现-Hanoi塔 3.3栈与递归的实现-递归实现 ■问题求解是递归的一Hanoi塔 ■调用函数与被调用函数一系统工作栈 void hanoi(int n,char a,char b,char c) n-圆盘数a-源塔座 ·执行被调用函数前 b-中介塔座c目标塔座 。现场保护：实在参数、远回地址 ■搬动方法 。为被调用函数的局部变量分配存储区 ■n=1,a->c 。将控制转移到被调函数的入口 ,从被调用函数返回调用函数前 。保存被调西数的计算结果 ■注意 。释放被调函数的数据区 用递归调用的结果， ,现场恢复：返国 不关注结果如何 获得的嘲节 32/50 图 3.3栈与递归的实现-递归实现 3.,3栈与递归的实现递归/回湖 ■递归过程与递归工作栈 。递归与回湖一N皇后问题 实陈的系就中，一兼统一处理递归调用布非递归调用 。回溯是按照某种条件往前试探搜案，若前进中 。递归工作栈 遭到失败则回过头来另择通路继续搜索. ,活动记录（栈帧stack frame) ,N皇后问题 实在参数、局部变量、上一层的远回地址 在n行m列的国际象棋拱盘上，若两个皇后 ·每进入一层递归，产生一个新的工作记录入栈 位于同一行、同一列或同一对角线上，则称 ·每退出一层递归，就从栈顶弹出一个工作记录 为它们为互相攻击。 ·当前执行层的工作记录必是找顶记录 n皇后问题是指： ■例子：P57 hanoi(3,a,b,c) 找到这n个皇后的互不攻击的布局 33/50 图 34/50 图 3.3栈与递归的实现-N皇后问题 3.3栈与递归的实现-N皇后问题 k=i+j 0#次对角线 -1#次对角线 ·基本思略 2#次时角战 依次为每一行确定读行里后的合法位置 0 3#次对角线 ,安放第i行直后时，需要在列的方向从0到l 4#次对角线 5#次时角线 沈探(j■0，，n-1) 6#次对角线 ,在第j列安放一个皇后 ·如果在列、主对角线、次对角线方向有其它皇 -0#主时角战 后，则出现攻击，撒消在第列安放的皇后： 3☒X☒ 1#主对角战 ,2#主对角线 如果没有出现攻击，在第j列安放的皇后不动 3#主对角线 递归安放第+1行业后 n+i-j- ,4#主对角战 5种主时角战 。如果第1行不能安放直后，则田满到第i1行，从 35750 6#主对角线 图 下一个列G+1愧埃兹每 图 66 31/50 3.3 栈与递归的实现–Hanoi塔 „ 问题求解是递归的—Hanoi塔 void hanoi(int n, char a, char b, char c) n-圆盘数 a-源塔座 b-中介塔座 c-目标塔座 „ 搬动方法 „ n=1, a->c „ n>1: hanoi(n-1, a, c, b) a->c hanoi(n-1, b, a, c) „ 注意 用递归调用的结果， 不关注该结果如何 获得的细节 32/50 3.3 栈与递归的实现–递归实现 „ 调用函数与被调用函数---系统工作栈 „ 执行被调用函数前 „ 现场保护：实在参数、返回地址 „ 为被调用函数的局部变量分配存储区 „ 将控制转移到被调函数的入口 „ 从被调用函数返回调用函数前 „ 保存被调函数的计算结果 „ 释放被调函数的数据区 „ 现场恢复：返回 33/50 3.3 栈与递归的实现–递归实现 „ 递归过程与递归工作栈 实际的系统中，一般统一处理递归调用和非递归调用 „ 递归工作栈 „ 活动记录(栈帧stack frame) 实在参数、局部变量、上一层的返回地址 „ 每进入一层递归，产生一个新的工作记录入栈 „ 每退出一层递归，就从栈顶弹出一个工作记录 „ 当前执行层的工作记录必是栈顶记录 „ 例子：P57 hanoi(3,a,b,c) 34/50 3.3 栈与递归的实现–递归/回溯 „ 递归与回溯—N皇后问题 „ 回溯是按照某种条件往前试探搜索,若前进中 遭到失败,则回过头来另择通路继续搜索. „ N皇后问题 在n行n列的国际象棋棋盘上，若两个皇后 位于同一行、同一列或同一对角线上，则称 为它们为互相攻击。 n皇后问题是指： 找到这 n 个皇后的互不攻击的布局 35/50 3.3 栈与递归的实现–N皇后问题 ♛ ♛ ♛ ♛ 1#主对角线 0 1 2 3 0 1 2 3 k = i+j k = n+i-j-1 0#主对角线 2#主对角线 4#主对角线 6#主对角线 3#主对角线 5#主对角线 1#次对角线 3#次对角线 0#次对角线 2#次对角线 4#次对角线 6#次对角线 5#次对角线 36/50 3.3 栈与递归的实现–N皇后问题 „ 基本思路 依次为每一行确定该行皇后的合法位置 „ 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) „ 在第 j 列安放一个皇后 „ 如果在列、主对角线、次对角线方向有其它皇 后，则出现攻击，撤消在第 j 列安放的皇后： „ 如果没有出现攻击，在第 j 列安放的皇后不动 递归安放第 i+1行皇后 „ 如果第 i 行不能安放皇后，则回溯到第 i-1 行，从 下一个列(j+1)继续试探