四色定理解题报告-PPT.ppt

四色定理解题报告来源：JZXXOJ-10601四色定理解题报告

目录算法的基本细化题目及算法初步构建进一步细化程序AC2四色定理解题报告

先看题目著名的四色定理你一定听说过吧？这可是近代世界三大数学难题之一唷（顺便提上一句，另外两个是费马定理和哥德巴赫猜想）。四色定理的提出来自英国。1852年，毕业于伦敦大学的弗南西斯?格思里(FrancisGuthrie)在一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”（注意：只要求有公共边的区域不同色就可以，只有公共顶点的同色也没关系）。四色定理一直都无法证明。直到1976年，在J.Koch的算法的支持下，美国数学家阿佩尔(KennethAppel)与哈肯(WolfgangHaken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，才终于完成了四色定理的证明。你的任务相对那些数学家们来说当然要容易得多：你只要编写一个程序，计算一下在给定的一张有5个区域的地图上，用四种颜色填充不同区域，并保证有公共边的区域不同色的方案数有多少就可以了。3四色定理解题报告

输入输出及样例输入第一行是一个整数N（０≤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