深度优先搜索解决坑爹的奥数_深度优先搜索你手里有编号为 1 ~ 9 的 九张扑克牌, 然后将这九张扑克牌放到 九个-程序员宅基地

技术标签: dfs  C++  深度优先搜索解决坑爹的奥数  

坑爹的奥数题目是:£££+£££=£££,将数字1~9分别填入9个£中,每个数字只能使用一次使得等式成立。例如173+286=459就是一个合理的组合,请问一共有多少种合理的组合呢?注意:173+286=459与286+173=459是同一种组合!!

深度优先搜索(Depth First Search,DFS)
DFS的关键在于解决“当下该如何做。”下面的代码就是深度优先搜索的基本模型:

void dfs(int step)
{
    
  判断边界
  尝试每一种可能 for (i=1;i<n;i++)
  {
    
  	继续下一步 dfs(step+1);
  }
返回
}

分析题目
这个题目就相当于你手中有编号为1~9的九张扑克牌,然后将这九张扑克牌放到九个盒子里面,并使得£££+£££=£££成立。其实就是判断一下a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]=a[7]*100+a[8]*10+a[9]
这个等式是否成立。

现在,基于深度优先搜索的基本模型和题目分析是不是已经知道怎么写了呢。那么下面我们就开始码代码啦!!

#作者:小斌斌(有问题加QQ:3105814524,备注来意)
#include<stdio.h>
int a[10],book[10],total=0;
void DFS(int step)//step表示站在第几个盒子面前
{
    
	int i;
	if(step==10)//如果站在第十个盒子面前,则表示前9个盒子已经放好扑克牌
	{
    
		//判断是否满足等式£££+£££=£££
		if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]=a[7]*100+a[8]*10+a[9])
		{
    
			//如果满足要求,可行解total+1,并打印这个解
			total++;
			printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
		}
	return ;//返回之前的一步(最近调用的地方)
	}
//此时站在弟step个盒子面前,应该放那张牌呢?
//按照1、2、3......n的顺序一一尝试
for (i=1;i<=9;i++)
{
    
//判断扑克i是否还在手上
if(book[i]==o)//book[i]为0表示扑克牌还在手上
{
    
//开始尝试使用扑克i
a[step]=i;//将扑克i放入到第step个盒子中
book[i]=1;//将book[i]的值设为1,表示扑克牌i已经不在手上
//第step个盒子已经放置好扑克牌,走到下一个盒子面前
DFS(step+1;//这里通过函数递归调用来实现(自己调用自己)
//这里非常重要的一步,一定要将刚才尝试的扑克牌收回,才能进行下一次尝试
book[i]=0;
}
}
return ;
}
int main()
{
    
	DFS(1);//首先站在第一个盒子面前
	printf("total=%d",total/2);//这里为什么要除以2前面已经解释过了哦
	getchar();getchar();
	return0;

}

根据这个坑爹的奥数题目是不是已经初步了解了深度优先搜索这个概念了呢。
赶紧去做一些深度优先搜索的题目去加强自己的技能吧!!!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45428890/article/details/105918894

智能推荐

TP5.1 搜索功能分页传参_tp5.1 分页传参前台-程序员宅基地

文章浏览阅读367次。1.html代码<form class="form-horizontal" action="{:url('admin/AuthRoles/lst')}" method="get"><div class="input-group input-group-sm"> <input type="text" id="search" name="search" styl..._tp5.1 分页传参前台

(6)学tp5之响应_tp 立即响应-程序员宅基地

文章浏览阅读815次。在手册中没有见到专门讲响应的地方。只有手册-》架构-》API友好 和 手册-》控制器-》Rest控制器中有一点。tp5中的响应,其实就是方便我们输出各种格式1、路由(用的是强制模式)2、控制器中的代码3、json和jsonp的区别,用dump()打印;jsonp和json不一样的地方,用红框圈出来了..._tp 立即响应

为什么每个扇区的容量一致-程序员宅基地

文章浏览阅读599次。如图。磁盘,每个扇区的容量是一致的

小甲鱼|Python002|用Python设计第一个游戏| 课后测试题及答案_小甲鱼python 作业-程序员宅基地

文章浏览阅读227次。0. 什么是BIF?BIF 就是 Built-in Functions,内置函数。为了方便程序员快速编写脚本程序(脚本就是要编程速度快快快!!!),Python 提供了非常丰富的内置函数,我们只需要直接调用即可,例如 print() 的功能是“打印到屏幕”,input() 的作用是接收用户输入(注:Python3 用 input() 取代了 Python2 的 raw_input(),用法如有不懂请看视频讲解)。太多BIF学不过来怎么办?看不懂英文说明怎么办?Python3的资料太少怎么办?没事,有_小甲鱼python 作业

关于ETTERCAP0.8.3报错问题_ettercap 删除注释后 报错-程序员宅基地

文章浏览阅读2.2k次。今天使用了一下ETTERCAP0.8.3发现了一个问题root@debian:/home/debian# sudo ettercap -Gettercap 0.8.2 copyright 2001-2015 Ettercap Development TeamNo protocol specifiedGTK+ failed to initialize. Is X running?搜索了很久,终于在git上找到了解决方案:就是输入xhost local:root这里要注意一点,不_ettercap 删除注释后 报错

Github连接不上问题_fastgithub 找不到任何可成功连接的ip-程序员宅基地

文章浏览阅读3.7k次,点赞3次,收藏4次。文章目录解决方法过程中问题解决方法在电脑的 C:\Windows\System32\drivers\etc 文件夹下修改或者添加140.82.114.3 github.com(ip地址需要查询)199.232.69.194 github.global.ssl.fastly.net(ip地址需要查询)查询github.com地址: https://www.ipaddress.com/ 过程中问题问题:host文件修改保存后只能另存为解决方法:修改并保存host文件..._fastgithub 找不到任何可成功连接的ip

随便推点

浅谈获取url传递的参数值的几种方式_<%=传获取的参数-程序员宅基地

文章浏览阅读1.3w次。以下内容是在开发中本人经常使用的方式,现总结如下:jsp页面中: //el表达式 获取请求参数var id = ${param.id}; var id = &lt;%=request.getParameter("id")%&gt; html页面中: //使用js 获取参数值function getQueryVariable(va..._<%=传获取的参数</div>

solr 实现数据的删除和修改_solr 修改数据 语句-程序员宅基地

文章浏览阅读9.3k次。修改主方法public int saveContent(String enterpriseId, String enterpriseName, String lableType, String resouce, String pubDate,String content) {int state = 0;LBHttpSolrServer server = SolrUtil.g_solr 修改数据 语句

惊人一谈:5G出现将让Wi-Fi产业消亡?-程序员宅基地

文章浏览阅读122次。前几日,网上流出两张微信截图,有行业人士说5G会让Wi-Fi死掉,消息一出,引起了行业内的热议。众所周知5G速度很快,但是怎么突然又牵扯出与Wi-Fi的恩怨呢?行业人士说5G出现,Wi-Fi必死。后续手机将不需要Wi-Fi芯片安装在上面。这些观点论据是否能站得住脚?包括乐鑫科技、全志科技、博通集成这一类有Wi-Fi芯片的公司未来会不会受到5G的冲击?据了解,该资深市场总监在电话里说,目前家庭的Wi..._5g wi-fi产业

什么是灰度发布?能给技术开发带来什么价值_灰度开发-程序员宅基地

文章浏览阅读2.1k次。什么是灰度发布呢?要想了解这个问题就要先明白什么是灰度。灰度从字面意思理解就是存在于黑与白之间的一个平滑过渡的区域,所以说对于互联网产品来说,上线和未上线就是黑与白之分,而实现未上线功能平稳过渡的一种方式就叫做灰度发布。在了解了什么是灰度发布的定义以后,就可以来了解一下灰度发布的具体操作方法了。_灰度开发

k8s资源指标API及metrics-server资源监控-程序员宅基地

文章浏览阅读896次。简述:在k8s早期版本中,对资源的监控使用的是heapster的资源监控工具。但是从 Kubernetes 1.8 开始,Kubernetes 通过 Metrics API 获取资源使用指标,例如容器 CPU 和内存使用情况。这些度量指标可以由用户直接访问,例如通过使用kubectl top 命令,或者使用集群中的控制器。 Metrics API: 通过 Metrics ...

ES Java API - 获取索引下数据量_java操作es查询索引中的doc数量-程序员宅基地

文章浏览阅读1.5w次。需求 获取ES某个索引下的数据总量代码示例引包import net.sf.json.JSONObject;import org.apache.commons.logging.Log;import org.apache.commons.logging.LogFactory;import org.elasticsearch.action.ActionFuture;import org.e_java操作es查询索引中的doc数量

推荐文章

热门文章

相关标签