填字游戲演算法

『壹』 應用問題求解，加油站有效加油位問題！

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語言實現

你可以考慮用回溯法實現