Computer Science - アルゴリズム (探索、noseテスト)

初めてのコンピュータサイエンス
Jennifer Campbell Paul Gries
Jason Montojo Greg Wilson (著)
長尾 高弘 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• BBEdit - Bare Bones Software, Inc., Emacs(Text Editor)
• プログラミング言語: Python

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の10章(アルゴリズム)の10.4(練習問題)を解いてみる。

2.

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

def getMin(sequence):
    res = (0, sequence[0])
    for i in range(1, len(sequence)):
        if sequence[i] < res[1]:
            res = (i, sequence[i])
        i += 1
    return res

def min_or_max_index(sequence, b):
    res = (0, sequence[0])
    if b:
        for i in range(1, len(sequence)):
            if sequence[i] < res[1]:
                res = (i, sequence[i])
            i += 1
    else:
        for i in range(1, len(sequence)):
            if sequence[i] > res[1]:
                res = (i, sequence[i])
            i += 1
    return res
            
if __name__ == '__main__':
    a = [1,2,3,4,5,0,1,2,3,4,5, 10, 9, 8, 7]
    print(getMin(a), min_or_max_index(a, True), min_or_max_index(a, False))

入出力結果(Terminal)

$ ./sample.py
(5, 0) (5, 0) (11, 10)
$

3.

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

import nose

def find_two_smallest(L):
    if not L:
        return None
    if len(L) == 1:
        return (0,)
    if L[0] < L[1]:
        min1, min2 = 0, 1
    else:
        min2, min1 = 1, 0
    
    for i in range(2, len(L)):
        if L[i] < L[min1]:
            min2 = min1
            min1 = i
        elif L[i] < L[min2]:
            min2 = i
    return (min1, min2)

def test_1():
    assert find_two_smallest([]) == None

def test_2():
    assert find_two_smallest([1]) == (0,)

def test_3():
    assert find_two_smallest([1,2]) == (0, 1)

def test_4():
    assert find_two_smallest([5,4,3,2,1,1,2,3,4,5]) == (4, 5)

def test_5():
    assert find_two_smallest([10] * 1000) == (0, 1)

            
if __name__ == '__main__':
    nose.runmodule()

入出力結果(Terminal)

$ ./sample.py
.....
----------------------------------------------------------------------
Ran 5 tests in 0.002s

OK
$