S
soit
Unregistered / Unconfirmed
GUEST, unregistred user!
我需要一个可以验证四色问题的小程序，最好有源码。谢谢！
人
人在边缘
Unregistered / Unconfirmed
GUEST, unregistred user!
呵呵！好经典的问题啊！你想要验证的小程序还可以，完全验证我可做不来哦！
把地图的一个区域作为一个结点，用边连接相邻区域对应的结点得到一个图。四种颜色作图就是把图的结
点分为四个集合。所谓要相邻区域的颜色不同，就是集合中的结点要互不相邻。
范例如下(TP7.0通过，Delphi下只要稍稍改动即可)：
Program fourcolor_c;
var
graph:array[1..150] of string[150];
n:byte;
procedure input;
var
i:byte;
p:byte;
begin
write('n=');readln
;
for i:=1 to ndo
begin
write(i,':');
graph:='';
repeat
read(p);
graph:=graph+chr(p)
until eoln;
end;
end;
procedure color(x:string;k:byte);
var w,i,n:byte;
begin
for w:=1 to 4do
begin
p:=1;
while(p<=length(graph[k]))and((ord(graph[k,p])>=k)or(w+48<>ord(x[ord(graph[k,p])])))do
p:=p+1;
if p>length(grapj[k]) then
if k<n
then
color(x+chr(w+48),k+1)
else
begin
for i:=1 to n-1do
write(i:3,'-',x);
writeln(n:3,'-',w);
end;
end;
end;
begin
input;
color('',1)
end.
应用例子如下：
一张地图被分为8块区域，那么我们假设代号分别为1,2,3,4,5,6,7,8. 则上面代码中的n＝8.
对于每个区域凡是与其相连的其他区域对应关系可以确定。
如我们假设，1号地区与2,3,4,5,6,7,8都相连；则可以表示为 1:2 3 4 5 6 7 8
同理 2:1 3 8 则表示2号地区与1,3,8相连；一次类推。
一旦上述条件输入计算机程序，上面的程序马上会给出所有符合条件的求解！
把地图的一个区域作为一个结点，用边连接相邻区域对应的结点得到一个图。四种颜色作图就是把图的结
点分为四个集合。所谓要相邻区域的颜色不同，就是集合中的结点要互不相邻。
范例如下(TP7.0通过，Delphi下只要稍稍改动即可)：
Program fourcolor_c;
var
graph:array[1..150] of string[150];
n:byte;
procedure input;
var
i:byte;
p:byte;
begin
write('n=');readln
;for i:=1 to ndo
begin
write(i,':');
graph:='';
repeat
read(p);
graph:=graph+chr(p)
until eoln;
end;
end;
procedure color(x:string;k:byte);
var w,i,n:byte;
begin
for w:=1 to 4do
begin
p:=1;
while(p<=length(graph[k]))and((ord(graph[k,p])>=k)or(w+48<>ord(x[ord(graph[k,p])])))do
p:=p+1;
if p>length(grapj[k]) then
if k<n
then
color(x+chr(w+48),k+1)
else
begin
for i:=1 to n-1do
write(i:3,'-',x);
writeln(n:3,'-',w);
end;
end;
end;
begin
input;
color('',1)
end.
应用例子如下：
一张地图被分为8块区域，那么我们假设代号分别为1,2,3,4,5,6,7,8. 则上面代码中的n＝8.
对于每个区域凡是与其相连的其他区域对应关系可以确定。
如我们假设，1号地区与2,3,4,5,6,7,8都相连；则可以表示为 1:2 3 4 5 6 7 8
同理 2:1 3 8 则表示2号地区与1,3,8相连；一次类推。
一旦上述条件输入计算机程序，上面的程序马上会给出所有符合条件的求解！
S
soit
Unregistered / Unconfirmed
GUEST, unregistred user!
哦，太感谢了，不过我还想知道怎么求得最佳解，其实我连最佳解是什么都不知道，
呵呵，要是你能教我的话，我再给你100分。
呵呵，要是你能教我的话，我再给你100分。
人
人在边缘
Unregistered / Unconfirmed
GUEST, unregistred user!
最优解？？？什么意思？？？
这个问题并不是求什么最优解啊！已经可以求出所有符合条件的解，不够完美吗？？？
我理解这个问题的最优解，应该是指对于给定地图是否还存在小于四色的解，即颜色数可否更少，是吗？
那很简单，你把上面的w值（即颜色数）改为3,2,1分别试试，如：for w:=1 to 3do
那么如果可以求得解，就比较一下哪个w值最小，这个值即为最优解。
例如：上例中，w分别取4,3,2,1以后，其中取4,3时可以有解，2,1无解，那么显然3为最优解。
即对于给定地图用三种颜色就够了！至于是哪三种具体颜色倒无所谓，不是吗？
哈哈！上面啰里啰嗦一大堆话，不知道你是否看明白了，相信你一定懂了！
这个问题并不是求什么最优解啊！已经可以求出所有符合条件的解，不够完美吗？？？
我理解这个问题的最优解，应该是指对于给定地图是否还存在小于四色的解，即颜色数可否更少，是吗？
那很简单，你把上面的w值（即颜色数）改为3,2,1分别试试，如：for w:=1 to 3do
那么如果可以求得解，就比较一下哪个w值最小，这个值即为最优解。
例如：上例中，w分别取4,3,2,1以后，其中取4,3时可以有解，2,1无解，那么显然3为最优解。
即对于给定地图用三种颜色就够了！至于是哪三种具体颜色倒无所谓，不是吗？
哈哈！上面啰里啰嗦一大堆话，不知道你是否看明白了，相信你一定懂了！
S
soit
Unregistered / Unconfirmed
GUEST, unregistred user!
多谢！
S
soit
Unregistered / Unconfirmed
GUEST, unregistred user!
如果你说的是对的，我会再给你100的。