aRe00t · August 29, 2015 14:24
diff --git a/who_is_the_lucky_dog.py b/who_is_the_lucky_dog.py
 # encoding: utf-8
 # http://weibo.com/1915548291/CqcYV0Ga3
 # 1到n个人排成一圈，从编号为1的人开始，依次说白，黑，白，黑，。。。，说到黑的人离队，问最后留下编号为几的人。


 def who_is_the_lucky_dog(n):
    if n < 1:
        return 'n must be greater than 0'
    elif n == 1:
        return 1
    else:
        if n % 2 == 0:
            return who_is_the_lucky_dog(n / 2) * 2 - 1
        else:
            x = who_is_the_lucky_dog((n + 1) / 2)
            return n if x == 1 else 2 * x - 3


 if __name__ == '__main__':
    print who_is_the_lucky_dog(99999999999999999999999999999999999999999999999999999999999999999999)
    seq = range(1, 100)
    print '\n'.join(["n = %s, it's %s" % item for item in zip(seq, map(who_is_the_lucky_dog, seq))])

 # 92160213331397440821331939651921477305451422309837710075585559003135
 # n = 1, it's 1
 # n = 2, it's 1
 # n = 3, it's 3
 # n = 4, it's 1
 # n = 5, it's 3
 # n = 6, it's 5
 # n = 7, it's 7
 # n = 8, it's 1
 # n = 9, it's 3
 # n = 10, it's 5
 # n = 11, it's 7
 # n = 12, it's 9
 # n = 13, it's 11
 # n = 14, it's 13
 # n = 15, it's 15
 # n = 16, it's 1
 # n = 17, it's 3
 # n = 18, it's 5
 # n = 19, it's 7
 # n = 20, it's 9
 # n = 21, it's 11
 # n = 22, it's 13
 # n = 23, it's 15
 # n = 24, it's 17
 # n = 25, it's 19
 # n = 26, it's 21
 # n = 27, it's 23
 # n = 28, it's 25
 # n = 29, it's 27
 # n = 30, it's 29
 # n = 31, it's 31
 # n = 32, it's 1
 # n = 33, it's 3
 # n = 34, it's 5
 # n = 35, it's 7
 # n = 36, it's 9
 # n = 37, it's 11
 # n = 38, it's 13
 # n = 39, it's 15
 # n = 40, it's 17
 # n = 41, it's 19
 # n = 42, it's 21
 # n = 43, it's 23
 # n = 44, it's 25
 # n = 45, it's 27
 # n = 46, it's 29
 # n = 47, it's 31
 # n = 48, it's 33
 # n = 49, it's 35
 # n = 50, it's 37
 # n = 51, it's 39
 # n = 52, it's 41
 # n = 53, it's 43
 # n = 54, it's 45
 # n = 55, it's 47
 # n = 56, it's 49
 # n = 57, it's 51
 # n = 58, it's 53
 # n = 59, it's 55
 # n = 60, it's 57
 # n = 61, it's 59
 # n = 62, it's 61
 # n = 63, it's 63
 # n = 64, it's 1
 # n = 65, it's 3
 # n = 66, it's 5
 # n = 67, it's 7
 # n = 68, it's 9
 # n = 69, it's 11
 # n = 70, it's 13
 # n = 71, it's 15
 # n = 72, it's 17
 # n = 73, it's 19
 # n = 74, it's 21
 # n = 75, it's 23
 # n = 76, it's 25
 # n = 77, it's 27
 # n = 78, it's 29
 # n = 79, it's 31
 # n = 80, it's 33
 # n = 81, it's 35
 # n = 82, it's 37
 # n = 83, it's 39
 # n = 84, it's 41
 # n = 85, it's 43
 # n = 86, it's 45
 # n = 87, it's 47
 # n = 88, it's 49
 # n = 89, it's 51
 # n = 90, it's 53
 # n = 91, it's 55
 # n = 92, it's 57
 # n = 93, it's 59
 # n = 94, it's 61
 # n = 95, it's 63
 # n = 96, it's 65
 # n = 97, it's 67
 # n = 98, it's 69
 # n = 99, it's 71
	# encoding: utf-8
	# http://weibo.com/1915548291/CqcYV0Ga3
	# 1到n个人排成一圈，从编号为1的人开始，依次说白，黑，白，黑，。。。，说到黑的人离队，问最后留下编号为几的人。


	def who_is_the_lucky_dog(n):
	if n < 1:
	return 'n must be greater than 0'
	elif n == 1:
	return 1
	else:
	if n % 2 == 0:
	return who_is_the_lucky_dog(n / 2) * 2 - 1
	else:
	x = who_is_the_lucky_dog((n + 1) / 2)
	return n if x == 1 else 2 * x - 3


	if __name__ == '__main__':
	print who_is_the_lucky_dog(99999999999999999999999999999999999999999999999999999999999999999999)
	seq = range(1, 100)
	print '\n'.join(["n = %s, it's %s" % item for item in zip(seq, map(who_is_the_lucky_dog, seq))])

	# 92160213331397440821331939651921477305451422309837710075585559003135
	# n = 1, it's 1
	# n = 2, it's 1
	# n = 3, it's 3
	# n = 4, it's 1
	# n = 5, it's 3
	# n = 6, it's 5
	# n = 7, it's 7
	# n = 8, it's 1
	# n = 9, it's 3
	# n = 10, it's 5
	# n = 11, it's 7
	# n = 12, it's 9
	# n = 13, it's 11
	# n = 14, it's 13
	# n = 15, it's 15
	# n = 16, it's 1
	# n = 17, it's 3
	# n = 18, it's 5
	# n = 19, it's 7
	# n = 20, it's 9
	# n = 21, it's 11
	# n = 22, it's 13
	# n = 23, it's 15
	# n = 24, it's 17
	# n = 25, it's 19
	# n = 26, it's 21
	# n = 27, it's 23
	# n = 28, it's 25
	# n = 29, it's 27
	# n = 30, it's 29
	# n = 31, it's 31
	# n = 32, it's 1
	# n = 33, it's 3
	# n = 34, it's 5
	# n = 35, it's 7
	# n = 36, it's 9
	# n = 37, it's 11
	# n = 38, it's 13
	# n = 39, it's 15
	# n = 40, it's 17
	# n = 41, it's 19
	# n = 42, it's 21
	# n = 43, it's 23
	# n = 44, it's 25
	# n = 45, it's 27
	# n = 46, it's 29
	# n = 47, it's 31
	# n = 48, it's 33
	# n = 49, it's 35
	# n = 50, it's 37
	# n = 51, it's 39
	# n = 52, it's 41
	# n = 53, it's 43
	# n = 54, it's 45
	# n = 55, it's 47
	# n = 56, it's 49
	# n = 57, it's 51
	# n = 58, it's 53
	# n = 59, it's 55
	# n = 60, it's 57
	# n = 61, it's 59
	# n = 62, it's 61
	# n = 63, it's 63
	# n = 64, it's 1
	# n = 65, it's 3
	# n = 66, it's 5
	# n = 67, it's 7
	# n = 68, it's 9
	# n = 69, it's 11
	# n = 70, it's 13
	# n = 71, it's 15
	# n = 72, it's 17
	# n = 73, it's 19
	# n = 74, it's 21
	# n = 75, it's 23
	# n = 76, it's 25
	# n = 77, it's 27
	# n = 78, it's 29
	# n = 79, it's 31
	# n = 80, it's 33
	# n = 81, it's 35
	# n = 82, it's 37
	# n = 83, it's 39
	# n = 84, it's 41
	# n = 85, it's 43
	# n = 86, it's 45
	# n = 87, it's 47
	# n = 88, it's 49
	# n = 89, it's 51
	# n = 90, it's 53
	# n = 91, it's 55
	# n = 92, it's 57
	# n = 93, it's 59
	# n = 94, it's 61
	# n = 95, it's 63
	# n = 96, it's 65
	# n = 97, it's 67
	# n = 98, it's 69
	# n = 99, it's 71