用回朔的办法解递归 L(m)=L(n-1)+n =L(n-2)+(n-1)+n =L(n-3)+(m-2)+(n-1)+n =L(0)+1+2+.+-2)H(m-l)tn L(m=nn+l)/2+1
用回朔的办法解递归 L(n) = L(n-1)+n = L(n-2)+(n-1)+n = L(n-3)+(n-2)+(n-1)+n = …… = L(0)+1+2+……+(n-2)+(n-1)+n L(n) = n(n+1)/2 + 1
递归思维:Josephus问题 ■ Live or die,it's a problem! Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents.During the Jewish Roman war,he was among a band of 41 Jewish rebels trapped in a cave by the Romans.Preferring suicide to capture,the rebels decided to form a circle and,proceeding around it,to kill every third remaining person until no one was left.But Josephus,along with an unindicted co-conspirator,wanted none of this suicide nonsense;so he quickly calculated where he and his friend should stand in the vicious circle. We use a simpler version: “every second
递归思维:Josephus 问题 Live or die, it’s a problem! Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish Roman war, he was among a band of 41 Jewish rebels trapped in a cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend should stand in the vicious circle. We use a simpler version: “every second
试试看:n=10 3 survivor J(10)=5
试试看:n=10 1 8 7 6 2 4 5 10 3 9 1 7 5 9 3 1 7 5 9 3 survivor J(10)=5
For 2n Persons (n=1,2,3,...) 2m黑-& 2n-1 3 2n3 2n- n persons left 下一轮将如何进行?它和上一轮有什么相同之处?
For 2n Persons (n=1,2,3,... ) 1 2n 2 2n-1 3 k+1 k k-1 1 2n-1 3 2n-3 5 k+3 k+1 k-1 n persons left 下一轮将如何进行?它和上一轮有什么相同之处?
For 2n Persons (n=1,2,3,...) 2n-1上13 12 2- 5将“第二轮”的问 题看做规模为n的 问题 假设在规模为n 的问题中,解 是m:J(n)=m 0-】 规模为n的问题中,解是m,这个m在2n规模问题中,位置在哪里?
For 2n Persons (n=1,2,3,... ) 1 2n-1 3 2n-3 5 k+3 k+1 k-1 1 2 3 m+1 m m-1 将“第二轮”的问 题看做规模为n的 问题 规模为n的问题中,解是m,这个m在2n规模问题中,位置在哪里? 假设在规模为n 的问题中,解 是m:J(n)=m