[算法]NIM游戏及其相应变形的分析

Iambitious · 发表于 2006-8-7 16:09:21

費氏數列是指無窮數列 1,2,3,5,8,13,21,… 而言，它的一般表示式是 f0=1，f1=2， fn+2=fn+1+fn 真正把它計算出來是

計算的過程和我們要討論的沒有太大關係，茲從略。有一點可以注意的是，{fn} 幾乎成一等比級數。因為

,

，其絕對值小於 1，當 n 很大時，

變得很小，幾乎可以省略不計。也就是說

，幾乎是等比級數型式增加。
費氏級數最有趣的特性是，自然界許多生長的過程或多或少和它有點關聯。可參考《數學漫談》第四章（下）。

通常我們所熟悉的阿拉伯數字表示自然數的方法是利用 0,1,2,3,4,5,6,7,8,9 十個數字為基礎，借「位」的觀念，和「逢十進一」的方法組織而成。這就是十進位法。舉例來說， 345=3 x 102+4 x 101+5。仿照這個道理，有各種進位法，例如電腦所熟悉的二進位法，僅有 0 和 1 兩種基本數字，10110表示 1 x 24 + 0 x 23 + 1 x 22 + 1 x 21 + 0 = 16+4+2 = 22。八進位法，則僅有 0,1,2,3,4,5,6,7 八個數字。

標準的進位法中，各位都是滿一個固定數就進位。例如：十進位法是滿十進一，即個位數滿十進一到十位數，十位數滿十進一到百位數，百位數滿十進一到千位數，……等。

考慮一個自然數的無窮數列 B0,B1,B2,… 其中 B0=1，其餘各 Bn 均大於 1。我們可以採取一種名為 B 進位法的記數法則：由右邊算起，第一位滿 B1 進一到第二位，第二位滿 B2，進一到第三位，……，第 n 位滿 Bn，進一到第 n+1位。

任何一個自然數 x 可以有唯一的 B 進位表示法

，其中

。則

Iambitious · 发表于 2006-8-7 16:10:43

標準十進位法是取 Bi=10, i=1,2,…。各種 k 進位法是指 Bi=k, i=1,2,…而言。

[例6] Bn=n+1，求347的 B 進位表示法。

所以 347 = 2 x (2 x 3 x 4 x 5) + 4 x (2 x 3 x 4) + 1 x (2 x 3) + 2 x 2+1=24121B

假設 Pn=B0 B1 … Bn 則

成為一個以 1 為起點的嚴格遞增無窮自然數列。自然數 N 的 B 進位表示法

如果我們一開始就取一個以 1 為起點的嚴格遞增無窮自然數列

，對於任何自然數 N 表示成

,

有無困難？答案是有的。在 B 進位表示法中，每一個自然數恰有唯一的一種表示法；但是在這種新的表示法中，不一定每個自然數均只有一種表示法。

[例6.1] 數列

定義為 Pn=2n+1, 則

有趣的是，自然數的 P 數列表示法一定有解。
[定理2]

是一個以 1 為起點的嚴格遞增無窮自然數列，則每一自然數 N 至少可以表示成一種 P 數列表示法

[證] 利用數學歸納法證明：N<

n 時 N 有 P 數列表示法

。

Iambitious · 发表于 2006-8-7 16:11:30

n=1 時，N=l0，其中 l0(P)=N。若 n=k 時本定理成立，則 n=k+1 時，利用除法公式，可以找到 lk 及 r 使得

由歸納法假設

而且

。故

將上面這種理論用到費氏數列 {fn} 因為

，所以費氏表示法中的各個「位數」只能是 0 或 1。費氏數列表示法不具有唯一性。

[例7] 化60為費氏數列表示法。

n 0 1 2 3 4 5 6 7 8
fn 1 2 3 5 8 13 21 34 55

因為 fn+2=fn+1+fn，費氏數列表示法中有一種有趣的「進位法」：第 n 位和第 n+1 位都是 1 時，可以進位到第 n+2 位。如上例 10110110(f) 的第 5 和第 6 位都是 1，故可以進位到第 7 位，將原數化成 11000110(f)；同理，可將 11000110(f) 的第 2 和第 3 位進位到第 4 位，成為 11001000(f)。利用這個性質，在一數的某一費氏數列表示法中，如果有相鄰的兩位均是 1，則可以進位到左邊一位，化成另一個不同的表示法，繼續化簡，到最後，可以得到一種表示法，其中 li 各數目，相鄰兩個不同時為 1（否則，再進位即可），每一個數都有一種唯一的如此表示法，稱之為標準表示法。

另一有趣的性質是：如果 lnln-1 … l1l0(f) 中各位數字 0 和 1 相間出現，例如 101010(f) 或 10101(f) 則

Iambitious · 发表于 2006-8-7 16:16:03

現在回到第(二)節的數列 {an} 和 {bn}。一個相當有趣的事實是，如果將威氏遊戲的各組安全殘局 {an,bn} 用費氏數列標準表示法表示出來，如下表：

仔細觀察，各個 bn 恰好是 an 後面加一個 0，每個 an 最右邊有偶數個連續的 0（包括沒有 0），當然 bn 最右邊有奇數個連續的 0。有了這個結果，我們要檢查一組 {x,y}（其中 x <= y）是否安全殘局，就可以將 x 和 y 表成費氏數列標準表示法，再看看是否合於上述的條件即可。這中間的優點是，我們不必再計算所有

的安全殘局 {an,bn}，以決定 {x,y} 是否安全。更重要的是，我們將有一種簡便的方法，可以將不安全殘局 {x,y} 適當的取成某一安全殘局 {an,bn}。

當然，數論上的一些結果告訴我們

,

,（[x] 表示小於或等於 x 的最大整數，例如 [2.99]=[2.0]=[2]=2）由定理1，我們幾乎要求出 2x/(sqrt5-1) 組 {an,bn} 才能順利的判定安全殘局，以及由不安全殘局拿成安全殘局的方法。當 x 大的時候，這麼多的資料處理起來必然不方便。

上述 {an,bn} 的性質，只是依觀察而得，現在我們要證明其真實性。我們所以要這樣做，不光是因為數學上的嚴密性，在證明的過程中，用到的一些計算，將很有用處。

首先將自然數分成 A 和 B 兩部份，A 是所有費氏標準表示法中右邊有偶數個連續 0 的自然數的集合，B 則是所有費氏漂準表示法中右邊有奇數個連續 0 的自然數的集合。將 A 中之數由小而大排成一數列

設 bn' 是 an' 費氏標準表示法右邊再加一個 0 者。我們將證明

且合於第(二)節的(甲)(乙)條件。所以，事實上就是

因此證明了上述的性質。(乙)易於知道成立。因為

和

都是嚴格增加數列，為了證明(甲)，我們只要證明 bn'=an'+n 就可以，茲分下面兩步驟，證明之。

(第一) bn'-an'，隨 n 增加而增加。也就是，當 n>m 時， bn'-an'>bm'-am'。

[證] 假設

DoDo · 发表于 2006-8-7 16:16:45

感谢楼主!
小学时不知从哪里搞到过一本书, 专门讲小游戏中的数学原理的, 当时看得特别入迷, 可惜现在找不到了

Iambitious · 发表于 2006-8-7 16:18:56

上面均是標準表示法，但左邊有的填 0（即 lr 或

可能為 0... 等）以便對齊。 n>m 表示 an'>am'，也就是有一個 s<r 使得

對每一個 i>s 成立，

。因為

可見

bn'-an'>bm'-am'

(第二) 對於任一自然數 x，有一組 {an',bn'} 使得 bn'=an'+x。

[證]當 x 的費氏標準表示法右邊有奇數個連續的 0 時，取 an'=x0(f), bn'=x00(f) 即可以。

當 x 的費氏標準表示法右邊有偶數個連續的 0 時，即

取

利用

可見 bn'=an'+x 成立。

(第一)和(第二)證明了bn'=an'+n的確成立。

上面的證明不但說明了 {an,bn} 具有所述的性質，即是 an 為第 n 個費氏標準表示法之最右邊有偶數個連續 0 的自然數，bn 是第 n 個費氏標準表示法之最右邊有奇數個連續 0 的自然數，尤有進者，bn 的表示法等於 an 表示法右邊再加一個 0 而已。

而且由(第二)可以知道，對於任何一個自然數 x，不必用歸納法從 a1,b1,a2,b2,… 算起，一直求至 ax,bx。直接就可以算出 ax 和 bx 來。所以在利用定理1 的時候，我們就可以不必記憶一大堆 {an,bn} 值了。

Iambitious · 发表于 2006-8-7 16:30:36

在所有拈的變型遊戲中，單堆遊戲似乎是比較簡單的。最常見而為大眾熟悉的玩法是這樣的：「兩人輪流取一堆石頭，每人每次最少取 1 個，最多取 k 個，最後取光石頭的人贏得此遊戲。」請問有何致勝之道？

和前面一樣，所有的情況，可以分為安全和不安全兩種。在這裏 k+1 這個數扮演著極重要的角色，因為每次某一人拿的石頭數 i，合於 1 <= i < k + 1，可見 1 <= k + 1 - i <= k，另一人總是可以取 k+1-i 個石頭，使這兩次所取的石頭共有 k+1 個，由是可見 k+1 是安全殘局，利用歸納法則 k+1 的倍數必為安全殘局。反之，不是 k+1 倍數的任一自然數 n=q(k+1)+r，其中 1 <= r <= k，一次拿 r 個石頭就能到達 q(k+1)，即某一安全殘局，可見此時為不安全殘局。

相反的規定：「最後取光石頭的人輸」，也可以分析知道，安全殘局是 q(k+1)+1 這種型態的數。

並不是所有單堆遊戲都是如此容易的，例如「奇偶遊戲」則是較複雜的一種。所謂「奇偶遊戲」只是將上述的問題略加修改，最後取光石頭時的輸贏的規定不同，即「兩人輪流取一堆石頭，每人每次最少取 1 個，最多取 k 個，到最後石頭被取光時，若手中所有石頭總數為奇數，則此人贏得此遊戲。（也可以規定石頭總數為偶數的人贏得此遊戲）。」顯而易見的是，原先這堆石頭的總數要是奇數才有意義。這個遊戲較前者更複雜，其安全殘局視k的奇偶和 k+1 或 k+2 的倍數有關係。

另一個和骰子有關的單堆遊戲由古先生 1 提出來，問題是這樣的：「有一堆石頭，數目不拘。首先任意擲一骰子，看出現幾點，就取去幾個石頭。然後兩人輪流翻轉骰子到前次骰子出現那一面的旁邊四面中任一面，但不可以翻到對面，也不可以不翻，翻到幾點，就取去幾個石頭，如此輪流玩到一方沒有辦法拿石頭，也就是說，剩下的石頭數比他翻到的數目還小的時候，則他就算輸了。」

首先耍瞭解的一點是，骰子上面六個數目安排的方法。從1到6的各個自然數在骰子上各出現一次， 1的對面是6，2的對面是5，3的對面是4。

這個遊戲和第一個單堆遊戲有點類似，卻不相同。如果骰子出現i的時候，輪到你，則從1到6中的各數有兩個，即是i和7-i，你不能翻到，其餘四個隨你高興愛翻那一個都可以。所以每次你能夠取的石頭數，依前次對方所翻到的數目而定，而對方翻的數又因你前次翻的而定，如此相互影響，就顯得很複雜了。仔細分析的結果，可以發現其安全殘局和8的倍數有密切關係。有興趣的讀者可以自已試試看。

如果把骰子加成兩個，然後規定每次翻兩個骰子，把翻到的兩個數字和算出來，取掉同樣數目的石頭，則又如何呢？如果還是有兩個骰子，但每次只任選其中一個將它翻到新數目，看這數目是多少，就取掉多少石頭，則又如何？或者，還是兩個骰子，每次只任意翻轉其中一個到新數目，但把這個新數目和另一個未翻的骰子相加，算出其和，取掉同樣數目的石頭，則又如何？當然，增加骰子的數目，則遊戲更複雜。

最後我們想仔細討論的一個單堆遊戲叫做「雙倍遊戲」。這個遊戲和骰子的單堆遊戲有一共同的特性：每次所拿石頭的個數受上次對方所拿石頭的個數影響。

問題是這樣的：「兩人輪流取石，每人每次至少取 1 個石頭，至多取上次對方所拿石頭數目的兩倍；最後拿光石頭的人贏得此遊戲。當然，第一個人不能第一次就取光所有石頭。」

[例8] 2 是安全殘局，因對方只能取 1。

[例9] 3 是安全殘局。因

[例10] 5 是安全殘局。因

如此繼續推演下去，一個很有意思的結論是，所有費氏級數的項 fn 均是安全殘局其餘都是不安全殘局。要證明這件事情可以分幾步完成，主要的概念還是在於自然數的費氏數列標準表示法。
(i) 如果 n >= 1，則 fn<fn+1<2fn。
[證明]因為 f1=2，f2=3，f3=5，所以 n=1,2, 時易知為對。

若 n<k 時定理成立，則

兩式相加

由歸納法得證。
ii) 如果你留下 x=fk1+fk2+ … +fkn-1+fkn 個石頭，其中

i = 1,2,...n-1，而且對方下次所能取走的石頭數目小於 fkn 則你留下的是一安全殘局。

[證明] 假設對方拿走

個石頭，其中

,

, i=1,2,…,m-1。

當

時，

則

所以你可以取走 y' 個石頭，使剩下 x'=fk1+fk2+ … +fkn-1 個石頭，而且

也就是對方下次所能取走的石頭數目小於 fkn+1 如此又可用歸納法繼續推演本定理。其次，如果 kn>2+kn+1 分解

其中 t 為 >= 3 為奇數，而且 kn-t=kn+1 或 1+kn+1。

所以你可以取走 y' 個石頭，使剩下

個石頭，而且

2y'<2fkn-t<fkn-t+fkn-t+1=fkn-t+2

也就是下次對方所能取走的石頭數目小於 fkn-t+2。同理可用歸納法。

Iambitious · 发表于 2006-8-7 16:32:18

(iii) 雙倍遊戲中的安全殘局是 fn, n=1,2,…。

[證明] x=fn 時就如(ii)所述，對方所取的石頭不超過

，所以你是留下安全殘局。

若一開始 x 不是 fn 型態，化為費氏標準式，

對方可以取去 fkm 剩下

；輪到你時不得取超過

，由(ii)可知他留下了他的安全殘局，所以一開始是你的不安全殘局。

Iambitious · 发表于 2006-8-7 16:32:58

有興趣嗎？讓我們隨便規定一個玩法：「一堆石頭有100個，兩人輪流取石，每次每人至少取一個，最多取上次對方取走石數的三倍。最後取光的贏得遊戲。當然，第一個拿的人不可以第一次就取光所有石頭。」

筆者不曉得其中有何規則。

來吧！你先？還是我先？東南亞電影外加牛肉麵一碗。

1.《數學漫談》，大衛．柏佳米尼及《時代生活》雜誌社編輯部著，傅溥譯著，美亞書局發行。
2. A.M. Yaglom and I.M. Yaglom,《Challenging Mathematical Problems with Elementary Solutions》, vol. 1 and 2, translated into English by James McCawley, Jr.
3. C.S. Cheng（鄭清水） and F.K. Huang（黃光明）,〈The Even-odd Game〉, 民國六十年六月份《學聲》（清華大學數學學會出版）, pp.7-10.

Iambitious · 发表于 2006-8-7 16:38:02

學歷
康乃爾大學運籌學博士 1978/09--1982/08

國立中央大學數學學士 1970/09--1974/06

專長暨研究領域
組合最優化    運籌學    演算理論    離散數學

經歷
國立臺灣大學數學系教授 2001/08--今

國立交通大學應用數學系教授 1988/02--2001/07
國立中央大學數學系副教授 1983/08--1988/01
國立交通大學副教務長 1998/09--2000/07
國立交通大學應用數學系系主任 1993/08--1995/07
國科會自然處數學學門計畫審議人 1994/01--1996/12
國科會自然處數學學門計畫審議人 1991/07--1992/06

Publication List (March 17, 2004)

(Papers with NSC numbers at end are results of projects supported by the National Science Council.)

      * J.-J. Pan and G. J. Chang, "Isometric path numbers of graphs," submitted. (NSC92-2115-M002-015) [#139] [arXiv:math.CO/0310332]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang, ``The weighted independent domination problem is NP-complete for chordal graphs," Disc. Appl. Math. (accepted).  (NSC91-2115-M002-011)
      * G. J. Chang, L.-D. Tong and H.-T. Wang, ``Geodetic spectra of graphs," European J. Combin. (accepted).  (NSC90-2115-M002-024) [#123] [pdf file]
      * Y.-L. Lai and G. J. Chang (2004), ``On the profile of the corona of two graphs," Inform. Process. Letters 89, 287-292.  (NSC92-2115-M002-015)  [#122]  [pdf file]
      * M. J. Chen,  G. J. Chang and D. B. West (2004), ``Interval numbers of powers of block graphs," Disc. Math. 275, 87-96. (NSC85-2121-M009-037)  [#76]  [pdf file]
      * C. Y. Chen, Y. P. Wang and G. J. Chang, ``Vertex and tree arboricities of graphs,'' J. Combin. Optimization (accepted).  (NSC89-2115-M009-037)  [#71]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and C. Lu (2003), ``Distance-two labelings of graphs,'' European J. Combin. 24, 53-58. (NSC89-2115-M009-037)  [#126]  [pdf file]
      * C.-S. Liao and G. J. Chang, ``k-Domination in graphs,"  Inform. Process. Letters. (NSC89-2115-M009-037) [#121]  [pdf file]
      * G. J. Chang and S.-C. Liaw (2003), ``The L(2,1)-labeling problem on ditrees,'' Ars Combin. 66, 23-31. (NSC89-2115-M009-037 and Lee Center)  [#118]
      * H. G. Yeh and G. J. Chang (2003), ``Centers and medians of distance-hereditary graphs,'' Disc. Math. 265, 310. (NSC87-2115-M009-007) [#98]  [pdf file]
      * -----------------------------------------------------------------------------------------------------------------------
      * C.-S. Liao and G. J. Chang (2002), ``Algorithmic aspect of k-domination in graphs," Taiwanese J. Math. 6, 415-420. (NSC89-2115-M009-037 and Lee Center)  [#120]  [pdf file]
      * G. J. Chang (2002), ``Corrigendum for `The path-partition problem in block graphs','' Inform. Process. Letters 83, 293. (NSC89-2115-M009-037)  [#117] [pdf file]
      * S. T. Juan and G. J. Chang (2002), ``Group testing in bipartite graphs,'' Taiwanese J. Math. 6, 67-73. (NSC89-2115-M009-007)  [#115]  [pdf file]
      * G. J. Chang, L. D. Tong, J. H. Yan, and H. G. Yeh, ``A note on Gallai-Roy-Vitaver Theorem,'' Disc. Math. (accepted). (NSC88-2115-M009-009) [#111] [pdf file]
      * G. J. Chang, S. C. Liaw and H. G. Yeh (2002), ``k-Subdomination in graphs,'' Disc. Math. 120, 55-60. (NSC88-2115-M009-009 and Lee Center)  [#110] [pdf file]
      * M. J. Chen and G. J. Chang (2002), ``Total interval numbers of complete r-partite graphs," Disc. Appl. Math. 122, 83-92. (NSC88-2115-M009-009 and Lee Center)  [#106] [pdf] file]
      * M. J. Jou and G. J. Chang (2002), ``Algorithmic aspects of counting independent sets,'' Ars Combinatoria 65, 265-277.  (NSC86-2115-M009-002)  [#91]
      * M. S. Chang, S. C. Wu, G. J. Chang, and H. G. Yeh (2002), ``Domination on distance-hereditary graphs,'' Disc. Applied Math. 116, 103-113. (NSC85-2121-M009-024)  [#69] [pdf file]
      * -----------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (2001), ``A survey on circular chromatic numbers of graphs,'' AMS/IP Studies in Advanced Math. 20, 497-502. (NSC88-2115-M009-009)  [#114]  [doc file]
      * Venkatesan Guruswami, C. Pandu Rangan, M. S. Chang, G. J. Chang and C. K. Wong (2001), ``The K_r-packing problem,'' Computing 66, 79-89. Conference version ``The vertex-disjoint triangle problem,'' Lecture Notes Comput. Sci. 1517 (1998), 26-37. (NSC88-2115-M009-009 and Lee Center)  [#113]
      * G. J. Chang, S. T. Juan, and D. D.-L. Liu (2001), ``No-hole 2-distance colorings for unit interval graphs,'' Ars Comb. 61, 233-144. (NSC88-2115-M009-009)  [#101]
      * M. J. Chen and G. J. Chang (2001), ``Families of graphs closed under taking power,'' Graph and Combinatorics 17, 207-212. (NSC87-2115-M009-007)  [#95]  [pdf file]
      * L. D. Tong, F. K. Hwang and G. J. Chang (2001), ``Channel graphs of bit permutation networks,'' Theore. Comput. Sci. 263, 139-143. (NSC86-2115-M009-002)  [#93]  [pdf file]
      * G. J. Chang, S. T. Juan and D. D.-F. Liu (2001), ``Minimum span of no-hole (r+1)-distance colorings,'' SIAM J. Discrete Math. 14, 370-380. (NSC87-2115-M009-007 and Lee Center)       [#83]  [pdf file]
      * H. G. Yeh and G. J. Chang (2001), ``Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs,'' Theorect. Comput. Sci.  263, 3-8. (NSC87-2121-M009-007) [#68]  [pdf file]
      * ------------------------------------------------------------------------------------------------------------------------
      * L. Huang and G. J. Chang (2000), ``Circular chromatic numbers of distance graphs with distance sets missing multiples,'' European J. Combinatorics 21, 241-248. (NSC87-2115-M009-007) [#104]  [pdf file]
      * G. J. Chang and X. Zhu (2000), ``Pseudo Hamiltonian-connected graphs,'' Disc. Applied Math. 100, 145-153. (NSC87-2115-M009-007)  [#103]  [pdf file]
      * G. J. Chang, B. L. Chen, K. C. Huang, and H. L. Fu (2000), ``Linear k-arboricities of trees,'' Disc. Appl. Math. 103, 281-287. (NSC87-2115-M009-007)  [#97]  [pdf file]
      * G. J. Chang, W. T. Ke, D. Kuo, D. D.-F. Liu, and R. K. Yeh (2000), ``On L(d,1)-labelings of graphs,'' Disc. Math. 220, 57-66. (NSC87-2115-M009-007)  [#96]  [pdf file]
      * M. J. Jou and G. J. Chang (2000), ``The number of maximum independent sets in graphs,'' Taiwanese J. Math. 4, 685-695. (NSC86-2115-M009-002)  [#94]  [pdf file]
      * S. C. Liaw, D. Kuo, and G. J. Chang (2000), ``Integral sum numbers of graphs,'' Ars Combinatoria 54, 259-268. (NSC84-2121-M009-023)  [#61]
      * G. J. Chang, L. Cui and F. K. Hwang (2000), Reliabilities of Consecutive-k Systems, Kluwer Academic Publishers, Netherlands.  [B1]
      * ------------------------------------------------------------------------------------------------------------------------
      * G. J. Chang, L. Cui and F. Hwang (1999), ``New comparisons in Birnhaum importance for the consecutive-k-out-of-n systems,'' Prob. Eng. Inform. Sci. 13, 187-192. ``Corrigenda'' in the same journal 14 (2000), 405. (NSC87-2115-M009-001)  [#108] [pdf file]
      * G. J. Chang, L. Cui and F. Hwang (1999), ``Reliabilities for (n,f,k) systems,'' Stat. Prob. Letters 43, 237-242. (NSC87-2115-M009-001)  [#107]  [pdf file]
      * X. Lu, D. W. Wang, G. J. Chang, I. J. Lin, and C. K. Wong (1999), ``On k-ary spanning trees of tournaments,'' J. Graph Theory 30, 167-176. (NSC87-2115-M009-007)  [#102]  [pdf file]
      * L. Huang and G. J. Chang (1999), ``The circular chromatic number of the Myceilkian of G^d_k,''J. Graph Theory 32, 63-71. (NSC87-2115-M009-007)  [#100]  [pdf file]
      * Y. S. Lee and G. J. Chang (1999), ``Bipartite Steinhaus graphs,'' Taiwanese J. Math. 3, 303-310. (NSC83-0208-M009-050)  [#99]  [pdf file]
      * S. C. Liaw and G. J. Chang (1999), ``Rabin numbers of butterfly networks,'' Disc. Math. 196, 219-227. (NSC86-2115-M009-002)  [#90]  [pdf file]
      * G. J. Chang (1999), ``Algorithmic aspects of linear k-arboricity,'' Taiwanese J. Math. 3, 73-81. (NSC86-2115-M009-002)  [#89]  [pdf file]
      * G. J. Chang, F. K. Hwang, and L. D. Tong (1999), ``Characterizing bit permutation networks,'' Networks 33, 261-267. (NSC86-2115-M009-002)  [#88] [pdf file]
      * S. C. Liaw and G. J. Chang (1999), ``Wide diameters of butterfly networks,'' Taiwanese J. Math. 3, 83-88. (NSC86-2115-M009-002)  [#87]  [pdf file]
      * G. J. Chang, F. K. Hwang, and L. D. Tong (1999), ``The consecutive-4 digraphs are hamiltonian,'' J. Graph Theory 31, 1-6. (NSC86-2115-M009-002)  [#85]  [pdf file]
      * G. J. Chang, D. D.-F. Liu, and X. Zhu (1999), ``Distance graphs and T-coloring,'' J. Comb. Theory, Series B 75, 259-269. (NSC86-2115-M009-002)  [#84]  [pdf file]
      * S. C. Liaw and G. J. Chang (1999), ``Generalized diameters and Rabin numbers of networks,'' J. Comb. Optimization 2, 371-384 . (NSC86-2115-M009-002)  [#82]
      * G. J. Chang, F. L. Chen, L. Huang, F. K. Hwang, S. T. Juan, U. G. Rothblum, I. F. Sun, J. W. Wang, and H. G. Yeh (1999), ``Sortability of partition properties,'' J. Comb. Optimization 2, 413-427 . (NSC86-2115-M009-002)  [#81]
      * G. J. Chang, L. L. Hung and X. D. Zhu (1999), ``Circular chromatic numbers of Myceilski's graphs,'' Disc. Math. 205, 23-37. (NSC85-2121-M009-024)  [#73]  [pdf file]
      * S. J. Hu, S. T. Juan, and G. J. Chang (1999), ``T-Colorings and T-edge spans of graphs,'' Graphs and Combinatorics 15, 295-301. (NSC85-2121-M009-024)  [#66]  [pdf file]
      * G. J. Chang and M. J. Jou (1999), ``The number of maximal independent sets in connected triangle-free graphs,'' Disc. Math. 197/198, 169-178. (NSC84-2121-M009-023)  [#65]  [pdf file]
      * H. Y. Lee and G. J. Chang (1999), ``Linear algorithms for finding w-median of graphs,'' JCMCC 31, 183-192. (NSC84-2121-M009-023)  [#58]
      * G. J. Chang, B. DasGupta, W. M. Dy\'a\v cek, M. F\"urer, M. Koerlin, Y.-S. Lee, T. Whaley (1999), ``Characterizations of bipartite Steinhaus graphs,'' Disc. Math. 199, 11-25. (NSC83-0208-M009-050)  [#56]  [pdf file]
      * G. J. Chang, F. K. Hwang, and Y. C. Yao (1999), ``Localizing combinatorial properties for partitions on block graphs,'' J. Comb. Optimization 2, 429-441. (NSC82-0208-M009-050)  [#48]
      * ----------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1998), ``Algorithmic aspects of domination in graphs,'' in Handbook of Combinatorial Optimization (D.-Z. Du and P. M. Pardalos eds.), Vol. 3, 339-405. (NSC87-2115-M009-007)    [#109]
      * G. J. Chang, L. L. Huang, and X. D. Zhu (1998), ``Circular chromatic numbers and fractional chromatic numbers of distance graphs,'' European J. Combinatorics 19, 423-431. (NSC86-2115-M009-002)  [#86]  [pdf file]
      * S. C. Liaw, H. G. Yeh, F. K. Hwang, and G. J. Chang (1998), ``A simple and direct derivation for the number of noncrossing partitions,'' Proc. AMS 126, 1579-1581. (NSC86-2115-M009-002) [#80]  [pdf file]
      * H. G. Yeh, S. C. Liaw, F. K. Hwang, and G. J. Chang (1998), ``Enumerating partitions with given part-sizes,'' Bull. Inst. Math., Academia Sinica 26, 33-38. (NSC86-2115-M009-002)  [#79]
      * S. C. Liaw, G. J. Chang, F. Cao, and D. F. Hsu (1998), ``Fault-tolerant routing in circulant networks and cycle prefix networks,'' Annals of Combin. 2, 165-172. (NSC86-2115-M009-002)  [#78]
      * H. G. Yeh and G. J. Chang (1998), ``The path-partition problem in bipartite distance-hereditary graphs,'' Taiwanese J. Math. 2, 353-360. (NSC84-2121-M009-023)  [#62]  [pdf file]
      * H. G. Yeh and G. J. Chang (1998), ``Weighted connected domination and Steiner trees in distance-hereditary graphs,'' Disc. Applied Math. 87, 245-253; extended abstract in Lecture Note in Computer Science 1120 (1996) 48-52. (NSC84-2121-M009-023)  [#59]
      * F. K. Hwang and G. J. Chang (1998), ``Enumerating consecutive and nested partitions for graphs,'' European J. Combin. 19, 63-70. (NSC82-0208-M009-050)  [#45]  [pdf file]
      * G. J. Chang and P. H. Ho (1998), ``The β-assignment problems,'' European J. Oper. Research 104, 593-600. (NSC77-0208-M009-21)  [#36]
      * G. J. Chang and F. H. Hao (1998), ``The ratio of degree sums on graph decompositions,'' Bull. Inst. Math. Academia Sinica 26, 247-255.  [#35]
      * S. F. Hwang and G. J. Chang (1998), ``k-Neighborhood-covering and -independence problems for chordal graphs,'' SIAM J. Disc. Math. 11, 633-643. (NSC81-0208-M009-26)  [#32]  [pdf file]
      * -----------------------------------------------------------------------------------------------------------------------
      * H. G. Yeh and G. J. Chang (1997), ``Algorithmic aspects of majority domination,'' Taiwanese J. Math. 1, 343-350. (NSC85-2121-M009-024)  [#77]  [pdf file]
      * G. J. Chang, F. K. Hwang, and L. D. Tong (1997), ``The Hamiltonian properties of consecutive-3 digraphs,'' Math. Computer Modeling 25, 83-88. (NSC86-2115-M009-002)  [#75]  [pdf file]
      * J. H. Yan, K. W. Lih, D. Kuo, and G. J. Chang (1997), ``Signed degree sequences of signed graphs,'' J. Graph Theory 26, 111-117. (NSC85-2121-M009-024)  [#70]  [pdf file]
      * C. Y. Chen, C. C. Chang, and G. J. Chang (1997), ``Proper interval graphs and the guard problem,'' Disc. Math. 170, 223-230. (NSC84-2121-M009-023)  [#67]
      * H. Y. Lee and G. J. Chang (1997), ``Medians of graphs and kings of tournaments,'' Taiwanese J. Math. 1, 103-110. (NSC84-2121-M009-023)  [#64]  [pdf file]
      * M. J. Jou and G. J. Chang (1997), ``Maximal independent sets in graphs with at most one cycle,'' Disc. Appl. Math. 79, 67-73. (NSC84-2121-M009-023)  [#63]  [pdf file]
      * Y. J. Tsay and G. J. Chang (1997), ``The exact gossiping problem,'' Disc. Math. 163, 165-172. (NSC84-2121-M009-023)  [#60]
      * J. H. Yan, G. J. Chang, S. M. Hedetniemi, and S. T. Hedetniemi (1997), ``k-Path partitions in trees,'' Disc. Appl. Math. 78, 227-233. (NSC84-2121-M008-023)  [#57]  [pdf file]
      * D. Kuo, G. J. Chang, and Y. H. H. Kwong (1997), ``Cordial labeling of m K_n,'' Disc. Math. 169, 121-131. (NSC83-0208-M009-050)  [#53]  [pdf file]
      * J. J. Chen, G. J. Chang, and K. C. Huang (1997), ``Integral distance graphs,'' J. Graph Theory 25, 287-294. (NSC83-0208-M009-050)  [#51]  [pdf file]
      * G. J. Chang and F. K. Hwang (1997), ``Optimality of consecutive and nested tree partitions," Networks 30, 75-80. (NSC82-0208-M009-050)  [#47]  [pdf file]
      * G. J. Chang and P. H. Ho (1997), ``The β-assignment problem in general graphs,'' Computers and Oper. Research 24, 757-765. (NSC77-0208-M009-21)  [#31]  [pdf file]
      * -------------------------------------------------------------------------------------------------------------------
      * M. J. Jou, G. J. Chang, C. Lin, and T. H. Ma (1996), ``A finiteness theorem for maximal independent sets,'' Graphs and Combinatorics 12, 321-326. (NSC83-0208-M009-050)  [#55]
      * G. J. Chang (1996), ``Corrigendum,'' J. Comb. Theory (Series A) 73, 190-192. (NSC83-0208-M009-050)  [#54]  [pdf file]
      * G. J. Chang and Y. J. Tsay (1996), ``The partial gossiping problem,'' Disc. Math. 148, 9-14. (NSC83-0208-M009-050)  [#50]
      * M. S. Chang, Y. H. Chen, G. J. Chang, and J. H. Yan (1996), ``Algorithmic aspects of the generalized clique-transversal problem on chordal graphs,'' Disc. Appl. Math. 66, 189-203. (NSC82-0208-M009-050)  [#49]
      * G. J. Chang and D. Kuo (1996), ``The L(2,1)-labeling problem on graphs,'' SIAM J. Disc. Math. 9, 309-316. (NSC82-0208-M009-050)  [#44]
      * J. H. Yan, J. J. Chen, and G. J. Chang (1996), ``Quasi-threshold graphs,'' Disc. Appl. Math. 69, 247-255. (NSC81-0208-M009-26)  [#42]
      * --------------------------------------------------------------------------------------------------------------------
      * M. J. Jou and G. J. Chang (1995), ``Survey on counting maximal independent sets,'' Proceedings of the Second Asian Mathematical Conference, S. Tangmance and E. Schulz eds., World Scientific, page 265-275. (NSC84-2121-M009-023)  [#92]
      * G. J. Chang, F. K. Hwang, P. E. Wright, and G. J. Griggs (1995), ``A unique arithmetic labeling of macrohexagons,'' J. Comb. Designs 3, 169-177. (NSC82-0208-M009-050)  [#46]
      * G. J. Chang, C. Pandu Rangan, and Satyan R. Coorg (1995), ``Weighted independent perfect domination on cocomparability graphs,'' Disc. Appl. Math. 63, 215-222. (NSC82-0208-M009-050)  [#43]
      * S. F. Hwang and G. J. Chang (1995) ``The edge domination problem,'' Discussiones Math.--Graph Theory 15, 51-57. (NSC79-0208-M009-31)  [#30]
      * --------------------------------------------------------------------------------------------------------------------
      * J. H. Yan and G. J. Chang (1994), ``The path-partition problem in block graphs,'' Inform. Proc. Letters 52, 317-322. (NSC83-0208-M009-050)  [#52]
      * H. Y. Lee and G. J. Chang (1994), ``The w-median of a connected strongly chordal graph,'' J. Graph Theory 18, 673-680. (NSC81-0208-M009-26)  [#41]
      * G. J. Chang (1994), ``The domatic number problem,'' Disc. Math. 125, 115-122. (NSC80-0208-M009-26)  [#40]
      * S. F. Hwang and G. J. Chang (1994), ``Edge domatic numbers of complete n-partite graphs,'' Graphs and Combinatorics 10, 241-248. (NSC79-0208-M009-31)  [#39]
      * D. Kuo and G. J. Chang (1994), ``The profile minimization problem,'' SIAM J. Comput. 23, 71-81. (NSC79-0208-M009-31)  [#37]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1993), ``Strong sum graphs,'' Bulletin of ICA 7, 47-52. (NSC79-0208-M009-26)    [#33]
      * G. J. Chang, M. Farber, and Z. Tuza (1993), ``Algorithmic aspects of neighborhood numbers,'' SIAM J. Disc. Math. 6, 24-29. (NSC79-0208-M009-31)  [#29]
      * ---------------------------------------------------------------------------------------------------------------------
      * H. Y. Lee, H. M. Lee, and G. J. Chang (1992), ``Cordial labelings of graphs,'' Chinese J. Math.20, 263-273. (NSC79-0208-M009-04)  [#34]
      * H. M. Lee and G. J. Chang (1992), ``Set to set broadcasting in communication networks,'' Disc. Appl. Math. 40, 411-421.  [#28]
      * ---------------------------------------------------------------------------------------------------------------------
      * C. Chang and G. J. Chang (1991), ``An existence theorem for abstract stable sets,'' J. Austrail. Math. Soc. (Series A) 51, 468-472.  [#27]
      * G. J. Chang (1991), ``Centers of chordal graphs,'' Graphs and Combinatorics 7, 305-313. (NSC77-0208-M008-05)  [#26]
      * S. F. Hwang and G. J. Chang (1991), ``The k-neighbor domination problem in block graphs,'' European J. Oper. Research 52, 373-377. (NSC77-0208-M009-21)  [#25]
      * ---------------------------------------------------------------------------------------------------------------------
      * T. L. Lu, P. H. Ho, and G. J. Chang (1990), ``The domatic number problem in interval graphs,'' SIAM J. Disc. Math. 3, 531-536. (NSC77-0208-M009-21)  [#24]
      * F. C. Lai and G. J. Chang (1990), ``An upper bound for the transversal numbers of 4-uniform hypergraphs,'' J. Comb. Theory (Series B) 50, 129-133. (NSC77-0208-M008-05)  [#23]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1989), ``Total domination in block graphs,'' Operations Research Letters 8, 53-57.    [#22]
      * G. J. Chang (1989), ``On the number of SDR of a (t,n)-family,'' European J. Combinatorics 10, 231-234. (NSC74-0201-M008d-02)  [#21]
      * G. J. Chang (1988/89), ``Labeling algorithms for domination problems in sun-free chordal graphs,'' Disc. Appl. Math. 22, 21-34.  [#20]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1988), ``The k-path and the k-covering problems,'' Ars Combinatoria 25A, 11-20.    [#19]
      * G. J. Chang (1988), ``Bases theorems of general matroids,'' Tamkang J. Math. 19, 59-63.  [#18]
      * G. J. Chang and F. K. Hwang (1988), ``Optimal consecutive-k-out-of-n system under fixed budges,'' Prob. in Eng. and Inform. Sci. 2, 63-73.  [#17]
      * ---------------------------------------------------------------------------------------------------------------------
      * Y. C. Lin and G. J. Chang (1987), ``On the abstraction of linear duality,'' Chinese J. Math. 15, 207-213. (NSC74-0201-M008d-02)  [#16]
      * G. J. Chang and F. H. Hao (1987), ``The minimum of the antichains in the factor poset,'' Order 3, 355-357. (NSC74-0201-M008d-02)  [#15]
      * --------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1986), ``Existence and non-existence of association schemes,'' Bull. Inst. Math., Academia Sinica 14, 257-270. (NSC73-0208-M008-08)  [#14]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and J. Edmonds (1985), ``The poset scheduling problem,'' Order 2, 113-118. (NSC73-0208-M008-08)  [#13]
      * G. J. Chang and G. L. Nemhauser (1985), ``Covering, packing and generalized perfection,'' SIAM J. Alg. Disc. Meth. 6, 109-132. [#12]
      * G. J. Chang and F. K. Hwang (1985), ``Diagonal and pandiagonal tournament Latin squares,'' European J. Combinatorics 6, 149-155.  [#11]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and G. L. Nemhauser (1984), ``The k-domination and k-stability problems on sun-free chordal graphs,'' SIAM J. Alg. Disc. Meth. 5, 332-345.  [#10]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1983), ``Binary triangles,'' Bull. Inst. Math., Academia Sinica 11, 209-225.  [#9]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and G. L. Nemhauser (1982), ``R-Domination on block graphs,'' Operations Research Letters 1, 214-218.  [#8]
      * G. J. Chang, F. K. Hwang, and S. Lin (1982), ``Group testing with two defectives,'' Disc. Appl. Math. 4, 97-102.  [#7]
      * ---------------------------------------------------------------------------------------------------------------------
      * G. J. Chang, D. F. Hsu, and D. G. Rogers (1981), ``Additive variations on a graceful theme: some results on harmonious and other related graphs,'' Congressus Numerantium 32, 181-197.  [#6]
      * G. J. Chang and F. K. Hwang (1981), ``A group testing problem on two disjoint sets," SIAM J. Alg. Disc. Meth. 2, 35-38.  [#5]
      * -----------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and F. K. Hwang (1980), ``A group testing problem,'' SIAM J. Alg. Disc. Meth. 1, 21-24.  [#4]
      * -----------------------------------------------------------------------------------------------------------------------
      * G. J. Chang (1978), ``Complete diagonal of Latin squares,'' Canad. Math. Bull. 22, 477-481.  [#3]
      * -----------------------------------------------------------------------------------------------------------------------
      * G. J. Chang and K. W. Lih (1977), ``Polynomial representation of primes,'' Tamkang J. Math. 8, 197-198.  [#2]
      * G. J. Chang, M. C. Hu, K. W. Lih, and T. C. Sheih (1977), ``Exact difference triangles,'' Bull. Inst. Math., Academia Sinica 5, 191-197.  [#1]

		自动登录	找回密码
密码			注册

[算法]NIM游戏及其相应变形的分析

(三)費氏數列及進位法

(四)威氏遊戲的致勝方法

(五)單堆遊戲

(六)結語

作者张镇华简介