四色定理解题报告ppt课件

四色定理解题报告,作者：魏泽宇来源：JZXXOJ-1060,1,目录,2,先看题目,著名的四色定理你一定听说过吧？这可是近代世界三大数学难题之一唷（顺便提上一句，另外两个是费马定理和哥德巴赫猜想）。四色定理的提出来自英国。1852年，毕业于伦敦大学的弗南西斯格思里(FrancisGuthrie)在一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”（注意：只要求有公共边的区域不同色就可以，只有公共顶点的同色也没关系）。四色定理一直都无法证明。直到1976年，在J.Koch的算法的支持下，美国数学家阿佩尔(KennethAppel)与哈肯(WolfgangHaken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，才终于完成了四色定理的证明。你的任务相对那些数学家们来说当然要容易得多：你只要编写一个程序，计算一下在给定的一张有5个区域的地图上，用四种颜色填充不同区域，并保证有公共边的区域不同色的方案数有多少就可以了。,3,输入输出及样例,输入第一行是一个整数N（N10），分别表示地图中有公共边的区域的信息数量。下面N行，每行一对整数，表示对所有区域编号之后，此两个编号的区域是有公共边的。输出只有一个整数，表示用四种颜色填充地图的总方案数。注意，在某些方案中，所有四种颜色不必都用到。inputoutput432412131415,4,题意分析,看到这题我想到一个单词: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:=1to4dobeginbk:=k1;,ifpd(k)thenbeginsearch(k+1);bk:=0;end;bk:=0;end;end;,k1是枚举k颜色的量。pd（k）的意思是位置k上填颜色k1。b数组是存储颜色的数组。,8,代码碎片2:判断,functionpd(m:longint):boolean;vari2:longint;beginpd:=true;fori2:=1to5dobeginif(am,i2=1)and(bm=bi2)thenbeginpd:=false;break;,end;end;end;,用循环枚举每个区域(am,i2=1)判断两个区域是否相邻。(bm=bi2)判断颜色是否相同。,9,代码碎片3:预处理,fori:=1tondobeginreadln(i1,j1);ai1,j1:=1;aj1,i1:=1;end;,ai1,j1:=1;aj1,i1:=1;改成邻接表。,10,代码拼接,varn,total,i,j,i1,j1:longint;a:array1.5,1.5oflongint;b:array1.5oflongint;functionpd(m:longint):boolean;vari2:longint;beginpd:=true;fori2:=1to5dobeginif(am,i2=1)and(bm=bi2)thenbegin,pd:=false;break;end;end;end;proceduresearch(k:longint);vark1:longint;beginifk=6thenbegininc(total);exit;end;,fork1:=1to4dobeginbk:=k1;ifpd(k)thenbeginsearch(k+1);bk:=0;end;bk:=0;end;end;beginreadln(n);fori:=1to5do,forj:=1to5doai,j:=0;fori:=1tondobeginreadln(i1,j1);ai1,j1:=1;aj1,i1:=1;end;total:=0;fori:=1to4dobeginb1:=i;search(2);b1:=0;end;,end;writeln(total);end.,11,AC感言,说句大实话，这次AC，我自己付出了许多努力。就像周镇东说的，人生就像编程，一次次优化，一次次修改。现在，我想说，人生中会有许多if语句，你做的每件事都是一个子程序，但是，除非遇到halt，绝不exit出这个子程序我想说的还有很多很多，但总结成一句话：伟大的