數(shù)論 (3)

1、第十二講 數(shù)論,,第一節(jié) 最大公約數(shù),首先，我們來回顧一下公約數(shù)和最大公約數(shù)的概念：如果d是a的約數(shù)并且也是b的約數(shù)，則d是a與b的公約數(shù)。例如,30的約數(shù)為1，2，3，5，6，１0，15，30; 24的約數(shù)為1，2，3，4，6，12，24; 因此24與30的公約數(shù)1，2，3，6。1是任意兩個整數(shù)的公約數(shù)。,,兩個不同時為0的整數(shù)a與b的最大公約是其值為最大的公約數(shù)，表示為gcd(a，b)。顯然，gcd(24，30)＝6。在這節(jié)中，我

2、們僅限于對非負(fù)整數(shù)的情況進(jìn)行討論。這一限制是有道理的，因?yàn)間cd(a，b)＝gcd(│a│，│b│)。,,不妨設(shè)a>=b，一種十分容易想到的算法是：枚舉1到b的所有整數(shù)，在能同時整除a和b的數(shù)中取最大的。這個算法的時間復(fù)雜度為O(min(a,b))，當(dāng)min(a,b)較大的時候程序要執(zhí)行比較長的時間。    在引出新算法之前，我們先來證明一個被稱為gcd(歐幾里德)的遞歸定理:

3、0;gcd(a，b)＝gcd(b，a  mod  b),證明:,我們只要證明出gcd(a，b)與gcd(b，a  mod  b)可互相整除，上式一定成立。設(shè)d＝gcd(a，b)。將a mod b 化成a與b的線性組合    a mod b＝a－a div b * b    由于d能整除a和b，因此d一定能整除a與b的

4、線性組合，即d能整除(a mod b)。 又因?yàn)閐能整除b和(a mod b)，顯然d(＝gcd(a，b))能整除gcd(b，a mod b)。    同理可證：gcd(b，a mod b)能整除gcd(a，b),,下述算法是一個直接基于gcd定理之上的遞歸程序。該函數(shù)輸入非負(fù)整數(shù)a、 b，返回a和b的最大公約數(shù)。     function gcd(a，b:lon

5、gint):longint;  begin   if b=0 then    gcd:=a   else    gcd:=gcd(b，a mod b)  end;,,由于遞歸邊界gcd(a，0)＝a正確且遞歸調(diào)用過程中第二個值參嚴(yán)格遞減， 所以算法不可能無限遞歸下去，在運(yùn)行終止時總能求出正確的答案。例如gc

6、d(30，21)的計(jì)算過程    gcd(30，21)=gcd(21，9)=gcd(9，3)=gcd(3，0)=3    在這個計(jì)算過程中三次遞歸調(diào)用了gcd。此算法的時間復(fù)雜度為O(log(Max(a,b)))。,,同理求這兩個數(shù)的最小公倍數(shù)LCM ( a , b ),直接利用公式： LCM ( a , b ) * GCD( a , b ) = a

7、* b即可。      生活中許多有趣的問題，可以運(yùn)用gcd定理來解答。,例12_1 狼找兔子,一座山周圍有n個洞，逆時針編號為0，1，2，...n-1。 而一只狼從0號洞開始，逆時針方向計(jì)數(shù)，每遇到m個洞就進(jìn)洞找兔子。例如n=5，m=3，狼經(jīng)過的洞依次為0，3，1，4，2，0。    輸入n、m。試問兔子

8、有沒有幸免的機(jī)會?如果有，該藏在哪兒?,,分析：,不妨讓兔子躲在一號洞。因?yàn)槿衾悄軓?號洞到達(dá)1號洞，則它必能從1號洞到達(dá)2，...，n-1號洞，兔子難逃厄運(yùn)。反過來說，若有安全洞，則1號洞就是其中的一個。,,再來看狼的運(yùn)動。狼的第i次運(yùn)動后的洞址應(yīng)是(m*i) mod n(i為正整數(shù))。若( m* i) mod n=1，即狼第i次運(yùn)動后到達(dá)1號洞，則gcd(m，n)=1。因?yàn)槿鬵cd(m，n)=k>1，則由(m`*k*i)mod

9、(n`*k) =1 ，(設(shè)m`*k=m，n`*k=n)，m`*i*k-[(m`*i*k)/(n`*k)]*(n`*k)=1。得出k整除1，與k>1矛盾。,,而若gcd(m，n)=1，則必存在i使(m*i)mod n=1，因而兔子幸免的條件為gcd(m，n)>1。在此情況下，它應(yīng)選擇除{i*gcd(m，n)│i=0...(n/gcd(m，n)-1)}外的洞躲藏。下面，我們給出程序題解,,Program Hare_And_Wol

10、f;Var  m， n， d， i  :  Longint;function gcd(a，b:longint):longint; begin  if b=0 then   gcd:=a  else   gcd:=gcd(b，a mod b) end;Begin  Write('N

11、 M = ');  Readln(N， M);  d := gcd(m， n);    If d = 1                Then Writeln('No Answer')  

12、60;  Else Begin        Writeln('The hare can't hide in ');       For i := 0 to n div d - 1 Do Write(i * d:5);     &

13、#160; Writeln     End{else}End.{main},第二節(jié) 模取冪運(yùn)算,數(shù)論計(jì)算中經(jīng)常出現(xiàn)的一種運(yùn)算就是求一個數(shù)的冪ab對另外一個數(shù)n個模的運(yùn)算，即計(jì)算:ab mod n (a,b,n是正整數(shù))    由于計(jì)算機(jī)只能表示有限位的整數(shù)，所以編程時模取冪的運(yùn)算要注意值的大小范圍，當(dāng)ab的值超過整數(shù)范圍時,mod運(yùn)算便無法進(jìn)行。,

14、,如何解決這個問題，我們引出一個能計(jì)算ab mod n的值的有用算法——反復(fù)平方法，首先我們必須明確：d=ab mod n=(…((((a mod n)*a)mod n)*a)mod n…*a)mod n    {共b個a}     由此可以引出一個迭代式         d:=a;

15、0;        for i:=2 to b do            d:=d mod n*a;         d:=d mod n;,,時間復(fù)雜度為O（b），當(dāng)b很大

16、時，效率很低。我們可以將b轉(zhuǎn)換為二進(jìn)制數(shù),然后從最低位b0開始，由右至左逐位掃描，每次迭代時，用到下面兩個恒等式： a2c mod n =(ac)2 mod n      bi=0             a2c+1 mod n =a*(

17、ac)2 mod n   bi=1  (0<=c<=b)    其中c為b的二進(jìn)制數(shù)的后綴（bi-1...b0）對應(yīng)的十進(jìn)制數(shù)，當(dāng)c成倍增加時，算法保持d=ac mod n不變，直至c=b。時間復(fù)雜度: O(logb),,程序?qū)崿F(xiàn)可如下：function f(a,b,n:longint):longint; {函數(shù)輸入a，b，n，經(jīng)過反復(fù)平方計(jì)算和

18、返回ab mod n的值}var d,t:longint; begin  d:=1;t:=a;  while b>0 do {從右到左逐位分析b的二進(jìn)制值，并迭代計(jì)算ac mod n}  begin    if b mod 2 =1 then d:=d*t mod n;    b:=b div 2;     t:=t

19、*t mod n;   end;  f:=d {返回ab mod n的值}end;,第三節(jié) 素數(shù),數(shù)學(xué)類的基本算法大多數(shù)屬于初等數(shù)論范疇，相當(dāng)大一部分與素數(shù)有直接關(guān)系，因此素數(shù)是一個很基本又很重要的內(nèi)容?！　∥覀兿葋砜纯丛趺磁袛嘁粋€數(shù)是否素數(shù)。素數(shù)的定義為：如果一個數(shù)的正因子只有1和這個數(shù)本身，那么這個數(shù)就是素數(shù)。根據(jù)定義，我們立即能得到判斷一個數(shù)N（大于1）是否素數(shù)的簡單的算法：枚舉2到N-1之間的整數(shù)，判

20、斷是否能整除N。該算法的Pascal代碼。,,program Prime_1; var x:integer; function IsPrime(n:integer):boolean; {返回n是否素數(shù),n>=2} var i:integer; begin for i:=2 to n-1 do {枚舉因子i} if ( n mod i = 0 ) the

21、n {i能整除n嗎?} begin IsPrime:=false; {n不是素數(shù)} exit; end; IsPrime:=true; {n是素數(shù)} end; begin readln(x); if IsPrime(x) then writeln(x,'

22、is a prime!') else writeln(x,' is not a prime!'); end.,,如果n很大，那么上面的程序就要運(yùn)行比較長的一段時間，那么有沒有更快一點(diǎn)的算法呢？回答是肯定的！因?yàn)槿绻鹡含有不為1和自身的因子，那么這些因子中必定有不大于sqrt(n)的（假設(shè)n有因子p，1sqrt(n)，那么n/p也是n的因子，而且1<n/p<n

23、，所以n/p不大于sqrt(n)）。于是我們可以改進(jìn)上面的程序，得到另外一個 程序。容易知道這個算法的時間復(fù)雜度為O(sqrt(n))。,,program Prime_2; var x:integer; function IsPrime(n:integer):boolean; {返回n是否素數(shù),n>=2} var i:integer; begin for i:=2 to trunc(sqrt

24、(n)) do {枚舉因子i} if ( n mod i = 0 ) then {i能整除n嗎?} begin IsPrime:=false; {n不是素數(shù)} exit; end; IsPrime:=true; {n是素數(shù)} end; begin

25、 readln(x); if IsPrime(x) then writeln(x,' is a prime!') else writeln(x,' is not a prime!'); end.,問題描述：    列出所有從數(shù)字1到數(shù)字n的連續(xù)自然數(shù)的排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。輸入：n （1&l

26、t;=n<=9）輸出：    由1—n組成的所有不重復(fù)的數(shù)字序列，每行一個序列,第四節(jié) 全排列問題,樣例：p.in 3p.out1 2 31 3 22 1 32 3 13 1 23 2 1,問題分析,1 2 3；1 3 2； 2 1 3；2 3 1； 3 1 2；3 2 1。 從樣例我們可以發(fā)現(xiàn),每一個排列方式總

27、是在其前一個排列的基礎(chǔ)上通過順序逆轉(zhuǎn)而得到的.由此我們得到給定一個排列P1，P2，P3，……，Pn之后下一個排列的算法如下：,,S1：求滿足關(guān)系式P（j-1）<P（j）的j的最大值，記為i，即：i=max{j　|　P（j-1）<P（j）}    S2：求滿足關(guān)系式P(i-1)<P(k)的k的最大值，記為j，即：j=max{k　|　P（i-1）<P（k）}  &

28、#160; S3：將P（i-1）與P（j）互換得P=P1P2……Pn    S4：將交換后的序列從P（i）到P（n）進(jìn)行部分逆轉(zhuǎn)，使：        P（1）P（2）……P（i-1）P（i）P（i+1）……P（n-1）P（n）逆轉(zhuǎn)得到：        P（1）P

29、（2）……P（i-1）P（n）P（n-1）……P（i+1）P（i）,例如：設(shè)P（1）P（2）P（3）P（4）=3421，則    S1：i=max{j|P（j-1）<P（j）}=2    S2：j=max{k|P（i-1）<P（k）}=2    S3：將P（i-1）與P（j）即P（1）與P（2）交換得到序列4321

30、0;   S4：對于序列4321從P（i）即P（2）開始部分逆轉(zhuǎn)，得到下一個個排列，4321——〉4123,組合的生成,問題描述：    排列與組合是常用的數(shù)學(xué)方法，其中組合就是從n個元素中抽出r個元素（不分順序，且r<=n），我們可以簡單地將n個元素理解為自然數(shù)1，2，…，n，從中任取r個數(shù)。,,輸入：    一行兩個自然數(shù)n，r（1<n&

31、lt;21,1<=r<=n）輸出：    所有的組合，每一行組合占一行且其中的元素按由小到大的順序排列，每個元素占三個字符的位置，所有的組合也按字典順序。樣例：,compages.in5 3,compages.out1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5,問題分析,從上面的樣例我們可以看出組合的生成過程有如

32、下規(guī)律：    （1）最后一位最大可達(dá)n，倒數(shù)第二位最大可達(dá)n-1，依次類推……倒數(shù)第k位（k<=n）不得超過n-k+1。 因此，若r個元素的組合用C（1）C（2）……C（r）來表示，且設(shè)定C（1）<C（2）<……<C（r），則有：C（r）<=n-r+i，i=1，2，3，……，r。,,（2）當(dāng)存在C（j）<n-r+j時，其中下標(biāo)的最大值設(shè)為i，即有：

33、         i=max{j|C（j）<n-r+j}，        則有C（i）=C（i）+1，與之相應(yīng)的C（i+1）=C（i）+1，……，C（r）=C（r-1）+1,由此，可以得到從一個組合到其下一個組合的算法如下：    

34、S1:求滿足不等式C（i）<n-r+i的最大數(shù)i，即：i=max{j|C（j）<n-r+j}     S2:C（i）=C（i）+1     S3:從i+1位起修改：C（j）=C（j-1）+1，i+1<=j<=r,例如：對于樣例中序列C（1）C（2）C（3）=145。     S1:i

35、=max{j|C（j）<n-r+j}=1；     S2:C（1）=C（1）+1=1+1=2；     S3:從i+1位起修改：C（2）=C（1）+1=3，C（3）=C（2）+1=4。     則得到序列145的下一個組合234,第五節(jié) 因式分解,因式分解的算法很簡單，模擬手工分解的過程，我們得到分解

36、n的算法：枚舉所有不大于n的所有素數(shù)，判斷這些素數(shù)能整除n多少次。判斷2到n是否素數(shù)，總共要計(jì)算sqrt(2)+sqrt(3)+sqrt(4)…+sqrt(n)<=n*sqrt(n)次，因此算法的時間復(fù)雜度可以粗略地認(rèn)為是O(n*sqrt(n))。,,事實(shí)上，我們有更好的算法。先看一個顯而易見的結(jié)論：如果p是能整除n的所有大于1的數(shù)中最小的，那么p是n的一個素因子。基于這樣一個結(jié)論，我們得到代碼。,,Program YinShiF

37、enJie; var p:array[1..100] of integer; {素因子} s:array[1..100] of integer; {p[i]對應(yīng)的指數(shù)} i,j,n,pnum:integer; {n為需要分解的數(shù)，n=(p[1]^s[1])*(p[2]^s[2])...*(p[pnum]^s[pnum])} procedure YSFJ(x:integer); var i:

38、integer; begin pnum:=0; i:=2; while ( (x>1) and (i*i1) then {表明x是一個素數(shù)} begin inc(pnum); {找到一個新的素因子x} p[pnum]:=x; s[pnum]:=1; end; e

39、nd;   begin readln(n); YSFJ(n); {以下為輸出結(jié)果} write(n,' = ',p[1]); dec(s[1]); for i:=1 to pnum do for j:=1 to s[i] do write(' * ',p[i]); writeln;

40、 end.,第六節(jié) 進(jìn)制轉(zhuǎn)換,一、數(shù)的進(jìn)制的概念： 日常生活中我們計(jì)數(shù)的方式有很多，如一年有12個月，則是12進(jìn)制，一周有7天，則是7進(jìn)制，等等。實(shí)際都是我們?nèi)藶橐?guī)定的，而平常我們用的最多的最習(xí)慣的是10進(jìn)制，是因?yàn)槲覀児湃肆粝聛淼呢敻?，而古人是因?yàn)橛?0個手指便于幫助計(jì)數(shù)。需要強(qiáng)調(diào)的是任何一個值都可以用任何一種進(jìn)制描述，但它的值是不變的，正如我們今天在一周中可以描述為星期幾，在一月中描述為多少號一樣。,,使用R進(jìn)

41、制計(jì)數(shù)的規(guī)則：1、  只使用R個基數(shù)：0，1，2，……，R-1；2、  逢R進(jìn)一，退一當(dāng)R進(jìn)行數(shù)的運(yùn)算。,,二、R進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)這個轉(zhuǎn)化問題較簡單，根據(jù)上面講的R進(jìn)制的計(jì)數(shù)規(guī)則進(jìn)行展開就得到相應(yīng)的十進(jìn)制數(shù)的表示方法。       （anan-1……a1a0.a-1a-2……a-m）R=an*Rn+an-1*Rn-1+……+a1*R1+a0*R

42、0+a-1*R-1+a-2*R-2+……+a-m*R-m=,,三、十進(jìn)制數(shù)轉(zhuǎn)化為R進(jìn)制數(shù)由于十進(jìn)制數(shù)的整數(shù)與小數(shù)轉(zhuǎn)化為R進(jìn)制的方法不同，所以必須分開討論。先看十進(jìn)制整數(shù)的轉(zhuǎn)化，再討論十進(jìn)制小數(shù)的轉(zhuǎn)化，最后討論-R進(jìn)制的計(jì)數(shù)及轉(zhuǎn)化問題。,,1、 十進(jìn)制整數(shù)的轉(zhuǎn)化通過具體實(shí)例進(jìn)行分析，如對十進(jìn)制數(shù)325轉(zhuǎn)化，根據(jù)原理可以按下式這樣假設(shè)：    （325）10=3*102+2*101+5*100

43、60;             =（anan-1……a1a0）R           = an*Rn+an-1*Rn-1+……+a1*R1+a0*R0    

44、0;      =（an*Rn-1+an-1*Rn-2+……+a1）*R+a0,,兩邊同時除以R，得到整數(shù)部分和整數(shù)部分相等，余數(shù)和余數(shù)相等，顯然右邊的余數(shù)就是a0，再進(jìn)行同樣的處理就得到a1，一直這樣進(jìn)行下去，直到左邊的數(shù)為0是為止，由于先求出的是R進(jìn)制的最低位，再按求解過程倒過來寫出就得到相應(yīng)的R進(jìn)制數(shù)。,,以R=6為例，看轉(zhuǎn)化的過程：  &

45、#160;         （325）10=（1301）6最后，得到的規(guī)律就是“除R取余,逆序輸出”。,,2、 十進(jìn)制小數(shù)的轉(zhuǎn)化通過具體實(shí)例進(jìn)行分析，如對十進(jìn)制數(shù)0.375轉(zhuǎn)化，根據(jù)原理可以按下式這樣假設(shè)：       (0.375)10=3*10-1+7*10-2+5*10-3  

46、;          =（0.a-1a-2……a-m）R        =a-1*R-1+a-2*R-2+……+a-m*R-m            =(a-1+a-

47、2*R-1+……+a-m*R-m+1)*R-1,,兩邊同時乘以R，等式兩邊的整數(shù)部分和小數(shù)部分分別相等，顯然右邊的整數(shù)部分就是a-1，再去掉等式的整數(shù)部分，然后進(jìn)行相同的處理，就求得了a-2，一直進(jìn)行下去，直到左邊的值為0時或到要求的精度為止，這樣就將十進(jìn)制小數(shù)轉(zhuǎn)化為相應(yīng)的R進(jìn)制數(shù)了。,,以R＝2為例，說明求解過程：    （0．375）10=（0．011）2最后得到的規(guī)律就是“乘R取整”。,,

48、3、 R進(jìn)制數(shù)轉(zhuǎn)化為-R進(jìn)制數(shù)大家對R進(jìn)制數(shù)都已經(jīng)很熟悉了，但是，還有一種-R進(jìn)制數(shù)。任何一個整數(shù)n都可以表示成:其中 ai∈[0,R-1],ai是整數(shù)。并且ak0。,,現(xiàn)在我們來討論R進(jìn)制數(shù)怎么轉(zhuǎn)化為-R進(jìn)制數(shù)。需不需要先將R進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，再將相應(yīng)的十進(jìn)制利用上面的轉(zhuǎn)化規(guī)律化為-R進(jìn)制數(shù)，當(dāng)然這是一種方法，但我們完全可以不必這樣做。不妨以一個具體實(shí)例來討論轉(zhuǎn)化規(guī)律，如：,,（4325）6=4*63+3*62+2*61+5

49、*60將等式右邊改寫成一個-6進(jìn)制數(shù)的形式：    4*（-6）3+3*（-6）2+2*（-6）1+5*（-6）0比較觀察一下，發(fā)現(xiàn)偶次冪的項(xiàng)與6進(jìn)制數(shù)的相等，差別出在奇次冪的項(xiàng)，怎樣修改才使它滿足-6進(jìn)制數(shù)表示的形式呢？記住我們計(jì)數(shù)的原理：進(jìn)制只是表示方式不同，值是不變的。,,那么對于上面我們倒數(shù)第二項(xiàng)：2*61=X*（-6）1 ？  而基數(shù)X是一個0到5之間的數(shù)，顯然是不能成立的，要相等

50、X只能等于-2，而-2不能做為-6進(jìn)制的基數(shù)，解決這個問題就向高位借一個1，這樣X變?yōu)椋?-2），由于高位已經(jīng)是相等的，所以高位的基數(shù)相應(yīng)要加1。若高位基數(shù)加1后，值已超過5，則修改冪。,,這樣就能確保值沒有變：        2*61=（-6）2+4*（-6）1   處理方法可以從R進(jìn)制數(shù)的最低位按上面的方式往高位處理，就實(shí)現(xiàn)了把R進(jìn)制數(shù)轉(zhuǎn)化

51、為-R進(jìn)制的數(shù)了。對于上例我們處理后得到：1*（-6）4+2*（-6）3+4*（-6）2+4*（-6）1+5*（-6）0因此有：（4325）6=（12445）-6=989,四、 課堂練習(xí),,1、  將下面進(jìn)制的數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)：（123456.345）7   (2A45.ED2)162、  將下面的十進(jìn)制數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)，十六進(jìn)制數(shù)(精確到原來小數(shù)點(diǎn)位數(shù)的倍)：345.6825 

52、;                               4352.36十六進(jìn)制的16個基數(shù)表示如下：,3、  將下面相應(yīng)

53、的R進(jìn)制數(shù)轉(zhuǎn)化為-R進(jìn)制數(shù)：（2345．67）8        （347891.425）10,五、 應(yīng)用舉例,在信息學(xué)競賽中，巧妙地使用某些數(shù)制的特點(diǎn)，可能使解題變得相當(dāng)簡單，請看下面幾道例題。例12_2 火車轉(zhuǎn)軌問題     圖中兩條軌道連到一個鐵路轉(zhuǎn)軌處，形成一個鐵路轉(zhuǎn)軌網(wǎng)絡(luò)的棧。其中右邊軌道為輸入端，左邊軌道為輸出端

54、。如果執(zhí)行了Push,Push,Pop,Push,Push,Pop,Pop,Pop,就會將輸入端的車皮編號順序1，2，3，4變成2，4，3，1，請編程求左邊車皮編號為1，2，3，4時，在右邊軌道可能得到的所有車皮編號順序。,分析：,這個例子是典型的棧應(yīng)用題。但如果單純使用棧的技術(shù)，則在不斷的判定入棧出棧中，很容易迷失方向?，F(xiàn)在讓我們仔細(xì)分析，看看有沒有其它方法可以解決此題，1、四列車都必須經(jīng)過轉(zhuǎn)軌才能到達(dá)軌道的另一邊，且進(jìn)棧出棧各一次；

55、2、如果以1代表進(jìn)棧，0代表出棧，則火車的轉(zhuǎn)軌可以用一相應(yīng)二進(jìn)制數(shù)來表示，如，10代表火車進(jìn)棧后出棧，01代表火車出棧后進(jìn)棧；3、四列火車都到達(dá)轉(zhuǎn)軌的另一側(cè)，一共進(jìn)出棧8次，恰好一個字節(jié)8個位；4、由于必須先進(jìn)棧才能出棧，故在二進(jìn)制的每一位前，1的個數(shù)總不少于0的個數(shù)，否則轉(zhuǎn)軌內(nèi)無車可出。這樣就巧妙地利用數(shù)的進(jìn)制將原問題轉(zhuǎn)化為一求0至255內(nèi)的二進(jìn)制數(shù)中符合相應(yīng)條件的數(shù)的個數(shù)。,,,例12_3 城市街道   

56、60; 下圖是一個城市的街道圖，縱向有N段，橫向有M段。欲從左下角到右上角，如果在每一個路口只能向上或向右走，問一共有多少種行走路線？,分析：,解決這題有很多方法，如組合數(shù)學(xué)中加法原理，很容易得到遞推式，動態(tài)規(guī)劃（這兩者實(shí)際上是一樣的），搜索等?，F(xiàn)在，我們換一種思路：記向右走為1，向上走為0，則完成這件事就對應(yīng)一個二進(jìn)制數(shù)，它的位數(shù)為M+N位，且在這M+N位中，1的個數(shù)為M，如果一個二進(jìn)制數(shù)的前M+N位滿足1的個數(shù)為M，那么它就是一種符

57、合條件的行進(jìn)路線。滿足這樣條件的數(shù)，最小為2M，最大為2M+N-2N。問題轉(zhuǎn)化為求[2M，2M+N-2N]二進(jìn)制數(shù)中前M+N位里有M個1的個數(shù)。,,例12_4 放球方案     把N個球放入編號為0,1,2,……,49的50個盒內(nèi)（N<250），要求第i個盒內(nèi)必須放pi*mi只球，如果該盒無法滿足這一條件，則一個也不放。其中2<=m<=16，Pi是0到m-1之間的整數(shù)。求出放球的具體方案

58、。m、n從鍵盤輸入。,,分析：由題意已知：（1）第i個盒中放入pi*mi只球；（2）m一定；（3）0<=pi<=m-1；則可得出結(jié)論：(n)10=(p49p48...p2p1p0)m 由此得出了問題的原型：即將n轉(zhuǎn)化成m進(jìn)制數(shù)。   考慮是否需要第51只盒子，這里取m的最小值m=2，而n取最大值，即n=250-1。       &

59、#160;           又有n=250-1= ∑2i (i=0..49),所以在最壞的情況下也不需要第51只盒子。,,考慮到本題實(shí)際上就是一個進(jìn)制數(shù)轉(zhuǎn)換問題，但由于位數(shù)太多，采用comp類型存儲。用數(shù)學(xué)中的短除法來解決進(jìn)制數(shù)轉(zhuǎn)換問題是較常用的方法，但由于數(shù)據(jù)采用了comp類型存儲，使用稍有不便，因此可采用了從高位到低位，求出

60、pi的值。其簡單算法設(shè)計(jì)為：S1：輸入m，n； S2：求每個盒子中的球數(shù)；        找到放有小球且編號最大的盒子j；          for i:=j down to 0 do       &

61、#160;     求出本位的系數(shù)并去掉n中大于mi的部分；S3：輸出結(jié)果。,,例12_5 -P進(jìn)制數(shù)  大家對P進(jìn)制數(shù)都已經(jīng)很熟悉了，但是，還有一種-P進(jìn)制數(shù)。任何一個整數(shù)n都可以表示成， 其中 ai∈[0,p-1],ai是整數(shù)。并且ak0?，F(xiàn)在，你需要讀入一個整數(shù)n,(1<=|n|<=10100)。輸出它的-p進(jìn)制表示法。,,[輸入]第一行有一個正整數(shù)P(

62、2<=p<=100)。第二行有一個整數(shù)n,如果它是正數(shù)，前面沒有符號，否則他前面有一個負(fù)號“-”。[輸出]       輸出有兩行，第一行是一個數(shù)k。       第二行有k+1個數(shù)，表示a0、a1……ak，數(shù)字之間用一個空格分開。[輸入樣例1]    &

63、#160;  2       9[輸出樣例1]       4       1 0 0 1 1 [輸入樣例2]       3   &

64、#160;   -100[輸出樣例2]       5       2 1 1 1 2 1,分析：,和P進(jìn)制一樣，可以按照每一次確定最后一位的方法來確定這個p進(jìn)制數(shù)，方法可以這樣，設(shè)-P進(jìn)制數(shù)為n，那么求出一個數(shù)a，(0<=a<p)，使得n-a是p的倍數(shù)。顯然，這樣的數(shù)只可能有一個

65、，所以這個a就是-p進(jìn)制數(shù)的最后一位。然后，就可以遞歸的把(n-a)/(-p)=-(n-a)/p化成-p進(jìn)制數(shù)后，然后把a(bǔ)放到這個數(shù)的最后，就得到了n的-p進(jìn)制數(shù)。,,,例如樣例-100的-3進(jìn)制數(shù)，可以這樣求：,所以，求出的-3進(jìn)制數(shù)就是121112，所以輸出2 1 1 1 2 1。,,另外一種方法就是從熟悉的P進(jìn)制數(shù)出發(fā)，即先把n化成p進(jìn)制數(shù)，然后從低位到高位把它化成-p進(jìn)制數(shù)，即用一個指針，指針前面的是p進(jìn)制數(shù)，指針后面的就變成了

66、-p進(jìn)制數(shù)。還是看-100，由于是個負(fù)數(shù)，可以取大于等于它的絕對值的最小的3的冪，即243，所以-100=-243+143。那么143化成3進(jìn)制數(shù)就是12022。所以,,-100=-35+34+2*33+2*31+2*30=-35+34+2*33+(3-1)*31+2*30=-35+34+2*33+32+(-3)1+2*30=-35+34+(3-1)*33+32+(-3)1+2*30=-35+2*34+(-3)3+32+(-3)

67、1+2*30=1*(-3)5+2*(-3)4+1*(-3)3+1*(-3)2+1*(-3)1+2*(-3)0=(121112)-3。,,可以看出，上面的式子就是利用”奇數(shù)位上為負(fù)數(shù)，偶數(shù)位上為正數(shù)”來進(jìn)行變形，直到最后，所有的數(shù)位都滿足這個條件，就相當(dāng)于化成了-p進(jìn)制數(shù)。上面兩種方法雖然表面上不同，但是最后得到了相同的結(jié)果。往往作題時，總是會往地一種方法想，但其實(shí)，換個思路，又會得到一種解法。,,程序設(shè)計(jì)中可采用多種數(shù)學(xué)方法，恰如

68、其分的數(shù)學(xué)方法可以大大減少程序運(yùn)行的時間和所需空間，起到優(yōu)化程序的作用。遇到一道題目時,如進(jìn)制運(yùn)算,多項(xiàng)式運(yùn)算等,應(yīng)不急于馬上用遞歸,回溯等算法,無妨先用筆算,從中發(fā)現(xiàn)一些規(guī)律.但是也不是每一道題都可以用數(shù)學(xué)方法完成,數(shù)學(xué)方法只能用于一些求總數(shù),最值之類的題目上。,,例12_6 砝碼設(shè)計(jì)       設(shè)有一個天平,可以用來稱重。 任務(wù)一：設(shè)計(jì)n個砝碼的重量，用他們能稱出盡可能多的整數(shù)重

69、量。例如，n=2，設(shè)計(jì)2個砝碼的重量分別為1和3, 可稱重為1,2,3,4的連續(xù)重量。任務(wù)二：在給出n個砝碼能稱出最大重量范圍的一重量x，試給出稱出x的方案。,,在上例中:      給出x=2稱出的方案為2+1:3          x=4稱出的方案為4:1+3  

70、60;       x=1稱出的方案為1:1      輸入:n,x(n為砝碼個數(shù),x是在稱出最大重量范圍內(nèi)的重量)      輸出:砝碼方案,稱出x的方案.      輸入樣例1:2,2    

71、;      輸入樣例2:2,4      輸出樣例1:1,3          輸出樣例2:1,3             2+1:3

72、                  4:1+3,分析：,由題目任務(wù)一可知:n=2時砝碼重量最優(yōu)解為1,3. 我們可以試n=3,n=4...的情況,不難發(fā)現(xiàn)砝碼的重量均為3的1至n次方,由于理論推導(dǎo)涉及到累加等數(shù)學(xué)知識,我們著重看任務(wù)二.   

73、60;  任務(wù)二要求輸出用砝碼稱出重為x的重量,實(shí)際上就是用3的1至n次方的和差來表示x,如樣例中的2=3-1,4=1+3等,不難發(fā)現(xiàn),當(dāng)x除以3余1時,必然x要表示為x=a1+a2...+1,余2時x=a1+a2...-1,余0時不用1的砝碼.因此取x除以3的余數(shù),可以確定砝碼1用不用和用在天平的哪一邊.同理,判斷3的砝碼位置時,可先將x先除以3四舍五入,再除以3取余判斷.能用3的1至n次方的和差來表示x后,屏幕輸出再用一個

74、數(shù)組來處理就行了.,六、  小結(jié),這節(jié)課我們學(xué)習(xí)了數(shù)的進(jìn)制的概念，不同的進(jìn)制只是計(jì)數(shù)方法不同，它的值沒有發(fā)生變化，這對后面學(xué)習(xí)不同數(shù)的進(jìn)制的轉(zhuǎn)化起到了核心作用，正是利用這個原理我們輕松的實(shí)現(xiàn)了不同的進(jìn)制數(shù)表示的相互轉(zhuǎn)化，特別是對-R進(jìn)制數(shù)的學(xué)習(xí)，更拓寬了我們數(shù)的計(jì)數(shù)方法，加深了數(shù)的進(jìn)制概念的理解。最后數(shù)的進(jìn)制的應(yīng)用舉例，充分體現(xiàn)了解題思路的轉(zhuǎn)換，從而使問題變得更簡單，編程更容易。,第七節(jié) 線段性質(zhì),計(jì)算幾何學(xué)是研究幾何問題的算

75、法，在現(xiàn)代工程與數(shù)學(xué)，諸如計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人學(xué)都要應(yīng)用計(jì)算幾何學(xué)。青少年程序設(shè)計(jì)競賽中不時也出現(xiàn)一些簡單的幾何類型的試題。    我們將學(xué)習(xí)一些二維的(即平面上的)計(jì)算幾何學(xué)問題。每個輸入物體都用一個點(diǎn)的集合{Pi}表示(Pi=(Xi，Yi);0≤i≤n-1)這個點(diǎn)的集合描述了幾何物體的特征:如一組點(diǎn)或一組線段，或者一個多邊形按逆時針方向排列的頂點(diǎn)序列。輸出常常是有關(guān)這

76、些物體的問題的回答:如是否有直線相交，或者可能出現(xiàn)一個新的幾何物體，如頂點(diǎn)集合的凸包(包含這些頂點(diǎn)的最小凸多邊形),,從平面上取一固定點(diǎn)P1(P1=(X1，Y1))，從P1出發(fā)向某點(diǎn)P2(P2=(X2，Y2))引一條線段， 有方向且有長度，這樣的線段叫做有向線段，記作 P1P2，它的長度記作 P1P2=√(X1-X2)2+(Y1-Y2)2，點(diǎn)P1叫做它的始點(diǎn)，點(diǎn)P2叫做它的終點(diǎn);如果P1是原點(diǎn)(0，0)， 則我們把有向線段 P1P2簡記

77、為向量P2;如果不規(guī)定方向，則記線段為P1P2。,,下面，我們來討論三個問題。人們習(xí)慣使用平面解析幾何的方法求解，但由于計(jì)算過程中使用了三角函數(shù)和除法，使得運(yùn)算代價比較昂貴并且容易產(chǎn)生舍入誤差。例如確定兩條線段是否相交，通常是計(jì)算出形如y=kx+d的兩個直線方程，運(yùn)用除法找出直線的交點(diǎn)，并檢查該交點(diǎn)是否同時在兩條直線上。當(dāng)線段幾乎平行時，該算法對計(jì)算機(jī)中除法運(yùn)算的精確度非常敏感。而我們對這些幾何問題的計(jì)算，僅限于加、減、乘和比較運(yùn)算，不

78、可能產(chǎn)生計(jì)算誤差，而且算法簡潔高效。,,所有算法的程序描述中，我們對每個二維點(diǎn)的數(shù)據(jù)類型統(tǒng)一定義:    TYPE        POSTYPE=RECORD          X，Y：REAL；     

79、60; END;,,1.已知兩條有向線段P0 P1和P0 P2，對他們的公共端點(diǎn)P0來說，P0 P1是否在P1 P2的順時針方向 ？    首先，我們介紹一種叉積的概念，它是線段算法的中心。    考察下圖的兩個向量P1和P2,,我們把叉積P1*P2看作是由點(diǎn)(0，0)、P1、P2和P1+P2四個點(diǎn)圍成的平行四邊形的陰影面積。亦可把叉積定義為一個矩陣行列式  &

80、#160;                           ┌ X1，Y1 ┐       &#

81、160;           P1*P2=det└ X2，Y2 ┘                       

82、60;        =X1*Y2-X2*Y1                           

83、0;  =-P2*P1,,對原點(diǎn)(0，0)來說:      若向量P1在向量P2的順時針方向，則叉積P1ｘP2>0;      若向量P1在向量P2的逆時針方向，則叉積P1ｘP2<0;      若P2，P1兩個向量共線(方向可以相同或相反)，則叉積P2ｘP1=

84、0。    為了確定對公共端點(diǎn)P0，有向線段 P0 P1是否在有向線段P0 P2的順時針方向，我們僅需把原點(diǎn)平移至P0即可:,,,,即設(shè)向量P1'= P1-P0， P2'=P2-P0，其中          P1'= (X1'、Y1')=(X1-X0，Y1-Y0);

85、0;         P2'= (X2'、Y2')=(X2-X0，Y2-Y0);          P1'ｘP2'= (P1-P0)ｘ(P2-P0)=(X1-X0)(Y2-Y0)-(X2-X0)(Y1-Y0) 

86、60;  如果該叉積為正，則P0 P1在P0 P2的順時針方向;    如果為負(fù)，則P0 P1在P0 P2的逆時針方向;,,我們用函數(shù)multi(P1， P2，P3 )描述上述叉積的計(jì)算過程:Function Multi(Var p1， p2， p0 :PosType):Real;Begin  Multi := (p1.x - p0.x) * (p2.y - p0.y) - (p

87、2.x - p0.x) * (p1.y - p0.y)End;{multi},,2.確定兩條連續(xù)的有向線段P0 P1和P0 P2在P1點(diǎn)是向左轉(zhuǎn)還是向右轉(zhuǎn)   有了叉積的基礎(chǔ)，我們毋需通過對角∠P0 P1 P2的計(jì)算來確定兩條有向線段P0 P1和P0 P2在P1 點(diǎn)的轉(zhuǎn)向，而僅需要添加一條輔助的有向線段P0 P2， 并檢查P0 P2是在有向線段P0 P1的順時針方向還是逆時針方向。為了做到這一點(diǎn)，我們計(jì)算出叉積(

88、P2-P0)ｘ(P1-P0)=(X2-X0)(Y1-Y0)-(X1-X0)(Y2-Y0),,若該叉積為正，則P0 P2在P0 P1的逆時針方向，即P1點(diǎn)向左轉(zhuǎn)(見圖(a));    若該叉積為負(fù)，則P0 P2在P0 P1的順時針方向，即P1點(diǎn)向右轉(zhuǎn)(見圖(b));    若叉積為0，說明P0 P1和P2共線(見圖(c))。    顯然，我們可

89、以通過調(diào)用函數(shù)multi(P2，P1，P0)計(jì)算出叉積(P2-P0)ｘ(P1-P0)， 以確定兩條連續(xù)的有向線段P0 P1和P0 P2在P1點(diǎn)的轉(zhuǎn)向。,,3.確定兩條線段P1 P2和P3 P4是否相交    我們分兩步確定兩條線段是否相交    第一步:確定兩條線段是否不相交──快速排斥試驗(yàn)    先通過下述方法求出兩條線段的界限框(包含某線

90、段且四邊分別平行于X軸和Y軸的最小矩形)    線段P1 P2的界限框用矩形(^P1，^P2)表示，其左下角的點(diǎn)為^P1=(min(X1，X2 )，min(Y1，Y2))，右上角的點(diǎn)為^P2=(max(X1，X2)，max(Y1，Y2));    線段P3 P4的界限框用矩形(^P3，^P4)表示，其左下角的點(diǎn)為^P3=(min(X3，X4 )，min(Y3，Y4))，右上