兰州响应式网站建设,平台网站模板素材图片,网站开发实例及研究,云南网络科技公司排名目录
写在前面#xff1a;
题目#xff1a;P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述#xff1a;
输入格式#xff1a;
输出格式#xff1a;
输入样例#xff1a;
输出样例#xff1a;
解题思路#xff1a; …目录
写在前面
题目P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
输入格式
输出格式
输入样例
输出样例
解题思路
代码
AC
写在最后 写在前面
怎么样才能学好一个算法
我个人认为系统性的刷题尤为重要
所以为了学好深度优先搜索为了用好暴搜应对蓝桥杯
事不宜迟我们即刻开始刷题
题目P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述 输入格式
一个整数 n ( 1 ≤ n ≤ 24 )。
输出格式
一个整数能拼成的不同等式的数目。
输入样例
1.
14
2.
18
输出样例
1.
2
2.
9
解题思路
我们使用深度优先搜索的时候
第一个要注意的点是搜索的顺序
因为我们要保证
我们写出的递归结构能够遍历所有情况
在我们初学搜索的时候我们一定要画一个递归搜索树观察
递归非常抽象画图能很好的帮助我们解题。以上递归搜索的基本思路多熟悉总是好的 接下来是具体思路
根据题意可知 这样我们可以把它想象成
在ABC这三个位置上填数字
满足ABC以及ABC的火柴数等于n-4
那我们根据这个思路来画递归搜索数
根节点 往第一个位置填数字 继续往下递归搜索
我们发现其实这是一个指数型的枚举 我们继续往下搜索 以此类推我们能够搜索出所有的情况
然后再根据题意进行判断和剪枝
剪枝
如果A或者AB的火柴数已经大于题目要求的n
就直接return也就是剪枝。
接下来看代码
代码
//包常用头文件
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;//题目n最大是24如果不确定该开多大那就开大点
const int N 10010;int n;//计数最后输出
int res 0;int st[N];//各个数字的火柴数
int match[10010] { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };void dfs(int u, int sum)
{//如果A或者AB的火柴数已经大于题目要求的n剪枝if(sum n)return;if (u 3){//满足ABC以及ABC的火柴数等于n-4if (st[1] st[2] st[3] sum n - 4){res;}return;}//搜索for (int i 0; i 1000; i){st[u] i;dfs(u 1, sum match[i]);st[u] 0;}
}int main()
{scanf(%d, n);//递推取得每个数字的火柴数for(int i 10; i 1000; i){match[i] match[i / 10] match[i % 10];}dfs(1, 0);printf(%d, res);return 0;
} AC 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
