2018年11月22日木曜日

開発環境

問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の5章(水晶をどうぞ壊してください)、練習問題(問題3)を取り組んでみる。

コード(Emacs)

Python 3

#!/usr/bin/env python3
def convert_to_decimal(r, d, rep):
    return sum([rep[i] * r ** (d - (i + 1)) for i in range(d)])


def how_hard_is_the_crystal(n, d, did_break=None):
    r = 1
    while r ** d <= n:
        r += 1
    print(f'Radix chosen is {r}')

    ball_number = 1
    num_drops = 0
    floor_no_break = [0] * d
    lower = 0
    upper = n

    for i in range(d):
        for j in range(r - 1):
            floor_no_break[i] += 1
            floor = convert_to_decimal(r, d, floor_no_break)
            if floor > n:
                floor_no_break[i] -= 1
                break
            print(f'Interval: [{lower}, {upper}]')
            print(f'Broken balls: {ball_number - 1}')
            print(f'Drop ball {ball_number} from floor {floor}')
            # did_break = input('Did the ball break (yes/no)?: ')
            print(f'Did the ball break?: {did_break[i]}')
            num_drops += 1
            # if did_break == 'yes':
            if did_break[i] == 'yes':
                upper = floor - 1
                floor_no_break[i] -= 1
                ball_number += 1
                break
            lower = floor
    print(f'Interval: [{lower}, {upper}]')
    hardness = convert_to_decimal(r, d, floor_no_break)
    return hardness, num_drops


if __name__ == '__main__':
    def yes_no(n):
        if n % 2 == 0:
            return 'yes'
        return 'no'
    for did_break in [['no'] * 6,
                      ['yes'] * 6,
                      [yes_no(i) for i in range(6)],
                      [yes_no(i + 1) for i in range(6)]]:
        print(how_hard_is_the_crystal(128, 6, did_break))
        print()

入出力結果(Terminal, Jupyter(IPython))

$ ./sample3.py
Radix chosen is 3
Interval: [0, 128]
Broken balls: 0
Drop ball 1 from floor 81
Did the ball break?: no
Interval: [81, 128]
Broken balls: 0
Drop ball 1 from floor 108
Did the ball break?: no
Interval: [108, 128]
Broken balls: 0
Drop ball 1 from floor 117
Did the ball break?: no
Interval: [117, 128]
Broken balls: 0
Drop ball 1 from floor 126
Did the ball break?: no
Interval: [126, 128]
Broken balls: 0
Drop ball 1 from floor 127
Did the ball break?: no
Interval: [127, 128]
Broken balls: 0
Drop ball 1 from floor 128
Did the ball break?: no
Interval: [128, 128]
(128, 6)

Radix chosen is 3
Interval: [0, 128]
Broken balls: 0
Drop ball 1 from floor 81
Did the ball break?: yes
Interval: [0, 80]
Broken balls: 1
Drop ball 2 from floor 27
Did the ball break?: yes
Interval: [0, 26]
Broken balls: 2
Drop ball 3 from floor 9
Did the ball break?: yes
Interval: [0, 8]
Broken balls: 3
Drop ball 4 from floor 3
Did the ball break?: yes
Interval: [0, 2]
Broken balls: 4
Drop ball 5 from floor 1
Did the ball break?: yes
Interval: [0, 0]
(0, 5)

Radix chosen is 3
Interval: [0, 128]
Broken balls: 0
Drop ball 1 from floor 81
Did the ball break?: no
Interval: [81, 128]
Broken balls: 0
Drop ball 1 from floor 108
Did the ball break?: yes
Interval: [81, 107]
Broken balls: 1
Drop ball 2 from floor 90
Did the ball break?: no
Interval: [90, 107]
Broken balls: 1
Drop ball 2 from floor 99
Did the ball break?: no
Interval: [99, 107]
Broken balls: 1
Drop ball 2 from floor 102
Did the ball break?: yes
Interval: [99, 101]
Broken balls: 2
Drop ball 3 from floor 100
Did the ball break?: no
Interval: [100, 101]
Broken balls: 2
Drop ball 3 from floor 101
Did the ball break?: no
Interval: [101, 101]
(101, 7)

Radix chosen is 3
Interval: [0, 128]
Broken balls: 0
Drop ball 1 from floor 81
Did the ball break?: yes
Interval: [0, 80]
Broken balls: 1
Drop ball 2 from floor 27
Did the ball break?: no
Interval: [27, 80]
Broken balls: 1
Drop ball 2 from floor 54
Did the ball break?: no
Interval: [54, 80]
Broken balls: 1
Drop ball 2 from floor 63
Did the ball break?: yes
Interval: [54, 62]
Broken balls: 2
Drop ball 3 from floor 57
Did the ball break?: no
Interval: [57, 62]
Broken balls: 2
Drop ball 3 from floor 60
Did the ball break?: no
Interval: [60, 62]
Broken balls: 2
Drop ball 3 from floor 61
Did the ball break?: yes
Interval: [60, 60]
(60, 7)

$

0 コメント:

コメントを投稿

関連コンテンツ