應(yīng)用數(shù)學(xué)專業(yè)外文翻譯-其他專業(yè)-文庫吧資料
2025-01-27 11:08本頁面
【正文】 ee 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 the Tower of Hanoi, this is the recurrence solution (). The third stage is the one we will concentrate on throughout this book. In fact, we39。t ended； they39。 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。 T6 = 231+1= 63. Aha! It certainly looks as if Tn = 2n?1， for n≥0. () 武漢科技大學(xué)本科畢業(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。 T4 = 27+1= 15。t made a foolish error. Such checks will be especially valuable when we get into more plicated maneuvers in later chapters.) A set of equalities like () is called a recurrence (a. k. a. recurrence relation or recursion relation). It gives a boundary value and an equation for the general value in terms of earlier ones. Sometimes we refer to the general equation alone as a recurrence, although technically it needs a boundary value to be plete. The recurrence allows us to pute Tn for any n we like. But 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。t shown that 2Tn—1+1 moves are necessary. A clever person might be able to think of a shortcut. 武漢科技大學(xué)本科畢業(yè)論文外文翻譯 3 But is there a better way? Actually no. At some point we must move the largest disk. When we do, the n?1 smallest must be on a single peg, and it has taken at least Tn?1 moves to put them there. We might move the largest disk more than once, if we39。 because our construction proves only that 2Tn—1+1 moves suffice。 instead of 39。s change our perspec
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1