- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
四色定理解题报告来源:JZXXOJ-10601四色定理解题报告
目录算法的基本细化题目及算法初步构建进一步细化程序AC2四色定理解题报告
先看题目著名的四色定理你一定听说过吧?这可是近代世界三大数学难题之一唷(顺便提上一句,另外两个是费马定理和哥德巴赫猜想)。四色定理的提出来自英国。1852年,毕业于伦敦大学的弗南西斯?格思里(FrancisGuthrie)在一家科研单位搞地图着色工作时,发现了一种有趣的现象:“看来,每幅地图都可以用四种颜色着色,使得有共同边界的国家着上不同的颜色。”(注意:只要求有公共边的区域不同色就可以,只有公共顶点的同色也没关系)。四色定理一直都无法证明。直到1976年,在J.Koch的算法的支持下,美国数学家阿佩尔(KennethAppel)与哈肯(WolfgangHaken)在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿判断,才终于完成了四色定理的证明。你的任务相对那些数学家们来说当然要容易得多:你只要编写一个程序,计算一下在给定的一张有5个区域的地图上,用四种颜色填充不同区域,并保证有公共边的区域不同色的方案数有多少就可以了。3四色定理解题报告
输入输出及样例输入第一行是一个整数N(0≤N≤10),分别表示地图中有公共边的区域的信息数量。下面N行,每行一对整数,表示对所有区域编号之后,此两个编号的区域是有公共边的。?输出只有一个整数,表示用四种颜色填充地图的总方案数。注意,在某些方案中,所有四种颜色不必都用到。inputoutput4324121314154四色定理解题报告
题意分析看到这题我想到一个单词:water。我想:这题应该用深搜做,阶段是当前填完了多少格子。但是,理想很丰满,现实很骨感。我编好框架就傻眼了。言归正传,刚刚说了阶段是当前填完了多少格子,那么,每个阶段要干嘛呢?1.判断是否填完,填完则找到一种解(本题是求解总数)。2.枚举k位置上所有可能的颜色。3.若颜色可以填则填进去,填k+1号格子,现场恢复。5四色定理解题报告
一级算法开始PROsearch(k)if到达边界then增加解总数,返回枚举k位置上所有可能的颜色iif颜色i符合条件then现场保存search(k+1)现场恢复Main输入,初始化,预处理,进行第一阶段枚举,输出结束6四色定理解题报告
算法的基本细化增加解总数的方法是inc(total)。我们可以加一个pd函数,用来判断颜色是否可以填。第一阶段枚举时也要做现场保存和现场恢复这些工作,主程序调用search参数是2。预处理可以把基本数据变成邻接表。7四色定理解题报告
代码碎片1:深搜proceduresearch(k:longint);vark1:longint;beginifk=6thenbegininc(total);exit;end;fork1:=1to4dobeginb[k]:=k1;ifpd(k)thenbeginsearch(k+1);b[k]:=0;end;b[k]:=0;end;end;k1是枚举k颜色的量。pd(k)的意思是位置k上填颜色k1。b数组是存储颜色的数组。8四色定理解题报告
代码碎片2:判断functionpd(m:longint):boolean;vari2:longint;beginpd:=true;fori2:=1to5dobeginif(a[m,i2]=1)and(b[m]=b[i2])thenbeginpd:=false;break;end;end;end;用循环枚举每个区域(a[m,i2]=1)判断两个区域是否相邻。(b[m]=b[i2])判断颜色是否相同。9四色定理解题报告
代码碎片3:预处理fori:=1tondobeginreadln(i1,j1);a[i1,j1]:=1;a[j1,i1]:=1;end;a[i1,j1]:=1;a[j1,i1]:=1;改成邻接表。10四色定理解题报告
代码拼接varn,total,i,j,i1,j1:longint;a:a
您可能关注的文档
- 商务英语描述图表常用.doc
- 穿无菌手术衣、戴无菌手套、识别手术器械-PPT.ppt
- 幼儿教育心理学的研究对象、任务与研究内容-PPT.ppt
- 小学生全国普通话推广宣传主题班会ppt课件(优质ppt).pptx
- 2024幼儿园普通话推广幼儿园推普周PPT课件(优质ppt).pptx
- 幼儿园网络安全主题宣传教育ppt课件(优质ppt).pptx
- 新生儿呛奶知识学习孕妈育儿知识讲座ppt课件(优质ppt).pptx
- 小学如何讲普通话推广普通话主题教案PPT(优质ppt).pptx
- 新生儿低钙血症病例讨论医院病例分享会ppt课件(优质ppt).pptx
- 大学生网络安全教育PPT课件(优质ppt).pptx
文档评论(0)