c语言背包问题_背包问题贪心算法_背包问题 贪心算法(13)

for iß1 to n do ／／将所有结点标记为未访问／／

⑴

repeat

for i<--1 to n do ／／反复调用bfs／／

if visited(i)＝0 then ⑵ endif

repeat

end bft

2．找一个图的所有m—着色方案

procedure mcoloring(k)

／／这是图着色的一个递归回溯算法。图g用它的布尔邻接矩阵graPh(1：n，1：n)表示。它计算并打印出符合以下要求的全部解，把整数1，2，…，m分配给图中各个结点且使相邻近的结点的有不同的整数。k是下一个要着色结点的下标。／／

global integer m，n，x(1：n)boolean graPh(1；n，1：n)

integer k

loop／／产生对x(k)所有的合法赋值。／／

call nextvalue(k)。//将一种合法的颜色分配给x(k)／／

if ⑴ then exit endif ／／没有可用的颜色了／／

if ⑵

then print(x) ／／至多用了m种颜色分配给n个结点／／

else callmcoloring<k+1) ／／所有m—着色方案均在此反复递归调用中产生／／

endif

repeat

end mcoloring

三、问答题

1.二分查找的思想是什么？

2．请用递归方法写出归并排序法的主要思想和算法。

3.已知如下多段图，请用动态规划方法的向后处理法写出求解此问题的递推公式并完成对各结点的计算。

4. 最小自然数：求具有下列两个性质的最小自然数n：

(１)n的个位数是６；

(２)若将n的个位数移到其余各位数字之前，所得的新数是n的４倍。

提示：仍用穷举法寻找，当找到一个符合条件者便停止。“找到便停止”的重复，宜采用repeat－until循环。

5. 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-23877-13.html