13.3. SORTINGALGORITHMS
233
def merge(lst1, , lst2, , lst3):
# merge sorted d lists s lst1 and lst2 into lst3
# these indexes s keep p track of current position n in n each list
i1, i2, i3 3 = = 0, 0, 0
# all start at the front
n1, n2 = len(lst1), , len(lst2)
# Loop while e both h lst1 and lst2 have more e items
while i1 < < n1 1 and i2 < n2:
if lst1[i1] ] < < lst2[i2]:
# top of lst1 1 is s smaller
lst3[i3] = = lst1[i1]
#
copy it t into current spot in lst3
i1 = i1 1 + + 1
else:
# top of lst2 is s smaller
lst3[i3] = = lst2[i2]
#
copy it t into current spot in lst3
i2 = i2 2 + + 1
i3 = i3 + 1
# item added to o lst3, , update position
# Here either r lst1 1 or lst2 is done. One of f the e following loops will
# execute e to o finish up the merge.
# Copy remaining g items s (if any) from lst1
while i1 < < n1:
lst3[i3] = = lst1[i1]
i1 = i1 + 1
i3 = i3 + 1
# Copy remaining g items s (if any) from lst2
while i2 < < n2:
lst3[i3] = = lst2[i2]
i2 = i2 + 1
i3 = i3 + 1
Withthismergingalgorithminhand,it
'
seasytoseethegeneralstructureforadivide-and-conquersorting
algorithm.
Algorithm: mergeSort t nums
split nums into o two o halves
sort the first t half
sort the second d half
merge the two o sorted d halves back into nums
Lookingatthestepsinthisalgorithm,thefirstandlastpartslookeasy. Wecanuseslicingtosplitthelist,
andwecanusethemergefunctionthatwejustwrotetoputthepiecesbacktogether. Buthowdowesort
thetwohalves?
Well,let
'
sthinkaboutit. Wearetryingtosortalist,andouralgorithmrequiresustosorttwosmaller
lists.Thissoundslikeaperfectplacetouserecursion.MaybewecanusemergeSortitselftosortthetwo
lists.Let
'
sgobacktoourrecursionguidelinesandseeifwecandevelopaproperrecursivealgorithm.
Inorderforrecursiontowork,weneedtofindatleastonebasecasethatdoesnotrequirearecursive
call,andwealsohavetomakesurethatrecursivecallsarealwaysmadeonsmallerversionsoftheoriginal
problem. TherecursioninourmergeSortwillalwaysoccuronalistthatishalfaslargeastheoriginal,
sothelatterpropertyisautomaticallymet. Eventually,ourlistswillbeverysmall,containingonlyasingle
item.Fortunately,alistwithjustoneitemisalreadysorted!Voil´a,wehaveabasecase.Whenthelengthof
thelistislessthan2,wedonothing,leavingthelistunchanged.
Givenouranalysis,wecanupdatethemergeSortalgorithmtomakeitproperlyrecursive.
Add page to pdf preview - insert pages into PDF file in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Guide C# Users to Insert (Empty) PDF Page or Pages from a Supported File Format
adding page numbers pdf; adding page numbers pdf file
Add page to pdf preview - VB.NET PDF Page Insert Library: insert pages into PDF file in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
Easy to Use VB.NET APIs to Add a New Blank Page to PDF Document
add multi page pdf to word document; adding page numbers in pdf file
234
CHAPTER13. ALGORITHMANALYSISANDDESIGN
if len(nums) > > 1:
split nums s into o two halves
mergeSort the e first half
mergeSort the e second half
merge the e two o sorted halves back into nums
WecantranslatethisalgorithmdirectlyintoPythoncode.
def mergeSort(nums):
# Put items s of f nums in ascending order
n = len(nums)
# Do nothing g if f nums contains 0 or 1 items
if n > 1:
# split t into o two sublists
m = n / 2
nums1, nums2 2 = nums[:m], nums[m:]
# recursively y sort t each piece
mergeSort(nums1)
mergeSort(nums2)
# merge e the e sorted pieces back into original l list
merge(nums1, nums2, , nums)
Iknowthisuseofrecursionmaystillseemabitmysterioustoyou.Youmighttrytracingthisalgorithmwith
asmalllist(sayeightelements),justtoconvinceyourselfthatitreallyworks. Ingeneral,though,tracing
throughrecursivealgorithmscanbetediousandoftennotveryenlightening.
Recursioniscloselyrelatedtomathematicalinduction,anditrequiressomethingofaleapoffaithbefore
itbecomescomfortable. Aslongasyoufollowtherulesandmakesurethateveryrecursivechainofcalls
eventuallyreachesabasecase,youralgorithmswillwork. Youjusthavetotrustandletgoofthegrungy
details.LetPythonworryaboutthatforyou!
13.3.3 ComparingSorts
Nowthatwehavedevelopedtwosortingalgorithms,whichoneshouldweuse?Beforeweactuallytrythem
out,let
'
sdosomeanalysis. Asinthesearchingproblem,thedifficultyofsortingalistdependsonthesize
ofthelist.Weneedtofigureouthowmanystepseachofoursortingalgorithmsrequiresasafunctionofthe
sizeofthelisttobesorted.
Takealookbackatthealgorithmforselectionsort.Remember,thisalgorithmworksbyfirstfindingthe
smallestitem,thenfindingthesmallestoftheremainingelements,andsoon. Supposewestartwithalist
ofsizen.Inordertofindthesmallestvalue,thealgorithmhastoinspecteachofthenitems.Thenexttime
aroundtheouterloop,ithastofindthesmallestoftheremainingn
1items.Thethirdtimearound,thereare
n
2itemsofinterest.Thisprocesscontinuesuntilthereisonlyoneitemlefttoplace.Thus,thetotalnumber
ofiterationsoftheinnerloopfortheselectionsortcanbecomputedasthesumofadecreasingsequence.
n
n
1
n
2
n
3
1
Inotherwords,thetimerequiredbyselectionsorttosortalistofnitemsinproportionaltothesumofthe
firstnwholenumbers.Thereisawell-knownformulaforthissum,butevenifyoudonotknowtheformula,
itiseasytoderive.Ifyouaddthefirstandlastnumbersintheseriesyougetn
1.Addingthesecondand
secondtolastvaluesgives
n
1
2
n
1.Ifyoukeeppairingupthevaluesworkingfromtheoutside
in,allofthepairsaddton
1.Sincetherearennumbers,theremustbe
n
2
pairs.Thatmeansthesumofall
thepairsis
n
n
1
2
.
Youcanseethatthefinalformulacontainsann
2
term. Thatmeansthatthenumberofstepsinthe
algorithmisproportionaltothesquareofthesizeofthelist. Ifthesizeofthelistdoubles,thenumberof
stepsquadruples. Ifthesizetriples,itwilltakeninetimesaslongtofinish. Computerscientistscallthisa
quadraticorn-squaredalgorithm.
C# WinForms Viewer: Load, View, Convert, Annotate and Edit PDF
PDF Annotation. • Add sticky notes to PDF document in preview. Add text to PDF document in preview. • Add text box to PDF file in preview.
add pages to pdf acrobat; add pages to pdf in preview
C# WPF Viewer: Load, View, Convert, Annotate and Edit PDF
This page will mainly let you know: PDF Annotation. • Add sticky notes to PDF document. • Highlight PDF text in preview. • Add text to PDF document.
add blank page to pdf preview; adding page to pdf in preview
13.4. HARDPROBLEMS
235
Let
'
sseehowthatcomparestothemergesortalgorithm.Inthecaseofmergesort,wedividedalistinto
twopiecesandsortedtheindividualpiecesbeforemergingthemtogether.Therealworkisdoneduringthe
mergeprocesswhenthevaluesinthesublistsarecopiedbackintotheoriginallist.
Figure13.2depictsthemergingprocesstosortthelist[3, 1, 4, , 1, , 5, 9, 2, 6].Thedashed
linesshowhowtheoriginallistiscontinuallyhalveduntileachitemisitsownlistwiththevaluesshownat
thebottom.Thesingle-itemlistsarethenmergedbackupintothetwoitemliststoproducethevaluesshown
inthesecondlevel.Themergingprocesscontinuesupthediagramtoproducethefinalsortedversionofthe
listshownatthetop.
1
1
2
3
4
5
6
9
1
1
3
4
2
5
6
9
1
3
1
4
5
9
2
6
3
1
4
1
5
9
2
6
Figure13.2:Mergesrequiredtosort[3,1,4,1,5,9,2,6].
Thediagrammakesanalysisofthemergesorttrivial.Startingatthebottomlevel,wehavetocopythen
valuesintothesecondlevel.Fromthesecondtothirdlevel,thenvaluesneedtobecopiedagain.Eachlevel
ofmerginginvolvescopyingnvalues. Theonlyquestionlefttoanswerishowmanylevelsarethere? This
boilsdowntohowmanytimesalistofsizencanbesplitinhalf. Youalreadyknowfromtheanalysisof
binarysearchthatthisisjustlog
2
n. Therefore,thetotalworkrequiredtosortnitemsisnlog
2
n. Computer
scientistscallthisannlognalgorithm.
Sowhichisgoingtobebetter,then-squaredselectionsortorthen-log-nmergesort?Iftheinputsizeis
small,theselectionsortmightbealittlefaster,becausethecodeissimplerandthereislessoverhead.What
happens,thoughasngetslarger? Wesawintheanalysisofbinarysearchthatthelogfunctiongrowsvery
slowly(log
2
16
000
000
24)son
log
2
n
willgrowmuchslowerthann
n
.
Empiricaltestingofthesetwoalgorithmsconfirmsthisanalysis. Onmycomputer,selectionsortbeats
mergesortonlistsuptosizeabout50,whichtakesaround0.008seconds. Onlargerlists,themergesort
dominates. Figure13.3showsacomparisonofthetimerequiredtosortlistsuptosize3000. Youcansee
thatthecurveforselectionsortveersrapidlyupward(forminghalfofaparabola),whilethemergesortcurve
looksalmoststraight(lookatthebottom). For3000items,selectionsortrequiresover30secondswhile
mergesortcompletesthetaskinabout
3
4
ofasecond.Mergesortcansortalistof20,000itemsinlessthan
sixseconds;selectionsorttakesaround20minutes.That
'
squiteadifference!
13.4 HardProblems
Usingourdivide-and-conquerapproachwewereabletodesigngoodalgorithmsforthesearchingandsorting
problems. Divideandconquerandrecursionareverypowerfultechniquesforalgorithmdesign. . However,
notallproblemshaveefficientsolutions.
How to C#: Preview Document Content Using XDoc.Word
RasterEdge XDoc.Word provide you with APIs to get a thumbnail bitmap of the first page in the word document file. C# DLLs for Word File Preview. Add references:
add page number to pdf reader; add a page to a pdf file
How to C#: Preview Document Content Using XDoc.PowerPoint
APIs to get a thumbnail bitmap of the first page in the C# DLLs: Preview PowerPoint Document. Add necessary XDoc.PowerPoint DLL libraries into your created C#
add pages to pdf; adding a page to a pdf document
236
CHAPTER13. ALGORITHMANALYSISANDDESIGN
0
5
10
15
20
25
30
35
0
500
1000
1500
2000
2500
3000
Seconds
List Size
’selSort’
’mergeSort’
Figure13.3:Experimentalcomparisonofselectionsortandmergesort.
13.4.1 TowersofHanoi
Oneveryelegantapplicationofrecursiveproblemsolvingisthesolutiontoamathematicalpuzzleusually
calledtheTowerofHanoiorTowerofBrahma. ThispuzzleisgenerallyattributedtotheFrenchmathe-
maticianEdouardLucas,whopublishedanarticleaboutitin1883.Thelegendsorroundingthepuzzlegoes
somethinglikethis.
Somewhereinaremoteregionoftheworldisamonasteryofaverydevoutreligiousorder. Themonks
havebeenchargedwithasacredtaskthatkeepstimefortheuniverse. Atthebeginningofallthings,the
monksweregivenatablethatsupportsthreeverticalposts.Ononeofthepostswasastackof64concentric
goldendisks. Thedisksareofvaryingradiiandstackedintheshapeofabeautifulpyramid. Themonks
werechargedwiththetaskofmovingthedisksfromthefirstposttothethirdpost. Whenthemonkshave
completedtheirtask,allthingswillcrumbletodustandtheuniversewillend.
Ofcourse,ifthat
'
sallthereweretotheproblem,theuniversewouldhaveendedlongago.Tomaintain
divineorder,themonksmustabidebycertainrules.
1. Onlyonediskmaybemovedatatime.
2. Adiskmaynotbe“setaside.”Itmayonlybestackedononeofthethreeposts.
3. Alargerdiskmayneverbeplacedontopofasmallerone.
Versionsofthispuzzlewerequitepopularatonetime,andyoucanstillfindvariationsonthisthemein
toyandpuzzlestores. Figure13.4depictsasmallversioncontainingonlyeightdisks. . Thetaskistomove
thetowerfromthefirstposttothethirdpostusingthecenterpostassortofatemporaryrestingplaceduring
theprocess.Ofcourse,youhavetofollowthethreesacredrulesgivenabove.
Wewanttodevelopanalgorithmforthispuzzle. Youcanthinkofouralgorithmeitherasasetofsteps
thatthemonksneedtocarryout,orasaprogramthatgeneratesasetofinstructions.Forexample,ifwelabel
thethreepostsA,BandC.Theinstructionsmightstartoutlikethis:
Move disk from m A A to C.
C# PDF insert image Library: insert images into PDF in C#.net, ASP
How to insert and add image, picture, digital photo, scanned signature or logo into PDF document page in C#.NET class application?
add page number pdf file; add page numbers to pdf document
VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Remove bookmarks, annotations, watermark, page labels and article threads from PDF while compressing. Also a preview component enables compressing and
add a page to a pdf in reader; add page to pdf
13.4. HARDPROBLEMS
237
Figure13.4:TowerofHanoipuzzlewitheightdisks.
Move disk from m A A to B.
Move disk from m C C to B.
...
Thisisadifficultpuzzleformostpeopletosolve.Ofcourse,thatisnotsurprising,sincemostpeopleare
nottrainedinalgorithmdesign.Thesolutionprocessisactuallyquitesimple—ifyouknowaboutrecursion.
Let
'
sstartbyconsideringsomereallyeasycases. Supposewehaveaversionofthepuzzlewithonly
onedisk. Movingatowerconsistingofasinglediskissimple—wejustremoveitfromAandputitonC.
Problemsolved.OK,whatiftherearetwodisks?IneedtogetthelargerofthetwodisksovertopostC,but
thesmalleroneissittingontopofit. Ineedtomovethesmallerdiskoutoftheway,andIcandothisby
movingittopostB.NowthelargediskonAisclear;IcanmoveittoCandthenmovethesmallerdiskfrom
postBontopostC.
Nowlet
'
sthinkaboutatowerofsizethree.InordertomovethelargestdisktopostC,Ifirsthavetomove
thetwosmallerdisksoutoftheway. Thetwosmallerdisksformatowerofsizetwo. . UsingtheprocessI
outlinedabove,IcouldmovethistoweroftwoontopostB,andthatwouldfreeupthelargestdisksothatI
canmoveittopostC.ThenIjusthavetomovethetoweroftwodisksfrompostBontopostC.Solvingthe
threediskcaseboilsdowntothreesteps.
1. MoveatoweroftwofromAtoB.
2. MoveonediskfromAtoC.
3. MoveatoweroftwofromBtoC.
Thefirstandthirdstepsinvolvemovingatowerofsizetwo.Fortunately,wehavealreadyfiguredouthowto
dothis. It
'
sjustlikesolvingthepuzzlewithtwodisks,exceptthatwemovethetowerfromAtoBusingC
asthetemporaryrestingplaceandthenfromBtoC,usingAasthetemporary.
Wehavejustdevelopedtheoutlineofasimplerecursivealgorithmforthegeneralprocessofmovinga
towerofanysizefromoneposttoanother.
Algorithm: move e n-disk k tower from source to destination n via a resting place
move n-1 disk k tower r from source to resting place
move 1 disk tower r from m source to destination
move n-1 disk k tower r from resting place to destination
VB.NET PDF insert image library: insert images into PDF in vb.net
inserting image to PDF in preview without adobe provide users the most individualized PDF page image inserting function, allowing developers to add and insert
add page to pdf reader; add a page to a pdf in acrobat
How to C#: Preview Document Content Using XDoc.excel
you with APIs to get a thumbnail bitmap of the first page in the C# DLLs: Preview Excel Document without Microsoft Office Installed. Add necessary references:
add or remove pages from pdf; add pages to pdf online
238
CHAPTER13. ALGORITHMANALYSISANDDESIGN
Whatisthebasecaseforthisrecursiveprocess?Noticehowamoveofndisksresultsintworecursivemoves
ofn
1disks.Sincewearereducingnbyoneeachtime,thesizeofthetowerwilleventuallybe1.Atower
ofsize1canbemoveddirectlybyjustmovingasingledisk;wedon
'
tneedanyrecursivecallstoremove
disksaboveit.
FixingupourgeneralalgorithmtoincludethebasecasegivesusaworkingmoveToweralgorithm.
Let
'
scodeitupinPython.OurmoveTowerfunctionwillneedparameterstorepresentthesizeofthetower,
n;thesourcepost,source;thedestintationpost,dest;andthetemporaryrestingpost,temp.Weanuse
anintfornandthestrings”A”,”B”,and”C”torepresenttheposts.HereisthecodeformoveTower.
def moveTower(n, , source, , dest, temp):
if n == 1:
print "Move disk from", source, "to", , dest+"."
else:
moveTower(n-1, source, , temp, dest)
moveTower(1, source, , dest, temp)
moveTower(n-1, temp, , dest, source)
Seehoweasythatwas?Sometimesusingrecursioncanmakeotherwisedifficultproblemsalmosttrivial.
Togetthingsstarted,wejustneedtosupplyvaluesforourfourparameters. Let
'
swritealittlefunction
thatprintsoutinstructionsformovingatowerofsizenfrompostAtopostC.
def hanoi(n):
moveTower(n, "A", , "C", "B")
Nowwe
'
rereadytotryitout.Herearesolutionstothethree-andfour-diskpuzzles.Youmightwantto
tracethroughthesesolutionstoconvinceyourselfthattheywork.
>>> hanoi(3)
Move disk from m A A to C.
Move disk from m A A to B.
Move disk from m C C to B.
Move disk from m A A to C.
Move disk from m B B to A.
Move disk from m B B to C.
Move disk from m A A to C.
>>> hanoi(4)
Move disk from m A A to B.
Move disk from m A A to C.
Move disk from m B B to C.
Move disk from m A A to B.
Move disk from m C C to A.
Move disk from m C C to B.
Move disk from m A A to B.
Move disk from m A A to C.
Move disk from m B B to C.
Move disk from m B B to A.
Move disk from m C C to A.
Move disk from m B B to C.
Move disk from m A A to B.
Move disk from m A A to C.
Move disk from m B B to C.
So,oursolutiontotheTowerofHanoiisa“trivial”algorithmrequiringonlyninelinesofcode. What
isthisproblemdoinginasectionlabeledhardproblems? Toanswerthatquestion,wehavetolookatthe
efficiencyofoursolution. Remember,whenItalkabouttheefficiencyofanalgorithm,Imeanhowmany
C# PDF insert text Library: insert text into PDF content in C#.net
Able to add a single text character and text string formatted text and plain text to PDF page using .NET Supports adding text to PDF in preview without adobe
adding page numbers to a pdf document; add page to pdf online
13.4. HARDPROBLEMS
239
stepsitrequirestosolveagivensizeproblem.Inthiscase,thedifficultyisdeterminedbythenumberofdisks
inthetower.Thequestionwewanttoanswerishowmanystepsdoesittaketomoveatowerofsizen?
Justlookingatthestructureofouralgorithm,youcanseethatmovingatowerofsizenrequiresusto
moveatowerofsizen
1twice,oncetomoveitoffthelargestdisk,andagaintoputitbackontop.Ifwe
addanotherdisktothetower,weessentiallydoublethenumberofstepsrequiredtosolveit.Therelationship
becomesclearifyousimplytryouttheprogramonincreasingpuzzlesizes.
NumerofDisks StepsinSolution
1
1
2
3
3
7
4
15
5
31
Ingeneral,solvingapuzzleofsizenwillrequire2
n
1steps.
Computerscientistscallthisanexponentialtimealgorithm,sincethemeasureofthesizeoftheproblem,
n,appearsintheexponentofthisformula. Exponentialalgorithmsblowupveryquicklyandcanonlybe
practicallysolvedforrelativelysmallsizes,evenonthefastestcomputers. Justtoillustratethepoint,ifour
monksreallystartedwithatowerofjust64disksandmovedonediskeverysecond,24hoursaday,everyday,
withoutmakingamistake,itwouldstilltakethemover580billionyearstocompletetheirtask.Considering
thattheuniverseisroughly15billionyearsoldnow,I
'
mnottooworriedaboutturningtodustjustyet.
EventhoughthealgorithmforTowersofHanoiiseasytoexpress,itbelongstoaclassknownasin-
tractableproblems. Theseareproblemsthatrequiretoomuchcomputingpower(eithertimeormemory)
tobesolvedinpractice,exceptforthesimplestcases. Andinthissense,ourtoy-storepuzzledoesindeed
representahardproblem.Butsomeproblemsareevenharderthanintractable,andwe
'
llmeetoneofthose
inthenextsection.
13.4.2 TheHaltingProblem
Let
'
sjustimagineforamomentthatthisbookhasinspiredyoutopursueacareerasacomputerprofessional.
It
'
snowsixyearslater,andyouareawell-establishedsoftwaredeveloper.Oneday,yourbosscomestoyou
withanimportantnewproject,andyouaresupposedtodropeverythingandgetrightonit.
Itseemsthatyourbosshashadasuddeninspirationonhowyourcompanycandoubleitsproductivity.
You
'
verecentlyhiredanumberofratherinexperiencedprogrammers,anddebuggingtheircodeistakingan
inordinateamountoftime. Apparently,thesewet-behind-the-earsnewbiestendtoaccidentlywritealotof
programswithinifiniteloops(you
'
vebeenthere,right?).Theyspendhalfthedaywaitingfortheircomputers
torebootsotheycantrackdownthebugs.Yourbosswantsyoutodesignaprogramthatcananalyzesource
codeanddetectwhetheritcontainsaninfiniteloopbeforeactuallyrunningitontestdata. Thissoundslike
aninterestingproblem,soyoudecidetogiveitatry.
Asusual,youstartbycarefullyconsideringthespecifications.Basically,youwantaprogramthatcanread
otherprogramsanddeterminewhethertheycontainaninfiniteloop.Ofcourse,thebehaviorofaprogramis
determinednotjustbyitscode,butalsobytheinputitisgivenwhenitruns.Inordertodetermineifthereis
aninfiniteloop,youwillhavetoknowwhattheinputwillbe.Youdecideonthefollowingspecification:
Program: HaltingAnalyzer
Inputs: APythonprogramfile.
Theinputfortheprogram.
Outputs: “OK”iftheprogramwillevenutallystop.
“FAULTY”iftheprogramhasaninfiniteloop.
Rightawayyounoticeacoupleinterestingthingsaboutthisprogram. Oneisthatitisaprogramthat
examinesotherprograms. Youhavenotwrittenmanyofthesebefore,butyouknowthatit
'
snotaproblem
inprinciple. Afterall, , compilersandinterpretersarecommonexamplesofprogramsthatanalyzeother
programs.Youcanrepresentboththeprogramthatisbeinganalyzedandtheproposedinputtotheprogram
asPythonstrings.
240
CHAPTER13. ALGORITHMANALYSISANDDESIGN
Thesecondthingyounoticeis thatthisdescriptionsoundssimilartosomethingyou
'
veheardabout
before.Hmmm...aprogramthatdetermineswhetheranotherprogramwillhaltornot.Suddenlyitdawnson
you:thisisknownastheHaltingProblem,andit
'
sunsolvable.Thereisnopossiblealgorithmthatcanmeet
thisspecification!
Howdoweknowthatthereisnosolutiontothisproblem?Thisisaquestionthatallthedesignskillsin
theworldwillnotanswerforyou.Designcanshowthatproblemsaresolvable,butitcanneverprovethata
problemisnotsolvable.Todothat,weneedtouseouranalyticalskills.
Onewaytoprovethatsomethingisimpossibleistofirstassumethatitispossibleandshowthatthisleads
toacontradiction.Mathematicianscallthisproofbycontradiction.We
'
llusethistechniquetoshowthatthe
haltingproblemcannotbesolved.
Webeginbyassumingthatthereissomealgorithmthatcandetermineifaprogramterminateswhen
executedonaparticularinput.Ifsuchanalgorithmcouldbewritten,wecouldpackageitupinafunction.
def terminates(program, , inputData):
# program m and d inputData are both strings
# RETURNS S true e if program would halt when n run n with inputData
#
as its input.
Ofcourse,Ican
'
tactuallywritethefunction,butlet
'
sjustassumethatthisfunctionexists.
Usingtheterminatesfunction,wecanwriteagoofyprogram.
# goofy.py
import string
def terminates(program, , inputData):
# program m and d inputData are both strings
# RETURNS S true e if program would halt when n run n with inputData
#
as its input.
def main():
# Read a program m from m standard input
lines = []
print "Type e in n a program (type 'done' to quit)."
line = raw_input("")
while line e != = "done":
lines.append(line)
line = raw_input("")
testProg = = string.join(lines, , "\n")
# If program m halts s on itself as input, go o into o an infinite loop
if terminates(testProg, , testProg):
while 1: pass
main()
Thefirstthinggoofy.pydoesisreadinaprogramtypedbytheuser.Thisisaccomplishedwithasentinel
loopthataccumulateslinesinalistoneatatime. Thestring.joinfunctionthenconcatenatesthe
linestogetherusinganewlinecharacter("
n")betweenthem. Thiseffectivelycreatesamulti-linestring
representingtheprogramthatwastyped.
Goofy.pythencallstheterminatesfunctionandsendstheinputprogramasboththeprogramto
testandtheinputdatafortheprogram. Essentially,thisisatesttoseeiftheprogramreadfromtheinput
terminateswhengivenitselfasinput. Thepassstatementactuallydoesnothing;iftheterminates
functionreturnstrue,goofy.pywillgointoaninfiniteloop.
OK,thisseemslikeasillyprogram,butthereisnothinginprinciplethatkeepsusfromwritingit,provided
thattheterminatesfunctionexists. Goofy.pyisconstructedinthispeculiarwaysimplytoillustratea
point. Here
'
sthemilliondollarquestion:Whathappensifwerungoofy.pyand,whenpromptedtotype
13.4. HARDPROBLEMS
241
inaprogram,typeinthecontentsofgoofy.py?Putmorespecifically,doesgoofy.pyhaltwhengiven
itselfasitsinput?
Let
'
sthinkitthrough.Wearerunninggoofy.pyandprovidinggoofy.pyasitsinput. Inthecallto
terminates,boththeprogramandthedatawillbeacopyofgoofy.py,soifgoofy.pyhaltswhen
givenitselfasinput,terminateswillreturntrue.Butifterminatesreturnstrue,goofy.pythengoes
intoaninfiniteloop,soitdoesn
'
thalt!That
'
sacontradiction;goofy.pycan
'
tbothhaltandnothalt.It
'
s
gottobeoneortheother.
Let
'
stryittheotherwayaround. Supposethatterminatesreturnsafalsevalue. . Thatmeansthat
goofy.py,whengivenitselfasinputgoesintoaninfiniteloop.Butassoonasterminatesreturnsfalse,
goofy.pyquits,soitdoeshalt!It
'
sstillacontradiction.
Ifyou
'
vegottenyourheadaroundtheprevioustwoparagraphs,youshouldbeconvincedthatgoofy.py
representsanimpossibleprogram.Theexistenceofafunctionmeetingthespecificationforterminates
leadstoalogicalimpossibility.Therefore,wecansafelyconcludethatnosuchfunctionexists.Thatmeans
thattherecannotbeanalgorithmforsolvingthehaltingproblem!
Thereyouhaveit. Yourbosshasassignedyouanimpossibletask. Fortunately, , yourknowledgeof
computerscienceissufficienttorecognizethis. Youcanexplaintoyourbosswhytheproblemcan
'
tbe
solvedandthenmoveontomoreproductivepursuits.
13.4.3 Conclusion
Ihopethischapterhasgivenyouatasteofwhatcomputerscienceisallabout.Astheexamplesinthischapter
haveshown,computerscienceismuchmorethan“just”programming.Themostimportantcomputerforany
computingprofessionalisstilltheonebetweentheears.
Hopefullythisbookhashelpedyoualongtheroadtobecomingacomputerprogrammer.Alongtheway,
Ihavetriedtoithaspiqueyourcuriousityaboutthescienceofcomputing.Ifyouhavemasteredtheconcepts
inthistext,youcanalreadywriteinterestingandusefulprograms.Youshouldalsohaveafirmfoundationof
thefundamentalideasofcomputerscienceandsoftwareengineering. Shouldyoubeinterestedinstudying
thesefieldsinmoredepth,Icanonlysay“goforit.” Perhapsonedayyouwillalsoconsideryourselfa
computerscientist;Iwouldbedelightedifmybookplayedevenaverysmallpartinthatprocess.
Index
doc
,171
init
,168
name
,106
abstraction,148
accessor,68
accumulator,31
acronym,61
algorithm
analysis,2,233
definitionof,2
designstrategy,118
divideandconquer,235
exponentialtime,245
intractable,246
lineartime,234
logtime,234
quadratic(n-squared)time,241
algorithms
averagennumbers
countedloop,123
emptystringsentinel,128
interactiveloop,126
binarysearch,233
cannonballsimulation,162
futurevalue,23
futurevaluegraph,71,73
inputvalidation,135
linearsearch,232
max-of-three
comparingeachtoall,115
decisiontree,116
sequential,117
median,189
mergesort,240
messagedecoding,48
messageencoding,47
quadraticequationthree-waydecision,110
racquetballsimulation
simOneGame,150
selectionsort,238
simNGames,149
temperatureconversion,14
alias,69
analysisofalgorithms,2,233
and,132
operationaldefinition,138
AntsGoMarching,The,100
append,186
archery,85,121
argument,93
array,186
associative,199
arrow(onLines),82
ASCII,46
assignmentstatement,10,17–20
sematics,17
simultaneous,19
syntax,17
associativearray,199
attributes,161
private,178
averagennumbers
algorithm
emptystringsentinel,128
problemdescription,123
program
countedloop,123
emptystringsentinel,128
end-of-fileloop,130
fromfilewithreadlines,129
interactiveloop,126
negativesentinel,127
averagetwonumbers,20
average1.py,123
average2.py,126
average3.py,127
average4.py,128
average5.py,129
average6.py,130
avg2.py,20
babysitting,120
batchprocessing,58
exampleprogram,58
binary,4
binarysearch,232
bit,33
blackbox,207
Blackjack,159
242
Documents you may be interested
Documents you may be interested