填字游戏算法

‘壹’ 应用问题求解，加油站有效加油位问题！

1.已知有
3
个物品：(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积
M=20，根据
0-1
背
包动态规划的递推式求出最优解。
2.按要求完成以下关于排序和查找的问题。
①对数组
A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。
②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。
③给出上述算法的递归算法。
④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。
3.已知
1
(
)
*
(
)
i
i
k
k
ij
r
r
A
a
+
=
，
k
=1，2，3，4，5，6，
r
1
=5，
r
2
=10，
r
3
=3，
r
4
=12，
r
5
=5，
r
6
=50，
r
7
=6，
求矩阵链积
A
1
×A
2
×A
3
×A
4
×A
5
×A
6
的最佳求积顺序（要求给出计算步骤）
。
4.
根
据
分
枝
限
界
算
法
基
本
过
程
,
求
解
0-1
背
包
问
题
。
已
知
n=3,M=20
，
(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。
5.试用贪心算法求解汽车加油问题：
已知一辆汽车加满油后可行驶
n
公里，
而旅途中有若干个加油站。
试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。
6.试用动态规划算法实现下列问题：设
A
和
B
是两个字符串。我们要用最少的字符操作，将字符串
A
转换为字符串
B，这里所说的字符操作包括：
①删除一个字符。
②插入一个字符。
③将一个字符改为另一个字符。
请写出该算法。
7.对于下图使用
Dijkstra
算法求由顶点
a
到顶点
h
的最短路径。
8.试写出用分治法对数组
A[n]实现快速排序的算法。
9.有
n
个活动争用一个活动室。
已知活动
i
占用的时间区域为[s
i
，
f
i
]，
活动
i,j
相容的条件是：
sj≥f
i
，问题的解表示为(x
i
|
x
i
=1，2…，n,)，x
i
表示顺序为
i
的活动编号活动，求一个相容的活动子
集，且安排的活动数目最多。
10.设
x
1
、
x
2
、
x
3
是一个三角形的三条边，而且
x
1
+x
2
+x
3
=14。请问有多少种不同的三角形？给出解答过
程。
11.设数组
A
有
n
个元素，需要找出其中的最大最小值。
①请给出一个解决方法，并分析其复杂性。
②把
n
个元素等分为两组
A1
和
A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值
和最小值相比较，求出全部元素的最大值和最小值。如果
A1
和
A2
中的元素多于两个，则再用上述
方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的
算法描述，并分析其复杂性。
12.有
n
个程序和长度为
L
的磁带，
程序
i
的长度为
a
i
，
已知
L
a
n
i
i
≻
∑
=
1
，
求最优解(x
i
，
x
2
，
...，
x
i
，
…，
x
n
)，x
i
=0，1,
x
i
=1，表示程序
i
存入磁带，x
i
=0，表示程序
i
不存入磁带，满足
L
a
x
n
i
i
i
≤
∑
=
1
，
且存放的程序数目最多。
13.试用分治法实现有重复元素的排列问题：设
)
,...,
,
{
2
1
n
r
r
r
R
=
是要进行排列的
n
个元素，其中元素
n
r
r
r
,...,
,
2
1
可能相同，试设计计算
R
的所有不同排列的算法。
14.试用动态规划算法实现
0-1
闭包问题，请写出该算法。
15.试用贪心算法求解下列问题：将正整数
n
分解为若干个互不相同的自然数之和，使这些自然数的乘
积最大，请写出该算法。
16.试写出用分治法对一个有序表实现二分搜索的算法。
17.试用动态规划算法实现最长公共子序列问题，请写出该算法。
18.假设有
7
个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量
M＝150，
使用回溯方法求解此背包问题，请写出状态空间搜索树。
物品
A
B
C
D
E
F
G
重量
35
30
60
50
40
10
25
价值
10
40
30
50
35
40
30
19.求解子集和问题：对于集合
S={1，2
，6，8}，求子集，要求该子集的元素之和
d=9。
①画出子集和问题的解空间树；
②该树运用回溯算法，写出依回溯算法遍历节点的顺序；
③如果
S
中有
n
个元素，指定
d，用伪代码描述求解子集和问题的回溯算法。
20.求解填字游戏问题：在
3×3
个方格的方阵中要填入数字
1
到
N（N≥10）内的某
9
个数字，每个方
格填一个整数，似的所有相邻两个方格内的两个整数之和为质数。试采用回溯法写出满足这个要求
的一种数字填法的算法和满足这个要求的全部数字填法的算法。
21.试用动态规划算法实现最大子矩阵和问题：
求
n
m
×
矩阵
A
的一个子矩阵，
使其各元素之和为最大。
22.试用回溯法解决下列整数变换问题：关于整数
i
的变换
f
和
g
定义如下：
⎣
⎦
2
/
)
(
;
3
)
(
i
i
g
i
i
f
=
=
。
对于给定的两个整数
n
和
m
，要求用最少的变换
f
和
g
变换次数将
n
变为
m
。
23.关于
15
谜问题。在一个
4×4
的方格的棋盘上，将数字
1
到
15
代表的
15
个棋子以任意的顺序置入
各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则
是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为
了有效的移动，设计了估值函数
C
1
(x)，表示在结点
x
的状态下，没有到达目标状态下的正确位置
的棋子的个数。

‘贰’ 数独算法思路

数独(数和)（英：Cross Sums；日：カックロ）是一种数学智力游戏。数和把填字游戏和数独巧妙地结合在一起，采用填字游戏式的棋盘，解题时在空格中填上1-9的数字。这种游戏不仅需要逻辑思维能力，还需要一点加法运算。

电脑自动生成数独游戏的谜题

要得出所有满足条件的组合确实不是件容易的事情（主要是很多，打印起来很慢） 。但偶们的目标只是每次能得到一个新的组合，然后从格子里面随机遮掉一些数字就可以了。所以只需要在解数独游戏算法的基础上稍作修改即可。

所以，算法的步骤是：

1.往第一行或第一列随机填1-9的数字

2.调用解数独算法得到一个结果

3.每行随机遮掉1-8个数字。如果需要较大的难度，也可以将1-8改为2-8或3-8，等等。

以下是console工程的代码：

// sudoku.cpp : 定义控制台应用程序的入口点。
// by superarhow([email protected])

#include "stdafx.h"

#include "conio.h"

#define SUCCESS 1
#define _FAILED 0

/* 地图类型9*9的char，每个char从0-9，0表示待填 */
typedef char MAPTYPE[9][9];
/* 行数据，同时用作“可能性”数据。如LINETYPE a; 当a[0]为真时表示
当前位置可填1，a[1]为真时表示可填2，以此类推 */
typedef char LINETYPE[9];

typedef void (*ONMAPOKCALLBACK)(MAPTYPE map);

/* 打印地图 */
void mp_map(MAPTYPE dest)
{
for ( int j = 0; j < 9; j++ )
{
for ( int i = 0; i < 9; i++ )
{
printf("%d ", dest[i][j]);
}
printf("\n");
}
printf("\n");
}

int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback);

/* 填下一个格子。本行的可能性已在调用前算好，要考虑的是列的可能性和九宫格的可能性 */
/* nums_possible : array (0-8) means possible of number (1-9) */
int fill_pos(MAPTYPE dest, LINETYPE nums_possible, int line, int pos, ONMAPOKCALLBACK callback)
{
if ( pos >= 9 )
{
return fill_line(dest, line + 1, callback);
}
if ( dest[pos][line] != 0 ) return fill_pos(dest, nums_possible, line, pos + 1, callback);
for ( int i = 0; i < 9; i++ )
{
if ( !nums_possible[i] ) continue;
/* 检查本列是否重复 */
int vetical_failed = 0;
for ( int j = 0; j < 9; j++ )
if ( dest[pos][j] == i + 1 )
{
vetical_failed = 1;
break;
}
if ( vetical_failed ) continue;
/* 检查九宫格是否重复 */
int nine_failed = 0;
int m = pos / 3;
int n = line / 3;
m *= 3;
n *= 3;
for ( int y = n; y < n + 3; y++ )
{
for ( int x = m; x < m + 3; x++ )
{
if ( dest[x][y] == i + 1 )
{
nine_failed = 1;
break;
}
}
if ( nine_failed ) break;
}
if ( nine_failed ) continue;
/* all ok, try next position */
dest[pos][line] = i + 1;
nums_possible[i] = 0;
if ( fill_pos(dest, nums_possible, line, pos + 1, callback) )
{
/* 本行已全部OK，尝试下一行 */
if ( fill_line(dest, line + 1, callback) ) return SUCCESS;
/* 下一行失败，重新尝试本位置的剩余可能性 */
}
nums_possible[i] = 1;
dest[pos][line] = 0;
}
return _FAILED;
}

/* 填下一行 */
int fill_line(MAPTYPE dest, int line, ONMAPOKCALLBACK callback)
{
if ( line >= 9 )
{
/* map */
callback(dest);
return SUCCESS;
}
LINETYPE nums;
LINETYPE saveline;
/* calc possibility(for the current line) */
for ( int i = 0; i < 9; i++ ) nums[i] = 1; /* all can be */
for ( int i = 0; i < 9; i++ )
{
char n = dest[i][line];
/* save line */
saveline[i] = dest[i][line];
if ( n != 0 ) nums[n - 1] = 0; /* appears */
}
if ( !fill_pos(dest, nums, line, 0, callback) )
{
/* restore line */
for ( int i = 0; i < 9; i++ ) dest[i][line] = saveline[i];
return _FAILED;
}
return SUCCESS;
}

MAPTYPE g_result;

void on_map_ok(MAPTYPE map)
{
memcpy(g_result, map, sizeof(MAPTYPE));
}

#include "windows.h"

int _tmain(int argc, _TCHAR* argv[])
{
MAPTYPE dest;
memset(dest, 0, sizeof(MAPTYPE));
srand( GetTickCount() );
/* 随机填充第一行 */
char ch[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for ( int i = 0; i < 9; i++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int i = 0; i < 9; i++ ) dest[i][0] = ch[i];
if ( fill_line(dest, 0, on_map_ok) )
{
/* 修剪掉一些块 */
for ( int i = 0; i < 9; i++ )
{
/* 调整n的取值范围可改变难度 %6 + 3是比较难的 */
int n = (rand() % 6) + 3;
for ( int j = 0; j < 9; j++ ) ch[j] = j; /* ch: index to erase */
for ( int j = 0; j < 9; j++ )
{
int p = rand() % 9;
char t = ch[p];
ch[p] = ch[i];
ch[i] = t;
}
for ( int j = 0; j < n; j++ ) g_result[ch[j]][i] = 0;
}
mp_map(g_result);
}
getch();
return 0;
}

看完这些，你对数独的算法了解了吗？

‘叁’ 古人从冬至的第二天起开始数九，这习俗从何而来

这是我们老祖宗的算法，因为那时候还没有日历，所以就在冬至来临时，在第二天，再往后数九，所以就成了习惯。

自古以来，就有“寒天”来形容冬天的寒冷天气，长夜难眠，更不用说在条件简陋、没有暖气、没有电热毯的古代了。

九九寒心图:民间娱乐游戏，文人画八十一梅花，每天用朱笔染，九百九十天后，梅花图就完成了，那就是春花。还有填字游戏。九个字就是九个笔画，一天一笔画，完成之后，春天就来了。例如，常用的九个字“前庭会让人想起春风”。

测量太阳的影子:在冬至，太阳会测量一根长杆，测量影子的投射。这个时候的昼影是一年中最长的。在夏至，白天的影子是最短的。

吹灰:使用管道。当明清时期开始有玻璃管时，将芦苇烧成灰烬。在冬至，如果你仔细观察，你会发现火山灰会轻轻地飘出来。

这就是古人从冬至的第二天起就数九的原因了。

‘肆’ 求一个填字算法的C语言实现

你可以考虑用回溯法实现