四色定理解题报告

四色定理解题报告来源：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: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);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;beginreadln(n);fori:=1to5doforj:=1to5doa[i,j]:=0;fori:=1tondobeginreadln(i1,j1);a[i1,j1]:=1;a[j1,i1]:=1;end;total:=0;fori:=1to4dobeginb[1]:=i;search(2);b[1]:=0;end;end;writeln(total);end.11四色定理解题报告AC感言

说句大实话，这次AC，我自己付出了许多努力。

就像周镇东说的，人生就像编程，一次次优化，一次次修改。现在，我想说，人生中会有许多if语句，你做的每件事都是一个子程序，但是，除非遇到halt，绝不exit出这个子程序……

我想说的还有很多很多，但总结成一句话：

伟大的人不会踢开面前的石子，更不会绕开它。伟大的人不惧怕困难，他