用回朔的办法解递归 L(m)=L(-1)+n =L(n-2)+(n-1)+n =L(n-3)+(m-2)+(n-1)+n =L(0)+1+2+..+(n-2)t(n-1)tn L(m=n(n+)/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
试试看：=10 101-2 ZK-K survivor J(10)=5
试试看：n=10 1 8 7 6 2 4 5 10 3 9 survivor J(10)=5
我们有个递归的感觉 10一 J(10)=5 J(5)=3 J(2)=1 ·一轮一轮地寻找答案：幸存的解释是一样的 ·轮中元素的编码有变化，但是两轮之间编码可变换 ”抛去“编码”，幸存的是同一个人
我们有个递归的感觉 ◼ 一轮一轮地寻找答案：幸存的解释是一样的 ◼ 轮中元素的编码有变化，但是两轮之间编码可变换 ◼ 抛去“编码”，幸存的是同一个人 1 8 7 6 2 4 5 10 3 9 J(10)=5 1 4 3 2 5 1 2 J(5)=3 J(2)=1
一般的n呢？ 3 In/2]Y “一轮”之后 问题转换 如果J(n/2)中幸存者为m ,J()中应该是哪个？ “二轮”问题 原问题J(n) J(In/2J) ?和m什么关系？
一般的n呢？ 1 n 2 n-1 3 k+1 k k-1 “一轮”之后 原问题J(n) 1 n? 2 n-1 3 k k+1 k-1 1 ہn/2ۂ 2 k “二轮”问题 J(ہn/2ۂ( 问题转换 ? m 如果J(ہn/2ۂ(中幸存者为m ，J(n)中应该是哪个？ 如果J(ہn/2ۂ(中幸存者为m ，J(n)中应该是哪个？ ？和m什么关系？