首页 > 代码库 > 不容易系列之(3)—— LELE的RPG难题
不容易系列之(3)—— LELE的RPG难题
有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.
思路:运用递归算法。
a[1]=3,a[2]=6,a[3]=6
分两种情况讨论:
第一种:第(n-1)个格子与第一个格子不同色,那么涂(n-1)个格子共有a[n-1]种方法,由于(n-1)格子与第一个格子不同色,最后一格子只有一种颜色可涂。
第二种:第(n-1)个格子与第一个格子同色,前面的(n-2)个格子共有a[n-2]种凃法,加上的(n-1)个格子由于与第一个格子同色,所以不会与(n-2)个格子 颜色相同,此时最后一个格子有两种凃法,所有共有2*a[n-2]方法。
总和:a[n]=a[n-1]+2*a[n-2]
1 #include <iostream> 2 using namespace std; 3 int main() 4 { 5 long long a[100]; 6 a[1] = 3; 7 a[2] = 6; 8 a[3] = 6; 9 int n; 10 while (cin>>n) 11 { 12 for (int i=4; i <= n; i++) 13 { 14 a[i] = a[i - 1] + 2 * a[i - 2]; 15 } 16 cout << a[n] << endl; 17 } 18 }
不容易系列之(3)—— LELE的RPG难题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。