For 2n Persons (n=1,2,3,...) 2n-1 -12 n persons left 假设在规模为n 的问题中,解 是m:J(n)=m m-l ?=J(2n)=2m-1=2J(n)-1
For 2n Persons (n=1,2,3,... ) 1 2n 2 2n-1 3 n persons left ?=J(2n) 假设在规模为n 的问题中,解 是m:J(n)=m 1 2 3 m m-1 ? =2m-1=2J(n)-1
And What about 2n+1 Persons (=1,2,3,... m- 2n 2+y-35 2n-1X do the same: n persons left i- k+1 The smaller problem's solution is:J(n) And the solution of the original problem 2n+1 is 2+1
And What about 2n+1 Persons (n=1,2,3,... ) 1 2n+1 2 2n 3 k+1 k k-1 3 2n+1 5 2n-1 7 k+3 k+1 k-1 do the same: n persons left The smaller problem’s solution is: J(n) And the solution of the original problem 2n+1 is ...... 2J(n)+1
递归方程:奇偶数分情况列出 J01)=1; J2m)=2Jn)-1, forn≥1g J2m+1)=2Jm)+1, forn≥1. 间题3 你能解出这个递归式吗? 你能看出什么规律吗? 8 9 10 1112 13 14 15 16 17 J(n) 3 35 3 579 111315 3
递归方程:奇偶数分情况列出 n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 J(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1 3