「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#7

【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら

配列の要素の並びを反転する

配列の要素の並びを反転するプログラムを考えます。
[1, 2, 3, 4, 5, 6, 7]という配列があるとすると
1,7
2,6
3,5
のペアをそれぞれ入れ替えることを考えると次のようなアルゴリズムになります。
for i in range(n//2):
a[i](左側の要素の添字)とa[n-i-1](右側の要素の添字)の値を交換します。

list2-6

#ミュータブルなシーケンスの要素の並びを反転

from typing import Any, MutableSequence

def reverse_array(a: MutableSequence) -> None:
    '''ミュータブルなシーケンスaの要素の並びを反転'''
    n = len(a)
    for i in range(n // 2):
        a[i], a[n - i - 1] =  a[n - i - 1], a[i]

if __name__ == '__main__':
    print('配列の並びを反転します。')
    nx = int(input('要素数は:'))
    x = [None] * nx #要素nのリストを生成
    
    for i in range(nx):
        x[i] = int(input(f'x[{i}]:'))
        
    reverse_array(x) #xの並びを反転
    
    print('配列の要素の並びを反転しました')
    for i in range(nx):
        print(f'x[{i}] = {x[i]}')

反転とか並べ替えとは便利な気はしますが具体的にどのへんで使うんだろうという感じがしてイメージがわかないです…。(未熟故…。)

コラム 2-4リストの反転
先ほどは関数を定義していましたが、メソッドや関数も存在しているみたいです

・リストの反転(標準ライブラリ)
list型のreverseメソッドはインプレース(定位置)に反転する
使用例：x.reverse()
・反転したリストの生成(reversed関数)
使用例：y = list(reversed(x))

基数変換

10進数を2進数にしたりするやつですね。
0～9、A～Zを使って最大36進数まで作れるみたいです。

コラム2-5基数について
a**nという式があるとすれば、aが基数、n+1が桁数になる。
例)1234が10進数の場合
1234 = 1 * (10**3) + 2 * (10**2) + 3 * (10**1) + 4 * (10**0)

基数変換を行うプログラム
list2-7では基数変換を行うプログラムを下記に記述します。

list2-7

#読み込んだ10進数を2進数から36進数に基数変換して表示
def card_conv(x: int, r: int) -> str:
    '''整数値xをr進数に変換した数値を表す文字列を返却'''
    
    d = '' #変換後の文字列
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    n = len(str(x)) #変換前の桁数
    
    print(f'{r:2} | {x:{n}d}')
    while x > 0:
        d += dchar[x % r] #該当文字を取り出して連結
        x //= r
    
    return d[::-1] #反転して返却

if __name__ == '__main__':
    print('10進数を基数変換します。')
    
    while True:
        while True:
            no = int(input('変換する非負の整数：')) #非負の整数値を読み込む
            if no > 0:
                break
                
        while True:
            cd = int(input('何進数に変換しますか(2-36)：'))
            if 2 <= cd <= 36:
                break
        
        print(f'{cd}進数では{card_conv(no, cd)}です。')
        
        retry = input('もう一度しますか（Y…はい/N…いいえ）')
        if retry in {'N', 'n'}:
            break

多重ループが出てきましたね。2 <= cd <= 36のあたりも参考になります( ..)φメモメモ
ちょっと前にやったd[::-1]という表記もありますね。
だいぶ慣れてきた気がします。

さて、このままでは関数内の動きがいまいち見えてこないため、以下のように変更します。

list2-7(基数変換の過程を表示する)

#読み込んだ10進数を2進数から36進数に基数変換して表示
def card_conv(x: int, r: int) -> str: #今回では、xはno,rはcdを参照する
    '''整数値xをr進数に変換した数値を表す文字列を返却'''
    
    d = '' #変換後の文字列
    dchar = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' #文字列36個
    n = len(str(x)) #変換前の桁数　
    print(f'{r:2} | {x:{n}d}') #f{'r:2(rを2桁で表示)|{x}'}
    while x > 0: #非負の値の間実行
        print('   +' + (n + 2) * '-') #'   +'と'-*(n+2)個'を表示
        if x // r: #xをrで割ることができる場合(最後以外の段の線)
            print(f'{r:2} | {x // r:{n}d} … {x % r}') #f'{r:2} (rを2桁で表示)| {x // r:{n}d(x//rをn桁の10進数で表示)} … {x % r}(x/rの余り)'
        else: #xをrで割ることができない場合(最後の段の線)
            print(f'     {x // r:{n}d} … {x % r}') #f'     (空白){x // r:{n}d}(x//rをn桁の10進数で表示) … {x % r}(x/rの余り)'
        d += dchar[x % r] #該当文字を取り出して連結(0～Zまでの値)(d = d + dchar[x % r]と同じ)
        x //= r #x = x // rと同じ
    
    return d[::-1] #反転して返却


if __name__ == '__main__': #このファイルを動かすときのみ実行
    print('10進数を基数変換します。')
    
    while True: #Trueの間実行
        while True: #Trueの間実行
            no = int(input('変換する非負の整数：')) #非負の整数値を読み込む
            if no > 0: #読み込んだ数字が非負の整数であれば
                break #ループを抜ける
                
        while True: #Trueの間実行
            cd = int(input('何進数に変換しますか(2-36)：')) #数字を読み込む
            if 2 <= cd <= 36: #2から36までの数字であれば
                break　#ループを抜ける
        
        print(f'{cd}進数では{card_conv(no, cd)}です。')#cdと関数card_conv()に数値が代入される
        
        retry = input('もう一度しますか（Y…はい/N…いいえ）')
        if retry in {'N', 'n'}:
            break

処理付きでの結果が見れるようになりました。

自分なりに整理するために細かくコメントをつけてみました。(間違っていたらすみません。)

リストじゃなくて文字列でもリスト的な取出し方ができるんですね。ここでは、簡単な操作しかないからるリストに格納するまでもないということですかね？

だいぶ表記も増えたので、頭がこんがらがりそうですが、一文ずつ見ていけば理解できますね。

コラム2-6 関数間の引数の受け渡し
関数が受け取る仮引数と、呼び出す側が与える実引数について、list2C-5で考えてみます。
xの参照先に注目してみます。

list2C-5

#1からnまでの総和を求める(3を入れた時を想定してコメントを入れます)

def sum_1ton(n):#n = 3を代入してみる
    """1からnまでの整数の総和を求める"""
    s = 0
    while n > 0:#3>0(True)→2>0(true)→1>0(True)→0>0(False)
        s += n#0+3→3+2→5+1→6(終了)
        n -= 1#3-1→2-1→1-1→0(終了)
    return s#3→5→6(終了)

x = int(input('xの値：'))#3を入れる
print(f'1から{x}までの総和は{sum_1ton(x)}です。')#1から3までの総和は6です。

list2C-5の場合、仮引数のnの値が3→2→1…と減っていきます。(最後は0になる)
関数sum_1tonに与えている実引数はxです。実行例の場合関数から戻って来た後に「1から3までの総和は6です」と返ってくるため、変数xの値は3であることが確認できます。この時、仮引数nに実引数xの値がコピーされているのではなく仮引数nに実引数xが代入されているそうです。これは代入でコピーされるものが値ではなく参照先のため、nとxの参照先が同じになるんですね。
つまり、関数実行時にはn, x = 3, 3であるのに対して、関数終了時にはn, x = 0, 3となります。(3自体がイミュータブルなオブジェクトのため、仮引数の参照先が変化します)
次はミュータブルオブジェクトの例です。

list2C-6

#リストの任意の要素の値を更新する(ここではindex, value = 2, 99を想定します)

def change(lst, idx, val):#change([11,22,33,44,55]xを参照, 2, 99)
    """lst[idx]の値をvalに更新"""
    lst[idx] = val #x[2]なので33の位置に99が入り、print関数で出力される
    
x = [11, 22, 33, 44, 55]
print('x =', x)

index = int(input('インデックス：'))#2を入力
value = int(input('新しい値　　：'))#99を入力

change(x, index, value)#change([11,22,33,44,55], 2, 99)
print(f'x = {x}')#変更後のxが参照される([11,22,99,44,55]) 

list2C-5ではxの参照先が3で固定されていたのに対して、list2C-6ではxの参照先が[11,22,33,44,55]から[11,22,99,44,55]に変更されました。
list2C-6の仮引数はlstにあたり、lstとxが同じ参照先になっています。
つまり、lst, x =[11,22,99,44,55], [11,22,99,44,55]で同様の参照先であることがわかりますね。

少しややこしい話な気はしますが、私の解釈ではint型(1などの数字)とlist型(任意で決定するもの)はオブジェクトとして同列に扱われるとなのではないかと思っています。(訂正があればコメントお願いします)

今回は以上です。ありがとうございました。