C大学教程课后习题答案13

Chapter14

RECURSION

1.SolutionstoandRemarksonSelectedProgrammingAssignments

1.FibonacciNumbers

ThesesolutionshavebeentestedundertwoLinuxversionsusingtwoversionsofg++,

underWindowsXPwithVC++6.0andBorland5.0.Thefullrecursiveversionisslow.It

takesabout17secondsfor1computationofFibl(35)onanolder,veryslowmachine

(i486DX2/100,16MBRAM).Onamoremodemmachine(1GHzAthlon.266MHz

frontsidebus,512MBDDRRAM,fastdiskdrives)itrunsabitfaster:N=35takes3

seconds,N=40takesabout30seconds,N=41about50seconds,andN=42takes80

seconds.AvalueofNgreaterthan47resultsinintegeroverflowandincorrectresultswith

allthecompilersmentionedabove.

Withmostimplementations,longintisatypethesamesizeasint.Becausethereare

afewimplementationsthatprovidealongintthatislongerthananint,Iusedlong

astheargumentandreturntypesforthefibfunction.

TogetFibonaccinumbersuptoN=5()forcheckingtheresultsoftheprogram,Ichanged

thelongtypeintherecursivefunctiontolonglong(a19digitintegertypesupported

byGNUg++,butnotANSI/ISOC++).Icompiledthisusingg++-3.0undertheDebian

Linux3.0operatingsystemonaK6-2/350witha100MHzbackplaneand400KRAM.On

thissomewhatslowmachine,thisversionoftheprogramtookabouttwohoursforN==50,

givingpresumablycorrectresults.(IacknowledgethatIdidnotlookthemup.)Theresults

agreewiththecodewithalongreturnandlongparametertypeuptoN=47.

ThisfunctioncomputesanddiscardstoomanyoftheFibonaccinumbers.Thiskindof

recursioniscalledUmbrellarecursion'becauseitspreadslikeanumbrella,recomputing

valuesmanytimes.

1

Copyright©2008PearsonEducation,Inc.PublishingasPearsonAddison-Wesley

//File:chi4prglFibonacci.cc

//Chapter14,ProgrammingProblem#1

//Writearecursivefunctionforafunctionhavingone

//parameterthatgeneratesthenthFibonaccinumber.

#include<iostream>

♦include<cmath>

//Thisisthefullrecursiveversion.

unsignedlongFibl(intn)

(

if(n==0||n==1)

return1;

returnFibl(n-1)+Fibl(n-2);

}

intmain()

(

usingnamespacestd;

charans;

intN;

do

(

cout<<111willdisplayfibonaccinumbers0-N.\nn;

cout<<"Enteranlimit,\nH;

cin>>N;

for(inti=0;i<N;i++)

cout<<Fibl(i)<<endl;

cout<<nY/ytocontinue,anythingelsequits\nn;

cin>>ans;

(Y

11

}whileoansIIy==ans);

return

}

2.RecursiveIndexofSmallest

CAUTIONS:Pleasewarnthestudentthatnumber_usedisNOTthelargestindexused,ratherit

isthenumberofelements.

Thiswasmyhardest-to-find-errorincodingthis.Ialsorecommendthatthestudentremovethe

SortfunctionfromDisplay10-12.IncludingSortobscuresthebehaviorofthe

index_of_smallest.Ihaditfindingthemaximum,butIdidn'tspotthatuntilIremoved

thesortroutineanditssupportroutines.

Thisismodifiedfromcodeofthetext.Ipreferthatthestudentnotreinventthewheel:use.She

shouldreusecodefromthetext'sDisplaystoadvantage!

//file:chl4prg2.cc

//Teststheprocedurerecursivefunctionindex_of_smallest

//Sortroutineremovedtosimplifythetestingenvironment.

♦include<iostream>

voidfill_array(inta口，intsize,int&number_used);

//Precondition:sizeisthedeclaredsizeofthearraya.

//Postcondition:number_usedisthenumberofvaluesstored

//ina[0]througha[number_used-1]havebeenfilledwith

//nonnegativeintegersreadfromthekeyboard.

intindex__of_smallest(constinta口，

intstart_indexzintnumber__used);

//NOTE:designandimplementationofthisfunctionareat

//theendofthisfile.

//Precondition:0<=start_index<number_used.

//Referencedarrayelementshavevalues.

//Returnvalueistheindexisuchthata[i]isthesmallest

//ofthevalues

//a[start_index],a[start_index+1a[number_used-1].

intmain()

usingnamespacestd;

cout<<"Thisprogramtestsrecursivefunction"

<<nindex_of_smallest”<<endl<<endl;

intsample_array[10],number_used;

fill_array(sample_array<10,number__used);

intiindex_of_smallest(sample_array,0znumber_used);

cout<<“Th㊀numberofelementsis”

<<number__used<<endl;

cout<<“FortheminimumelementinthearrayINDEX="

<<i<<endl;

cout<<“Thearrayelementis”<<sample_array[i]

<<endl<<endl;

cout<<nTheelementsinthearrayare:\nn;

for(intindex=0;index<number_used;index++)

cout<<sample_array[index]<<

cout<<endl;

return0;

}

//Usesiostream

voidfill_array(inta口，intsize,int&number_used)

(

usingnamespacestd;

cout<<"Enterupto"<<size

<<”nonnegativewholenumbers.\nH

<<"Marktheendofthelistwith”

<<”anegativenumber.\nu;

intnext,index=0;

cin>>next;

while((next>=0)&&(index<size))

(

a[index]=next;

index++;

cin>>next;

)

number_used=index;

)

RecursiveFunctionIndex_of_Smallest

Thisrecursivefunctionreturnstheindexoftheminimumelementinthearraysegmentbetween

start_indexandnumber_used.

NonrecursiveCase:Ifwehaveonlyoneelementinasubarraywherestart_indexhasthe

valuenumber_usedthenthatelementistheminimum,andstart_indexistheindexwe

want.

RecursiveCase:Ifthereismorethanoneelement,taketheelementwithsmallestindexand

compareitsvaluetotheminimumvalueofthearrayelementatindexreturnedbythefunction

operatingontherestofthearray.

intindex_of_smallest(constinta口，intstart_indexzint

number_used)

(

if(start_index==number_used-1)

returnstart_index;

intmin=a[start_index];

intindex_of_min=

index_of_smallest(a,start_index+lrnumber_used);

if(min>a[index_of_min])

returnindex_of_min;

else

returnstart_index;

)

Atypicalrun:

Thisprogramtestsrecursivefunctionindex_of_sma11est

Enterupto10nonnegativewholenumbers.

Marktheendofthelistwithanegativenumber.

435603-1

Thenumberofelementsis6

FortheminimumelementinthearrayINDEX=4

Thearrayelementis0

Theelementsinthearrayare:

435603

Anothertestrun:

Thisprogramtestsrecursivefunctionindex_of_smallest

Enterupto10nonnegativewholenumbers.

Marktheendofthelistwithanegativenumber.

9238456329-1

Thenumberofelementsis10

FortheminimumelementinthearrayINDEX=1

Thearrayelementis2

Theelementsinthearrayare:

9238456329

3.NoSolutionProvided.

4.BinomialCoefficients.

Writearecursivefunctionthatusesthegivenrecursiveformulatocalculatebinomial

coefficients.Test.

Asecondpartgivesaconventionalformulaforthefactorial,instructsthestudentto

discoverarecursiveversionsandtowritearecursivefunctionforthefactorial.Test.

Notesonlyonthisproblem.ThestudentsshouldhaveseenthePascalTrianglein

mathematicscoursesbythistime.Ifnot,suggestittothem.Idoitthisway:

(x+y)1=1*x+l*y

(x+y)2=l*x2+2*x*y+2*y2

(x+y)3=l*x3+3*x2*yx+3*x1：7+y3

(x+y)4=1*x4+4*x3*y1+6*x2*y2+4*x1*y3+y'

(x+y)3=l*x5+5*x4*y1+10*x3*y2+10*x2*y3+5*x1*y4+

Wherethecoefficientsare

11

121

1331

14641

15101051

Thecoefficients,whenrearrangedare:

121

1331

14641

15101051

ThenweidentifytherowswithC(n,r)wherethenisthesecondentryinanyrow,and

risthecolumnofthatrow,startingwith0:

C(l,0)C(lr1)

C(2,0)C(2Z1)C(2,2)

C(3Z0)C(3,l)C(3Z2)C(3,3)

C(4,0)C(4,l)C(4,2)C(4,3)C(4,4)

C(5,0)C(5,l)C(5,2)C(5,3)C(5,4)C(5,5)

Prodthestudentsalittle.Theywillseethataddinganytworowitemsgivesthevalue

directlyundertheseconditem.Thereistherecursionrelationtheyneed:

C(n,r)+C(n,r+l)=C(n+1,r+1)

Thisisanotherumbrellarecursion,similarinthisrespecttoProgrammingproblem#1.It

takesconsiderabletimeandspacetodothiswithrecursion.

Ifbinomialcoefficientsarereallyneeded,abunchofthemarelikelyneeded.Itisbetterto

useasolutionwhereallthecoefficientsuptothoseneededarecomputedandstored(in

someglobalarray,oritcouldbearrangedforthefunctiontoreturnacurrentlyavailable

value,orifitisnotavailable,tocomputeallbinomialcoefficientsuptotheonedesired.

(Thisisagoodplacefortheideasofa"dynamicarray"ora"source"class.)

5.RecursiveReverseArraySegment.

Theproblemistorecursivelyreverseanarraysegment.Thefunctiontakesanarray

argumentandtwointegerargumentsthatspecifythestartandtheendofthesegmentofthe

arraytobereversed.

voidrecursive_reverse(inta口，intstart,intend);

Thetaskissplitintotwopieces:

NonRecursive:Hereifthereisonlyoneelement,wearedoneoriftherearetwo

elements,wecanjustswapthem,andwearedone.

Recursive:Reversethestartandendelements.Arecursivecallismadetothe

functiontofinishthejob:

recursive_reverse(a,start+lzend-1);

Housekeeping:Howdoweknowifthereisonlyoneelement?Howdoweknow

wehaveonlytwoelements?

Ifthereisanoddnumberofarrayelementstobeswapped,wetakecareoftwoat

time.Wewindupwithonearrayelementforthenon-recursivecasetodealwith.

Thenwecantest

start==end.

Howdoyouknowthereareonlytwoelementstobeswapped?

Ifstart+1==end,thenthereonlytwoelements.Weswapthemandquit.

Recursivecase:

Ifthereisanevennumberofarrayelementstobeswapped,allofthemwillbe

dealtwithintherecursivecase.Therewillbeonelastrecursivecallmadewithan

arrayoftwoelements(start+1==end).Inthiscall,thislastpairwillbe

swapped.Therewillbeonelastrecursivecallwithstartargumentstart+1+1

andendargumentend-1.Thismakesthevaluesofstartandendinthe

nextrecursivecallhavevaluessuchthatstart<end.Thissignalsthatthelast

pairhavebeenswapped.

(Actually,thetwoelementsubcasecanberemoved.Theexplanationissomewhatmore

obscure.)

Code:

♦include<iostream>

voidrecursive_reverse(chara[],intstart,intend)

(

if(start>=end)//jobisdone!

return;

if(start+1==end)//onlytwoelements,swapthem

(

chartemp=a[start];

a[start]=a[end];

a[end]=temp;

return;

}

//makerecursivecalltofinish

//swapstartandendelements

chartemp=a[start];

a[start]=a[end];

a[end]=temp;//makerecursivecalltofinish

recursive_reverse(a,start+1,end-1);

)

intmain()

(

usingnamespacestd;

chara[20];

for(inti=0;i<20;i++)

a[i]=+i;

cout<<"array:"<<endl;

for(i=0;i<20;i++)

cout<<a[i]<<”H;

cout<<endl;

recursive_reverse(a,5,19);//endisanarrayelement

cout<<"arraywithelementswithindex5-19reversed"”;

for(i=0;i<20;i++)

cout<<a[i]<<”n;

cout<<endl;

for(i=0;i<20;i++)

a[i]=1A1+i;

cout<<"array:“<<endl;

for(i=0;i<20;i++)

cout<<a[i]<<"";

cout<<endl;

recursive_reverse(az3Z12);//endisanarrayelement

cout<<"arraywithelementswithindex3-12reversed\nf,;

for(i=0;i<20;i++)

cout<<a[i]<<”n;

cout<<endl;

)

ATrialrun:

array:

ABCDEFGH工JKLMNOPQRST

arraywithelementswithindex5-19reversed

ABCDETSRQPONMLKJIHGF

array:

ABCDEFGH工JKLMNOPQRST

arraywithelementswithindex3-12reversed

ABCMLKJIHGFEDNOPQRST

StringReverseII

Oncethefunctionaboveisfullydebugged,defineafunctionthattakesasingleargument

whichisanarraythatcontainsastringvalueandthatreversesthespellingofthestring

valueinthearrayargument.Thisfunctioncallstherecursivefunctionjustdefined.

♦include<iostream>

#include<cstring>

voidrecursive_reverse(chara[],intstart,intend);

voidstring_reverse(charstr[])

(

intlength=strlen(str);

recursive_reverse(str,0,length-1);

}

intmain()

{

usingnamespacestd;

chara[20];

for(inti=0;i<20;i++)

a[i]=1A1+i;

a[19]=,\01;//makeastringoutofit!

cout<<nstringbeforereversing:"<<a<<endl;

string__reverse(a);

cout<<nstringafterreversing:"<<a<<endl;

return0;

)

AtrialRun:

stringbeforereversing:ABCDEFGHIJKLMNOPQRS

stringafterreversing:SRQPONMLKJIHGFEDCBA

6.IterativeReverseCharArraySegment

//File:chl4prg6.cc

//Codeandtestaniterativeversionofreversesegmentfrom

//anarrayofchar.Thenwriteanotherfunctionthatcalls

this

//toandreversesastring.

//iterative_reverse:

//Swaptheends,backuponefromeachend,repeat

//whilestart<end.

♦include<iostream>

#include<cstring>

voiditerative_reverse(chara[],intstart,intend)

(

while(start<end)

(

chartemp=a[start];

a[start]=a[end];

a[end]=temp;

start+4-;

end——;

)

)

voidstring_reverse(charstr[])

intlength=strlen(str);

iterative_reverse(str,0,length-1);

)

constintSIZE=10;

intmain()

(

usingnamespacestd;

chara[SIZE];

for(intj=2;j<SIZE;j++)

(

for(inti=0;i<j;i++)

a[i]=1A*+i;

a[j-1]=1\01;//makeastringoutofit!

cout<<"stringbeforereversing:"<<a<<endl;

string_reverse(a);

cout<<"stringafterreversing:"<<a<<endl<<

endl;

}

return0;

}

Atypicalrun:

stringbeforereversing:A

stringafterreversing:A

stringbeforereversing:AB

stringafterreversing:BA

stringbeforereversing:ABC

stringafterreversing:CBA

stringbeforereversing:ABCD

stringafterreversing:DCBA

stringbeforereversing:ABCDE

stringafterreversing:EDCBA

stringbeforereversing:ABCDEF

stringafterreversing:FEDCBA

stringbeforereversing:ABCDEFG

stringafterreversing:GFEDCBA

stringbeforereversing:ABCDEFGH

stringafterreversing:HGFEDCBA

7.RecursiveSortintarray

ThiscodewasadaptedfromDisplay12-13.Thesortroutinewasrenderedrecursive.

Notethatthetext'swarningfromtheChapterSummarymustbetakentoheart.Itis

frequentlynecessarytodoasomewhatmoregeneralproblemthantheiterativecodesolves.

Here,Ihadtomaketherecursivesortroutinesortfromaspecifiedindex.Theindexisthe

positionthatthesortingstarts.Theforloopwasabletosetwiththeiterativecodebutitis

necessarytothispassintotherecursivesort.

//File:14-6.cc

//Teststheproceduresort.

♦include<iostream>

#include<cstdlib>

voidfill_array(inta[],intsize,int&number_used);

//Precondition:sizeisthedeclaredsizeofthearraya.

//Postcondition:number_usedisthenumberofvaluesstored

//ina[0]througha[number_used-1]havebeenfilledwith

//nonnegativeintegersreadfromthekeyboard.

voidsort(inta[],intstartrintnumber_used);

//Precondition:start<declaredsizeofarraya,

//number_used<=declaredsizeofthearraya.Thearray

//elementsa[start]througha[number_used-1]havevalues.

//Postcondition:Thevaluesofa[start]through

//a[number_used-1]havebeenrearrangedsothat

//a[start]<=a[start+1]<=.,・<=a[number_used-1].

voidswap_values(int&vl,int&v2);

//Swapsthevaluesofvlandv2.

intindex_of_smallest(constinta[]z

intstart_index,

intnumb㊀r_us㊀d);

//Precondition:0<=start_index<number_used.

//Referencedarrayelementshavevalues.

//Returnstheindexisuchthata[i]isthesmallestof

//thevaluesa[start_index],a[start_index+1],・・・,

//a[number_used-1].

intmain()

usingnamespacestd;

cout<<"Thisprogramsortsnumbersfrom”

<<nlowesttohighest.\nn;

intsample_array[10],number_used;

fill_array(sample_arrayz10,number__used);

sort(sample__arrayz0,number_used);

cout<<nInsortedorderthenumbersare:\nn;

for(intindex=0;index<number_used;index++)

cout<<sample_array[index]<<"n;

cout<<endl;

return0;

)

//Usesiostream.h:

voidfill_array(inta[]rintsize,int&number_used)

{

usingnamespacestd;

cout<<"Enterupto”<<size

<<”nonnegativewholenumbers.\nn

<<"Marktheendofthelistwitha”

<<nnegativenumber.\nH;

intnext,index=0;

cin>>next;

while((next>=0)&&(index<size))

a[index]=next;

index++;

cin>>next;

)

number_used=index;

}

//RecursiveInsertionSort:

//Placesmallestintothelowestposition,thenrecur.

//Sortsarrayfrominitialpositionindextoposition

//number_used-1

voidsort(inta[],intstart,intnumber_used)

(

intindex_of_next_smallest;

if(start<number_used-1)

{//Placethecorrectvalueina[start]:

index_of_next_smallest=

index_of__smallest(azstart,number_used);

swap__values(a[start],a[index__of_next_smallest]);

start++；

sort(azstart,numbereused);

//a[0]<=a[1]<=...<=a[start]arethesmallest

//oftheoriginalarrayelements.

)

)

voidswap__values(int&vl,int&v2)

inttemp;

temp=vl;

vl=v2;

v2=temp;

}

//Recursiveroutine

intindex_of_smallest(constinta[]zintstart_indexzint

number__used)

{

if(start_index==number_used-1)

returnstart_index;

intmin=a[start_index];

intindex_of_min=

index_of_smallest(a,start_index+l,number_used);

if(min>a[index_of_min])

returnindex_of_min;

else

returnstart_index;

}

8.TowersofHanoi

//ch9Prob7.cpp

//TowersofHanoi

♦include<iostream>

voidtowers(intcount,charsrc,chardestzcharspare)

usingstd::cout;usingstd::endl;

if(1==count)

cout<<"Moveadiskfrompost”<<src

<<"topost”<<dest<<endl;

else

(

towers(count-1,src,spare,dest);

towers(1,src,dest,spare);

towers(count-1,spare,dest,src);

)

)

intmain()

(

usingstd::cout;usingstd::endl;

usingstd::cin;

cout<<"TOWERSofHanoi"<<endl;

cout<<"Enteranumberofdiskstoplay.

<<”1111givenecessarymoves.\nn;

intnumber;

charA=1A1,B=C=;

cin>>number;

cout<<number<<endl;

towers(number,A,B,C);

return0;

)

Atypicalrun:

TOWERSofHanoi

Enteranumberofdiskstoplay.I!11givenecessarymoves.

3

MoveadiskfrompostAtopostB

MoveadiskfrompostAtopostc

MoveadiskfrompostBtopostc

MoveadiskfrompostAtopostB

MoveadiskfrompostCtopostA

MoveadiskfrompostCtopostB

MoveadiskfrompostAtopostB

//

***********************************************************************

//Chl4Proj9.cpp

//

//ThisprogramcalculatesarecursivesolutiontotheJumpIt!game.

//

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

#include<iostream>

usingnamespacestd;

//Functionprototyptes

intjumplt(intboard[]);

//============-------

//jumpit:

//Solvestheproblemrecursivelybythefollowing:

//Ifthecurrentpositionistheendoftheboardthen

//simplyreturnthevalueatboard[currentposition].

//Otherwise,returntheminimumofjumplt(currentPosition+1)and

//jumplt(currentPosition+2)+board[currentposition]

//====================

intjumplt(intboard[],intcurpositionzconstintboardsize)

(

if(curposition==boardsize-1)

(

returnboard[curposition];

)

elseif(curposition==boardsize)

//Ifwereachthiscasewetriedtojump

//pasttheend,whichisinvalid.

//Returnalargecostsowewon'tpickthis

//solution.

return99999999;

)

//Costifwemoveonepieceforward

intjumpl=jumpIt(board,curposition+1,boardsize);

//Costifwejumpthenextsquare

intjump2=jumplt(board,curposition+2zboardsize);

if(jump1<jump2)

returnjumpl+board[curposition];

else

returnjump2+board[curposition];

mainfunction

intmain()

(

intboard[]={0,3,80,6,57,10};

intboardsize=6;

n

cout<<Theoptimalsolutionhascostof”<<jumplt(board,0Aboardsize)

<<endl;

return0;

*****★★★************★★****★************★*****★*************★******★****

//Chl4ProjlO.cpp

//

//Thisprogramcalculatesarecursivesolutiontothenumberof

//chocolatebarswecangetifitcosts$l/barandeachbarhasa

//couponwhere7couponsgetsusanadditionalfreebar.

//

***********************************************************************

#include<iostream>

usingnamespacestd;

//Functionprototyptes

intcomputeBars(intdollars,intcoupons);

//

//computeBars:

//dollarsandcouponsistheinitialnumberofdollarsand

//couponswehave.

//Solvestheproblemrecursivelybythefollowing:

//ifdollars=0andcoupons<7return0

//bars=dollars(spendalldollarsonbars)

//coupons+=bars(newcouponsfromeachbarwejustgot)

//return(bars)+computeBars(coupons/7,coupons%7)

//

intcomputeBars(intdollars,intcoupons)

(

if((dollars==0)&&(coupons<7))

(

return0;

)

intbars=dollars;

coupons+=bars;

returnbars+computeBars(coupons/7Zcoupons%7);

)

//====================

//mainfunction

//====================

intmain()

(

intdollars;

intbars;

cout<<"Enternumberofdollarsyouwanttospendoncandybars.\nn;

cin>>dollars;

bars=computeBars(dollars,0);

cout<<"Youcanget”<<bars<<"barswith$"<<dollars<<*'.\nn;

return0;

11.

//*********************************************************************

//Chl4Projll.cpp

//

//Writearecursiveprogramthatgeneratesallthepermutationsofaset

//ofnumbers.

/I*********************************************************************

//FileName:permutations.cpp

//Author:

//EmailAddress:

//ProjectNumber:14.11

//Description:Recursivelyfindsallpermutationsofasetofintegers

//LastChanged:October13r2007

#include<vector>

#include<iostream>

usingnamespacestd;

//Nodestructureusedtocreateasimplelinkedlist

//ofvectors.Eachnode'svectorwillcontainaunique

//permutation.

structNode

(

vector<int>numbers;

Node*next;

)；

typedefNode*NodePtr;

voidprint_permutations(intn);

//Usesthepermutationsfunctiontoprintallpermutationsof

//thefirstnwholenumbers

NodePtrpermut