應用數(shù)學專業(yè)外文翻譯-其他專業(yè)(編輯修改稿)
2025-02-24 11:08 本頁面
【文章內(nèi)容簡介】 nobody really like to pute from a recurrence， when n is large； it takes too long. The recurrence only gives indirect, local information. A solution to the recurrence would make us much happier. That is, we39。d like a nice, neat, closed form for Tn that lets us pute it quickly， even for large n. With a closed form, we can understand what Tn really is. So how do we solve a recurrence? One way is to guess the correct solution, then to prove that our guess is correct. And our best hope for guessing the solution is to look (again) at small cases. So we pute, successively, T3 = 23+1= 7。 T4 = 27+1= 15。 T5 = 215+1= 31。 T6 = 231+1= 63. Aha! It certainly looks as if Tn = 2n?1， for n≥0. () 武漢科技大學本科畢業(yè)論文外文翻譯 4 At least this works for n≤6. Mathematical induction is a general way to prove that some statement about the integer n is true for all n≥n0. First we prove the statement when n has its smallest value,no。 this is called the basis. Then we prove the statement for n n0,assuming that it has already been proved for all values between n0 and n?1, inclusive。 this is called the induction. Such a proof gives infinitely many results with only a finite amount of work. Recurrences are ideally set up for mathematical induction. In our case, for example， () follows easily from ()： The basis is trivial， since T0 = 20?1= the induction follows for n 0 if we assume that () holds when n is replaced by n?1： Tn= 2Tn+1= 2(2n?1?1)+1=2n?1. Hence () holds for n as well. Good! Our quest for Tn has ended successfully. Of course the priests39。 task hasn39。t ended； they39。re still dutifully moving disks,and will be for a while, because for n = 64 there are 264?1 moves (about 18 quintillion). Even at the impossible rate of one move per microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. Lucas39。s original puzzle is a bit more practical, It requires 28?1 = 255 moves, which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applications of all kinds. In finding a closedform expression for some quantity of interest like Tn we go through three stages： 1 Look at small cases. This gives us insight into the problem and helps us in stages 2 and 3. 2 Find and prove a mathematical expression for the quantity of interest. For the Tower of Hanoi, this is the recurrence () that allows us, given the inclination， to pute Tn for any n. 3 Find and prove a closed form for our mathematical t
范文總結(jié)相關推薦
鄂ICP備17016276號-1