递归问题 跑道 汽车 绕圈问题 Python实现

在此用Python实现一个递归问题，感觉自己能简单写递归了。还记得从前看C语言书上的汉诺塔问题真的是。。有些费解，不过现在感觉守得云开见月明了。

问题描述：
一个圆形车道，一共n个位置，有m辆车，开始的位置分别是 0 1一直到m-1，每一轮只能有一个车往前开，但只有前面有空时车才能开，假设每一时刻所以可以移动的车它们移动的概率是相等的。

求 某一时刻所有车的位置的均值的 均值和标准差
求 某一时刻所有车的位置的标准差的 均值和标准差

递归层数很深的时候，计算很慢。但情况个数毕竟是有限的，所以尝试了每次将情况去重并统计次数，再计算下一轮结果，至少内存不超。

import pandas as pd
import numpy as np
import time
M=5
agg_fun={'Label':['count']}
f=lambda x: 1 if x is True else 0
def car_location(N,M,T):if T==1:temp_car=pd.DataFrame(columns=["car"+str(s) for s in np.arange(0,M,1)])temp_car=temp_car.append(pd.Series(np.arange(0,M,1),index=["car"+str(s) for s in np.arange(0,M,1)]),ignore_index=True)temp_car.loc[temp_car.shape[0]-1][M-1]+=1unique_car_loc=temp_carunique_car_loc["count"]=Noneunique_car_loc.loc[0]["count"]=1columns=["car"+str(s) for s in np.arange(0,M)]unique_car_loc.loc[0][columns]=unique_car_loc.loc[0][columns].sort_values()               return unique_car_locelse:last_location=car_location(N,M,T-1)  #last_location=unique_car_locstart = time.clock()temp_car=last_location[last_location.columns[0:M]] # only location without duplicatescount_car=last_location[last_location.columns[M]] # only countnew_car=pd.DataFrame(columns=last_location.columns)columns=["car"+str(s) for s in np.arange(0,M)]for row in temp_car.index:       # 遍历每一种不重复情况     loc_diff=np.diff(temp_car.loc[row]).tolist()            if loc_diff.count(1)==len(loc_diff):               new_car=new_car.append(pd.concat([temp_car.loc[row],pd.Series(count_car[row],index=["count"])]),ignore_index=True)new_car.loc[new_car.shape[0]-1,"car"+str(M-1)]+=1new_car.loc[new_car.shape[0]-1][columns]=new_car.loc[new_car.shape[0]-1][columns].sort_values()               elif loc_diff.count(1)!=len(loc_diff):if temp_car.loc[row]["car4"]-temp_car.loc[row]["car0"]!=N-1 and temp_car.loc[row]["car4"]-temp_car.loc[row]["car0"]!=-1:new_car=new_car.append(pd.concat([temp_car.loc[row],pd.Series(count_car[row],index=["count"])]),ignore_index=True)new_car.loc[new_car.shape[0]-1,"car"+str(M-1)]+=1 # 最后一辆车移动loc_diff=pd.DataFrame(loc_diff)for ins in loc_diff[loc_diff!=1].dropna().index:new_car=new_car.append(pd.concat([temp_car.loc[row],pd.Series(count_car[row],index=["count"])]),ignore_index=True)new_car.loc[new_car.shape[0]-1,"car"+str(ins)]+=1 # 最后一辆车移动new_car_loc=new_car[new_car.columns[0:M]]  new_car_loc=new_car_loc.astype(int)new_car_loc[new_car_loc>=N-1]=new_car_loc-(new_car_loc//N)*Nfor ind in new_car_loc.index:new_car_loc.loc[ind][columns]=new_car_loc.loc[ind][columns].sort_values()   unique_car_loc=new_car_loc.drop_duplicates().reset_index().drop(["index"],axis=1)last_count=new_car[new_car.columns[M]]   #之前的次数 与下一次的相乘case_car_loc=pd.DataFrame(columns=["cishu"])for ind in np.arange(0,unique_car_loc.shape[0]):comp=(new_car_loc==unique_car_loc.loc[ind]).applymap(f)comp_stat=pd.DataFrame(np.sum(comp,axis=1)==M,columns=["Label"])pre_stat=np.sum(last_count.loc[np.argwhere(comp_stat["Label"]==True)[:,0]])case_car_loc=case_car_loc.append(pd.Series(pre_stat,index=["cishu"]),ignore_index=True)  elapsed = (time.clock() - start)                        unique_car_loc["count"]=case_car_loc["cishu"]/10print("T

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！