计算机算法.pdf

文档介绍：该【计算机算法 】是由【fangjinyan2017001】上传分享，文档一共【38】页，该文档可以免费在线阅读，需要了解更多关于【计算机算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.


(Algorithm)


!"#$%
§1&'()
1
*(Algorithm)

%+,-./
0,12,34./256
$7.89%
:;<
=>?,***@AB
C;<;<CDE<7
8

8FGHIDE<70JKLMN5OPQ%;<10CRS
T
,UVW
IXDE<7%;<1Y,Z[\I]^G_`a1b
cd`a1%cd`a1CDeTXfghcdi;< ghj
***@klmbno%G_`a1CeT,./pq89rs
k.t;Juvw4xH
t;0C1%
1C;<1&y%z{|
&y}
~D4“€
lL.”“;<Cjƒ`T„…“;<
0Cjgh†‡`Tlm]bcd&yƒˆ‰pqlw%”Š
‹Œ;<CŽlw%
ghcdC;<1
&y%;<C‘’ghpqgh‘’
89_;<Cbghcd“”•–
—
1976
˜™4L“;<=+ghcd”()%HIžlŸghcdC
 ¡¢£1,ghcd¢f%
¤¥
;<¤6¦§pq¨©¤¥
]ª
]«pq%
¬­
;<1®¯(]Žb’p)p¢±
Ta%²³´µ¶
20·¸50¹60˜€ºhash»¼W<
½¾¿j-%
2TÀ
Á^ÂÃÄÅ\IÆÇÈ
Æ1U
IgaÉ]Ê%
Ë̀žÈxn+l=(xn+a/xn)/2,ºÁÈ
*xÍÎÏxo
:ºÐ|x2-a|<eÑÒÓ
Ôx=(x+a/x)/2,Ò::.
ÓÕ4X
Æ2Um,nÖםØg
ËÙÒÚÛÜUÝÞgm,nÖםØgºÁÈ
*r=mmodn
:ßà!ár=0
m=n
n=r
r=mmodn
ÔÕ4n
ÛâÅ4C.]ãäeåJuvwCæ
‡89çK

It;H‡89èj
é34
ê.%
•–Websterë´jAlgorithmëìÁD4ÈCjí******@./

Igt;89îïïZð†
Iñò?ó%«ôÀõ
I
0C_L./
Iö„†
÷ø8t;%
•–
—34L
ùõŸÈ
IC
I
úûÑüXýîBûÑûTL
I./†
ê`Tþ<7%
3`ÿ

Knuth

5
1)(finiteness)
 !"#$%&'( )*
+,-(./(0 12345678#9:( ;<=>?@AB#
C;
@DC)E=FG#
2)HI(definiteness)
 ;
JKLH
IM(<NOPQMRSTUV
WX#Y“[X,YUC\]^_`”(bc^ `dbc_ `(e
'fghY“ijkXl^8”(l^8(mnbQo(e'f#
 ;(pqrs<f
<NO>?#
3)=](effectiveness)
 ;
JKbV5?
(tVuWvVw]
xyz{#|
Y ;<=>?}c~C5C€+‚ƒC„…†‡ˆ‰Š#
4)Œ(input)
 NO}tQŒk#
5)Œ>(output)
 tQŒ>#:.
‡Ž‘(’“‚ 4\
”• b–HIM
—˜™
/(pš™/›I4—˜
z{(œžŸ „¡¢
W#
4 W£¡¢
¤¥
¦§
¡¢¨©Vuvª«¤¥
1)¬I¡¢p¤¡¢i>
b­.
¬®#|Y¯°¡¢(±²¡
¢(³´­µ¶¡¢(·¸¹º¡¢ˆ#
2)»¼½¡¢p¤¡¢b V=
W;„>»¼W#|Y„¾C
¿8(»À²Á¡¢(»ÂŸ-ᢈ#
3)¾C¡¢p¤¡¢bIÄ"ÅÆ„C8W(|Y†Ç„‡,
ÉÊ`(¾C„8ˆ#
5 ËÌ+Í
 ËÌ+ÍËÌ+ͨ©uvª†Î
1) Ð ÐbÑÐ>=ÒÓHW£¡¢
 #ÔÕÖ
×( ÐdÑØ =ÒÙÚÛo
PÜÝ*(`]ÞßÛà#áâ(
ãäÆåæ
çß(dÑÐ>ÍèéWÍèêÇRÍèëì
 #
2) uí uí
îïbð
`])*RÙÚ
Ý*(uíR
ñÛò«
¼ó#
3)Vé‘ôõ
 ËÌ;(ö“
ËÌ÷ø;V鑏#
’“'¡¢ bVW
b'VêùǶ(`])*ú
ÒûRPÜÝ*úÒ¨
ÅÆü‚îýNO
ŒKVþ>ÓH
ÿ

§2
1







!"#$%&'()*

)+
,- ./ 0123456789.:;<=>&)
9
)?
***@ABCDEFGHI12
12J-
KLMN-OPQRKLSTUVWXYZ[\KLL)
]^
_`
QRKLA_abAc_d\e
K=>ff&Ac_

`
Ag_`
hV)+i?
)MN
ejklm"!\no9

1HbpR)qrH(bruteforcemethod)W5s(divideandconquer)W
u#(greedymethod)Wvwxy(dynamicprogramming)W{|(back:.
tracking)>5}~(branchandboundmethod)W€(probabilistic
algorithm)‚ƒ(approximatealgorithm)W„xy….
2b‡ˆ
1)>
‰Š‹ŒŽ


ej‘- 
’“”9
•–—9˜?™š-(›œožŸ”Ÿœ
 ¡C-34
¢£ 
Ž¤)¥¦¤)§¨

©•ª«¬
ª«k­®-›n`¯°±²³ª´µ¶·`
¯°›a¸¯°GR¹nGRº»¼„

½9¹º»GR¼„)?
¾E19
•­¿®¤hÀ
Á‡
`¯°Ãa¸¯°"¤)DE]ÄÅ¯°…

2)78;<
Rd
DE)ÆÇ.:;<
ÈÄ)É`ÊË
q̺ÇÆ

.:oÍœÎϤ)µ9Ѓ
hÑÒÎ78;<Ó
C-OÔ;<¤ÕÖ9
×-™šV¤ØŠÙڟ”WŸÛR
d=>;<¤)ÜÝ
Þk`;<ßàº)*`
©•ª«¬

hRáâ¶ã78;<•á1äh78áåæçè\GRçè

á1ª«¬
¯°éæá
3)





©•ª«
¬
hÀêëìQ)hVíîïð
GR·"ßàGRº»
ñOPÀò
q
óôõQ)hVŸ”
ökXŠ\‚ƒ"’ßà
÷ŠøÇù./oÍ
úßàÇùûü:.
4)56
`
h)ý &)A_
*
1256
Q‘®þÿ



5)



!"!#$%&'()*+
,-.
6)/0
123
456789:12#;

123<=>?&***@A1
23 BC ***@A12
D48:12#;EFGHIJK
J1MNOA=1012,B=-1012,C=l,
A+B+CP
Q7?&
RSST7UTV!W XYHZ
[:\]#;
1)A+B+C=1012+(-1012)+1=1
2)A+C+B=10l2+l+(-1012)=0
^_ `aIbcT:12#;
J2dbX?-(1015+1)X+1()15=OHI
1)efg&dhi
A=1
B=-(1015+1)
C=1015
D=SQRT(B*B-4*A*C)
Xl=(-B+D)/(2*A)
X2=(-B-D)/(2*A)
#;jOXl=1015,X2=0
2)g&klm@
A=1
B=-(1015+l)
C=1015
D=SQRT(B*B-4*A*C)
Xl=(-B+D)/(2*A)
X2=C/(A*X1)
#;jOXl=1015,X2=l
^_ `*IbcT:12#;
nCoj

pqCTr 7
456st
pqu
v wxyzuv{|:.
}>
123 ~C€{/0l‚
123ƒ„
_nH…\†‡*ˆ Bo~60‰
123Š_T‹Œ ?
Žb
Š_C6b/0123&‘’b“‘’/0C12
 ”•|q–
—˜™123
1979š ›œBoyeržŸ 
Moore¡¢ £&¤!¥¦§0
‰123nZb¨!¥¦§©ª¦«!A
m@¬0‰#­®
ƒ ¯°0‰+±B&‚+±0‰123²³*I´µ-.
§3
¶·3¸¹
7
º6st¶·3¶·3
»¶·3  ¼
?½
6¾ ¿&
ÀÁ6ÂÃ;*I
¼•Ä ÅÃÆǚÈ
ɍÊ˚ ‚
ÌÍÎÏ°&ÐPJà ÑÒӝCramerÔÕCdÖ
×3Ø!b"ÙI!¥b BC ÚÔÕ7dÖ×3Ø!b"

 ”¼{Û?½܍C\8fÝoÚ ”st
T
Þ3 ºßstà­@¼
¸¹á
Vâ㸹á
?½ÀÁ»




1
¶·q
¶·q6C䶷q
Timecomplexity
»¶·q
Space
complexityo
¶·qCä

Rå æ
ØÐ
¶·qCä
½6¿&Áç»|èXY6éA

¶·q
j°8Åêëìíîï*I
V⠔q*I
Rå \ðß
‚©g&
7'(ñ} òóºß©
{󙛚֖
}jÚ –
&
”¼{Û?½øù
¼ú!ƒq

Rå
€û*I
üýõZ
%þøù
ßÿ








!"#$%&'()*+,-x./$01“x(2”4-

$2
4-*+564"7#$%
89:;<
)$01“
8<”4-
"
> 

?@ABC$DEFGHBC"
-I2JK$LMNOGHEFP QR"#$
89:;<$


9:SBTCU"VWEFXYZ[\GH$9:.
:<^S_\GH$`abX^c\GH"
d>e$564f^ 

g\$


hEFGHnj$k$lmno\-f(n)"
Mstuv&uGHEF$w&
 

xt
uyzBC"#$''%c\-n&'()*+,-x./”$}f^~
€$#‚yzx,ƒ&./;N$„P &
2$}yzx
,ƒn./;N$…P n
2"†‡ˆ$N&‰N&EFGH,


%?Nyz‹ŒŽDhT"‘?’“w&”yz
‹Œ•–—g$˜‡XXf^™gQR564"
1)›œaQR(AverageBehavior)
^¨”tuyz

©ª›œ,g\564"
A(n)=¬p(x)®T(x)
xGDn
)
P(x)x—³´µ"
T(X)yz-x‹Œ

"
Dn>B’yz·¸"
A(n)
›œ
"
nEFGH"
2)º»‹Œnoa(Worst-casecomplexity)
W(n)=Max{T(x)}
xGDn
)
Dn>B’yz·¸"
T(x)yz-x‹Œ

"
W(n)º»‹Œnoa"
n:EFGH"
&ÈgÉ$W(n)52ÊA(n)5™Ë$W(n)8Ì͗I
564Î$ÏA(n)ÐBÑ^Ò,"
`ab~€(SequentialSearch)
yz&'(L(n),*+×./x,y—ƒ&
ÑØL(j)=*}
x?%L(n))$y—j=0"
#
j=l
while(j<=n)and(L(j)Wx)doj=j+l:.
if(j>n)thenj=0
outputj
áMâ㛜aQR
ä
./24-
$B:
åx%L(n))´µ-q,xOs¨L(k)-O´µ$B:
shB
}q=l$B
k›œLç*()&è./"
}q=,B
k›œLç*()3/4./"
áMâ㺻‹ŒQR
º»‹ŒQR&Èäîs$ï?hEFA"
2noaðPa
&>…lmñbò-EFGHnjT(n),ó-lmn
oa"
#‚ô%
õXc,öÑØ÷n>nol$Bó
T(n)hO(f(n))"‡lf(n)hT(n)ùcµ&Î"
X^f(n)B:
ϑB#CU
úû$„B÷nüýl$CUþÿ
:.
1


log2nnnlog2nn2n32n
010112
122484
248166416
382464512256
41664256409666536
5321601024327684294967296
3


!"#$%&'&(

)*+,-)*+.
/012
345"#6789:;<=>?@
3
ABC+D:;E2FG
HA5
IJ!
3C+?***@10KA5
LMNO6PQR
S(TUVW?***@L17KXY
3C+?***@1ZKA5
LMN
O6PQRS(TUV[W?***@
\]^_`ab
)*+6c(db
345"#6
7!ef"#45gh
ijklmno
12o
,
H;qr>stuv
w
2L1x,1yz{h
F6QRS(TUV

3C+?@|6P
3C+?***@10K}
)*+QRS(TUV6PQRS(TUV
1slh1slh

A2nlog2n62746213337805852617201193909231
A3n21000600003162189736
A4n3100**********
:.
~2
€ tu
‚ƒ
„…†‡Hˆ‰Š
‹g"#W;1Œ1b
Ž9‘’“”•%QRH”–"#—˜™š›
œ7VbŽ
€ bŽ
€ ;1
žŸ ¡;lmF
žŸ¢£¤6¥q+¦§,
žŸŸ¨1©ef"#Fž
ٻ
e«[¬
3
,­žQR
®®H¬¯°
H
3
€ „±htu€ ²e³´
1)µ¶(Enumeration)
µ¶·¸¹¶ªtuº»¼ŒF4"#½¶F61
¾eh¿eÀÁÂÃÄÅ#ÆÇBÈÉeÄÅ#ÆÇB
Ê#Æef4ÈËÄÅ#ÆÇB"#Ì4
Í1“ÏÐ"#”ҀÓоW3ÔÕоW2ÔyоÖW1Ô×
›100ÔØÙ100WÐ"6ÙÓÐ¥ÕÐ¥yÐÚgÛWÜ
12Ý"#½`ށßÒ
X+Y+Z=100
3X+2Y+Z/2=100
àáß"#àâ"#µ¶89ã
E¯Ò
for(x=0äx<33äx=x+l)
fbr(y=0äy<50äy=y+l)
{z=100-x-yä
if(3*x+2*y+z/2=100)
print(x,y,z)
)
return
Í2æç—m,nS(Óè
kæ`m,n„sy€Ê3m,nÓèk6éꦧÊ
[1,t],S(Óèç—[L]¦§zL]¦§zë(ìyµ¶Ãì~e
fÓèXÊFæ
If(m>n)t=nElset=m
While(mmodt,ornmodt#0)t=t-l
Return(t)
µ¶ehíM12rá4¦§îµ¶ïY
µ¶e«'𵶊.snñµ¶ò¦§ó}°³´"
#„‹g[ïôµ¶45:.
2)ö÷(Recurrence)
ö÷ÿ



!"#$
%!&'()*+,-./01
!23456789
:1<45=>?@*
ABCD-FGHI#$&J21L@*MN!OP
&JL@*Q*+R
0S=#$
In+=l/n
In=l/n-5In.|
J!
L#$_`a@*3hlcR01In3/def
0<In<
7<
k!R0145J21L@*5:
ABm#$45no1pq
o1
nInnIn
-

-

-

'17-
7-
-
9-
:.
|o1RS}
m#$45e~€
J!‚7ƒ|€
„…5†‡ˆ…InIe€
45‰45Š‹e€
JŒ€@Ž
‘…’“n”B#$

•–—`˜3120
|@*#$R,
0<In<n-1
š5›05In-I<5+5In-1<6In-1
AB#$05In.|<l/n<6In-1
œ0<In-1<
|ž0<Lo<
120Ÿ437
|ž01¡¢L5:
45no2pq
o2
nInnIn

-1
-1
-1
-1
'1
'1
-1



|oRS}£¤120e
€
¥Io€~¦
§¨©ª€«¬
«¦120€7I€5­0†
|ž•–RS}1
5®¯°±5²³:.
:2´
L2aµ¶·
´
L2µ¶·'(RS¸¹7´¶‹
x2-a=0
'(
ABCDR0#$
Xn+l=(Xn+a/Xn)/2
05n=<
(1)&Xº3X0
(2)nabs(x2-a)<s,x»7p´
¼7
L¦½2
(3)¾x=(x+a/x)/2
¸¿
ÀiÁ2Â$<
rootsquare(a)
{x=a;
while(abs(x*x-a)>e){x=(x+a/x)/2;}
print(x)
:3´ÃN2m,n#Ä2
7…ÅƶÇ
?ÈÉÊmËnAB̸ÍR0´ÃN2m,n#
Ä2#$<
mo=m,no=n
mi=nj.|,ni=mi-imodg
ÎÏni=0,mi»7p´#Ä25n=:
factor(m,n)
{while(n!=0){nl=mmodn;
m=n;
n=nl;
print(m);:.
3)-(Recursion)
-!ÐÑ5
ÒÓÔ¶n
LŠ‹ÎÕÖÕ×ØB%ÔÙ,
ÚmŠ‹!-2ÛÜeÝÞ-ßÁ2
:1<´2nàá
2nàá-ß7<
n(n-l)!n>l
1n=l
factor(n)
{if(n=l)thenf=l
elsef=n*factor(n-l)
retum(f)
}
-5ã-ßÎÕ&ä
åæç8èé
-®¯eê
¾cëìí©ª=îï0fð?ñòó/ôõ
:2ö÷ø(Ackermann)Á2
ö÷øÁ2ßùçúœ2a,b,cÜ
e
b+1a=0
ba=landc=0
Ack(a,b,c)=0a=2andc=0
1a=3andc=0
2a>=4andc=0
Ack(a-1,Akc(a,b,c-1),b)a>0andc>0
ö÷øÁ2ù-Æ!
Lû`:ü
%ýk“çÿ


”


Ack(a,b,c)
{if(a=0)acka=b+l;
elseif(c=0){switcha
case1:acka=b;
case2:acka=0;
case3:acka=l;
default:acka=2;
)
elseacka=ack(a-l,ack(a,b,c-l),b)
retum(acka):.
3
(HanoiTower)19
!Bramah"#$%&'()*+,&-./012234567+64
&8&9:01;<&-./=><&-./?***@ABC=<&DE:
1FGHI1/JKLMN,&-.OPQRS01=TUVW6XYZ
[*\]652^_`*ab%cdefg&hijklmIno,
VqrstuvwO=x?yz]=x
B{`64&1.|=x}B6
264-1=
~L€‚ƒ„()17…I
†‡ˆ‰Š<&€‹ŒŽ‘Œ’r(HanoiTower)
g6<&”•

–—%,&-.˜™š›r1,2,3,%N&œI:žˆŸ ¡¢I/
:£¤H1™-./¡œI:˜™r1,2,¥N,¦§+1™-.
/1.=2™-./L3™-.qrPQ?***@ABC=<&DE:1
FGHI1/Jš¨©¢
(1)ªN=l,œ«¬1™-.=2™-.­
(2)ªN>1,— ®N-1&1.¬1™-.=3™-.­®¯V<&1.
¬1™-.=2™-.­\— ®N-1&1.¬3™-.=2™-.
©°±+N-1&1.¬1™-.=3™-.\®¯V<&1.¬1™-
.=2™-.­¯V+N-1&1.¬3™-.=2™-.g²W³´
^µ¶=xN-1&1.~=xN&1.z
 ©¢
honoi(n,x,y,z)
{if(n=l)move(x,l,z)
else
{honoi(n-l,x,z,y)
move(x,n,z)
honoi(n-l,y,x,z)
honoi(n,x,y,z)·¸n&1.¹=x?y¬x-=z-,yrPº-
move(x,n,z)·¸®Nn™-=z-:.
»¼½¾

Ack()
{while(l)
{if(a=Oorc=0)
{if(a=0)t=b+l;
else{switcha
case1:t=b;
case2:t=0;
case3:t=l;
default:t=2;
}
if(top>0){(a,b,c)=s(top)
top=top-l;
a=a-l;
c=b;
b=t­
)
elsebreak;
}
else{top=top+l;
s(top)=(a,b,c);
c=c-l;
}
)
return(t)
)
š¨
1)ªa>0Ec>0,y®(a,b,c)¿ÀÁÂc=