Background

In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign letters to digits as shown in the following picture:

	1 ij	2 abc	3 def
4 gh	5 kl	6 mn
7 prs	8 tuv	9 wxy
0 oqz

Problem

Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.

Input

Input contains a series of tests. The first line of each test contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. The last line of input file contains call number -1.

Output

Each line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text "No solution.". If there are more solutions having the minimum number of words, you can choose any single one of them.

Sample

7325189087
            5
            it
            your
            reality
            real
            our
            4294967296
            5
            it
            your
            reality
            real
            our
            -1
            

reality our
            No solution.
            

在計算機圖形運算中，常常要將浮點數(shù)轉(zhuǎn)換為整數(shù)，例如在圖像的光柵化階段，就要執(zhí)行大量的類型轉(zhuǎn)換，以便將浮點數(shù)表示的坐標轉(zhuǎn)化為整數(shù)表示的屏幕坐標。Ok，it's so easy：
----------------------------------------------------------------------------------------
//
// 強制類型轉(zhuǎn)換
// 小數(shù)部分將被裁剪掉
//
int_val = (int)float_val;
----------------------------------------------------------------------------------------
嘿嘿，很高興你居然和我一樣單純！這個操作實在是太TINY了，以至于我從來沒想過它是怎么實現(xiàn)的，直到某天某個家伙跟我說，不要使用標準C類型轉(zhuǎn)換，因為那太慢了！我當時的震驚不下于倒霉的冒險者遇上了龍。

標準C類型轉(zhuǎn)換最大的優(yōu)點是，它是獨立于平臺的，無論是在X86上跑，還是在PowerPC上跑，你什么都不用擔心，編譯器會為你搞定一切。而這也恰恰是它最大的缺點——嚴重依賴于編譯器的實現(xiàn)。而實際測試表明，編譯器所生成的代碼，其速度實在不盡人意。

一個替代的方法是直接對數(shù)據(jù)位進行操作。如果你對IEEE浮點數(shù)的表示法比較熟悉的話（如果你壓根什么都不知道，請先查閱文末附錄中的資料），這是顯而易見的。它提取指數(shù)和尾數(shù)，然后對尾數(shù)執(zhí)行移位操作。代碼如下：
----------------------------------------------------------------------------------------
//
// 將32位浮點數(shù)fval轉(zhuǎn)換為32位整數(shù)并存儲在ival中
// 小數(shù)部分將被裁剪掉
//
void TruncToInt32 (int &ival, float fval)
{
ival = *(int *)&fval;

// 提取尾數(shù)
// 注意實際的尾數(shù)前面還有一個被省略掉的1
int mantissa = (ival & 0x07fffff) | 0x800000;

// 提取指數(shù)
// 以23分界，指數(shù)大于23則左移，否則右移
// 由于指數(shù)用偏移表示，所以23+127=150
int exponent = 150 - ((ival >> 23) & 0xff);

if (exponent < 0)
ival = (mantissa << -exponent);
else
ival = (mantissa >> exponent);

// 如果小于0，則將結(jié)果取反
if ((*(int *)&fval) & 0x80000000)
ival = -ival;
}
----------------------------------------------------------------------------------------
該函數(shù)有一個BUG，那就是當fval=0時，返回值是2。原因是對于語句mantissa>>exponent，編譯器使用了循環(huán)移位指令。解決方法是要么對0作特殊處理，要么直接用匯編來實現(xiàn)。

這個函數(shù)比標準的C轉(zhuǎn)換要快，而且由于整個過程只使用了整數(shù)運算，可以和FPU并行運行。但缺點是，(1)依賴于硬件平臺。例如根據(jù)小尾和大尾順序的不同，要相應(yīng)地修改函數(shù)。(2)對于float和double要使用不同的實現(xiàn)，因為二者的數(shù)據(jù)位不同。(3)對于float，只能保留24位有效值，盡管int有32位。

更快的方法是使用FPU指令FISTP，它將棧中的浮點數(shù)彈出并保存為整數(shù)：
----------------------------------------------------------------------------------------
//
// 將64位浮點數(shù)fval轉(zhuǎn)換為32位整數(shù)并存儲在ival中
// 小數(shù)部分將四舍五入到偶數(shù)
//
inline void RoundToIntFPU (int &ival, double fval)
{
_asm
{
fld fval
mov edx, dword ptr [ival]
fistp dword ptr [edx]
}
}
----------------------------------------------------------------------------------------
很好，無論速度還是精度似乎都相當令人滿意。但如果換一個角度來看的話，fistp指令需要6個cycle，而浮點數(shù)乘法才僅僅需要3個cycle！更糟的是，當fistp運行的時候，它必須占用FPU，也就是說，其他的浮點運算將不能執(zhí)行。僅僅為了一次類型轉(zhuǎn)換操作就要付出如此大的代價，光想想就覺得心疼。

當然，它也有很多優(yōu)點：更快的速度，更精確的數(shù)值（四舍五入到偶數(shù)），更強的適用性（float和double均可)。要注意的是，F(xiàn)PU默認的四舍五入到偶數(shù)（round to even）和我們平常所說的四舍五入（round）是不同的。二者的區(qū)別在于對中間值的處理上。考慮十進制的3.5和4.5。四舍五入到偶數(shù)是使其趨向于鄰近的偶數(shù)，所以舍入的結(jié)果是3.5->4，4.5->4；而傳統(tǒng)的四舍五入則是3.5->4，4.5->5。四舍五入到偶數(shù)可以產(chǎn)生更精確，更穩(wěn)定的數(shù)值。

除此之外，還有更好，更快的方法嗎？有的，那就是華麗的 Magic Number ！

請看下面的函數(shù)：
----------------------------------------------------------------------------------------
//
// 將64位浮點數(shù)轉(zhuǎn)換為32位整數(shù)
// 小數(shù)部分將四舍五入到偶數(shù)
//
inline void RoundToInt64 (int &val, double dval)
{
static double magic = 6755399441055744.0;
dval += magic;
val = *(int*)&dval;
}
----------------------------------------------------------------------------------------
快，這就是它最偉大的地方！你所需要的僅僅是一次浮點數(shù)加法，你還能再奢望些什么呢？

當然，絕對不要使用莫名其妙的代碼，現(xiàn)在馬上就讓我們來看看它是怎么變的戲法。

首先，我們要搞清楚FPU是怎樣執(zhí)行浮點數(shù)加法的。考慮一下8.75加2^23。8.75的二進制表示是1000.11，轉(zhuǎn)化為IEEE標準浮點數(shù)格式是1.00011*2^3。假設(shè)二者均是32位的float，它們在內(nèi)存中的存儲為：
----------------------------------------------------------------------------------------
符號位(31), 指數(shù)(30-23), 尾數(shù)(22-0)

8.75: 0, 10000010, 0001 1000 0000 0000 0000 000

2^23: 0, 10010110，0000 0000 0000 0000 0000 000
----------------------------------------------------------------------------------------
FPU所執(zhí)行的操作是：(1)提升指數(shù)較小者的指數(shù)，使二者指數(shù)相同；(2)將二者的尾數(shù)相加；(3)將結(jié)果規(guī)整為標準格式。讓我們具體來看看整個過程：
----------------------------------------------------------------------------------------
1，提升8.75的指數(shù)，尾數(shù)要相應(yīng)地右移23-3=20位：

8.75 = 1.00011*2^3 = .0000000000000000000100011*2^23

2，將二者相加。必須注意的是，
   由于float只有23位尾數(shù)，所以8.75的低位被移除掉了：

8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 +
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 =
0, 10010110, 0000 0000 0000 0000 0001 000

3，將規(guī)整為標準格式：

別忘了2^23還有個前導1，所以結(jié)果是規(guī)整的，無需執(zhí)行任何操作
----------------------------------------------------------------------------------------
你發(fā)現(xiàn)什么了嗎？不錯，將結(jié)果的尾數(shù)部分提取出來，正是int(8.75)！是的，magic number的奧妙就在這里，通過迫使FPU將尾數(shù)移位，從而獲得我們需要的結(jié)果。

但是別高興得太早，讓我們來看看負數(shù)的情況。以-8.75為例，-8.75加2^23相當于2^23減去8.75，過程如下：
----------------------------------------------------------------------------------------
2^23: 0, 10010110，0000 0000 0000 0000 0000 000
 -
8.75: 0, 10010110, 0000 0000 0000 0000 0001 000
 =
0, 10010110, 1111 1111 1111 1111 1110 000
----------------------------------------------------------------------------------------
很好，尾數(shù)部分正是int(-8.75)=-8的補碼。然而，2^23的前導1在減法過程中被借位了，所以結(jié)果的尾數(shù)前面并沒有1，F(xiàn)PU將執(zhí)行規(guī)整操作，最后我們得到的是：
----------------------------------------------------------------------------------------
0, 10010110, 1111 1111 1111 1111 1100 000
----------------------------------------------------------------------------------------
功虧一簣！等等，如果將2^23的尾數(shù)的最高位置1，那么在減法過程中不就可以保全前導1了嗎？完全正確，這就是我們需要的。所以最后的magic number是0,10010110,1000 0000 0000 0000 0000 000，也就是1.5*2^23。

然而，我們要清楚這個方法的一些局限性。首先，在將結(jié)果的float值保存為整數(shù)時，我們需要使用某些mask值將22-31位屏蔽掉。其次，float只能保有最多23位的有效值，在將尾數(shù)最高位置1后，有效值更是降到了22位，這意味著我們對大于2^23-1的數(shù)值無能為力。

相比之下，如果我們只處理double，那么所有的問題就都迎刃而解了。首先，double的指數(shù)位，符號位和尾數(shù)的最高位全部都在高32位，無需屏蔽操作。其次，double有多達52位的尾數(shù)，對于32位的int來說，實在是太奢侈了！

用于double的magic number是1.5*2^52=6755399441055744.0，推導過程是一樣的。

根據(jù)同樣的原理，我們還可以計算出將float和double轉(zhuǎn)化為定點數(shù)的magic number。例如對于16-16的定點數(shù)，尾數(shù)右移的位數(shù)比原先轉(zhuǎn)化為整數(shù)時要少16，所以對于double來說，相應(yīng)的magic number就是1.5*2^36。如果要轉(zhuǎn)化為8-24的定點數(shù)，則移位次數(shù)要少24，magic number是1.5*2^28。對于其他格式的定點數(shù)，以此類推。比起int(float_val*65536)這樣的表達式，無論是速度還是精度都要優(yōu)勝得多。

另外，不得不再次重申的是，對于在最后的結(jié)果中被移除掉的數(shù)值，F(xiàn)PU會將其四舍五入到偶數(shù)。然而，有時我們確實需要像floor和ceil那樣的操作，那該怎么辦呢？很簡單，將原數(shù)加上或減去一個修正值就可以了，如下所示：
----------------------------------------------------------------------------------------
// 修正值
static double magic_delta=0.499999999999;

// 截取到整數(shù)
inline void Floor64 (int &val, double dval)
{
RoundToInt64(val,dval-delta);
}

// 進位到整數(shù)
inline void Ceil64 (int &val, double dval)
{
RoundToInt64(val,dval+delta);
}
----------------------------------------------------------------------------------------
這個世界上沒有免費的午餐。我們獲得了速度，相對應(yīng)地，也必須付出一些代價，那就是可移植性。上述方法全都基于以下幾個假設(shè)：(1)在x86上跑；(2)符合IEEE的浮點數(shù)標準；(3)int為32位，float為32位，double為64位。局限性其實是蠻大的，相比之下，int_val=(int)float_val就要省事多了。當然，你也可以使用條件編譯。

最后，讓我們來看兩組實際的測試數(shù)值。這份報告來自于Sree Kotay和他的朋友Herf：
----------------------------------------------------------------------------------------
平臺：Pentium IV/1.2

64位浮點數(shù)到32位整數(shù)的轉(zhuǎn)換：

int(f)：        2772.65 ms
fistp：         679.269 ms
magic number：  622.519 ms

64位浮點數(shù)到16-16定點數(shù)的轉(zhuǎn)換：

int(f*65536)：  2974.57 ms
fistp：         3100.84 ms
magic number：  606.80 ms

floor函數(shù)：

ANSI floor：    7719.400 ms
magic number：  687.177 ms
----------------------------------------------------------------------------------------
平臺：Pentium D/3.2

64位浮點數(shù)到32位整數(shù)的轉(zhuǎn)換：

int(f)：        1948.470 ms
fistp：         523.792 ms
magic number：  333.033 ms

64位浮點數(shù)到16-16定點數(shù)的轉(zhuǎn)換：

int(f*65536)：  2163.56 ms
fistp：         7103.66 ms
magic number：  335.03 ms

floor函數(shù)：

ANSI floor：    3771.55 ms
magic number：  380.25 ms
----------------------------------------------------------------------------------------
性能的差距實在令人驚訝，不是嗎？我想說的是，寫編譯器的家伙絕對不是傻瓜（恐怕比你我都要聰明得多），他們當然知道所有這些優(yōu)秀的算法。但為什么編譯器的表現(xiàn)會如此糟糕呢？其中一個理由是，為了使浮點數(shù)運算盡可能精確和迅速，IEEE在算法的選擇上有很多的限制。而另一方面，IEEE的舍入規(guī)則（四舍五入到偶數(shù)）盡管從維持浮點數(shù)的連貫性上來看非常棒，但卻不符合ANSI C在浮點數(shù)到整數(shù)的類型轉(zhuǎn)換上的說明（截尾）。于是，編譯器不得不做一大堆的工作來保證行為的正確性（符合標準）。這在大部分情況下都不是什么問題——除非你在寫圖形/聲音/多媒體之類的代碼。

剛剛在我的賽揚1.1G上實際測試了一下。編譯器是VC2003，使用PerformenceCounter來計算時間，在DEBUG模式下，C標準轉(zhuǎn)換/FISTP/MagicNumber三種方法所耗費時間的比約為5/3/2。但在優(yōu)化全開的RELEASE模式下，標準C類型轉(zhuǎn)換的速度卻是遙遙領(lǐng)先于所有其他的方法！也不知道是我的測試方法有問題，還是該贊VS厲害。
--------------------------------------------------------------------------------------
參考文獻和相關(guān)資源可到鄙人的小店下載：http://greatsorcerer.go2.icpcn.com/info/float2int.html

1，What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg（PDF）：
這篇論文囊括了關(guān)于浮點數(shù)的所有東西，正如其名字所示，任何想要了解浮點數(shù)的人都必讀的文獻。（其中關(guān)于精度的討論實在令我受益非淺。） 

2，Let's Get to The Floating Point by Chris Hecker（PDF）：
早期的關(guān)于浮點數(shù)的文章，寫得非常棒，值得一看。
 
3，IEEE Standard 754 for Binary Floating Point Arithmetic by Prof.W.Kahan（PDF）：
關(guān)于IEEE754標準的說明。 

4，IA64 Floating Point Operations and the IEEE Standard for Binary Floating Point Arithmetic（PDF）：
關(guān)于IA64的浮點數(shù)實現(xiàn)。 

5，Know Your FPU: Fixing Floating Fast by Sree Kotay 

兩人游戲： 給定K堆火柴，每堆火柴數(shù)為N1,N2,N3,...Nk,
兩人輪流拿，看誰拿到最后一根火柴誰就勝利。
    規(guī)則：每次只能從一堆中拿，每次至少拿一根，最多可拿光。
假若我先走，求教我必勝的策略。
    比如：有三堆，1  2  3

---------------------------------------------------------------

求出 N = N1^N2^N3^…^Nk （“^”為C++中的按位異或運算符）。
若 N 等于零，稱此狀態(tài)為必勝狀態(tài)，否則稱為非必勝狀態(tài)。
從必勝狀態(tài)中改小一個且只改小一個數(shù)字是不可能到達另一個必勝狀態(tài)的。
從非必勝狀態(tài)中一定可以找到一個數(shù)n，使得n<Ni且N1^N2^…^Ni-1^n^Ni+1^…^Nk=0 (其中1<=i<=k)，也就是說從非必勝狀態(tài)一定可以只改小一個數(shù)字而到達必勝狀態(tài)。
若某一方保證每次拿火柴后當前狀態(tài)都是必勝狀態(tài)，此方將勝出（當然要求相對此方的初始狀態(tài)為非必勝狀態(tài)）。

---------------------------------------------------------------

發(fā)信人: Nature (成長●快樂●煩惱), 信區(qū): Mathematics
標  題: 關(guān)于取火柴問題的解答
發(fā)信站: 南京大學小百合站 (Tue May  7 09:22:18 2002), 站內(nèi)信件

題目1：    今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。

題目2：    今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，
可將一堆全取走，但不可不取，最后取完者為負，求必勝的方法。

解答如下：

先解決第1題

定義1：若所有火柴數(shù)異或為0，則該狀態(tài)被稱為利他態(tài)，用字母T表示；否則，
為利己態(tài)，用S表示。

定理1：對任何S態(tài)，存在方法，從其中取一堆中的若干根，使狀態(tài)變?yōu)門態(tài)。
引理1.1 ：A(i)為非副整數(shù)，i=1..n, 記c=A(1) xor A(2) xor ……  xor A(n),

若c>0,則存在A(t), A(t) xor c <A(t)
證明： 把c表示成二進制，記它的二進制數(shù)的最高位為第p位，
  則必然存在一個A(t),它二進制的第p位也是1。（否則，若所有的A(i)的第p位都是0，
c的第p位就也為0，矛盾！）
  x=a(t) xor c 的第p位將為1 xor 1,即0；
  又因為c的最高位為p，所以x高于p位的值不變。所以必有x<a(t).即a(t) xor 
c<a(t)
.
  命題得證。

再來證定理1.
證明：
 設(shè)共有n堆火柴，每堆的數(shù)目分別為A(i)，i=1..n，A(i)為非副整數(shù).
 記c=A(1) xor A(2) xor ……  xor A(n),
 因為是S態(tài)，所以 c>0;
 所以存在A(t), A(t) xor c <A(t)。
 A(t)' = A(t) xor c <A(t)
  c' = A(1) xor A(2) xor …  xor A(t)' xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor c xor … xor A(n)
   = A(1) xor A(2) xor …  xor A(t) xor … xor A(n) xor c
   = c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c <A(t) )，狀態(tài)成
為T態(tài)。
故命題成立。    #

定理2：T態(tài)，取任何一堆的若干根，都將成為S態(tài)。
證明：反證法：
  反設(shè)存在一堆，記為第m堆，從中取了若干根，根數(shù)由A(m)變?yōu)锳(m)' .
  A(m)>A(m)' 狀態(tài)均為T態(tài)。
  記c=A(1) xor A(2) xor … xor A(m) xor…  xor A(n),
  記c'=A(1) xor A(2) xor … xor A(m)' xor…  xor A(n),
  c=0;c'=0;
  所以有 0= A(1) xor A(2) xor … xor A(m) xor…  xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
     d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
        同理， d xor A(m)' =0
   A(m)'= d
  所以，A(m)'=A(m) . 矛盾！
  故反設(shè)不成立。原命題成立。 #

定理 3：S態(tài)，只要方法正確，必贏。
 最終勝利即由S態(tài)轉(zhuǎn)變?yōu)門態(tài)，任何一個S態(tài)，只要把它變?yōu)門態(tài)，（由定理一，
可以把它變成T態(tài)。）對方只能把T態(tài)轉(zhuǎn)變?yōu)镾態(tài)(定理2)。這樣，所有S態(tài)向T態(tài)的轉(zhuǎn)變都可以
有己方控制，對方只能被動地實現(xiàn)由T態(tài)轉(zhuǎn)變?yōu)镾態(tài)。故S態(tài)必贏。 #
定理4：T態(tài)，只要對方法正確，必敗。
 由定理3易得。


我們再來處理第2題。我們會發(fā)現(xiàn)兩題會有一些相同之處，控制S->T態(tài)的人控制著
主動權(quán)
。經(jīng)過分析，我們有以下結(jié)論：
定義2：若一堆中僅有1根火柴，則被稱為孤單堆。若大于1根，則稱為充裕堆。
定義3：T態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利他態(tài)，用T2表示；若充
裕堆的堆數(shù)等于0，則稱為部分利他態(tài)，用T0表示。
定理4：不存在充裕堆數(shù)為1的T態(tài)。
證明：
 孤單堆的根數(shù)異或只會影響二進制的最后一位，但充裕堆會影響高位（非最后一位）。

 一個充裕堆，高位必有一位不為0，則所有根數(shù)異或不為0。故不會是T態(tài)。
定義4：S態(tài)中，若充裕堆的堆數(shù)大于等于2，則稱為完全利己態(tài)，用S2表示；若充
裕堆的堆數(shù)等于1，則稱為自主利己態(tài)，用S1表示; 若充裕堆的堆數(shù)等于0，則稱為部分利
己態(tài)，用S0表示。

定理4：S0態(tài)，即僅有奇數(shù)個孤單堆，必敗。T0態(tài)必勝。
證明：S0態(tài)，其實就是每次只能取一根。每次第奇數(shù)根都由己取，第偶數(shù)根都由對
方取，所以最后一根必己取。敗。
  同理, T0態(tài)必勝#
定理5：S1態(tài)，只要方法正確，必勝。
證明：若此時孤單堆堆數(shù)為奇數(shù)，把充裕堆取完；否則，取成一根。
   這樣，就變成奇數(shù)個孤單堆，由對方取。
   由定理4，對方必輸。己必勝。 #
定理6：S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)。
證明：充裕堆數(shù)不可能一次由2變?yōu)?。得證。 #
定理7：S2態(tài)可一次轉(zhuǎn)變?yōu)門2態(tài)。
證明：由定理1，S態(tài)可轉(zhuǎn)變?yōu)門態(tài)，態(tài)可一次轉(zhuǎn)變?yōu)門態(tài)
   又由定理6，S2態(tài)不可轉(zhuǎn)一次變?yōu)門0態(tài)，
   所以轉(zhuǎn)變的T態(tài)為T2態(tài)。 #
定理8：T2態(tài)，只能轉(zhuǎn)變?yōu)镾2態(tài)或S1態(tài)。
證明：. 由定理2，T態(tài)必然變?yōu)镾態(tài)。
     由于充裕堆數(shù)不可能一次由2變?yōu)?，所以此時的S態(tài)不可能為S0態(tài)。
  命題得證。
定理9：S2態(tài)，只要方法正確，必勝.
證明：方法如下：
   1） S2態(tài)，就把它變?yōu)門2態(tài)。（由定理7）
   2） 對方只能T2轉(zhuǎn)變成S2態(tài)或S1態(tài)(定理8)
  若轉(zhuǎn)變?yōu)镾2, 轉(zhuǎn)向1）
  若轉(zhuǎn)變?yōu)镾1, 這己必勝。（定理5）
定理10：T2態(tài)必輸。
證明：同9。
 綜上所述，必輸態(tài)有： T2,S0
     必勝態(tài)：   S2,S1,T0.
兩題比較：
第一題的全過程其實如下：
 S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二題的全過程其實如下：
 S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下劃線表示勝利一方的取法。
    是否發(fā)現(xiàn)了他們的驚人相似之處。
我們不難發(fā)現(xiàn)(見加黑部分)，S1態(tài)可以轉(zhuǎn)變?yōu)镾0態(tài)（第二題做法），也可以轉(zhuǎn)變?yōu)?
T0（第一題做法）。哪一方控制了S1態(tài)，他即可以有辦法使自己得到最后一根（轉(zhuǎn)變?yōu)?
T0）,也可以使對方得到最后一根（轉(zhuǎn)變?yōu)镾0）。
 所以，搶奪S1是制勝的關(guān)鍵！
 為此，始終把T2態(tài)讓給對方，將使對方處于被動狀態(tài)，他早晚將把狀態(tài)變?yōu)镾1.
(見定理9的證明).