对于这个题 首先想到的是递归解决 很明显这道题的递归出口为
①n=1 时方法种为1 n=2时 方法种数为2
②那么接下来需要思考解决n>2的情况下这道题的递推公式 (递归函数思考模式)
以下是我的思考过程: 这道题只有两种瓷砖 1与2 那么我可以将当长度为N的 地板的所有可能情况枚举出来放在一起 (为解集) 可将这些结果分为A B 块 其中A 块为所有1长度为1开头的所有情况
其中B块 为所有长度为2开头的所有情况的组合 那么我们的递推公式就可以很好的得出 :::
令 F( n ) 这个函数的功能是求出长度为n的地板一共有多少种结果 显然其返回值为一个整型
那么 根据以上分析有: F(n)= F(n-1)+F(n-2) 其中F(n-1) 为已知第一块瓷砖长度为1 那么所有可能的情况数与长度为n-1的所有组合情况相同 F(n-2)亦然
至此 写递归函数的所有条件已经具备 可得到具体的F(n) 函数体
if(n==1||n==2) return n; // 注意这里一定是 两个出口
return F(n)= F(n-1)+F(n-2)
方法一:
if(n==1||n==2) return n; // 注意这里一定是 两个出口
return F(n)= F(n-1)+F(n-2)
方法二: 深度搜索(注意控制递归出口: if(cnt>n)return; 否者会栈溢出
import java.util.Scanner; public class 瓷砖铺放复习 { public static void main(String[] args) { Scanner read=new Scanner(System.in); n=read.nextInt(); dfs(0); System.out.println(sum); } public static int n; public static int sum=0; public static void dfs(int cnt) { if(cnt==n) { sum++; return; } if(cnt>n)return; dfs(cnt+1); dfs(cnt+2); } }
写在最后: 我们写递归程序不必去考虑计算机是怎样去实现的(即迭代思维) 而只需要将任务分配给他