"2017阿里巴巴机试题目"

  "约瑟夫问题"

Posted by Kakarotto on March 17, 2017

30分钟实在太紧

基础实在太不扎实

说多了都是泪

题目描述:

N个人抢红包,面额有1,5,10,终极红包是10000,每个人依次抢红包。抢到红包为10的退出,最后留下的人拿10000的红包,问最后是谁拿到10000的红包。

模型建立

本质上就是N个人报数,报到数为3的人退出,然后下一个人接着报一,当报到最后一个人时,就回到第一个人重新报数,但是注意如果最后一个人报的是2,那么第一个人就要接着报3。人数会越来越少,所以最后剩下的人就是拿到最大红包的人。

暴力解法

时间就30分钟,也不知道这种相关算法,直接硬着头皮解,大致思路是把n个人存为一个数组,(元素下标+M)mod 3==0的,让这个元素为零。然后把元素为零的去处掉,形成新的数组,最后剩下一个数就是所求。

关键问题是,前一次最后一个人报的数和整个数组的长度将影响下一次M的取值,其实就是前一次M的取值和数组长度直接影响后一次M的取值,直接暴力枚举有九种可能,详情见后面程序。

程序实现

用python写相关程序:

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 17 13:23:46 2017

@author: Kakarotto
"""


def union(lst_1):
    lst_2=[]
    for i in lst_1:
        if i!=0:
            lst_2.append(i)
    return lst_2  
def clear_lst(lst_1,m):
    for index,i in enumerate(lst_1):
        if (index+m)%3==0:
            lst_1[index]=0
    return lst_1,len(lst_1)
n=input()
lst=range(n+1)[1:]
m=1
for i in range(n):
    lst,leng=clear_lst(lst,m)
    if m==1:
        if leng%3==1:
            m=2
        elif leng%3==2:
            m=0
        else:
            m=1
    elif m==2:
        if (leng-2)%3==1:
            m=2
        elif (leng-2)%3==2:
            m=0
        else:
            m=1
    else:
        if (leng-1)%3==1:
            m=2
        elif (leng-1)%3==2:
            m=0
        else:
            m=1    
    lst=union(lst)
    if len(lst)==1:
        break
print lst[0]

然而尼玛时间不够啊,if条件我没枚举完,说多了都是泪。

正确解法

微信询问647(某大牛),告诉我是约瑟夫环问题,遂百度之,吐了一口老血。。。。。。。。

其实这个数学模型非常简单,大致思想如下: 首先我们来模拟一下算法操作,假设这个数列为:

[1,2,3,4,5,6,7,8,9,10]

我们首先让第一个人出列,然后将前面的数放在最后得到这样的数列:

[4,5,6,7,8,9,10,1,2]

所以每次操作我们只操作一次,然后将前面的数放在最后去,得到新的数列,然后继续下次操作。

我们假设这个数列长为n,报到第k个数的人出列。我们再假设最后留下的人的下标为f(n,k),注意这个下标是在数列长度为n的情况,当按上述操作一次后,长度就会变为n-1,且由于我们把数列进行了变换,使得这时候最后留下的人的坐标在操作一次后有了改变。改变为多少呢? 显然两种情况:

  • f(n-1,k)=f(n,k)-k
  • f(n-1,k)=f(n,k)+n-k

所以整理上面的等式,再注意f(n-1,k)下标是不能超过n的,所以我们有递推等式:

f(n,k)=(f(n-1,k)+k)%n

这个递推等式是从f(1,k)开始的,很显然f(1,k)剩下的人在长度为1的数列下标为0,所以根据上面的递推就能很快的算出,最后留下的人是多少了。

n=input()#输入人数
k=input()#输入报数要出去的数字
f=0
for i in range(n+1)[2:]:
    f=(f+k)%i
print f+1

继续吐了一口血。。。。。。。

时间完全绰绰有余。。。。。。。。