2641: 回溯法-放烟花问题
金币值：3
定数：10
时间限制：10.000 s
内存限制：128 M
正确：2
提交：2
正确率：100.00% 命题人：
题目描述
现有n个炮筒可以独自放烟花，如果因为某种原因造成相邻的两个炮筒不能同时放烟花，则有多少种不同的放烟花方案数目。
测试代码 复制
#include "stdio.h"
double count = 0;
int x[41];
int n;
void Backtrack(int i)
{
}
int main(void)
{
scanf("%d",&n);
Backtrack(1);
printf("%.0lf", count);
return 0;
}输入格式
第1行输入1个正整数n的值（n<=40）
输出格式
不同的放烟花方案数目
输入样例 复制
3输出样例 复制
5提示
可以用回溯法或分枝限界法实现。上面的样例中如果没有两个炮筒不能同时放烟花的约束，则有8种情况；如果有了前面所说的限制条件，则110（前两个炮筒不能同时放烟花）、011（后两个炮筒不能同时放烟花）、111（三个炮筒不能同时放烟花）三种方案不可行。