浙大城院數(shù)學(xué)建模4

1、2022-7-2MCM1第四章、線性代數(shù)模型第四章、線性代數(shù)模型 4.1 4.1 幾個(gè)數(shù)學(xué)游戲幾個(gè)數(shù)學(xué)游戲 4.2 Drer4.2 Drer魔方魔方( (或幻方或幻方) )問(wèn)題問(wèn)題 4.3 4.3 密碼的設(shè)計(jì)、解碼與破譯密碼的設(shè)計(jì)、解碼與破譯 4.44.4考慮年齡結(jié)構(gòu)的人口模型考慮年齡結(jié)構(gòu)的人口模型(Leslie(Leslie模模型型) )2022-7-2MCM2 4.1 4.1 幾個(gè)數(shù)學(xué)游戲幾個(gè)數(shù)學(xué)游戲 向量、向量空間、矩陣等都是線性代數(shù)中的重要概向量、向量空間、矩陣等都是線性代數(shù)中的重要概念，本節(jié)將通過(guò)一些簡(jiǎn)單的實(shí)例來(lái)說(shuō)明它們?cè)趯?shí)際中的念，本節(jié)將通過(guò)一些簡(jiǎn)單的實(shí)例來(lái)說(shuō)明它們?cè)趯?shí)際中的應(yīng)用。

2、應(yīng)用。 例例4.14.1 人、狗、雞、米過(guò)河問(wèn)題人、狗、雞、米過(guò)河問(wèn)題 這是一個(gè)人所共知而又十分簡(jiǎn)單的智力游戲。某人這是一個(gè)人所共知而又十分簡(jiǎn)單的智力游戲。某人要帶狗、雞、米過(guò)河，但小船除了需要有人去劃以外，要帶狗、雞、米過(guò)河，但小船除了需要有人去劃以外，最多只能載一物過(guò)河，而當(dāng)人不在場(chǎng)時(shí)，狗要咬雞、雞最多只能載一物過(guò)河，而當(dāng)人不在場(chǎng)時(shí)，狗要咬雞、雞要吃米，問(wèn)此人應(yīng)如何過(guò)河。要吃米，問(wèn)此人應(yīng)如何過(guò)河。 要知道例要知道例4.14.1的答案并不困難。第一次，人只能帶的答案并不困難。第一次，人只能帶雞過(guò)河。到了對(duì)岸，人只有自己回來(lái)，將雞留在對(duì)岸，雞過(guò)河。到了對(duì)岸，人只有自己回來(lái)，將雞留在對(duì)岸，否則，

3、又返回了初始狀態(tài)。否則，又返回了初始狀態(tài)。2022-7-2MCM3 接下來(lái)，人可以帶狗過(guò)河，也可以帶米過(guò)河，但回接下來(lái)，人可以帶狗過(guò)河，也可以帶米過(guò)河，但回來(lái)時(shí)有一定要將雞帶回，來(lái)時(shí)有一定要將雞帶回，按此推導(dǎo)下去，讀者不，按此推導(dǎo)下去，讀者不難找到過(guò)河方法。我們研究本例的目的不在于找出答案，難找到過(guò)河方法。我們研究本例的目的不在于找出答案，而是想設(shè)計(jì)出一種讓計(jì)算機(jī)自行搜索尋找答案的方法。而是想設(shè)計(jì)出一種讓計(jì)算機(jī)自行搜索尋找答案的方法。為此目的，我們先把例為此目的，我們先把例1 1轉(zhuǎn)化為狀態(tài)轉(zhuǎn)移問(wèn)題。首先，應(yīng)轉(zhuǎn)化為狀態(tài)轉(zhuǎn)移問(wèn)題。首先，應(yīng)當(dāng)如何表達(dá)狀態(tài)呢？不同的情況應(yīng)采取不同的方法，在當(dāng)如何表達(dá)狀

4、態(tài)呢？不同的情況應(yīng)采取不同的方法，在本例中，人雞狗米都只有兩種可能狀態(tài)，即在此岸或在本例中，人雞狗米都只有兩種可能狀態(tài)，即在此岸或在彼岸（不在此岸）。我們將用向量來(lái)表示狀態(tài)，可采取彼岸（不在此岸）。我們將用向量來(lái)表示狀態(tài)，可采取如下方法：一物在此岸時(shí)相應(yīng)分量取如下方法：一物在此岸時(shí)相應(yīng)分量取1 1，而在彼岸時(shí)則相，而在彼岸時(shí)則相應(yīng)分量取為應(yīng)分量取為0 0，例如（，例如（1,0,1,01,0,1,0）表示人和雞在此岸，而）表示人和雞在此岸，而狗和米則在彼岸。狗和米則在彼岸。2022-7-2MCM4(i) (i) 可取狀態(tài)：根據(jù)題意，并非所有狀態(tài)都是允許的，可取狀態(tài)：根據(jù)題意，并非所有狀態(tài)都是允許

5、的，例如（例如（0,1,1,00,1,1,0）就是一個(gè)不可取的狀態(tài)，因?yàn)楣窌?huì)咬雞。）就是一個(gè)不可取的狀態(tài)，因?yàn)楣窌?huì)咬雞。本題中可取狀態(tài)（即系統(tǒng)允許的狀態(tài)）可以用窮舉法列本題中可取狀態(tài)（即系統(tǒng)允許的狀態(tài)）可以用窮舉法列出來(lái)，它們是：出來(lái)，它們是： (1 1 1 1) (0 0 0 0)(1 1 1 0) (0 0 0 1)(1 1 0 1) (0 0 1 0)(1 0 1 1) (0 1 0 0)(1 0 1 0) (0 1 0 1)人在此岸人在對(duì)岸 總共有十個(gè)可取狀態(tài)。對(duì)一般情況，也可找出狀態(tài)總共有十個(gè)可取狀態(tài)。對(duì)一般情況，也可找出狀態(tài)為可取的充要條件，讓計(jì)算機(jī)根據(jù)充要條件來(lái)檢查得到為可取的充

6、要條件，讓計(jì)算機(jī)根據(jù)充要條件來(lái)檢查得到的狀態(tài)是否為可取狀態(tài)。的狀態(tài)是否為可取狀態(tài)。2022-7-2MCM5(ii) (ii) 可取運(yùn)算：狀態(tài)轉(zhuǎn)移需要經(jīng)過(guò)狀態(tài)運(yùn)算來(lái)實(shí)現(xiàn)。在可取運(yùn)算：狀態(tài)轉(zhuǎn)移需要經(jīng)過(guò)狀態(tài)運(yùn)算來(lái)實(shí)現(xiàn)。在實(shí)際問(wèn)題中，擺一次渡即可改變現(xiàn)有狀態(tài)。為此再引入一實(shí)際問(wèn)題中，擺一次渡即可改變現(xiàn)有狀態(tài)。為此再引入一個(gè)四維向量個(gè)四維向量( (轉(zhuǎn)移向量轉(zhuǎn)移向量) )，用它來(lái)反映擺渡情況。例如，用它來(lái)反映擺渡情況。例如(1(1，1 1，0 0，0)0)表示人帶狗擺渡過(guò)河。根據(jù)題意，允許使用的轉(zhuǎn)表示人帶狗擺渡過(guò)河。根據(jù)題意，允許使用的轉(zhuǎn)移向量只能有移向量只能有(1(1，0 0，0 0，0)0)、(1(1

7、，1 1，0 0，0)0)、(1(1，0 0，1 1，0)0)、（、（1 1，0 0，0 0，1)1)四個(gè)。四個(gè)。 為實(shí)現(xiàn)本題中的狀態(tài)轉(zhuǎn)移，規(guī)定一個(gè)狀態(tài)向量與轉(zhuǎn)為實(shí)現(xiàn)本題中的狀態(tài)轉(zhuǎn)移，規(guī)定一個(gè)狀態(tài)向量與轉(zhuǎn)移向量之間的運(yùn)算。規(guī)定狀態(tài)向量與轉(zhuǎn)移向量之和為一移向量之間的運(yùn)算。規(guī)定狀態(tài)向量與轉(zhuǎn)移向量之和為一新的狀態(tài)向量，其運(yùn)算為對(duì)應(yīng)分量相加，且規(guī)定新的狀態(tài)向量，其運(yùn)算為對(duì)應(yīng)分量相加，且規(guī)定0+0=00+0=0，1+0=0+1=11+0=0+1=1，1+1=01+1=0。例如。例如(1(1，1 1，1 1，1)+(11)+(1，0 0，1 1，0)=(00)=(0，1 1，0 0，1)1)，其實(shí)際意義為

8、人狗雞米原來(lái)均在此岸，其實(shí)際意義為人狗雞米原來(lái)均在此岸，人帶雞過(guò)河，轉(zhuǎn)變?yōu)樾碌臓顟B(tài)此岸僅剩狗和米，人帶雞過(guò)河，轉(zhuǎn)變?yōu)樾碌臓顟B(tài)此岸僅剩狗和米，( (注：此注：此處作這樣的運(yùn)算規(guī)定完全是為了與實(shí)際情況相符處作這樣的運(yùn)算規(guī)定完全是為了與實(shí)際情況相符) )。2022-7-2MCM6 在具體轉(zhuǎn)移時(shí)，只考慮由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)在具體轉(zhuǎn)移時(shí)，只考慮由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移。問(wèn)題化為：由初始狀態(tài)移。問(wèn)題化為：由初始狀態(tài)(1(1，1 1，1 1，1)1)出發(fā)，經(jīng)過(guò)奇出發(fā)，經(jīng)過(guò)奇數(shù)次的上述運(yùn)算能否轉(zhuǎn)化為數(shù)次的上述運(yùn)算能否轉(zhuǎn)化為(0(0，0 0，0 0，0)0)的轉(zhuǎn)化問(wèn)題，的轉(zhuǎn)化問(wèn)題，進(jìn)而，如果能，我們還想知

9、道具體應(yīng)當(dāng)如何轉(zhuǎn)化進(jìn)而，如果能，我們還想知道具體應(yīng)當(dāng)如何轉(zhuǎn)化 。 由于規(guī)定的運(yùn)算十分容易在計(jì)算機(jī)上實(shí)現(xiàn)，這樣一由于規(guī)定的運(yùn)算十分容易在計(jì)算機(jī)上實(shí)現(xiàn)，這樣一來(lái)就把一個(gè)數(shù)學(xué)游戲轉(zhuǎn)化為了一個(gè)可以在計(jì)算機(jī)上計(jì)算來(lái)就把一個(gè)數(shù)學(xué)游戲轉(zhuǎn)化為了一個(gè)可以在計(jì)算機(jī)上計(jì)算的數(shù)學(xué)問(wèn)題的數(shù)學(xué)問(wèn)題( (即建模即建模) )。當(dāng)然，像本題這樣簡(jiǎn)單的問(wèn)題，。當(dāng)然，像本題這樣簡(jiǎn)單的問(wèn)題，也可通過(guò)筆算方法求解，具體可如下進(jìn)行分析也可通過(guò)筆算方法求解，具體可如下進(jìn)行分析(第一次渡河第一次渡河)(1,1,0,0)(0,0,1,1)()(1,0,1,0)(0,1,0,1)()(1,1,1,1) (1,0,0,1)(0,1,1,0)()(

10、1,0,0,0)(0,1,1,1)()不可取可取不可取不可取2022-7-2MCM7(第二次渡河第二次渡河)(1,1,0,0)(1,0,0,1)()(1,0,1,0)(1,1,1,1)(,)(0,1,0,1) (1,0,0,1)(1,1,0,0)()(1,0,0,0)(1,1,0,1)()不可取循環(huán) 回到原先出現(xiàn)過(guò)的狀態(tài)不可取可取 以下可繼續(xù)進(jìn)行下去，直至轉(zhuǎn)移目的實(shí)現(xiàn)。以下可繼續(xù)進(jìn)行下去，直至轉(zhuǎn)移目的實(shí)現(xiàn)。上述分析實(shí)際上采用的是窮舉法，對(duì)于規(guī)模較大上述分析實(shí)際上采用的是窮舉法，對(duì)于規(guī)模較大的問(wèn)題是不宜采用的。的問(wèn)題是不宜采用的。2022-7-2MCM8例例4.2 4.2 夫妻過(guò)河問(wèn)題夫妻過(guò)河問(wèn)

11、題 這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問(wèn)題。有三對(duì)夫妻要這是一個(gè)古老的阿拉伯?dāng)?shù)學(xué)問(wèn)題。有三對(duì)夫妻要過(guò)河，船最多可載兩人，約束條件是根據(jù)阿拉伯法律，過(guò)河，船最多可載兩人，約束條件是根據(jù)阿拉伯法律，任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在任一女子不得在其丈夫不在場(chǎng)的情況下與其他男子在一起，問(wèn)此時(shí)這三對(duì)夫妻能否過(guò)河？一起，問(wèn)此時(shí)這三對(duì)夫妻能否過(guò)河？ 這一問(wèn)題的狀態(tài)和運(yùn)算與前一問(wèn)題有所不同，根這一問(wèn)題的狀態(tài)和運(yùn)算與前一問(wèn)題有所不同，根據(jù)題意，狀態(tài)應(yīng)能反映出兩岸的男女人數(shù)，過(guò)河也同據(jù)題意，狀態(tài)應(yīng)能反映出兩岸的男女人數(shù)，過(guò)河也同樣要反映出性別，故可如下定義：樣要反映出性別，故可如下定義：(i) (i) 可取狀

12、態(tài)：用可取狀態(tài)：用H H和和W W分別表示此岸的男子和女子數(shù)，分別表示此岸的男子和女子數(shù)，狀態(tài)可用矢量狀態(tài)可用矢量( (H H，W W) )表示，其中表示，其中00H H、W W33。可取狀?？扇顟B(tài)為態(tài)為(0,(0,i i) )，( (i i, ,i i) )，(3,(3,i i) )，00i i33。( (i i, ,i i) )為可取狀為可取狀態(tài)，這是因?yàn)榭偪梢赃m當(dāng)安排而使他們是態(tài)，這是因?yàn)榭偪梢赃m當(dāng)安排而使他們是i i對(duì)夫妻。對(duì)夫妻。2022-7-2MCM9(ii) (ii) 可取運(yùn)算：過(guò)河方式可以是一對(duì)夫妻、兩個(gè)男人可取運(yùn)算：過(guò)河方式可以是一對(duì)夫妻、兩個(gè)男人或兩個(gè)女人，當(dāng)然也可以是一

13、人過(guò)河。轉(zhuǎn)移向量可取或兩個(gè)女人，當(dāng)然也可以是一人過(guò)河。轉(zhuǎn)移向量可取成成(1 1）i im m, (, (1)1)i in n），其中），其中m m、n n可取可取0 0、1 1、2 2，但，但必須滿足必須滿足11m m+ +n n22。當(dāng)。當(dāng)j j為奇數(shù)時(shí)表示過(guò)河。當(dāng)為奇數(shù)時(shí)表示過(guò)河。當(dāng)j j為偶為偶數(shù)時(shí)表示由對(duì)岸回來(lái)，運(yùn)算規(guī)則同普通向量的加法。數(shù)時(shí)表示由對(duì)岸回來(lái)，運(yùn)算規(guī)則同普通向量的加法。問(wèn)題歸結(jié)為由狀態(tài)問(wèn)題歸結(jié)為由狀態(tài)(3,3)(3,3)經(jīng)奇數(shù)次可取運(yùn)算，即由可取經(jīng)奇數(shù)次可取運(yùn)算，即由可取狀態(tài)到可取狀態(tài)的轉(zhuǎn)移，轉(zhuǎn)化為狀態(tài)到可取狀態(tài)的轉(zhuǎn)移，轉(zhuǎn)化為(0,0)(0,0)的轉(zhuǎn)移問(wèn)題。和的轉(zhuǎn)移問(wèn)題。

14、和上題一樣，我們既可以用計(jì)算機(jī)求解，也可以分析求上題一樣，我們既可以用計(jì)算機(jī)求解，也可以分析求解，此外，本題還可用作圖方法來(lái)求解。解，此外，本題還可用作圖方法來(lái)求解。2022-7-2MCM102022-7-2MCM112022-7-2MCM12 關(guān)于夫妻過(guò)河還可以編出許多其他形式的問(wèn)題，下關(guān)于夫妻過(guò)河還可以編出許多其他形式的問(wèn)題，下面我們來(lái)討論一些同樣有趣的問(wèn)題。為了敘述簡(jiǎn)便，先面我們來(lái)討論一些同樣有趣的問(wèn)題。為了敘述簡(jiǎn)便，先約定一些符號(hào)，這些符號(hào)將被應(yīng)用于以下的各個(gè)問(wèn)題之約定一些符號(hào)，這些符號(hào)將被應(yīng)用于以下的各個(gè)問(wèn)題之中。記想過(guò)河的夫妻對(duì)數(shù)為中。記想過(guò)河的夫妻對(duì)數(shù)為n n，船可載的人數(shù)為，船

15、可載的人數(shù)為m m，n n對(duì)對(duì)夫妻過(guò)河所需的最少擺渡次數(shù)為夫妻過(guò)河所需的最少擺渡次數(shù)為k k。 這三對(duì)夫妻是可以過(guò)河的。假如按這樣的方案過(guò)這三對(duì)夫妻是可以過(guò)河的。假如按這樣的方案過(guò)河，共需經(jīng)過(guò)十一次擺渡。河，共需經(jīng)過(guò)十一次擺渡。 不難看出，在上述規(guī)則下，不難看出，在上述規(guī)則下，4 4對(duì)夫妻就無(wú)法過(guò)河了，對(duì)夫妻就無(wú)法過(guò)河了，讀者可以自行證明之。類似可以討論船每次可載三人的讀者可以自行證明之。類似可以討論船每次可載三人的情況，其結(jié)果是情況，其結(jié)果是5 5對(duì)夫妻是可以過(guò)河的，而六對(duì)以上時(shí)對(duì)夫妻是可以過(guò)河的，而六對(duì)以上時(shí)就無(wú)法過(guò)河了。假如船每次可以載四人，則任意多對(duì)夫就無(wú)法過(guò)河了。假如船每次可以載四人

16、，則任意多對(duì)夫妻均可過(guò)河，最易看出的一個(gè)方案是讓一對(duì)夫妻當(dāng)船員妻均可過(guò)河，最易看出的一個(gè)方案是讓一對(duì)夫妻當(dāng)船員工即可。工即可。2022-7-2MCM13( (問(wèn)題問(wèn)題1)1) 2 2對(duì)夫妻要過(guò)河，船每次只能渡對(duì)夫妻要過(guò)河，船每次只能渡2 2人，應(yīng)如何人，應(yīng)如何過(guò)河，最少擺渡幾次？過(guò)河，最少擺渡幾次？( (即即n=2n=2，m=2m=2，求，求k=?)k=?)本問(wèn)題很容易解答，讀者可自行完成本問(wèn)題很容易解答，讀者可自行完成( (答案為答案為k=5)k=5)。( (問(wèn)題問(wèn)題2)2) n n對(duì)夫妻要過(guò)河，船每次可載對(duì)夫妻要過(guò)河，船每次可載n-1n-1人，應(yīng)如何過(guò)人，應(yīng)如何過(guò)河，最少要擺幾次渡？（河，

17、最少要擺幾次渡？（n=m-1n=m-1，求，求k=?k=?）。）。答案如下：答案如下：(1)n=3(1)n=3，m=2m=2，k=11; (2) n=4k=11; (2) n=4，m=3m=3，k=9k=9 (3)n5 (3)n5，m=n-1m=n-1，k=7k=7( (問(wèn)題問(wèn)題3)3) 1883 1883年，呂卡斯年，呂卡斯(Rcrations)(Rcrations)提出以下問(wèn)提出以下問(wèn)題：題：n n對(duì)夫妻要過(guò)河，船至少應(yīng)可載幾人對(duì)夫妻要過(guò)河，船至少應(yīng)可載幾人(m?)(m?)他們才他們才可能過(guò)河，最少擺渡次數(shù)為多少？可能過(guò)河，最少擺渡次數(shù)為多少？2022-7-2MCM14德蘭努瓦德蘭努瓦(M

18、. Delannoy)(M. Delannoy)證明：證明：(1)n=2(1)n=2，m=2m=2，k=5k=5； (2)n=3(2)n=3，m=3m=3，k=11k=11(3)n=4(3)n=4，m=3m=3，k=9k=9； (4)n=5(4)n=5，m=3m=3，k=11k=11(5)n6(5)n6，m=4m=4，k=2n-3k=2n-3 2022-7-2MCM15 有些較為復(fù)雜的問(wèn)題，開始時(shí)常常給人以一種有些較為復(fù)雜的問(wèn)題，開始時(shí)常常給人以一種變幻莫測(cè)的感覺。但經(jīng)過(guò)細(xì)微的分析研究，可以發(fā)現(xiàn)變幻莫測(cè)的感覺。但經(jīng)過(guò)細(xì)微的分析研究，可以發(fā)現(xiàn)其中存在著某些內(nèi)在的關(guān)系。在使用適當(dāng)?shù)臄?shù)學(xué)工具其中存在

19、著某些內(nèi)在的關(guān)系。在使用適當(dāng)?shù)臄?shù)學(xué)工具后，這些內(nèi)在關(guān)系就被一一揭露出來(lái)了。后，這些內(nèi)在關(guān)系就被一一揭露出來(lái)了。 德國(guó)著名的藝術(shù)家德國(guó)著名的藝術(shù)家Albrecht Drer(1471-1521)Albrecht Drer(1471-1521)于于15141514年曾鑄造了一枚名為年曾鑄造了一枚名為“Melencotia I”Melencotia I”的銅幣。的銅幣。令人奇怪的是在這枚銅幣的畫面上充滿了數(shù)學(xué)符號(hào)、令人奇怪的是在這枚銅幣的畫面上充滿了數(shù)學(xué)符號(hào)、數(shù)字及幾何圖形。這里，我們僅研究銅幣右上角的數(shù)數(shù)字及幾何圖形。這里，我們僅研究銅幣右上角的數(shù)字問(wèn)題。字問(wèn)題。 4.2 Drer4.2 Drer

20、魔方魔方( (或幻方或幻方) )問(wèn)題問(wèn)題2022-7-2MCM161 1、DrerDrer魔方魔方16 3 這是一個(gè)由自然數(shù)組成的方塊，稱之為這是一個(gè)由自然數(shù)組成的方塊，稱之為DrerDrer魔方，魔方，其數(shù)字排列如下：其數(shù)字排列如下： 什么是魔方？我們來(lái)下一個(gè)定義。我們所謂的魔方什么是魔方？我們來(lái)下一個(gè)定義。我們所謂的魔方是指由是指由1 1n n2 2這這n n2 2個(gè)正整數(shù)按一定規(guī)則排列成的一個(gè)個(gè)正整數(shù)按一定規(guī)則排列成的一個(gè)n n行行n n列的正方形。列的正方形。 2022-7-2MCM17 按不同的要求，它可以具有某些特定的性質(zhì)，按不同的要求，它可以具有某些特定的性質(zhì)，n n稱稱為此魔方

21、的階。例如，上面給出的為此魔方的階。例如，上面給出的DrerDrer魔方是魔方是4 4階的，階的，它的每一行數(shù)字之和為它的每一行數(shù)字之和為3434，每一列數(shù)字之和為，每一列數(shù)字之和為3434，把對(duì)，把對(duì)角線角線( (或反對(duì)角線或反對(duì)角線) )上的數(shù)字加起來(lái)是上的數(shù)字加起來(lái)是3434，每個(gè)小方塊中，每個(gè)小方塊中的數(shù)字之和也是的數(shù)字之和也是3434，若把四個(gè)角上的數(shù)字加起來(lái)還是，若把四個(gè)角上的數(shù)字加起來(lái)還是3434，多么奇妙！最后一行中間兩個(gè)數(shù)字恰好是銅幣的鑄造時(shí)多么奇妙！最后一行中間兩個(gè)數(shù)字恰好是銅幣的鑄造時(shí)間間15141514年。年。 構(gòu)造魔方是一個(gè)古老的數(shù)學(xué)游戲，起初它還和神靈構(gòu)造魔方是一個(gè)

22、古老的數(shù)學(xué)游戲，起初它還和神靈聯(lián)系在一起，帶有深厚的迷信色彩。傳說(shuō)三千二百多年聯(lián)系在一起，帶有深厚的迷信色彩。傳說(shuō)三千二百多年前前( (公元前公元前22002200年年) )，因治水出名的皇帝大禹就構(gòu)造了三，因治水出名的皇帝大禹就構(gòu)造了三階魔方階魔方( (被人們稱被人們稱“洛書洛書”) )，至今還有人把它當(dāng)作符咒，至今還有人把它當(dāng)作符咒用于某些迷信活動(dòng)，用于某些迷信活動(dòng)，2022-7-2MCM188 1 ( (被人稱為洛書的被人稱為洛書的3 3階魔方階魔方) ) 大約在十五世紀(jì)時(shí)，魔方傳到了西方，著名的科尼大約在十五世紀(jì)時(shí)，魔方傳到了西方，著名的科尼利厄斯利厄斯阿格里帕阿格里帕(1486-15

23、35)(1486-1535)先后構(gòu)造出了先后構(gòu)造出了3 39 9階的魔階的魔方。方。 如何構(gòu)造出各種階數(shù)的魔方呢？假如你知道方法，如何構(gòu)造出各種階數(shù)的魔方呢？假如你知道方法，構(gòu)造它其實(shí)并不困難。構(gòu)造它其實(shí)并不困難。 在構(gòu)造在構(gòu)造n n階魔方時(shí)，首先要看清階魔方時(shí)，首先要看清n n是奇數(shù)還是偶數(shù)，是奇數(shù)還是偶數(shù)，在構(gòu)造時(shí)要巧妙地利用某種形式的對(duì)稱性。在構(gòu)造時(shí)要巧妙地利用某種形式的對(duì)稱性。2022-7-2MCM19 我們先來(lái)看我們先來(lái)看n n是奇數(shù)的情況，奇數(shù)階魔方的構(gòu)造方法是奇數(shù)的情況，奇數(shù)階魔方的構(gòu)造方法如下：如下： 首先，在第一行中間寫首先，在第一行中間寫1 1；然后每次向右上方移一；然后每

24、次向右上方移一格，依次填由小到大排列的下一個(gè)數(shù)，格，依次填由小到大排列的下一個(gè)數(shù)，( (注：向上移出注：向上移出界時(shí)填下一列最后一行的小方格；向右移出界時(shí)填第一界時(shí)填下一列最后一行的小方格；向右移出界時(shí)填第一列上一行的小方格，就好像上下邊是相連的、左右邊也列上一行的小方格，就好像上下邊是相連的、左右邊也是相連的一樣是相連的一樣) )。此外，當(dāng)下面想填的格已填過(guò)數(shù)或已。此外，當(dāng)下面想填的格已填過(guò)數(shù)或已達(dá)到魔方的右上角時(shí)，改填剛才填的格子正下方的小方達(dá)到魔方的右上角時(shí)，改填剛才填的格子正下方的小方格，此后繼續(xù)按原方法填，直至完全填完所有小方格。格，此后繼續(xù)按原方法填，直至完全填完所有小方格。例如，

25、按上述方法可構(gòu)造出下面的例如，按上述方法可構(gòu)造出下面的5 5階魔方：階魔方：2022-7-2MCM20作為練習(xí)，請(qǐng)你給出一個(gè)作為練習(xí)，請(qǐng)你給出一個(gè)7 7階階的魔方的魔方( (見習(xí)題見習(xí)題) )。 偶數(shù)階的魔方可以利用奇數(shù)階魔方拼接而成，拉偶數(shù)階的魔方可以利用奇數(shù)階魔方拼接而成，拉爾夫爾夫斯特雷奇給出了一種拼接的方法。限于篇幅的斯特雷奇給出了一種拼接的方法。限于篇幅的限止，我們不在此詳細(xì)介紹了，作為一個(gè)例子，我們限止，我們不在此詳細(xì)介紹了，作為一個(gè)例子，我們采用他的方法構(gòu)造一個(gè)采用他的方法構(gòu)造一個(gè)6 6階的魔方。階的魔方。第一步第一步 利用利用1-91-9，10-1810-18，19-2719-

26、27及及28-3628-36構(gòu)造出構(gòu)造出4 4個(gè)個(gè)3 3階的魔方，它們分別是：階的魔方，它們分別是：2022-7-2MCM21第二步第二步 利用圖利用圖11-911-9中的中的A A、B B、C C、D D容易拼出一個(gè)容易拼出一個(gè)6 6階階的魔方。為了保證性質(zhì)的成立，還需要作一些調(diào)整，的魔方。為了保證性質(zhì)的成立，還需要作一些調(diào)整，如果你有興趣，不妨可以找一下調(diào)整的方法，如果你有興趣，不妨可以找一下調(diào)整的方法，( (調(diào)整后調(diào)整后得到的得到的6 6階魔方見圖階魔方見圖4-24-2所示所示) )2022-7-2MCM22( (圖圖4-24-2 ) )2022-7-2MCM23 上述方法并非構(gòu)造魔方的

27、唯一方法，但不論采用上述方法并非構(gòu)造魔方的唯一方法，但不論采用什么方法來(lái)構(gòu)造魔方，都應(yīng)當(dāng)盡可能利用某種形式的對(duì)什么方法來(lái)構(gòu)造魔方，都應(yīng)當(dāng)盡可能利用某種形式的對(duì)稱性。在魔方的構(gòu)造中包含了許多有趣的數(shù)學(xué)問(wèn)題，但稱性。在魔方的構(gòu)造中包含了許多有趣的數(shù)學(xué)問(wèn)題，但由于很多人研究過(guò)這些問(wèn)題，我們一般只能把它們當(dāng)成由于很多人研究過(guò)這些問(wèn)題，我們一般只能把它們當(dāng)成一些練習(xí)題。一些練習(xí)題。 互不相同的同階魔方究竟有多少個(gè)？人們知道，三互不相同的同階魔方究竟有多少個(gè)？人們知道，三階魔方只有一個(gè)，當(dāng)然，通過(guò)鏡面反射和繞中心旋轉(zhuǎn)可階魔方只有一個(gè)，當(dāng)然，通過(guò)鏡面反射和繞中心旋轉(zhuǎn)可以產(chǎn)生以產(chǎn)生8 8種不同的表現(xiàn)形式。四階

28、魔方共有種不同的表現(xiàn)形式。四階魔方共有880880個(gè)，而通個(gè)，而通過(guò)反射與旋轉(zhuǎn)可有過(guò)反射與旋轉(zhuǎn)可有70407040種不同的形式。沒有人知道五階種不同的形式。沒有人知道五階或更高階魔方的數(shù)量。例如，對(duì)五階魔方，人們可用某或更高階魔方的數(shù)量。例如，對(duì)五階魔方，人們可用某種辦法作出實(shí)質(zhì)上不同的種辦法作出實(shí)質(zhì)上不同的5760057600個(gè)個(gè)( (不含反射與旋轉(zhuǎn)而得不含反射與旋轉(zhuǎn)而得出的出的) )，如加上用其他方法構(gòu)造的，已知的五階魔方總，如加上用其他方法構(gòu)造的，已知的五階魔方總數(shù)遠(yuǎn)遠(yuǎn)超過(guò)了一千三百萬(wàn)個(gè)，魔方數(shù)量隨階數(shù)數(shù)遠(yuǎn)遠(yuǎn)超過(guò)了一千三百萬(wàn)個(gè)，魔方數(shù)量隨階數(shù)n n增長(zhǎng)已增長(zhǎng)已達(dá)到了驚人的速度，令人目瞪口

29、呆。達(dá)到了驚人的速度，令人目瞪口呆。2022-7-2MCM242 2、松馳問(wèn)題的討論、松馳問(wèn)題的討論 假如我們放松對(duì)構(gòu)造魔方的數(shù)必須是假如我們放松對(duì)構(gòu)造魔方的數(shù)必須是1-n21-n2的要求而的要求而允許它們?nèi)∪我鈱?shí)數(shù)，允許它們?nèi)∪我鈱?shí)數(shù)，( (就像將整數(shù)規(guī)劃或就像將整數(shù)規(guī)劃或0-10-1規(guī)劃松馳規(guī)劃松馳成相應(yīng)的線性規(guī)劃那樣成相應(yīng)的線性規(guī)劃那樣) )，問(wèn)題也許會(huì)簡(jiǎn)單得多。我們，問(wèn)題也許會(huì)簡(jiǎn)單得多。我們?nèi)砸笏鼈兙哂心承┨囟ǖ男再|(zhì)，并不妨仍把它們稱為仍要求它們具有某些特定的性質(zhì)，并不妨仍把它們稱為魔方，當(dāng)然，此時(shí)問(wèn)題已發(fā)生了實(shí)質(zhì)性的變化，不再是魔方，當(dāng)然，此時(shí)問(wèn)題已發(fā)生了實(shí)質(zhì)性的變化，不再是原先討

30、論的問(wèn)題了。原先討論的問(wèn)題了。 為簡(jiǎn)單起見，我們用為簡(jiǎn)單起見，我們用n n階方陣來(lái)記這樣的魔方。易見，階方陣來(lái)記這樣的魔方。易見，若若A A與與B B均為具有指定性質(zhì)的魔方，則對(duì)任意的實(shí)數(shù)均為具有指定性質(zhì)的魔方，則對(duì)任意的實(shí)數(shù)和和，A+BA+B也是。這一性質(zhì)表明，具有指定性質(zhì)的魔方也是。這一性質(zhì)表明，具有指定性質(zhì)的魔方全體構(gòu)成一個(gè)線性空間。根據(jù)線性代數(shù)知識(shí)，要刻畫一全體構(gòu)成一個(gè)線性空間。根據(jù)線性代數(shù)知識(shí)，要刻畫一個(gè)線性空間只需指出它的維數(shù)并求出此線性空間的一組個(gè)線性空間只需指出它的維數(shù)并求出此線性空間的一組基底即可?；准纯?。2022-7-2MCM25不妨仍以不妨仍以4 4階方陣為例。首先，定

31、義階方陣為例。首先，定義0-0-方與方與1-1-方如下：方如下：其中其中R R為行和，為行和，C C為列和，為列和，D D為對(duì)角線和，為對(duì)角線和，S S為小方為小方塊和。塊和。 現(xiàn)在，我們來(lái)研究具有性質(zhì)現(xiàn)在，我們來(lái)研究具有性質(zhì)R=C=D=SR=C=D=S的方陣構(gòu)成的線的方陣構(gòu)成的線性空間性空間 ，類似于構(gòu)造，類似于構(gòu)造n n維歐氏空間的標(biāo)準(zhǔn)基，我們利用維歐氏空間的標(biāo)準(zhǔn)基，我們利用0 0和和1 1來(lái)構(gòu)造一些來(lái)構(gòu)造一些R=C=D=S=1R=C=D=S=1的最簡(jiǎn)單的方陣，不難看出，的最簡(jiǎn)單的方陣，不難看出，1 1在第一行中共有在第一行中共有4 4種排法，為保持上述性質(zhì)的成立，在種排法，為保持上述性質(zhì)

32、的成立，在第一行的第一行的1 1取定后，第二行中的取定后，第二行中的1 1尚有兩種取法。當(dāng)?shù)诙杏袃煞N取法。當(dāng)?shù)诙械男械? 1也取定后，第三行與第四行的也取定后，第三行與第四行的1 1就完全定位了，故就完全定位了，故一共可作出一共可作出8 8個(gè)不同的最簡(jiǎn)方陣，稱之為基本魔方并記之個(gè)不同的最簡(jiǎn)方陣，稱之為基本魔方并記之為為Q1Q1，Q8Q8。2022-7-2MCM2611000001000010100Q21000000101000010Q30001100000100100Q40001010010000010Q50010100001000001Q60100001010000001Q7001001

33、0000011000Q80100000100101000Q2022-7-2MCM27 顯然，顯然，D D中任何一個(gè)元素都可以用中任何一個(gè)元素都可以用Q Q1 1，Q Q2 2，Q Q8 8來(lái)來(lái)線性表示，它們能否構(gòu)成線性表示，它們能否構(gòu)成D D的一組基，關(guān)鍵在于它們是的一組基，關(guān)鍵在于它們是否線性無(wú)關(guān)。否線性無(wú)關(guān)。容易看出容易看出145823670QQQQQQQQ 所以所以Q Q1 1，Q Q2 2，Q Q8 8這這8 8個(gè)基本方是線性相關(guān)的，即個(gè)基本方是線性相關(guān)的，即至少存在一個(gè)至少存在一個(gè)Q Qj j，可以通過(guò)其它，可以通過(guò)其它7 7個(gè)基本方的線性組合個(gè)基本方的線性組合得到，這得到，這8 8

34、個(gè)基本方的地位是等同的，故可不妨設(shè)個(gè)基本方的地位是等同的，故可不妨設(shè)j=8j=8。下面驗(yàn)證下面驗(yàn)證Q Q1 1，Q Q2 2，Q Q7 7是否線性相關(guān)。是否線性相關(guān)。令，令， 即即 710iiirQ2022-7-2MCM2812657343547162462531771324560000000000000000rrrrrrrrrrrrrrrrrrrrrrrrrrrr 等號(hào)兩邊對(duì)應(yīng)元素相比較，得等號(hào)兩邊對(duì)應(yīng)元素相比較，得r r1 1=r=r2 2=r=r7 7=0=0，所以，所以Q Q1 1，Q Q2 2，Q Q7 7是線性無(wú)關(guān)的。是線性無(wú)關(guān)的。Q Q1 1，Q Q2 2，Q Q7 7是是D D

35、空間空間的一組基，的一組基，D D中任何元素都可以由中任何元素都可以由Q Q1 1，Q Q2 2，Q Q7 7的線性的線性組合生成?？梢赃@樣認(rèn)為：組合生成?？梢赃@樣認(rèn)為： Q Q1 1，Q Q2 2，Q Q8 8 是是D D的生的生成集，但不是最小生成集，而成集，但不是最小生成集，而 Q Q1 1，Q Q2 2，Q Q7 7 是是D D的的最小生成集。最小生成集。2022-7-2MCM29 現(xiàn)在，我們回到現(xiàn)在，我們回到Albrecht DrerAlbrecht Drer鑄造的銅幣，以鑄造的銅幣，以Q Q1 1，Q Q2 2， ， Q Q7 7的 線 性 組 合 表 示 銅 幣 上 的 魔 方

36、，的 線 性 組 合 表 示 銅 幣 上 的 魔 方 ， D = D = d d1 1Q Q1 1+d+d2 2Q Q2 2+d+d7 7Q Q7 7，即解方程組，即解方程組 126573435471624625317713245616321351011896712515141dddddddddddddddddddddddddddd解得解得1234567D=8Q +8Q +7Q +6Q +3Q +3Q +5Q2022-7-2MCM303 3、D D空間的子空間和空間的子空間和D D空間的擴(kuò)展空間的擴(kuò)展 改變對(duì)改變對(duì)DrerDrer魔方數(shù)字和的要求，我們可以利用線魔方數(shù)字和的要求，我們可以利用線

37、性子空間的定義，構(gòu)造性子空間的定義，構(gòu)造D D的子空間或者構(gòu)造新的空間包含的子空間或者構(gòu)造新的空間包含D D空間。這里，我們規(guī)定僅包含空間。這里，我們規(guī)定僅包含0 0方的向量空間維數(shù)為零。方的向量空間維數(shù)為零。( 1 ) ( 1 ) 要 求 數(shù) 字 方 的 所 有 數(shù) 都 相 等 。 這 是 集 合要 求 數(shù) 字 方 的 所 有 數(shù) 都 相 等 。 這 是 集 合G=rE,rRG=rE,rR，G G是以是以G=EG=E為基的一維向量空間，是為基的一維向量空間，是D D的一維子空間。的一維子空間。(2) (2) 要求列和，行和及每條主、付對(duì)角線上數(shù)字和都相要求列和，行和及每條主、付對(duì)角線上數(shù)字和

38、都相等，得到等，得到5 5維泛對(duì)角方的向量空間維泛對(duì)角方的向量空間B B。例如：。例如：2022-7-2MCM3117211161611223127621126712PH=N=R=C=S=46H=N=R=C=S=46其中其中H H為主對(duì)角線和，為主對(duì)角線和，N N為付對(duì)角線和。為付對(duì)角線和。它的基它的基BBBB為為11010101001010101P21001011010010110P30110100101101001P40101101010100101P51100001111000011P2022-7-2MCM32(3) (3) 要求行和，列和及兩條對(duì)角線上的元素和相等，要求行和，列和及兩條

39、對(duì)角線上的元素和相等，得到得到8 8維向量空間維向量空間Q Q，基向量，基向量Q QB B= Q= Q1 1，Q Q2 2，Q Q7 7，N N0 0 ，其中，其中Q Q1 1，Q Q2 2，Q Q7 7是是D D的基，的基，00110000000000110N例如：例如：679812657510967779TR=C=D=30R=C=D=302022-7-2MCM33(4) (4) 僅要求行和與列和相等，可以得到僅要求行和與列和相等，可以得到1010維向量空間維向量空間，它的基，它的基B B= Q= Q1 1，Q Q2 2，Q Q7 7，N N1 1，N N2 2，N N3 3 ，其中，其中Q

40、 Q1 1，Q Q2 2，Q Q7 7是是D D的基，而的基，而10000100110010000N20101101010010110N30100100000010010N2022-7-2MCM34(5) (5) 如果我們對(duì)數(shù)字沒任何要求，那么所有的如果我們對(duì)數(shù)字沒任何要求，那么所有的4 44 4數(shù)數(shù)字方組成的向量空間字方組成的向量空間M M，它的維數(shù)是，它的維數(shù)是1616，基向量，基向量MBMB中的中的元素應(yīng)是標(biāo)準(zhǔn)基，元素應(yīng)是標(biāo)準(zhǔn)基，( (即僅有一個(gè)元素為即僅有一個(gè)元素為1 1，其余元素均，其余元素均為為0 0的方陣的方陣) )。 Botsch(1976 Botsch(1976年年) )證明

41、了可以構(gòu)造大量的證明了可以構(gòu)造大量的D D的子空間的子空間或或D D的擴(kuò)張空間。對(duì)于的擴(kuò)張空間。對(duì)于1 1與與1616之間的每一個(gè)數(shù)之間的每一個(gè)數(shù)K K，都存在，都存在K K維的維的4 44 4方的向量空間，其中的每一方陣都具有某些方的向量空間，其中的每一方陣都具有某些特定的性質(zhì)。特定的性質(zhì)。由上可知，有下式成立由上可知，有下式成立(向量空間向量空間) 0GBDQM 0 1 5 7 8 10 160 1 5 7 8 10 16( (維數(shù)維數(shù)) ) 2022-7-2MCM35 4.3 4.3 密碼的設(shè)計(jì)、解碼與破譯密碼的設(shè)計(jì)、解碼與破譯 密碼的設(shè)計(jì)和使用至少可以追溯到四千多年前的埃密碼的設(shè)計(jì)和使

42、用至少可以追溯到四千多年前的埃及及 、巴比倫、羅馬和希臘，歷史極為久遠(yuǎn)。古代隱藏信、巴比倫、羅馬和希臘，歷史極為久遠(yuǎn)。古代隱藏信息的方法主要有兩大類：其一為隱藏信息載體，采用隱息的方法主要有兩大類：其一為隱藏信息載體，采用隱寫術(shù)等；其二為變換信息載體，使之無(wú)法為一般人所理寫術(shù)等；其二為變換信息載體，使之無(wú)法為一般人所理解。本節(jié)只涉及后者，介紹一些采用數(shù)學(xué)工具對(duì)信息加解。本節(jié)只涉及后者，介紹一些采用數(shù)學(xué)工具對(duì)信息加密、解密的方法。密、解密的方法。 在密碼學(xué)中，信息代碼被稱為密碼，加密前的信息在密碼學(xué)中，信息代碼被稱為密碼，加密前的信息被稱為明文，經(jīng)加密后不為常人所理解的用密碼表示的被稱為明文，經(jīng)

43、加密后不為常人所理解的用密碼表示的信息被稱為密文信息被稱為密文(ciphertext)(ciphertext)，將明文轉(zhuǎn)變成密文的過(guò)，將明文轉(zhuǎn)變成密文的過(guò)程被稱為加密程被稱為加密(enciphering)(enciphering)，其逆過(guò)程則被稱為解密，其逆過(guò)程則被稱為解密(deciphering)(deciphering)，而用以加密、解密的方法或算法則被稱，而用以加密、解密的方法或算法則被稱為密碼體制為密碼體制(crytosystem)(crytosystem)。2022-7-2MCM36 記全體明文組成的集合為記全體明文組成的集合為U U，全體密文組成的集合為，全體密文組成的集合為V V

44、，稱，稱U U為明文空間，為明文空間，V V為密文空間。加密常利用某一被稱為密文空間。加密常利用某一被稱為密鑰的東西來(lái)實(shí)現(xiàn)，它通常取自于一個(gè)被稱為密鑰空為密鑰的東西來(lái)實(shí)現(xiàn)，它通常取自于一個(gè)被稱為密鑰空間的含有若干參數(shù)的集合間的含有若干參數(shù)的集合K K。按數(shù)學(xué)的觀點(diǎn)來(lái)看，加密與。按數(shù)學(xué)的觀點(diǎn)來(lái)看，加密與解密均可被看成是一種變換解密均可被看成是一種變換( (或稱映射或稱映射) )：取一：取一k kK K， u uU U，令，令 ，v v為明文為明文u u在密鑰在密鑰K K下的密文，下的密文，而解碼則要用到而解碼則要用到K K的逆變換的逆變換K K-1-1， 。由此可見，。由此可見，密碼體系雖然可以

45、千姿百態(tài)，但其關(guān)鍵還在于密鑰的選密碼體系雖然可以千姿百態(tài)，但其關(guān)鍵還在于密鑰的選取。取。kuvV 1kvu 隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，大量各具特色隨著計(jì)算機(jī)與網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，大量各具特色的密碼體系不斷涌現(xiàn)。離散數(shù)學(xué)、數(shù)論、計(jì)算復(fù)雜性、的密碼體系不斷涌現(xiàn)。離散數(shù)學(xué)、數(shù)論、計(jì)算復(fù)雜性、混沌、混沌、，許多相當(dāng)高深的數(shù)學(xué)知識(shí)都被用上，逐步，許多相當(dāng)高深的數(shù)學(xué)知識(shí)都被用上，逐步形成了形成了( (并仍在迅速發(fā)展的并仍在迅速發(fā)展的) )具有廣泛應(yīng)用面的現(xiàn)代密碼具有廣泛應(yīng)用面的現(xiàn)代密碼學(xué)。學(xué)。 2022-7-2MCM37 早期密碼大體可分三類：代替法密碼、移位密碼和早期密碼大體可分三類：代替法密碼、

46、移位密碼和代數(shù)密碼。代數(shù)密碼。代替法密碼代替法密碼 代替法密碼采用另一個(gè)字母表中的字母來(lái)代替明文代替法密碼采用另一個(gè)字母表中的字母來(lái)代替明文中的字母，明文字母與密文字母保持一一對(duì)應(yīng)關(guān)系，但中的字母，明文字母與密文字母保持一一對(duì)應(yīng)關(guān)系，但采用的符號(hào)改變了。加密時(shí)，把明文換成密文，即把明采用的符號(hào)改變了。加密時(shí)，把明文換成密文，即把明文中的字母用密文字母表中對(duì)應(yīng)位置上的字母取代。解文中的字母用密文字母表中對(duì)應(yīng)位置上的字母取代。解密時(shí)，則把密文換成明文，即把密文中的字母用明文字密時(shí)，則把密文換成明文，即把密文中的字母用明文字母表中對(duì)應(yīng)位置上的字母代回母表中對(duì)應(yīng)位置上的字母代回, ,解密過(guò)程是加密過(guò)程

47、的逆解密過(guò)程是加密過(guò)程的逆過(guò)程。在代替法加密過(guò)程中，明文字母表、密文字母表過(guò)程。在代替法加密過(guò)程中，明文字母表、密文字母表及兩者間的對(duì)應(yīng)關(guān)系即為代替法密鑰，密鑰既可以采用及兩者間的對(duì)應(yīng)關(guān)系即為代替法密鑰，密鑰既可以采用標(biāo)準(zhǔn)字母表，也可以任意建立。例如，我們可采用以下標(biāo)準(zhǔn)字母表，也可以任意建立。例如，我們可采用以下的明文字母表和密文字母表：的明文字母表和密文字母表： 2022-7-2MCM38明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMNOPQRSTUVWXYZABCDEFGHIJKLM

48、NOPQRSTUVWXYZABCDEFGHIJ 密鑰還經(jīng)常用一密鑰字或密鑰短語(yǔ)生成混淆字母表。密鑰還經(jīng)常用一密鑰字或密鑰短語(yǔ)生成混淆字母表。密鑰字或密鑰短語(yǔ)可以存放在識(shí)別碼、通行字或密鑰的密鑰字或密鑰短語(yǔ)可以存放在識(shí)別碼、通行字或密鑰的秘密表格中。混合一個(gè)字母表，常見的有兩種方法，這秘密表格中?；旌弦粋€(gè)字母表，常見的有兩種方法，這兩種方法都采用了一個(gè)密鑰字或一個(gè)密鑰短語(yǔ)。兩種方法都采用了一個(gè)密鑰字或一個(gè)密鑰短語(yǔ)。方法一：方法一： a)a)選擇一個(gè)密鑰字或密鑰短語(yǔ)，例如：選擇一個(gè)密鑰字或密鑰短語(yǔ)，例如：constructconstructb)b)去掉其中重復(fù)的字母，得：去掉其中重復(fù)的字母，得：c

49、onstruconstruc)c)在修改后的密鑰字后面接上從標(biāo)準(zhǔn)字母表中去在修改后的密鑰字后面接上從標(biāo)準(zhǔn)字母表中去掉密鑰中的已有字母后剩下的字母，得：掉密鑰中的已有字母后剩下的字母，得：明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 CONSTRUABDEFGHIJKLMPQVWXYZCONSTRUABDEFGHIJKLMPQVWXYZ2022-7-2MCM39 在設(shè)計(jì)密鑰時(shí)，也可在明文字母表中選擇一個(gè)特定在設(shè)計(jì)密鑰時(shí)，也可在明文字母表中選擇一個(gè)特定字母，然后從該特定字母開始寫密鑰字并將密鑰字隱

50、藏字母，然后從該特定字母開始寫密鑰字并將密鑰字隱藏于其中。例如，對(duì)于上例，選取特定字母于其中。例如，對(duì)于上例，選取特定字母k k，則可得：，則可得： 明文字母表明文字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ密文字母表密文字母表 KLMPQVWXYZCONSTRUABDEFGHIJ KLMPQVWXYZCONSTRUABDEFGHIJ 方法二：方法二： a) a)選擇一個(gè)密鑰字或密鑰短語(yǔ)，例如：選擇一個(gè)密鑰字或密鑰短語(yǔ)，例如：constructconstruct b) b)去掉其中重復(fù)的字母，得：去掉其中重復(fù)的字母，得：con

51、struconstru c) c)這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由這些字母構(gòu)成矩陣的第一行，矩陣的后續(xù)各行由標(biāo)準(zhǔn)字母表中去掉密鑰字的字母后剩下的字母構(gòu)成標(biāo)準(zhǔn)字母表中去掉密鑰字的字母后剩下的字母構(gòu)成2022-7-2MCM40construab de fghijklm p qv w xyz d)d)把所得矩陣中的字母按列的順序選出，得：把所得矩陣中的字母按列的順序選出，得：caivobjwndkxselytfmzrgpuhqcaivobjwndkxselytfmzrgpuhq按照此方法產(chǎn)生的字母表稱為混淆字母表。按照此方法產(chǎn)生的字母表稱為混淆字母表。2022-7-2MCM41 在代替法加

52、密中，除了使用混淆字母表外，還可在代替法加密中，除了使用混淆字母表外，還可以使用混淆數(shù)?；煜龜?shù)由以下方法產(chǎn)生：以使用混淆數(shù)?；煜龜?shù)由以下方法產(chǎn)生： a)a)選一密鑰字或密鑰短語(yǔ)，例如：選一密鑰字或密鑰短語(yǔ)，例如：constructconstructb)b)按照這些字母在標(biāo)準(zhǔn)字母表中出現(xiàn)的相對(duì)順序給它們按照這些字母在標(biāo)準(zhǔn)字母表中出現(xiàn)的相對(duì)順序給它們編號(hào)，對(duì)序列中重復(fù)的字母則自左向右編號(hào)，得：編號(hào)，對(duì)序列中重復(fù)的字母則自左向右編號(hào)，得： construct construct 143675928 143675928c)c)自左向右選出這些數(shù)字，得到一混淆數(shù)字組：自左向右選出這些數(shù)字，得到一混淆數(shù)字

53、組：143675928143675928，混淆字母表由從小到大的順序取矩陣中相，混淆字母表由從小到大的順序取矩陣中相應(yīng)列得出應(yīng)列得出, ,先取第一列、再取第先取第一列、再取第8 8列、列、，依次得出秘，依次得出秘文字母表。文字母表。 為增加保密性，在使用代替法時(shí)還可利用一些其他技為增加保密性，在使用代替法時(shí)還可利用一些其他技巧，如單字母表對(duì)多字母表、單字母對(duì)多字母、多重代巧，如單字母表對(duì)多字母表、單字母對(duì)多字母、多重代替等，這里就不再一一細(xì)說(shuō)了。替等，這里就不再一一細(xì)說(shuō)了。2022-7-2MCM42移位密碼體制移位密碼體制 移位密碼采用移位法進(jìn)行加密，明文中的字母重新移位密碼采用移位法進(jìn)行加密

54、，明文中的字母重新排列，本身不變，只是位置改變了。排列，本身不變，只是位置改變了。 現(xiàn)在所知的最為古老的加密方法現(xiàn)在所知的最為古老的加密方法天書就是移位法天書就是移位法的一種。早在的一種。早在40004000多年前，古希臘人就用一種名叫多年前，古希臘人就用一種名叫“天天書書”的器械來(lái)加密消息。該密碼器械是用一條窄長(zhǎng)的草的器械來(lái)加密消息。該密碼器械是用一條窄長(zhǎng)的草紙纏繞在一個(gè)直徑確定的圓筒上，明文逐行橫寫在紙帶紙纏繞在一個(gè)直徑確定的圓筒上，明文逐行橫寫在紙帶上，當(dāng)取下紙帶時(shí)，字母的次序就被打亂了，消息得以上，當(dāng)取下紙帶時(shí)，字母的次序就被打亂了，消息得以隱蔽。收方閱讀消息時(shí)，要將紙帶重新繞在直徑與

55、原來(lái)隱蔽。收方閱讀消息時(shí)，要將紙帶重新繞在直徑與原來(lái)相同的圓筒上，才能看到正確的消息，在這里圓筒的直相同的圓筒上，才能看到正確的消息，在這里圓筒的直徑起到了密鑰的作用。徑起到了密鑰的作用。2022-7-2MCM43 另一種移位法采用將字母表中的字母平移若干位的另一種移位法采用將字母表中的字母平移若干位的方法來(lái)構(gòu)造密文字母表，傳說(shuō)這類方法是由古羅馬皇帝方法來(lái)構(gòu)造密文字母表，傳說(shuō)這類方法是由古羅馬皇帝凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。凱撒最早使用的，故這種密文字母表被稱為凱撒字母表。例如，如用將字母表向右平移例如，如用將字母表向右平移3 3位的方法來(lái)構(gòu)造密文字母位的方法來(lái)構(gòu)造密文字

56、母表，可得：表，可得： 明文字母表：明文字母表： ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ 密文字母表：密文字母表： DEFGHIJKLMNOPQRTSUVWXYZABCDEFGHIJKLMNOPQRTSUVWXYZABC 使用這一密文字母表加密，使用這一密文字母表加密，THANK YOU THANK YOU 被加密成被加密成 WKDQN BRXWKDQN BRX，起到了一定的保密作用。，起到了一定的保密作用。 以上兩種移位極易被人破譯，為打破字母表中原有的以上兩種移位極易被人破譯，為打破字母表中原有的順序還可采用所謂路線加密法，

57、即把明文字母表按某種順序還可采用所謂路線加密法，即把明文字母表按某種既定的順序安排在一矩陣中，然后用另一種順序選出矩既定的順序安排在一矩陣中，然后用另一種順序選出矩陣中的字母來(lái)產(chǎn)生密文表。陣中的字母來(lái)產(chǎn)生密文表。2022-7-2MCM44例如，對(duì)明文：例如，對(duì)明文：THE HISTORY OF ZJU IS MORE THAN ONE THE HISTORY OF ZJU IS MORE THAN ONE HUNDRED YEARS.HUNDRED YEARS.以以7 7列矩陣表示如下：列矩陣表示如下：THEHISTTHEHISTORYOFZJORYOFZJUISMOREUISMORETHAN

58、ONETHANONEHUNDREDHUNDREDYEARSYEARS再按事先約定的方式選出密文。例如，如按列選出，得到再按事先約定的方式選出密文。例如，如按列選出，得到密文：密文： touthyhrihueeysanahomndrifoorsszrnetjeedtouthyhrihueeysanahomndrifoorsszrnetjeed2022-7-2MCM45 使用不同的順序進(jìn)行編寫和選擇，可以得到各種不使用不同的順序進(jìn)行編寫和選擇，可以得到各種不同的路線加密體制。對(duì)于同一明文消息矩陣，采用不同同的路線加密體制。對(duì)于同一明文消息矩陣，采用不同的抄寫，得到的密文也是不同的。如果對(duì)上例明文消

59、息的抄寫，得到的密文也是不同的。如果對(duì)上例明文消息矩陣從左上角開始沿對(duì)角線抄寫，得到的密文是：矩陣從左上角開始沿對(duì)角線抄寫，得到的密文是： tohuretiyhhhsoiyuamfsennoztadorjrrneseedtohuretiyhhhsoiyuamfsennoztadorjrrneseed 在使用上述方法時(shí)矩陣的規(guī)模必須事先約定，它在使用上述方法時(shí)矩陣的規(guī)模必須事先約定，它增加了對(duì)明文的保護(hù)程度。當(dāng)明文超過(guò)規(guī)定矩陣的大小增加了對(duì)明文的保護(hù)程度。當(dāng)明文超過(guò)規(guī)定矩陣的大小時(shí)，可以另加一矩陣。當(dāng)需要加密的字母數(shù)小于矩陣大時(shí)，可以另加一矩陣。當(dāng)需要加密的字母數(shù)小于矩陣大小時(shí)，可以在矩陣中留空

60、位或以無(wú)用的字母來(lái)填滿矩陣。小時(shí)，可以在矩陣中留空位或以無(wú)用的字母來(lái)填滿矩陣。 移位法也可和代替法結(jié)合使用，并使用約定的單詞移位法也可和代替法結(jié)合使用，并使用約定的單詞或短語(yǔ)作密鑰，以進(jìn)一步加強(qiáng)保密性，這就是鑰控列序或短語(yǔ)作密鑰，以進(jìn)一步加強(qiáng)保密性，這就是鑰控列序加密法。加密法。 2022-7-2MCM46例如，用密鑰字例如，用密鑰字 constructconstruct對(duì)明文對(duì)明文MATHEMATICAL MATHEMATICAL MODELING IS USEFULMODELING IS USEFUL加密：加密：1 4 36 75 9 2 81 4 36 75 9 2 8CONSTRUCT