游戏开始

~一个有关算法的虚拟故事 (powered by rst2S5)

Authors:ZoomQuiet+gdg[AT]gmail.com
URL:http://s5.zoomquiet.io/140511-hoa6-start4game/

<免责/>

山寨的,非业界公认的,个人体验为基础! 是也乎;-)
参考所有同好行为总结而得
  • 一切资料来自网络互动挖掘
  • 一切想法来自日常学习工作
  • 一切体悟来自各种沟通交流
  • 一切知识来自社区分享印证
  • 一切经验来自个人失败体验

高橋流!

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)
高橋流

文字

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

巨大

幻灯

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

很多

播放

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

播放

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

!

播放

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

非常!

所以:

Takahashi-method 幻灯风格 源自 Ruby 专家高橋征義(Masayoshi Takahashi)

<brief/>

是也乎;-)

<Zoom.Quiet>

是也乎;-)
是也乎,是也乎 Zoom.Quiet

有称...

;-} 是也乎;-)

周导

其实...

基调是分享交流;-} 是也乎;-)

大妈

牛妞

\ (^o^) / 596d
表情牛妞
  • 我的女儿刚刚一岁半,非常牛,,,脾气牛,头脑牛,虽然不会说话,但是已经能指挥我们干活了...
  • 120426-niuniu-表情帝

牛妞

\ (^o^) / 1096d
表情牛妞
  • 我的女儿刚刚一岁半,非常牛,,,脾气牛,头脑牛,虽然不会说话,但是已经能指挥我们干活了...
  • 120426-niuniu-表情帝

</Zoom.Quiet>

  • 纯种Pythoner,自由软件原教旨主义者
  • 关注社会化教育及知识管理;喜爱SF和摄影。
  • 尝试使用Pythonic体验感化国人主动进入自由软件世界体验/学习/再创作

(^.^)

<brief/>

是也乎;-)

游戏.

是也乎;-)
  • ...

当然的...

是也乎;-)

Py

  • ...

calc.py

硬找 是也乎;-)
for i in seq:
    product = (i[0]*100 + i[1]*10 + i[2]) * (i[3]*10 + i[4])
    if product > maximum:
       maximum = product
       max_item = i
    elif product == maximum:
       max_item += ','+i
return max_item, maximum
  • ...

permute1.py

自动生成seq 是也乎;-)
def permute(seq):
  result = []
  for a in seq:
    for b in seq:
      for c in seq:
        for d in seq:
          for e in seq:
            if a!=b and a!=c and a!=d and a!=e and \
               b!=c and b!=d and b!=e and \
               c!=d and c!=e and d!=e:
              result.append(''.join([a,b,c,d,e]))
  return result
  • ...

结果?

是也乎;-)
$ python permute1.py
Maxmum at 87596 ,product 84000
  • ...

然后呢...

是也乎;-)

通用化

  • ...

只能...

是也乎;-)

递归

  • ...

排列

是也乎;-)
  • ...

递归函式

是也乎;-)
  • ...

permute2.py

自动生成seq 是也乎;-)
def permute(seq):
  l = len(seq)
  if l == 1:
    return [seq]
  else:
    res=[]
    for i in range(len(seq)):
      rest = seq[:i] + seq[i+1:]
      for x in permute(rest):
        res.append(seq[i:i+1] + x)
    return res
  • ...

permute2.py

自动生成seq 是也乎;-)
seq = list("1234")
thelist = permute(seq)
thelist = [ ''.join(x) for x in thelist ]
print thelist
  • ...

permute2.py

自动生成seq 是也乎;-)
$ python permute2.py
['1234', '1243', '1324', '1342', '1423',
'1432', '2134', '2143', '2314',
'2341', '2413', '2431', '3124',
'3142', '3214', '3241', '3412', '3421',
'4123', '4132', '4213', '4231', '4312', '4321']
  • ...

但是...

是也乎;-)

能再

快卟?

  • ...

发现...

是也乎;-)
  • ...

permute3.py

自动生成seq 是也乎;-)
def permute(seq):
  l = len(seq)
  if l <= 2:
    if l == 2: return [ seq, [seq[1], seq[0]] ]
    else:      return [seq]
  else:
    res=[]
    for i in range(len(seq)):
      rest = seq[:i] + seq[i+1:]
      for x in permute(rest):
        res.append(seq[i:i+1] + x)
    return res
  • ...

calc.py

自动生成seq 是也乎;-)
def calc(seq, where):
  maximum, max_item = 0, []
  for i in seq:
    product = int(i[:where]) * int(i[where:])
    if product > maximum:
       maximum, max_item = product, i
    elif product == maximum:
       max_item += ','+ i
  print "Maximum at", max_item, ",product", maximum

if __name__ == "__main__":
  seq = [ "56789", "56798" ]
  where = 3
  calc(seq,where)
  • ...

permute3.py

自动生成seq 是也乎;-)
import sys, calc
seq = list(sys.argv[1])
where = int(sys.argv[2])
thelist = [ ''.join(x) for x in permute(seq) ]
Print 'Got', len(thelist), 'items.'
calc.calc(thelist, where)
  • ...

permute3.py

自动生成seq 是也乎;-)
$ time python permute3.py 56789 3
Got 120 items.
Maximum at 87596 ,product 84000

real    0m0.040s
user    0m0.030s
sys     0m0.010s
  • ...

但是...

是也乎;-)

能再

快卟?

  • ...

ASPN: Getting permutation of a sequence

Python recipes « ActiveState Code 是也乎;-)
def getPerm(seq, index):
    "Returns the <index>th permutation of <seq>"
    seqc= list(seq[:])
    seqn= [seqc.pop()]
    divider= 2 # divider is meant to be len(seqn)+1, just a bit faster
    while seqc:
        index, new_index= index//divider, index%divider
        seqn.insert(new_index, seqc.pop())
        divider+= 1
    return seqn
  • ...

号称

是也乎;-)

O(n)

  • ...

算法时间复杂度

表示法 是也乎;-)
  • ...

常见 时间复杂度

表示法 是也乎;-)
  • ...

号称

是也乎;-)

!

O(n)

  • ...

test.py

自动生成seq 是也乎;-)
from permute4.py import permute

seq = list("1234")
for i in range(30):
  print permute(seq, i)
  • ...

test.py

自动生成seq 是也乎;-)
$ python test.py
1234 1243 1324 1423 1342 1432 2134
2143 3124 4123 3142 4132 2314
2413 3214 4213 3412 4312 2341 2431
3241 4231 3421 4321 1234 1243
1324 1423 1342 1432
  • ...

permute4.py

def getPerm(seq, index):
    seqc= list(seq[:])
    seqn= [seqc.pop()]
    divider= 2
    while seqc:
        index, new_index= index/divider
            , index%divider
        seqn.insert(new_index, seqc.pop())
        divider+= 1
    return seqn
  • ...

肿么的?

getPerm(seq, index) 是也乎;-)
  • ...

快?!

自动生成seq 是也乎;-)
$ time cpython permute4.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002

real    0m0.389s
user    0m0.370s
sys     0m0.010s
  • ...

但是...

是也乎;-)

着!

  • ...

<brief/>

是也乎;-)

Python

是也乎;-)

Slackware / RedHat / Redflag / Mandrake / Debian / XP / NT2000|3|5 / DOS / Solaris/ AIX / Unicos / OSX ...

  • ...

传说...

是也乎;-)

任何递归/回溯函数都

可以还原成非递归的!

  • ...

求排列的方法

是也乎;-)
  • ...

permute5.py

是也乎;-)
def permute(seq):
  result = []
  for i in seq:
    seq1 = seq[:]
    seq1.remove(i)
    for j in seq1:
      seq2 = seq1[:]
      seq2.remove(j)
      for l in seq2:
        seq3 = seq2[:]
        seq3.remove(l)
        for m in seq3:
          seq4 = seq3[:]
          seq4.remove(m)
          result.append(''.join([i,j,l,m,seq4[0]]))
  return result
  • ...

求排列的方法

是也乎;-)
  • ...

动态语言

是也乎;-)

自己

自己

  • ...

permute5.py v2

是也乎;-)
def genfunc(n):
  head = """
def permute(seq0):
  result = [] """
  boiler = """
for counter%i in seq%i:
  seq%i = seq%i[:]
  seq%i.remove(counter%i)"""
  for i in range(1,n):
    space = '  '*i
    head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
  temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
  head = head + '\n' + space + "  result.append(''.join([%s]))"%(temp)
  return head + '\n  return result\n'
  • ...

permute5.py v2 调用

是也乎;-)
import sys
functext = genfunc(len(sys.argv[1]))
print functext
exec(functext)
print dir()
thelist = permute(list(sys.argv[1]))
print 'Got', len(thelist), 'items.'
  • ...

permute5.py v2 运行

是也乎;-)
$ python permute5.py 12345 3

def permute(seq0):
  result = []
  for counter1 in seq0:
    seq1 = seq0[:]
    seq1.remove(counter1)
    for counter2 in seq1:
      seq2 = seq1[:]
      seq2.remove(counter2)
      for counter3 in seq2:
        seq3 = seq2[:]
        seq3.remove(counter3)
        for counter4 in seq3:
          seq4 = seq3[:]
          seq4.remove(counter4)
          result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]]))
  return result

['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc',
'permute', 'sys']
Got 120 items.
  • ...

permute5.py v2 输出

是也乎;-)
...
          result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]]))
  return result

['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc',
'permute', 'sys']
Got 120 items.
  • ...

permute5.py v2 计时

是也乎;-)
...
import sys, calc
functext = genfunc(len(sys.argv[1]))
#print functext
exec(functext)
thelist = permute(list(sys.argv[1]))
print 'Got',len(thelist),'items.'
calc.calc(thelist,int(sys.argv[2]))
  • ...

permute5.py v2 time

是也乎;-)
$ time cpython permute5.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002

real    0m0.213s
user    0m0.200s
sys     0m0.010s
  • ...

等等...

是也乎;-)

也许

数学...

是也乎;-)

课本

排列组合原理

是也乎;-)
                      [4321]
                      [3421]
             [321]  < [3241]
      [21] < [231]... [3214]
             [213]...
[1] <
             [321]...
      [21] < [231]...
             [213]...
  • ...

求排列的方法

是也乎;-)
  • ...

求排列的方法

是也乎;-)
  • ...

permute6.py

是也乎;-)
def permute(seq):
  seqn = [seq.pop()]
  while seq:
    newseq = []
    new = seq.pop()
    #print "seq:",seq,'seqn', seqn ,'new', new
    for i in range(len(seqn)):
      item = seqn[i]
      for j in range(len(item)+1):
        newseq.append(''.join([item[:j]
            , new
            , item[j:]]))
    seqn = newseq
    #print 'newseq',newseq
  return  seqn
  • ...

permute6.py 调用

是也乎;-)
import sys, calc
seq = list(sys.argv[1])
where = int(sys.argv[2])
thelist = permute(seq)
print 'Got', len(thelist), 'items.'
calc.calc(thelist, where)
  • ...

permute6.py 运行

是也乎;-)
$ time cpython permute6.py 1234567 4
Got 5040 items.
Maximum at 6531742 ,product 4846002

real    0m0.167s
user    0m0.150s
sys     0m0.020s
  • ...

但是...

是也乎;-)

能再

快卟?

  • ...

<brief/>

是也乎;-)

permute6.py 结果

是也乎;-)
Got 24 items.
[
'1234', '2134', '2314', '2341',
'1324', '3124', '3214', '3241',
'1342', '3142', '3412', '3421',
'1243', '2143', '2413', '2431',
'1423', '4123', '4213', '4231',
'1432', '4132', '4312', '4321'
]
  • ...

目测...

是也乎;-)

对称!

  • ...

permute7.py

是也乎;-)
def permute(seq):
  seqn = [ seq.pop()+seq.pop() ] # 仅改此处
  while seq:
    newseq = []
    new = seq.pop()
    #print "seq:",seq,'seqn', seqn ,'new', new
    for i in range(len(seqn)):
      item = seqn[i]
      for j in range(len(item)+1):
        newseq.append(''.join([item[:j]
            , new
            , item[j:]]))
    seqn = newseq
    #print 'newseq',newseq
  return  seqn
  • ...

求排列的方法

是也乎;-)
  • ...

calc2.py

是也乎;-)
def calc2(seq, where):
  maximum, max_item = 0, []
  for i in seq:
    product = int(i[:where]) * int(i[where:])
    if product > maximum:
       maximum, max_item = product, i
    elif product == maximum:
       max_item += ','+i
    rev = list(i)
    rev.reverse() # 专门配合permute7.py
    i = ''.join(rev)
    product = int(i[:where]) * int(i[where:])
    if product > maximum:
       maximum, max_item = product, i
    elif product == maximum:
       max_item += ','+i
  print "Maximum at", max_item, ",product", maximum
  • ...

permute.py v2~7 对比

是也乎;-)
$ time python permute2.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902

real    0m46.478s
user    0m46.020s
sys     0m0.430s
  • ...

permute.py v1~7 对比

是也乎;-)
$ time python permute3.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902

real    0m38.997s
user    0m38.600s
sys     0m0.400s
  • ...

permute.py v1~7 对比

是也乎;-)
$ time python permute4.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902

real    0m33.845s
user    0m33.460s
sys     0m0.380s
  • ...

permute.py v1~7 对比

是也乎;-)
$ time python permute5.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902

real    0m10.681s
user    0m10.530s
sys     0m0.150s
  • ...

permute.py v1~7 对比

是也乎;-)
$ time python permute6.py 123456789 5
Got 362880 items.
Maximum at 875319642 ,product 843973902

real    0m8.279s
user    0m8.110s
sys     0m0.170s
  • ...

permute.py v1~7 对比

是也乎;-)
$ time cpython permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902

real    0m7.827s
user    0m7.650s
sys     0m0.180s
  • ...

7倍!

是也乎;-)
  • ...

但是...

是也乎;-)

着!

  • ...

排列组合原理

是也乎;-)
                      [4321]
                      [3421]
             [321]  < [3241]
      [21] < [231]... [3214]
             [213]...
[1] <
             [321]...
      [21] < [231]...
             [213]...
  • ...

求排列的方法

是也乎;-)
  • ...

求排列的方法

是也乎;-)
  • ...

94介样

是也乎;-)

没错

  • ...

求排列的方法

是也乎;-)
  • ...

求排列的方法

是也乎;-)
  • ...

最大好处...

原子化 是也乎;-)

分布式

  • ...

这不94..

原子化 是也乎;-)

等等?!

  • ...

permute4.py

def getPerm(seq, index):
    seqc= list(seq[:])
    seqn= [seqc.pop()]
    divider= 2
    while seqc:
        index, new_index= index/divider
            , index%divider
        seqn.insert(new_index, seqc.pop())
        divider+= 1
    return seqn
  • ...

世上聪明人太多..

是也乎;-)

残念

  • ...

<brief/>

是也乎;-)

梦...

是也乎;-)
讲演之禅

提出挑战

是也乎;-)
  • ...

游戏.

是也乎;-)
  • ...

阿凡提没电脑...

是也乎;-)

等等!

  • ...

数学推理

是也乎;-)
# 假设五个数为  [a][b][c]*[d][e]
# 展开的话...

  a * 100 * d * 10
+ a * 100 * e * 1
+ b * 10  * d * 10
+ b * 10  * e * 1
+ c * 1   * d * 10
+ c * 1   * e * 1
  • ...

矩阵

是也乎;-)
# 这个可以写成一个矩阵

      d    e
a  1000  100
b   100   10
c    10    1
  • ...

数值推理

是也乎;-)
  • ...

对数矩阵

是也乎;-)
      d    e
a  1000  100
b   100   10
c    10    1

# 用对数来记数
# 100 = 10e2, 用 2 来代表好了

   d e
a  3 2
b  2 1
c  1 0
  • ...

数值推理

是也乎;-)
  • ...

对数矩阵

是也乎;-)
   d e
a  3 2
b  2 1
c  1 0

# 贡献基数
    a = 5
    b = 3
    c = 1
    d = 6
    e = 3
  • ...

数值推理

是也乎;-)
  • ...

对数矩阵

是也乎;-)
   d e
a  4 3
b  3 2
c  2 1

# 贡献基数
    a = 7
    b = 5
    c = 3
    d = 9
    e = 6
  • ...

数值推理~错?

是也乎;-)
  • ...

数值推理

是也乎;-)
  • ...

二阶基数

是也乎;-)
  • ...

二阶基数

是也乎;-)
  • ...

三阶基数

是也乎;-)
  • ...

但是...

是也乎;-)

妥当

  • ...

半个...

是也乎;-)

馒头

  • ...

答案进入脑海

是也乎;-)
  • ...

每次只求一个位置!

是也乎;-)
  • ...

每次只求一个位置!

是也乎;-)
  • ...

wise.py

基于阿凡提的 wise 是也乎;-)
def solve(seq,where):
  n = len(seq)
  seq.sort()
  seq.reverse()
  table = [ [] for i in range(n) ]
  left, right = where, n - where
  leftr = long('1'*left) # 全1 的占位数值
  rightr = long('1'*right)
  flag=[] # 已经选好的位置
  for item in [ int(x) for x in seq]:
    for i in range(left):
      table[left-i-1] = (leftr + 10**i) * rightr
    for i in range(right):
      table[right-i+where-1] = leftr * (rightr + 10**i)
  • ...

wise.py

基于阿凡提的 wise 是也乎;-)
  for i in flag:
    table[i] = 0
  tablesorted = table[:]
  tablesorted.sort()
  maxindex = table.index(tablesorted[-1])
  if maxindex >= where:
     rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
  else:
     leftr = leftr + (item-1) * 10**(left-maxindex-1)
  flag.append(maxindex)
  #print maxindex, leftr, rightr
return leftr, rightr
  • ...

对比

是也乎;-)
$time python permute7.py 123456789 5
Got 181440 items.
Maximum at 875319642 ,product 843973902

real    0m7.827s
user    0m7.650s
sys     0m0.180s

$ time python wise2.py 123456789 5
Maximum at 87531 9642 ,product 843973902

real    0m0.042s
user    0m0.010s
sys     0m0.030s
  • ...

Wow

是也乎;-)

两百

!

  • ...

跳出限制

不用阶乘|zqeye|

n!

  • ...

这种感觉

是也乎;-)

to

hack

  • ...

<brief/>

是也乎;-)

glace的自省

  • CPU: Pentium III 866 RAM: 128 MB
  • Slackware Linux: 9.0 Linux Kernel: 2.4.2 GCC: 3.2.2
  • Python: 修改过的 2.1.3
  • ...

总之

期望可以记住的~单位时间可以记住的只有7+-2 个 是也乎;-)

<discuss/>

是也乎;-)

Q&A

.

.

Authors:ZoomQuiet+gdg[AT]gmail.com
URL:http://s5.zoomquiet.io/140511-hoa6-start4game/

最后的最后...

好书推荐... 是也乎;-)
讲演之禅

<版本/>

是也乎;-)
Authors:ZoomQuiet+gdg[AT]gmail.com
URL:http://s5.zoomquiet.io/140511-hoa6-start4game/

S5

纯HTML 幻灯撰写框架!... S5icon
  • 仅仅依靠 CSS+JS 的HTML格式幻灯演示框架
pix/2010-01-18-230729_605x421_leo.png