バイナリサーチ

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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)
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)
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
Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter

	

素数を無限に列挙するジェネレータ

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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でやってる人を見かけたので俺も。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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でもやってみた。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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でやってみた。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
# 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
# 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
# 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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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)
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)
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)もやってみた。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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)
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)
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

マージソート

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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)もやってみた。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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)もやってみた。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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回ループをまわすだけなので速い。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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
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
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]