| xie 的个人资料追忆似水流年照片日志列表 |  工具  帮助 |
|
9月24日 赛马(抄的)有36匹马，六个跑道？没有记时器等设备，用最少的比赛次数算出跑的最快的前三名马？
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
其实用排除法就可以把过程看的很清楚了，前面的步骤一样，6组分别比之后6个第一名比，这时候，假设排名为：A1、 B1、 C1、 D1、 E1、F1，此时可以断定A1为最快的马，然后排除法，看那些不可能是前三： 1、D，E，F组全部排除； 2、A组后三名全部排除（前面至少已经有A1,A2,A3）； 3、B组后四名全部排除（前面至少已经有A1,B1，B2）; 4、C组其实后五名都可以排除（前面至少已经有A1,B1，C1）； 剩下的就只有：A2、A3、B1、B2、C1，跑一次ok了 9月17日 Coins gameN coins lay linear. Two men are taking them in turn. They can take one coin or adjacent two per time. 1. The one who takes the last coin is winner. Please analyze the strategy. 2. The one who takes the last coin is loser. Please analyze the strategy. s = { (1,):0 }
def perm(L):
for i in range(len(L)):
for j in range((L[i]+1)/2):
yield sorted(k for k in L[:i]+[j,L[i]-j-1]+L[i+1:] if k>0)
yield sorted(k for k in L[:i]+[j,L[i]-j-2]+L[i+1:] if k>0)
def win(L):
k = tuple(L)
r = s.get(k)
if r is not None:
return r
for l in perm(L):
if not win(l):
s[k] = 1
return 1
s[k] = 0
return 0
for i in range(1, 100):
print i, win([i])
print len(s)I found hardly to understand the python. -_-!!!!!!!!!!
9月16日 quick sort(Bentley-McIlroy 3-way partitioning)Partitioning invariant move from left to find an element that is not less move from right to find an element that is not greater stop if pointers have crossed exchange if left element equal, exchange to left end if right element equal, exchange to right end Partitioning invariant Swap equals to center after partition KEY FEATURES always uses N-1 (three-way) compares no extra overhead if no equal keys only one “extra” exchange per equal Output[i] will be multiplication from A[0] to A[N] excluding A[i]suppose there is an array A[N] of N numbers. We have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ In C#: static int[] array_multiplier( int[] inp) { int[] x = new int[inp.Length]; x[0] = 1; for (int i = 1; i < x.Length; ++i) { x[i] = x[i-1] * inp[i-1]; } int[] y = new int[inp.Length]; y[y.Length-1] = 1; for (int i = y.Length-2; i >= 0; --i) { y[i] = y[i+1] * inp[i+1]; } int[] output = new int[inp.Length]; for (int i = 0; i < output.Length; ++i) { output[i] = x[i] * y[i]; } return output; } |
|
|
