第八讲弟归犷法举例 下楼问题 八皇后问题
1 ➢下楼问题 第八讲 递归算法举例 ➢八皇后问题
讨论问题“下楼问 从楼上走到楼下共有h个台阶,每一步有三种走法 >走一个台阶 >走二个台阶; 走三个台阶。 问可走出多少种方案,希望用递归思想来编程
2 讨论问题 “下楼问 题” 从楼上走到楼下共有h个台阶，每一步有三种走法 ➢ 走一个台阶； ➢ 走二个台阶； ➢ 走三个台阶。 问可走出多少种方案，希望用递归思想来编程
定义: >Try(i,s)站在第i级台阶上往下试走第s步的过程 j=1,2,3—在每一步可以试着走的台阶数 >take [s] 存储第s步走过的台阶数 >i<j 说明第i级台阶已比要走的级台阶小,j不 可取 >i> 说明站在第i级台阶上可试走j个台阶为一步 说明这一步走完后已到了楼下,这时一条 下楼方案已试成,即可输出这一方案了
3 定义： ➢ Try(i,s)——站在第i级台阶上往下试走第s步的过程 ➢ j=1,2,3 —— 在每一步可以试着走的台阶数 ➢ take[s] —— 存储第s步走过的台阶数 ➢ i<j —— 说明第i级台阶已比要走的j级台阶小，j不 可取 ➢ i>j —— 说明站在第i级台阶上可试走j个台阶为一步 ➢ i==j —— 说明这一步走完后已到了楼下，这时一条 下楼方案已试成，即可输出这一方案了
思路: 1、用枚举的方法,试着一步一步地走,从高到低,让 先取h值从楼上走到楼下,每走一步i的值会减去每 步所走的台阶数j,即ih(初值),以后i=i-j, (j=1,2,3),当i=0时,说明已走到楼下。 2、枚举时,每一步都要试或者是为1,或是为2,或是 为3。这时可用for循环结构。 3、每一步走法都用相同的策略,故可以用递归算法
4 思路： 1、用枚举的方法，试着一步一步地走，从高到低，让i 先取h值从楼上走到楼下，每走一步i的值会减去每一 步所走的台阶数j，即i=h（初值），以后i=i-j， (j=1,2,3)，当i=0时，说明已走到楼下。 2、枚举时，每一步都要试j或者是为1，或是为2，或是 为3。这时可用for循环结构。 3、每一步走法都用相同的策略，故可以用递归算法
A try(i, s) 见图 B p p p F 什窭也不 H akes]=j 输出 try(i-J,S+1)
5 见图 输出 A try(i,s) i<j j=3 1 F 2 Lp Lp Lp H Q B E G P C D try(i-j,s+1) 什么也不做 i>=j take[s]=j i==j i>j