微软100题第18题（求出在这个圆圈中剩下的最后一个数字）

微软100题第18题（求出在这个圆圈中剩下的最后一个数字）

————————————————------------------------------------------------------------------------------------------------------------------

1scala版本

package ms/** * 第18题（数组）：题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。 */class Circle(){ var start=Node(0) def this(n:Int){ this() var tmp=start; for(i<-1 until n){ tmp.next=Node(i) tmp=tmp.next } tmp.next=start; } def printCircle(){ var tmp=start while(tmp.next!=start){ print(tmp.value+",") tmp=tmp.next } print(tmp.value+",") } def computeLast(m:Int):Int={ while(start.next!=start){ for(i<-0 until m-2){ start=start.next } start.next=start.next.next start=start.next } return start.value } case class Node(val value:Int,var next:Node=null)}object MicroSoft018 { def main(args: Array[String]): Unit = { val c=new Circle(10) c.printCircle() println() println(c.computeLast(3)) } }

2java版

3python版本

'''Created on 2017-1-18@author: admin'''from _overlapped import NULLclass Circle: def __init__(self,n): if n<0: raise ValueError self.start=self.Node(0) tmp=self.start for i in range(1,n): tmp.next=self.Node(i) tmp=tmp.next tmp.next=self.start def computeLastValue(self,m): while self.start.next!=self.start: for i in range(0,m-2): self.start=self.start.next self.start.next=self.start.next.next; self.start=self.start.next return self.start.value def printCircle(self): tmp=self.start while(tmp.next!=self.start): print(tmp.value,end=",") tmp=tmp.next print(tmp.value) class Node: def __init__(self,value): self.value=value self.next=NULLif __name__ == '__main__': c=Circle(10) c.printCircle() print(c.computeLastValue(3))

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。