カテゴリー: algorithm

AOJの問題を解く途中で作ったのでメモしておく。結局使わなくなったけど。
あらかじめソートされているのが前提。見つからないときは None を返す。

def binary_search(lis, x):
    if len(lis) == 0:
        return None
    else:
        i = len(lis) / 2
        if lis[i] == x:
            return x
        elif x < lis[i]:
            return binary_search(lis[:i], x)
        else:
            return binary_search(lis[i+1:], x)

a = range(100000)
print binary_search(a, 3359)
print binary_search(a, 100001)
print binary_search(a, 0)
print binary_search(a, -1)

実行結果：

^o^ > python binary_search.py
3359
None
0
None

エラトステネスの篩を応用して書いてみた。

import sys
import itertools

def primes():
    p = []
    p.append(2)
    yield 2
    p.append(3)
    yield 3
    for n in itertools.count(6, 6):
        n1 = n - 1
        for x in p:
            if n1 % x == 0:
                break
            else:
                p.append(n1)
                yield n1
               n2 = n + 1
               for y in p:
                   if n2 % y == 0:
                       break
                   else:
                       p.append(n2)
                       yield n2

n = int(sys.argv[1])
for p in primes():
    if p < n:
        print p
    else:
        break

^o^ > python primes3.py 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

ここでは100未満の素数を出力している。さすがに primes3.py 1000000 とかやると遅い。

Pythonでやってる人を見かけたので俺も。

import random

def insertion_sort(lis):
    for i in range(1,len(lis)):
        tmp = lis.pop(i)
        for j in range(i):
            if tmp < lis[j]:
                lis.insert(j, tmp)
                break
            else:
                lis.insert(i, tmp)
                return lis


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", 
 l2 = insertion_sort(l)
print "sorted: ", l2

実行結果：

^o^ > python insertion_sort.py
unsorted: [1, 9, 6, 3, 8, 6, 5, 2, 7, 4, 2, 9, 8, 5, 7, 3, 4, 1]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

Python の for文には else をつけることができるんだ。初めて使った。

GCD

mathモジュールに最大公約数（GCD）を求める関数が無いようなので作ってみた。
アルゴリズムの説明はWikipediaに載っている。

cf. http://ja.wikipedia.org/wiki/%E3%83%A6%E3%83%BC%E3%82%AF%E3%83%AA%E3%83%83%E3%83%89%E3%81%AE%E4%BA%92%E9%99%A4%E6%B3%95

def gcd(a, b):
    if a < b:
        a, b = b, a
        if b == 0:
            return a
        c = a % b
        return gcd(b, c)


if __name__ == '__main__':
    import sys

    a = int(sys.argv[1])
    b = int(sys.argv[2])
    print gcd(a, b)

実行例：

^o^ > python gcd.py 24 36
12

LCM

ついでに最小公倍数（LCM）もやってみた。

import gcd

def lcm(a, b):
    return a * b / gcd.gcd(a,b)


if __name__ == '__main__':
    import sys

    a = int(sys.argv[1])
    b = int(sys.argv[2])
    print lcm(a, b)

実行例：

^o^ > python lcm.py 24 36
72

追記

よくよく調べたらfractionsモジュールにgcd関数があった。

>>> import fractions
>>> fractions.gcd(24, 36)
12

import random

def merge_sort(lis):
    l = len(lis)
    if l <= 1:
        return lis
    else:
        h = l/2
        lis1 = lis[0:h]
        lis2 = lis[h:l]
        return merge(merge_sort(lis1), merge_sort(lis2))

def merge(lis1, lis2):
    merged = []
    while True:
        if len(lis1) == 0:
            merged += lis2
            break
        elif len(lis2) == 0:
            merged += lis1
            break
        else:
            if lis1[0] <= lis2[0]:
                merged.append(lis1.pop(0))
            else:
                merged.append(lis2.pop(0))
    return merged


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l
l2 = merge_sort(l)
print "sorted: ", l2    

実行例：

^o^ > python merge_sort.py
unsorted: [6, 9, 6, 3, 4, 1, 4, 5, 3, 1, 2, 8, 7, 2, 5, 7, 9, 8]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

バブルソート（bubble sort）もやってみた。

import random

def bubble_sort(lis):
    l = range(1, len(lis))
    l.reverse()
    for i in l:
        for j in range(1, i+1):
            if lis[j-1] > lis[j]:
                lis[j], lis[j-1] = lis[j-1], lis[j]
    return lis


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l

l2 = bubble_sort(l)
print "sorted: ", l2

実行結果：

^o^ > python bubble_sort.py
unsorted: [7, 6, 8, 2, 1, 4, 2, 6, 8, 3, 4, 5, 9, 9, 3, 5, 7, 1]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

分布数え上げソートをやったついでに、クイックソート（quick sort）もやってみた。

import random

def quick_sort(lis):
    if len(lis) == 0:
        return []
    p = lis.pop(0)
    left = [x for x in lis if cmp(x, p) < 0]
    right = [x for x in lis if cmp(x, p) >= 0]
    return quick_sort(left) + [p] + quick_sort(right)


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l

l2 = quick_sort(l)
print "sorted: ", l2

実行例：

^o^ > python quick_sort.py
unsorted: [2, 7, 9, 1, 8, 6, 3, 5, 1, 5, 2, 4, 8, 7, 3, 9, 4, 6]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]

PHPでやってる人を見かけたので、Pythonでやってみた。

cf. 第４回 分布数え上げソート – noldor’s diary

分布数え上げソート（counting sort）ってのは、要素の最小値と最大値がわかっている場合に

1. 各要素の出現回数を数える
2. 小さい順に要素を出現回数分だけ出力する

っていうアルゴリズムだ。基本的に2回ループをまわすだけなので速い。

import random

def counting_sort(lis, min, max):
    counter = [0] * (max + 1)
    for i in lis:
        counter[i] += 1
        r = []
        for i in range(min, max+1):
            for j in range(counter[i]):
                r.append(i)
                return r


l = range(1,10) * 2
random.shuffle(l)
print "unsorted:", l

l2 = counting_sort(l, 1, 9)
print "sorted: ", l2

実行例：

^o^ > python counting_sort.py
unsorted: [1, 3, 7, 6, 9, 4, 7, 5, 2, 6, 9, 5, 1, 4, 8, 8, 3, 2]
sorted:   [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9]