nbhkdz.com冰点文库

七巧板染色


回专题模式 回学习阶段模式 【题目名称、来源】 七巧板染色(经典问题 qiqiaob.pas) 【问题描述】 如下图所示,七巧板中有一些板块是相邻的,现在要用红、黄、蓝、白四种颜色将七巧板 染色,要求任意相邻的两块板颜色不能相同,请枚举出所有方案和方案总数。

输入: N {共有多少相邻块,用两个相邻块编号表示,1 2 相邻不重复列举为 2 1} 12 16

23 24 34 45 46 56 57 67 输出: 所有方案 方案数 【所属专题】 回溯 【适合学习阶段】 第一阶段、第二阶段 【解题思路】 问题分析: 将七巧板抽象成图,相邻的板块之间有一条边,不相邻的板块间没有边。 存储结构: var tu:array [1..7,1..7] of integer{有七巧板抽象出来的图}; s:array[1..7] of integer;{栈,用来记录每一块板染成什么颜色 Four Color:1,2,3,4} color:array[1..4] of boolean;{标志数组,该颜色是否使用过} 【测试数据】 【源程序】 program qiqiaob;

var tu:array [1..7,1..7] of integer{有七巧板抽象出来的图}; s:array[1..7] of integer;{栈,用来记录每一块板染成什么颜色 Four Color:1,2,3,4} color:array[1..4] of boolean;{标志数组,该颜色是否使用过} i,j,count,n,head,tail:integer; function can(step,color:integer):boolean; var i:integer; begin can:=true; for i:= 1 to step do begin if (tu[step,i]=1)and(s[i]=color) then begin can:=false; break; end; end; end; procedure go(step:integer); var i,j,k:integer; begin for i:=1 to 4 do begin s[step]:=i;{color a board} if can(step,i) then begin if step=7 then begin for j:=1 to 7 do write(s[j],' '); writeln;count:=count+1; end else go(step+1); s[step]:=0;{回溯} end; end; end; begin assign(input,'qiqiaob.in'); assign(output,'qiqiaob.out'); reset(input); rewrite(output); for i:=1 to 7 do for j:=1 to 7 do tu[i,j]:=0; for i:=1 to 4 do color[i]:=false; count:=0; {初始化数组和变量} readln(n); for i:=1 to n do begin readln(head,tail); tu[head,tail]:=1;

tu[tail,head]:=1; end; go(1); writeln('count=',count); close(input); close(output); end.


美术基本知识

七巧板宋代,早称燕几图,创始人黄伯思。特点巧、变、复、朴、分、合 长命兜肚...拚连 剪纸类型单色、套色、染色、分色、阴文剪纸、阳文剪纸 剪纸种类黑白剪纸、...

几何专题之五近期杯赛试题解析(08)_6

(a) ,ABCD 是一个长方形,其中阴 是由一副面积为 100 平方厘米的七巧板(...方体中,表面积最小的是___平方厘米; 五、立体的分割、展开、染色: 27. (...

2016中考科学密卷押题(二)

地球的岩石圈好像一整块拼好的“七巧板” ,说明全球由七大板块组 成 5. 盐酸...另一边以 45°再慢慢盖上)防止气泡产生;④在盖玻片一侧 滴红墨水 (染色,便于...

形式与政治

我们倡导理性平和的心态,但如果监管防线屡屡失守,瘦肉精猪 肉、染色馒头、毒生姜...正如一副七巧板,拼版如何摆放,决定组成什么图案。社会终究是由不同群体组成,铁板...

专业题

木偶傀儡戏分类仗头木偶、提线木偶、铁枝木偶、布袋木偶 七巧板宋代,早称燕几图...拚连 剪纸类型单色、套色、染色、分色、阴文剪纸、阳文剪纸 剪纸种类黑白剪纸、...

巴赫班2015年6月份主题

1.科学:花台布 2.美术:染色窗花 3.计算:小猪的苹果(401 页) 4.语言:我的...美丽的小桥 2.阅读区: 小熊过桥 3.建构区:搭建小桥 4.益智区:七巧板— 拼...

几何专题之五近期杯赛试题解析(08)

ABCD 是一个长方形,其中阴 影部分是由一副面积为 100 平方厘米的七巧板(如图...方体中,表面积最小的是___平方厘米; 五、立体的分割、展开、染色: 27. (...

几何专题之五近期杯赛试题解析(08)

(a) ,ABCD 是一个长方形,其中阴 副面积为 100 平方厘米的七巧板(如图 b)...方体中,表面积最小的是___平方厘米; 五、立体的分割、展开、染色: 27. (...

几何专题之五近期杯赛试题解析(08)_4

ABCD 是一个长方形,其中阴 影部分是由一副面积为 100 平方厘米的七巧板(如图...方体中,表面积最小的是___平方厘米; 五、立体的分割、展开、染色: 27. (...

几何专题之五近期杯赛试题解析(08)

ABCD 是一个长方形,其中阴 影部分是由一副面积为 100 平方厘米的七巧板(如图...方体中,表面积最小的是___平方厘米; 五、立体的分割、展开、染色: 27. (...