バイナリサーチ

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 をつけることができるんだ。初めて使った。

Luhnアルゴリズムでクレジットカードの番号をチェック:Haskell版

こないだやったLuhnアルゴリズムでのチェックをHaskellでもやってみた。

module Main (main) where

import Data.Char

numbers = [
  "5555555555554444",
  "5105105105105100",
  "4111111111111111",
  "4012888888881881",
  "3530111333300000",
  "3566002020360505",
  "30569309025904",
  "38520000023237",
  "378282246310005",
  "371449635398431",
  "378734493671000",
  "6011111111111117",
  "6011000990139424"
]

checkNumber num = sum' `mod` 10 == 0
  where
    sum' = sum $ zipWith add' (cycle [1,2]) (reverse num)
    add' x y = let z = x * digitToInt y
    in
    if z > 9 then z - 9 else z

main = mapM_ (print . checkNumber) numbers

実行結果:

^o^ > runhaskell checkCardNumber.hs
True
True
True
True
True
True
True
True
True
True
True
True
True

Luhnアルゴリズムでクレジットカードの番号をチェック

クレジットカード番号のチェックサムには Luhnアルゴリズムというのが使われているのを知った。

cf. Luhnアルゴリズムでクレジットカードの番号をチェック – brainstorm
cf. Luhnアルゴリズム – Wikipedia

Rubyでやってみた。

# coding: utf-8
#
# Check number with Luhn algorithm

def check_number(digits)
  even = false
  sum = digits.reverse.split(//).inject(0) do |s, d|
    d = d.to_i
    if even
      d = d * 2
      s -= 9 if d > 9
    end
    even = !even
    s += d
  end
  sum % 10 == 0
end


NUMBERS = [
  '5555555555554444',
  '5105105105105100',
  '4111111111111111',
  '4012888888881881',
  '3530111333300000',
  '3566002020360505',
  '30569309025904',
  '38520000023237',
  '378282246310005',
  '371449635398431',
  '378734493671000',
  '6011111111111117',
  '6011000990139424'
]

NUMBERS.each do |digits|
  puts check_number(digits)
end

カード番号の例は↓ここで紹介されているもの。
cf. ECサイトの動作テストに使える、クレジットカードのテスト番号一覧 – Webクリエイターボックス

実行結果:

^o^ > check_card_numbers.rb
true
true
true
true
true
true
true
true
true
true
true
true
true

Pythonでユークリッドの互除法

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. 第4回 分布数え上げソート – 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]