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

《C++大学教程课后习题答案13.pdf》由会员分享，可在线阅读，更多相关《C++大学教程课后习题答案13.pdf（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Chapter 14RECURSION1.Solutions to and Remarks on Selected Programming Assignments1.Fibonacci NumbersThese solutions have been tested under two Linux versions using two versions of g+,under Windows XP with VC+6.0 and Borland 5.0.The full recursive version is slow.Ittakes about 17 seconds for 1 comput

2、ation of Fib 1(35)on an older,very slow machine(i486DX2/100,16 MB RAM).On a more modem machine(1 GHz Athlon.266 MHz front sidebus,512 MB DDR RAM,fast disk drives)it runs a bit faster:N=35 takes 3 seconds,N=40 takes about 30 seconds,N=41 about 50 seconds,and N=42 takes 80 seconds.A valueof N greater

3、than 47 results in integer overflow and incorrect results with all the compilersmentioned above.With most implementations,long in t is a type the same size as in t.Because there area few implementations that provide a long in t that is longer than an in t,I used long asthe argument and return types

4、for the fib function.To get Fibonacci numbers up to N=50 for checking the results of the program,I changedthe long type in the recursive function to long long(a 19 digit integer type supportedby GNU g+,but not ANSI/ISO C+).I compiled this using g+-3.0 under the DebianLinux 3.0 operating system on a

5、K6-2/350 with a 100 MHz backplane and 400K RAM.Onthis somewhat slow machine,this version of the program took about two hours for N=50,giving presumably correct results.(I acknowledge that I did not look them up.)The resultsagree with the code with a long return and long parameter type up to N=47.Thi

6、s function computes and discards too many of the Fibonacci numbers.This kind ofrecursion is called umbrella recursion*because it spreads like an umbrella,recomputingvalues many times.1Copyright 2008 Pearson Education,Inc.Publishing as Pearson Addison-Wesley/File：chl4prglFibonacci.cc/Chapter 14,Progr

7、amming Problem#1/Write a recursive function for a function having one/parameter that generates the nth Fibonacci number.#include#include/This is the full recursive version.unsigned long Fibl(int n)if(n=0|n=1)return 1；return Fibl(n-1)+Fibl(n-2)；)int main()using namespace std；cihar ans；dntoNcout 工 wil

8、l display fibonacci numbers 0-N.n；cout N；for(int i=0；icout Fibl(i)cout ans；while(Y*=ansreturn 0；N;i+)endl；continue,I I y=anything else quitsll；ans)；2.Recursive Index of SmallestCAUTIONS:Please warn the student that number_used is NOT the largest index used,rather itis the number of elements.This was

9、 my hardest-to-find-error in coding this.I also recommend that the student remove theSort function from Display 10-12.Including Sort obscures the behavior of thein d e x _ o f_ sm allest.I had it finding the maximum,but I didnt spot that until I removedthe sort routine and its support routines.This

10、is modified from code of the text.I prefer that the student not reinvent the wheel:use.Sheshould reuse code from the texts Displays to advantage!/f i l e:c h l4 p rg 2.cc/T e s ts th e p ro ced u re re c u rs iv e fu n c tio n in d e x _ o f_ sm allest/S o rt ro u tin e removed to sim p lify th e te

11、 s tin g en v iro n m en t.#in clu d e v o id f i l l _ a r r a y(in t a z in t s i z e,int&num ber_used)；/P re c o n d itio n：s iz e is th e d e c la re d s iz e of th e a rra y a./P o s tc o n d itio n：num ber_used is th e number of v a lu e s sto re d/i n a 0 th ro u g h anum ber_used-1 have been

12、 f i l l e d w ith/n o n n eg ativ e in te g e rs re a d from th e k ey b o ard.in t in d e x _ o f_ sm a lle st(c o n st in t a zin t s ta r t_ in d e xz in t num ber_used)；/NOTE：d e sig n and im p lem en tatio n of th is fu n c tio n a re a t/th e end of th is f i l e./P re c o n d itio n：0=s ta r

13、t_ in d e x num ber_used./R e fe re n c e d a rra y elem ents have v a lu e s./R e tu rn v alu e is th e index i such th a t a i is th e s m a lle st/o f th e v a lu es/a s ta r t_ in d e x ,a s ta rt_ in d e x +1 ,.,anum ber_used-1.in t m ain()u sin g nam espace s t d；cout This program tests recurs

14、ive function index_of_smallest endl endl；int sample_array 10,number_used；fill_array(sample_array,10 z number_used)；int i=index_of_smallest(sample_array,0,number_used)；cout The number of elements is number_used endl；cout For the minimum element in the array INDEX=i endl；cout The array element is endl

15、 endl；sample_arrayicout The elements in the array are：n；for(int index=0；index number_used；index+)cout sample_arrayindex cout endl；return 0；)/Uses iostreamvoid fill_array(int a,int size,int&number_used)using namespace std；cout nEnter up to”size nonnegative whole numbers.nn Mark the end of the list wi

16、th”n e x t；w hile(next=0)&(index n e x t；)num ber_used=in d e x；)Recursive Function I ndex_o f _Sma 11 e s tThis recursive function returns the index of the minimum element in the array segment betweens ta rt_ in d e x and num ber_used.Non recursive Case:If we have only one element in a subarray whe

17、re s ta rt_ in d e x has thevalue num ber_used then that element is the minimum,and s ta rt_ in d e x is the index wewant.Recursive Case:If there is more than one element,take the element with smallest index andcompare its value to the minimum value of the array element at index returned by the func

18、tionoperating on the rest of the array.in t in d e x _ o f_ sm a lle st(c o n st in t a ；in t s ta r t_ in d e xz in tnum ber_used)-i f (start_index=num bereused-1)re tu rn start_index；in t min=a s ta rt_ in d e x；in t index_of_m in=in d e x _ o f_ sm a lle st(a,s ta r t_ in d e x+l,num ber_used)；if

19、(m in a index_of_m in)re tu rn index_of_m in；e ls ereturn start_index；)A typical run:This program tests recursive function index_of_smallestEnter up to 10 nonnegative whole numbers.Mark the end of the list with a negative number.4 3 5 6 0 3-1The number of elements is 6For the minimum element in the

20、array INDEX=4The array element is 0The elements in the array are：4 3 5 6 0 3Another test run:This program tests recursive function index_of_smallestEnter up to 10 nonnegative whole numbers.Mark the end of the list with a negative number.9 2 3 8 4 5 6 3 2 9-1The number of elements is 10For the minimu

21、m element in the array INDEX=1The array element is 2The elements in the array are：9 2 3 8 4 5 6 3 2 93.No Solution Provided.4.Binomial Coefficients.Write a recursive function that uses the given recursive formula to calculate binomialcoefficients.Test.A second part gives a conventional formula for t

22、he factorial,instructs the student todiscover a recursive versions and to write a recursive function for the factorial.Test.Notes only on this problem.The students should have seen the Pascal Triangle inmathematics courses by this time.If not,suggest it to them.I do it this way:(x+y)1=l*x+l*y(x+y)2=

23、l*x2+2*x*y+2*y2(x+y)3=l*x3+3*x2*y1+3*x1*y2+y3(x+y)4=l*x4+4*x3*yr+6*x2*y2+4*x1*yi+y4(x+y)5=l*x5+5*x4*yL+10*x3*y2+10*x2*y3+5*x1*y4+x5Where the coefficients are1i1 31 41 5 10123610114 15 1The coefficients,when rearranged are:1 11 21 31 41 513 16 4 110 10 51Then we identify the rows with C(n,r)where the

24、 n is the second entry in any row,andr is the column of that row,starting with 0：C(l,0)C(l,l)C(2,0)C(2Z1)C(2,2)C(3z0)C(3Z1)C(3,2)C(3,3)C(4,0)C(4,l)C(4,2)C(4,3)C(4,4)C(5,0)C(5,1)C(5,2)C(5Z 3)C(5,4)C(5Z 5)Prod the students a little.They will see that adding any two row items gives the valuedirectly un

25、der the second item.There is the recursion relation they need:C(nz r)+C(nz r+1)=C(n+1,r+1)This is another umbrella recursion,similar in this respect to Programming problem#1.Ittakes considerable time and space to do this with recursion.If binomial coefficients are really needed,a bunch of them are l

26、ikely needed.It is better touse a solution where all the coefficients up to those needed are computed and stored(insome global array,or it could be arranged for the function to return a currently availablevalue,or if it is not available,to compute all binomial coefficients up to the one desired.(Thi

27、s is a good place for the ideas of a dynamic array or a source1 1 class.)5.Recursive Reverse Array Segment.The problem is to recursively reverse an array segment.The function takes an arrayargument and two integer arguments that specify the start and the end of the segment of thearray to be reversed

28、.void recursive_reverse(int a z int start,int end)；The task is split into two pieces:Non Recursive:Here if there is only one element,we are done or if there are twoelements,we can just swap them,and we are done.Recursive:Reverse the start and end elements.A recursive call is made to thefunction to f

29、inish the job:recursive_reverse(a,start+1z end-1)；House keeping:How do we know if there is only one element?How do we knowwe have only two elements?If there is an odd number of array elements to be swapped,we take care of two attime.We wind up with one array element for the non-recursive case to dea

30、l with.Then we can tests t a r t =end.How do you know there are only two elements to be swapped?If s t a r t +1=end,then there only two elements.We swap them and quit.Recursive case:If there is an even number of array elements to be swapped,all of them will be dealtwith in the recursive case.There w

31、ill be one last recursive call made with an arrayof two elements(s ta rt+1 =end).In this call,this last pair will beswapped.There will be one last recursive call with start argument s t a r t +1+1and end argument e n d-1.This makes the values of s t a r t and end in the nextrecursive call have value

32、s such that s ta r t e n d.This signals that the last pairhave been swapped.(Actually,the two element subcase can be removed.The explanation is somewhat moreobscure.)Code:#in clu d e v o id re c u rs iv e _ re v e rs e(c h a r a ,in t s t a r t z in t end)(i f(s t a r t =end)/jo b is done 1r e tu r

33、n；i f(s t a r t +1=end)/o n ly two e le m e n ts,swap them(ch ar temp=a s t a r t ；a s ta rt=a e n d；a end=temp；return；)/make recursive call to finish/swap start and end elementschar temp=a start；a start=a end；aend=temp；/make recursive call to finishrecursive_reverse(a,start+1,end-1)；int main()(usin

34、g namespace std；char a 20；for(int i=0；i 20；i+)a i=*A+i；cout array：endl；for(i=0;i 20;i+)cout a i H；cout endl；recursive_reverse(a,5 z 19)；cout narray with elements/end is an array elementwith index 5-19 reversednnfor(i=0;i 20;i+)cout ai cout endl；for(i=0;i 20;i+)a i=f A1+i；cout array：endl；for(i=0;i 20

35、;i+)cout ai H；cout endl；recursive_reverse(az 3 z 12)；/end is an array elementcout array with elements with index 3-12 reversednH；for(i=0;i 20;i+)cout ai cout endl；A Trial run:array：A B C D E F G H I JK L M N O P Q RS Tarray with elements with index 5-19 reversedA B C D E T S R Q PO N M L K J I HG Fa

36、rray：A B C D E F G H I JK L M N O P Q RS Tarray with elements with index 3-12reversedA B C M L K J I H GF E D N O P Q RS TString Reverse IIOnce the function above is fully debugged,define a function that takes a single argumentwhich is an array that contains a string value and that reverses the spel

37、ling of the stringvalue in the array argument.This function calls the recursive function just defined.#include ttinclude void recursive reverse(char a ,int start z int end)；void string_reverse(char str)int length=strlen(str)；recursive_reverse(str,0z length-1)；int main()(using namespace std；char a 20

38、；for(int i=0；i 20；a i=1 A+i；a 19=,0 ；/makecout string beforestring_reverse(a)；cout 1 1 string afterreturn 0；)A trial Run:string before reversing：string after reversing：i+)a string out of it!reversing：a endlreversing：a endlABCDEFGHIJKLMNOPQRSSRQPONMLKJIHGFEDCBA6.Iterative Reverse Char Array Segment/F

39、ile：ch14prg6.cc/Code and test an iterative version of reverse segment from/an array of char.Then write another function that callsthis/to and reverses a string./iterative_reverse：/Swap the endsz back up one from each end,repeat/while start end.#include#include void iterative_reverse(char a口，int star

40、t z int end)(while(start end)(char temp=a start；a start=aend；a end=temp；start+；end-；)void string_reverse(char str)(int length=strlen(str)；iterative_reverse(str,0z length-1)；一const int SIZE=10；int main()(using namespace std；char aSIZE；for(int j =2；j SIZE；j +)for(int i=0；i j；i+)a i=1A*+i；a j-1=1 0 ；/m

41、ake a string out of it!cout nstring before reversing：1 1 a endl；string_reverse(a)；cout string after reversing：1 1 a endl endl；)return 0；)A typical run:string before reversing：Astring after reversing：Astring before reversing：ABstring after reversing：BAstring before reversing：ABCstring after reversing

42、：CBAstring before reversing：ABCDstring after reversing：DCBAstring before reversing：ABCDEstring after reversing：EDCBAstring before reversing：ABCDEFstring after reversing：FEDCBAstring before reversing：ABCDEFGstring after reversing：GFEDCBAstring before reversing：string after reversing：ABCDEFGHHGFEDCBA7

43、.Recursive Sort int arrayThis code was adapted from Display 12-13.The sort routine was rendered recursive.Note that the texts warning from the Chapter Summary must be taken to heart.It isfrequently necessary to do a somewhat more general problem than the iterative code solves.Here,I had to make the

44、recursive sort routine sort from a specified index.The index is theposition that the sorting starts.The fo r loop was able to set with the iterative code but it isnecessary to this pass into the recursive sort./File:14-6.cc/Tests the procedure sort.ttinclude#include void fill_array(int a口，int size,i

45、nt&number_used)；/Precondition：size is the declared size of the array a./Postcondition：number_used is the number of values stored/in a 0 through anumber_used-1 have been filled with/nonnegative integers read from the keyboard.void sort(int a,int start,int number_used)；/Precondition：start declared siz

46、e of array a,/number_used=declared size of the array a.The array/elements astart through anumber_used-1 have values./Postcondition：The values of a start through/anumber_used-1 have been rearranged so that/astart=astart+1=.=a number used-1.void swap_values(int&vl,int&v2)；/Swaps the values of vl and v

47、2.int index_of_smallest(const int a；int start_indexzint number_used)；/Precondition：0=start_index number_used./Referenced array elements have values./Returns the index i such that ai is the smallest of/the values a start_index,a start_index+1，,/a number_used-1.int main()(using namespace std；cout This

48、 program sorts numbers from nlowest to highest.nn；int sample_array10 z numbereused；fill_array(sample_array,10 z number_used)；sort(sample_arrayz 0,number_used)；cout In sorted order the numbers are：n；for(int index=0；index number_used；index+)cout sample_array index ；cout endl；return 0；)/Uses iostream.h

49、：void fill_array(int a,int size,int&number_used)using namespace std；cout Enter up to n size nonnegative whole numbers.n Mark the end of the list with a next；while(next=0)&(index next；)number_used=index；)一/Recursive Insertion Sort：/Place smallest into the lowest position,then recur./Sorts array from

50、initial position index to position/number_used-1void sort(int a z int start,int number_used)(int index_of_next_smallest；if(start number_used-1)/Place the correct value in a start：index_of_next_smallest=index_of_smallest(a,start,number_used)；swap_values(astart,aindex_of_next_smallest)；start+；sort(a,s