A. 求我描述的地图填色问题详解(100分,只求详尽)
最少填色数量,这个似乎不用证明了吧.最少4色.
以下是李宽证明法:
证明：
首先进行抽象处理:有颜色点表示地区，连线表示相邻及版图走向。
因为地图为平面，地区版图不可相叠覆盖。
所以连线不能交叉。
因为连线两端颜色不同。
所以两两相连的几个点颜色各不相同。
所以N个点两两相连共需N种颜色。
至此，四色问题转化为：在连线不允许交叉的前提下，最多有4个点可实现两两相连。也就是说，不可能有更多点两两相连，也就不可能出现更多色。
点数为1、2、3时均成立。由于线的形状，点的位置不影响相邻关系，故点数为3时两两相连可画成三角形。点数为4时，最终均可化为三角形内含有一点且该点与三顶点分别相连的形式。即有一点被三点封闭。
点数为5时，容易发现，无论第五点放在平面什么位置，都无法实现5个点在连线不交叉的前提下两两相连。（关键）
因为连线过程是递进的。即必然先满足三点两两相连，后满足四点两两相连，随后第五点。而已知第五点连线失败，点数更多也就不可能实现了。
环状地区，可抽象为环。环本身是封闭的。相对于环外点和环，环可视为点。在环内加点连线，最终可形成封闭区
点和环均定义为元素，欲用最少色涂最多元素，同时欲用更多色，必产生封闭区域。再用元素最少情况下，三点三线、一点一环两线、两点外一环三线为三种情况。在此基础上加点，最多四元素两两相连，最多为3+1=4色。（易操作）
无论多少元素建立连线，都不会出现多于四点两两相连情况。故最多四色。
由此，四色问题证毕。
B. 关于C语言编程问题
#include <stdio.h>
void main()
{
char box[5];
int i;
printf("********************************\n");
printf("* 放球问题 *\n");
printf("********************************\n");
// a:红 b:黄 c:黑 d:白
for(box[1]='a';box[1]<='d';box[1]++)
for(box[2]='a';box[2]<='d';box[2]++)
{
if (box[1]!=box[2])
for(box[3]='a';box[3]<='d';box[3]++)
{
if(box[1]!=box[3]&&box[2]!=box[3])
for(box[4]='a';box[4]<='d';box[4]++)
{
if(box[1]!=box[4]&&box[2]!=box[4]&&box[3]!=box[4])
if ( (box[1]=='c'&&box[2]!='b' || box[1]!='c'&&box[2]=='b')
&& (box[2]=='c'&&box[3]!='d'||box[2]!='c'&&box[3]=='d')
&& (box[2]=='a'&&box[4]!='d'||box[2]!='a'&&box[4]=='d')
)
for(i=1;i<5;i++)
switch(box[i])
{
case 'a': printf("box[%d]=red ball\n",i);break;
case'b': printf("box[%d]=yellow ball\n",i);break;
case 'c': printf("box[%d]=black ball\n",i);break;
case 'd': printf("box[%d]=white ball\n",i);break;
}
}
}
}
}
C. C语言编程地图着色
书上有嘛
D. 四色问题C语言怎么解决
思路：建立数据结构，录入数据内容，遍历着色，输出第一个可行的着色方案。
下面就四个方面详细分析一下
首先分析数据结构：
对于地图，一个区块包含一个唯一编号数据（这个编号可以是地名，也可以是数字）用来区分该区块和其他区块的不同
另外要着色，还要考虑该区块和其他区块连接的情况
最后就是区块本身的颜色
通过上面的分析，即可建立如下数据结构：
structarea{
intnID;//这里以数字替代名称，作为地块的唯一标识
intnColor;//用1,2,3,4表示不同的颜色，用0表示还没有着色
area*pNei;//邻接的区块
intnNei;//邻接区块的数量
};然后需要录入数据，这个请依据具体的地图进行处理，撰写相应的录入函数，填入上面的数据结构
假设录好的数据如下：
structareacity[64];//假设已经录制好了数据，初始所有城市颜色都为0
数据录好后，我们可以如下方式进行遍历，尝试着色
遍历分为个模块：一个是遍历模块，一个是校验模块
校验模块依序检查所有的城市和其邻接城市是否存在同色的情况，是则返回false，否则返回true
遍历模块则逐个城市进行上色尝试
可以考虑递归
下面给一个递归的示例：
检测模块：
boolisOk(){
for(inti=0;i<64;i++)//假设有64个城市，其初始值和城市关系已经录制完毕
{
for(intj=0;j<city[i].nNei;j++){
if(nColor==city[i].pNei[j].nColor)
returnfalse;
}
}
returntrue;
}遍历递归模块：
booladdcity(intnIndex){
if(nIndex>=64)returntrue;//所有城市都着色了，则返回成功
for(inti=1;i<=4;i++){
city[nIndex].nColor=i;
if(isOk()){//本城市的颜色找到了
if(addcity(nIndex+1)==true){//找下一个城市的颜色
returntrue;
}else{//无法为下一个城市着色
continue;//更改本城市颜色
}
}
}
returnfalse;//没有一个颜色可行，返回上一级，重新寻找
}调用的时候可以采用下面的方式：
if(addcity(0)==false){
printf("无法找到答案，四色定理错误！
");
}else{
printf("找到了答案，城市和着色结果如下：
");
for(inti=0;i<64;i++){
printf("city%03dcolor%d
",city[i].nID,city[i].nColor);
}
}E. 地图着色问题C/C++
从一个省开始，给它涂上任意一种颜色1，遍历它旁边的省份，涂上与已经涂色并于他相邻的省份不同的颜色就行了。
理论上4种颜色就够了.地图的四色问题嘛!
可能会有多组解。用递归（dfs)就可以输出所有解了。
地图着色算法C语言源代码
前面我写了一个地图着色（即四色原理）的C源代码。
写完以后想了一下，感觉还不完善，因为从实际操作的角度来考虑，四种可用的颜色放在旁边，不同的人可能会有不同的选择顺序，另外，不同的人可能会选择不同的城市作为着色的起点，而当时的程序没有考虑这个问题。于是，把程序修改为下面的样子，还请同行分析并指出代码中的不足之处：
＃i nclude <stdio.h>
#define N 21
int allcolor[4];/*可用的颜色*/
int ok(int metro[N][N],int r_color[N],int current)
{/*ok函数和下面的go函数和原来的一样,保留用来比较两种算法*/
int j;
for(j=1;j<current;j++)
if(metro[current][j]==1&&r_color[j]==r_color[current])
return 0;
return 1;
}
void go(int metro[N][N],int r_color[N],int sum,int current)
{
int i;
if(current<=sum)
for(i=1;i<=4;i++)
{
r_color[current]=i;
if(ok(metro,r_color,current))
{
go(metro,r_color,sum,current+1);
return;
}
}
}
void color(int metro[N][N],int r_color[N],int sum,int start)
{
int i,j,k;
r_color[start]=allcolor[0];
for(i=start+1;i!=start;i=(i+1)%(sum+1))/*把所有编号看作一个环*/
if(i==0)/*城市号从1开始编号,故跳过0编号*/
continue;
else
for(j=0;j<4;j++)
{
r_color[i]=allcolor[j];/*选取下一种颜色,根据allcolor中颜色顺序不同，结果不同*/
for(k=1;k<i;k++)/*检查是否有冲突，感觉还可以改进，如使用禁忌搜索法*/
if(metro[i][k]==1&&r_color[k]==r_color[i])
break;
if(k>=i)
break;
}
}
void main()
{
int r_color[N]={0};
int t_color[N]={0};
int i;
int start;/*着色的起点*/
int metro[N][N]={{0},
{0,1,1,1,1,1,1},
{0,1,1,1,1},
{0,1,1,1,0,0,1},
{0,1,1,0,1,1},
{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},
{0,1,0,1,0,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,1,1,1,1,0,0,1},
{0,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,1,1,1,0,1},
{0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1}};
allcolor[0]=1;allcolor[1]=2;allcolor[2]=3;allcolor[3]=4;/*选色顺序，顺序不同，结果不同*/
start=1;
/* clrscr();*/
printf("\nAll color is:\n");
for(i=0;i<4;i++)/*当前选色顺序*/
printf("%d ",allcolor[i]);
go(metro,r_color,20,1);
printf("\nFirst method:\n");
for(i=1;i<=20;i++)
printf("%3d",r_color[i]);
color(metro,t_color,20,start);
printf("\nSecond method:\n");
printf("\nAnd the start metro is:%d\n",start);
for(i=1;i<=20;i++)
printf("%3d",t_color[i]);
}
说是人性化着色，其实还有一个问题没有考虑，那就是操作员跳跃式着色，就像大家玩“扫雷”游戏一样。其实也容易实现，可以像定义选色顺序一样定义着色顺序。
F. 四色问题C语言怎么解决
图论的面着色问题。
首先是要输入一个图。地图中的每一个区域在图中成为一个顶点(Vertex)，两个区域相邻在图中表示为两个顶点之间的一条边(Edge)。
这个要怎么输入呢？测试的时候可以先在代码里直接内置图的结构，要用户输入的话那就是UI的问题了。
输入完成以后，程序的内存里就有一张无向图了，图的表示方法，简单的可以用邻接矩阵来表示。
至于算法，一个比较简单的是深度优先搜索。
比如总共有10个顶点，那么至多有4^10种着色方案。
从(c1,
c1,
c1,
c1,
c1,
c1,
c1,
c1,
c1,
c1)到(c4,
c4,
c4,
c4,
c4,
c4,
c4,
c4,
c4,
c4)逐一判断即可。判断的过程中可以加入剪枝操作以提高效率。
比如(c1,
c1,
...)这个方案在确定了2个顶点的颜色后已经矛盾了，那么就直接把后面的剪掉，从(c1,
c2,
...)开始搜索
G. C语言做四色问题要代码
//线性地区的方案
#include<stdio.h>
intn=0;
intmain()
{
printf(“输入n的值=”);
scanf("%d",&n);
printf(" ");
inti=0;
inta=rand()%3+1;
intb=0;
for(i=0;i<n;i++)
{
printf("地区%d=%d ",i+1,a);
while(1)
{
b=rand()%3+1;
if(b!=a)
{
a=b;
break;
}
}
}
return0;
}