算法设计:设计一个拉斯维加斯算法,对于给定的自然数n(1≤n≤100)计算在n×n个方格组成的棋盘上最少要放置多少个皇后才能控制棋盘上的所有方格,且放置的皇后互不攻击.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.
结果输出:将计算的最少皇后数及最佳放置方案输出到文件output.txt.文件的第1行是最少皇后数:接下来的1行是皇后的最佳放置方案.
A.礼、乐、射、御、书、数
B.琴、棋、书、画、骑、射
C.礼、乐、诗、书、射、术
D.诗、书、礼记、仪礼、左传、公羊传
(a)在图8.10中找出两个不同大小的最小支配集。
(b)设棋盘的64个方块用64个顶点表示,如果两顶点对应的两个方块是在同一行,同一列或同一对角线上,则这两顶点之间有一条边。已知5个皇后能被放在棋盘上,使它们支配所有64个方块,而且5是必须的最小皇后数,再用图论名词叙述这一结论.