2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩90頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第十二講 數(shù)論,,第一節(jié) 最大公約數(shù),首先,我們來回顧一下公約數(shù)和最大公約數(shù)的概念:如果d是a的約數(shù)并且也是b的約數(shù),則d是a與b的公約數(shù)。例如,30的約數(shù)為1,2,3,5,6,10,15,30; 24的約數(shù)為1,2,3,4,6,12,24; 因此24與30的公約數(shù)1,2,3,6。1是任意兩個(gè)整數(shù)的公約數(shù)。,,兩個(gè)不同時(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ù),在能同時(shí)整除a和b的數(shù)中取最大的。這個(gè)算法的時(shí)間復(fù)雜度為O(min(a,b)),當(dāng)min(a,b)較大的時(shí)候程序要執(zhí)行比較長的時(shí)間。    在引出新算法之前,我們先來證明一個(gè)被稱為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),,下述算法是一個(gè)直接基于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)用過程中第二個(gè)值參嚴(yán)格遞減, 所以算法不可能無限遞歸下去,在運(yùn)行終止時(shí)總能求出正確的答案。例如gc

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

7、* b即可。      生活中許多有趣的問題,可以運(yùn)用gcd定理來解答。,例12_1 狼找兔子,一座山周圍有n個(gè)洞,逆時(shí)針編號為0,1,2,...n-1。 而一只狼從0號洞開始,逆時(shí)針方向計(jì)數(shù),每遇到m個(gè)洞就進(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號洞就是其中的一個(gè)。,,再來看狼的運(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)算就是求一個(gè)數(shù)的冪ab對另外一個(gè)數(shù)n個(gè)模的運(yùn)算,即計(jì)算:ab mod n (a,b,n是正整數(shù))    由于計(jì)算機(jī)只能表示有限位的整數(shù),所以編程時(shí)模取冪的運(yùn)算要注意值的大小范圍,當(dāng)ab的值超過整數(shù)范圍時(shí),mod運(yùn)算便無法進(jìn)行。,

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

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

16、時(shí),效率很低。我們可以將b轉(zhuǎn)換為二進(jìn)制數(shù),然后從最低位b0開始,由右至左逐位掃描,每次迭代時(shí),用到下面兩個(gè)恒等式: 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成倍增加時(shí),算法保持d=ac mod n不變,直至c=b。時(shí)間復(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é) 素?cái)?shù),數(shù)學(xué)類的基本算法大多數(shù)屬于初等數(shù)論范疇,相當(dāng)大一部分與素?cái)?shù)有直接關(guān)系,因此素?cái)?shù)是一個(gè)很基本又很重要的內(nèi)容。  我們先來看看怎么判斷一個(gè)數(shù)是否素?cái)?shù)。素?cái)?shù)的定義為:如果一個(gè)數(shù)的正因子只有1和這個(gè)數(shù)本身,那么這個(gè)數(shù)就是素?cái)?shù)。根據(jù)定義,我們立即能得到判斷一個(gè)數(shù)N(大于1)是否素?cái)?shù)的簡單的算法:枚舉2到N-1之間的整數(shù),判

20、斷是否能整除N。該算法的Pascal代碼。,,program Prime_1; var x:integer; function IsPrime(n:integer):boolean; {返回n是否素?cái)?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不是素?cái)?shù)} exit; end; IsPrime:=true; {n是素?cái)?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)行比較長的一段時(shí)間,那么有沒有更快一點(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)上面的程序,得到另外一個(gè) 程序。容易知道這個(gè)算法的時(shí)間復(fù)雜度為O(sqrt(n))。,,program Prime_2; var x:integer; function IsPrime(n:integer):boolean; {返回n是否素?cái)?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不是素?cái)?shù)} exit; end; IsPrime:=true; {n是素?cái)?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ù)字序列,每行一個(gè)序列,第四節(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),每一個(gè)排列方式總

27、是在其前一個(gè)排列的基礎(chǔ)上通過順序逆轉(zhuǎn)而得到的.由此我們得到給定一個(gè)排列P1,P2,P3,……,Pn之后下一個(gè)排列的算法如下:,,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),得到下一個(gè)個(gè)排列,4321——〉4123,組合的生成,問題描述:    排列與組合是常用的數(shù)學(xué)方法,其中組合就是從n個(gè)元素中抽出r個(gè)元素(不分順序,且r<=n),我們可以簡單地將n個(gè)元素理解為自然數(shù)1,2,…,n,從中任取r個(gè)數(shù)。,,輸入:    一行兩個(gè)自然數(shù)n,r(1<n&

31、lt;21,1<=r<=n)輸出:    所有的組合,每一行組合占一行且其中的元素按由小到大的順序排列,每個(gè)元素占三個(gè)字符的位置,所有的組合也按字典順序。樣例:,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個(gè)元素的組合用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時(shí),其中下標(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,由此,可以得到從一個(gè)組合到其下一個(gè)組合的算法如下:    

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的下一個(gè)組合234,第五節(jié) 因式分解,因式分解的算法很簡單,模擬手工分解的過程,我們得到分解

36、n的算法:枚舉所有不大于n的所有素?cái)?shù),判斷這些素?cái)?shù)能整除n多少次。判斷2到n是否素?cái)?shù),總共要計(jì)算sqrt(2)+sqrt(3)+sqrt(4)…+sqrt(n)<=n*sqrt(n)次,因此算法的時(shí)間復(fù)雜度可以粗略地認(rèn)為是O(n*sqrt(n))。,,事實(shí)上,我們有更好的算法。先看一個(gè)顯而易見的結(jié)論:如果p是能整除n的所有大于1的數(shù)中最小的,那么p是n的一個(gè)素因子?;谶@樣一個(gè)結(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是一個(gè)素?cái)?shù)} begin inc(pnum); {找到一個(gè)新的素因子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個(gè)月,則是12進(jìn)制,一周有7天,則是7進(jìn)制,等等。實(shí)際都是我們?nèi)藶橐?guī)定的,而平常我們用的最多的最習(xí)慣的是10進(jìn)制,是因?yàn)槲覀児湃肆粝聛淼呢?cái)富,而古人是因?yàn)橛?0個(gè)手指便于幫助計(jì)數(shù)。需要強(qiáng)調(diào)的是任何一個(gè)值都可以用任何一種進(jìn)制描述,但它的值是不變的,正如我們今天在一周中可以描述為星期幾,在一月中描述為多少號一樣。,,使用R進(jìn)

41、制計(jì)數(shù)的規(guī)則:1、  只使用R個(gè)基數(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ù)這個(gè)轉(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,,兩邊同時(shí)除以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,,兩邊同時(shí)乘以R,等式兩邊的整數(shù)部分和小數(shù)部分分別相等,顯然右邊的整數(shù)部分就是a-1,再去掉等式的整數(shù)部分,然后進(jìn)行相同的處理,就求得了a-2,一直進(jìn)行下去,直到左邊的值為0時(shí)或到要求的精度為止,這樣就將十進(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ù)。任何一個(gè)整數(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)然這是一種方法,但我們完全可以不必這樣做。不妨以一個(gè)具體實(shí)例來討論轉(zhuǎn)化規(guī)律,如:,,(4325)6=4*63+3*62+2*61+5

49、*60將等式右邊改寫成一個(gè)-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是一個(gè)0到5之間的數(shù),顯然是不能成立的,要相等

50、X只能等于-2,而-2不能做為-6進(jìn)制的基數(shù),解決這個(gè)問題就向高位借一個(gè)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個(gè)基數(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)軌問題     圖中兩條軌道連到一個(gè)鐵路轉(zhuǎn)軌處,形成一個(gè)鐵路轉(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時(shí),在右邊軌道可能得到的所有車皮編號順序。,分析:,這個(gè)例子是典型的棧應(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次,恰好一個(gè)字節(jié)8個(gè)位;4、由于必須先進(jìn)棧才能出棧,故在二進(jìn)制的每一位前,1的個(gè)數(shù)總不少于0的個(gè)數(shù),否則轉(zhuǎn)軌內(nèi)無車可出。這樣就巧妙地利用數(shù)的進(jìn)制將原問題轉(zhuǎn)化為一求0至255內(nèi)的二進(jìn)制數(shù)中符合相應(yīng)條件的數(shù)的個(gè)數(shù)。,,,例12_3 城市街道   

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

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

58、。m、n從鍵盤輸入。,,分析:由題意已知:(1)第i個(gè)盒中放入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í)際上就是一個(gè)進(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:求每個(gè)盒子中的球數(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ù)。任何一個(gè)整數(shù)n都可以表示成, 其中 ai∈[0,p-1],ai是整數(shù)。并且ak0?,F(xiàn)在,你需要讀入一個(gè)整數(shù)n,(1<=|n|<=10100)。輸出它的-p進(jìn)制表示法。,,[輸入]第一行有一個(gè)正整數(shù)P(

62、2<=p<=100)。第二行有一個(gè)整數(shù)n,如果它是正數(shù),前面沒有符號,否則他前面有一個(gè)負(fù)號“-”。[輸出]       輸出有兩行,第一行是一個(gè)數(shù)k。       第二行有k+1個(gè)數(shù),表示a0、a1……ak,數(shù)字之間用一個(gè)空格分開。[輸入樣例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)制一樣,可以按照每一次確定最后一位的方法來確定這個(gè)p進(jìn)制數(shù),方法可以這樣,設(shè)-P進(jìn)制數(shù)為n,那么求出一個(gè)數(shù)a,(0<=a<p),使得n-a是p的倍數(shù)。顯然,這樣的數(shù)只可能有一個(gè)

65、,所以這個(gè)a就是-p進(jìn)制數(shù)的最后一位。然后,就可以遞歸的把(n-a)/(-p)=-(n-a)/p化成-p進(jìn)制數(shù)后,然后把a(bǔ)放到這個(gè)數(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ù),即用一個(gè)指針,指針前面的是p進(jìn)制數(shù),指針后面的就變成了

66、-p進(jìn)制數(shù)。還是看-100,由于是個(gè)負(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ù)位都滿足這個(gè)條件,就相當(dāng)于化成了-p進(jìn)制數(shù)。上面兩種方法雖然表面上不同,但是最后得到了相同的結(jié)果。往往作題時(shí),總是會往地一種方法想,但其實(shí),換個(gè)思路,又會得到一種解法。,,程序設(shè)計(jì)中可采用多種數(shù)學(xué)方法,恰如

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

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

70、60;       x=1稱出的方案為1:1      輸入:n,x(n為砝碼個(gè)數(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時(shí)砝碼重量最優(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時(shí),必然x要表示為x=a1+a2...+1,余2時(shí)x=a1+a2...-1,余0時(shí)不用1的砝碼.因此取x除以3的余數(shù),可以確定砝碼1用不用和用在天平的哪一邊.同理,判斷3的砝碼位置時(shí),可先將x先除以3四舍五入,再除以3取余判斷.能用3的1至n次方的和差來表示x后,屏幕輸出再用一個(gè)

74、數(shù)組來處理就行了.,六、  小結(jié),這節(jié)課我們學(xué)習(xí)了數(shù)的進(jìn)制的概念,不同的進(jìn)制只是計(jì)數(shù)方法不同,它的值沒有發(fā)生變化,這對后面學(xué)習(xí)不同數(shù)的進(jìn)制的轉(zhuǎn)化起到了核心作用,正是利用這個(gè)原理我們輕松的實(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ì)競賽中不時(shí)也出現(xiàn)一些簡單的幾何類型的試題。    我們將學(xué)習(xí)一些二維的(即平面上的)計(jì)算幾何學(xué)問題。每個(gè)輸入物體都用一個(gè)點(diǎn)的集合{Pi}表示(Pi=(Xi,Yi);0≤i≤n-1)這個(gè)點(diǎn)的集合描述了幾何物體的特征:如一組點(diǎn)或一組線段,或者一個(gè)多邊形按逆時(shí)針方向排列的頂點(diǎn)序列。輸出常常是有關(guān)這

76、些物體的問題的回答:如是否有直線相交,或者可能出現(xiàn)一個(gè)新的幾何物體,如頂點(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。,,下面,我們來討論三個(gè)問題。人們習(xí)慣使用平面解析幾何的方法求解,但由于計(jì)算過程中使用了三角函數(shù)和除法,使得運(yùn)算代價(jià)比較昂貴并且容易產(chǎn)生舍入誤差。例如確定兩條線段是否相交,通常是計(jì)算出形如y=kx+d的兩個(gè)直線方程,運(yùn)用除法找出直線的交點(diǎn),并檢查該交點(diǎn)是否同時(shí)在兩條直線上。當(dāng)線段幾乎平行時(shí),該算法對計(jì)算機(jī)中除法運(yùn)算的精確度非常敏感。而我們對這些幾何問題的計(jì)算,僅限于加、減、乘和比較運(yùn)算,不

78、可能產(chǎn)生計(jì)算誤差,而且算法簡潔高效。,,所有算法的程序描述中,我們對每個(gè)二維點(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的順時(shí)針方向 ?    首先,我們介紹一種叉積的概念,它是線段算法的中心。    考察下圖的兩個(gè)向量P1和P2,,我們把叉積P1*P2看作是由點(diǎn)(0,0)、P1、P2和P1+P2四個(gè)點(diǎn)圍成的平行四邊形的陰影面積。亦可把叉積定義為一個(gè)矩陣行列式  &

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的順時(shí)針方向,則叉積P1xP2>0;      若向量P1在向量P2的逆時(shí)針方向,則叉積P1xP2<0;      若P2,P1兩個(gè)向量共線(方向可以相同或相反),則叉積P2xP1=

84、0。    為了確定對公共端點(diǎn)P0,有向線段 P0 P1是否在有向線段P0 P2的順時(shí)針方向,我們僅需把原點(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'xP2'= (P1-P0)x(P2-P0)=(X1-X0)(Y2-Y0)-(X2-X0)(Y1-Y0) 

86、60;  如果該叉積為正,則P0 P1在P0 P2的順時(shí)針方向;    如果為負(fù),則P0 P1在P0 P2的逆時(shí)針方向;,,我們用函數(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的順時(shí)針方向還是逆時(shí)針方向。為了做到這一點(diǎn),我們計(jì)算出叉積(

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

89、以通過調(diào)用函數(shù)multi(P2,P1,P0)計(jì)算出叉積(P2-P0)x(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)),右上

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論