四色定理解题报告.ppt

《四色定理解题报告.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、四色定理解题报告作者：魏泽宇来源：JZXXOJ-1060目录算法的基本细化题目及算法初步构建进一步细化程序AC先看题目著名的四色定理你一定听说过吧？这可是近代世界三大数学难题之一唷（顺便提上一句，另外两个是费马定理和哥德巴赫猜想）。四色定理的提出来自英国。1852年，毕业于伦敦大学的弗南西斯•格思里(FrancisGuthrie)在一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家着上不同的颜色。”（注意：只要求有公共边的区域不同色就可以，只有公共顶点的同色也没关系）。四色定理一直都无法证明。直到1976年，在J.Koch的算法的支持

2、下，美国数学家阿佩尔(KennethAppel)与哈肯(WolfgangHaken)在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，才终于完成了四色定理的证明。你的任务相对那些数学家们来说当然要容易得多：你只要编写一个程序，计算一下在给定的一张有5个区域的地图上，用四种颜色填充不同区域，并保证有公共边的区域不同色的方案数有多少就可以了。输入输出及样例输入第一行是一个整数N（０≤N≤10），分别表示地图中有公共边的区域的信息数量。下面N行，每行一对整数，表示对所有区域编号之后，此两个编号的区域是有公共边的。输出只有一个整数，表示用四种颜色填充地图的总方案数。注意

3、，在某些方案中，所有四种颜色不必都用到。inputoutput432412131415题意分析看到这题我想到一个单词:water。我想：这题应该用深搜做，阶段是当前填完了多少格子。但是，理想很丰满，现实很骨感。我编好框架就傻眼了。言归正传，刚刚说了阶段是当前填完了多少格子，那么，每个阶段要干嘛呢？1.判断是否填完，填完则找到一种解（本题是求解总数）。2.枚举k位置上所有可能的颜色。3.若颜色可以填则填进去，填k+1号格子，现场恢复。一级算法开始PROsearch(k)if到达边界then增加解总数，返回枚举k位置上所有可能的颜色iif颜色i符合条件then现场保存search（k+1）现场恢复

4、Main输入，初始化，预处理，进行第一阶段枚举，输出结束算法的基本细化增加解总数的方法是inc（total)。我们可以加一个pd函数，用来判断颜色是否可以填。第一阶段枚举时也要做现场保存和现场恢复这些工作，主程序调用search参数是2。预处理可以把基本数据变成邻接表。代码碎片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;en

5、d;end;k1是枚举k颜色的量。pd（k）的意思是位置k上填颜色k1。b数组是存储颜色的数组。代码碎片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])判断颜色是否相同。代码碎片3:预处理fori:=1tondobeginreadln(i1,j1);a[i1,j1]:=1

6、;a[j1,i1]:=1;end;a[i1,j1]:=1;a[j1,i1]:=1;改成邻接表。代码拼接varn,total,i,j,i1,j1:longint;a:array[1..5,1..5]oflongint;b:array[1..5]oflongint;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;proceduresearch(k:longint);v

7、ark1:longint;beginifk=6thenbegininc(total);exit;end;fork1:=1to4dobeginb[k]:=k1;ifpd(k)thenbeginsearch(k+1);b[k]:=0;end;b[k]:=0;end;end;beginreadln(n);fori:=1to5doforj:=1to5doa[i,j]:=0;fori:=1tondobegi