AtCoder練習1

Pythonで数字の各桁の和を求める方法

Pythonでは、数字の各桁の和を求めるためにいくつかの方法があります。ここでは、その代表的な方法を紹介します。

方法1: 文字列操作を使う

数字を文字列に変換し、各桁を取り出して整数に変換し、それらを合計する方法です。

def sum_of_digits(n):
    return sum(int(digit) for digit in str(n))

# 使用例
n = 12345
print(sum_of_digits(n))  # 出力: 15

方法2: 数学的操作を使う

数字を10で割りながら各桁を取り出して合計する方法です。

コードをコピーする
def sum_of_digits(n):
    total = 0
    while n > 0:
        total += n % 10
        n //= 10
    return total

# 使用例
n = 12345
print(sum_of_digits(n))  # 出力: 15

※n //= 10は、Pythonの代入演算子を使った整数除算（フロア除算）です。これは、変数nを10で割り、その結果をnに再代入することを意味します。具体的には、小数点以下を切り捨てた整数部分をnに再代入します。

方法3: 再帰を使う

再帰を使って各桁の和を求める方法です。

コードをコピーする
def sum_of_digits(n):
    if n == 0:
        return 0
    else:
        return n % 10 + sum_of_digits(n // 10)

# 使用例
n = 12345
print(sum_of_digits(n))  # 出力: 15

方法4: map関数を使う

map関数を使って各桁を整数に変換し、それらを合計する方法です。

コードをコピーする
def sum_of_digits(n):
    return sum(map(int, str(n)))

# 使用例
n = 12345
print(sum_of_digits(n))  # 出力: 15

まとめ

Pythonで数字の各桁の和を求める方法はいくつかありますね。

ソートアルゴリズムの紹介

選択ソート (Selection Sort)

動作原理

選択ソートは、配列から最小（または最大）の要素を順に選び、それを現在の位置に置くことを繰り返してソートを行います。

実装

arr = [64, 25, 12, 22, 11]

# 選択ソートの実装
n = len(arr)
for i in range(n):
    min_idx = i
    for j in range(i + 1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j
    arr[i], arr[min_idx] = arr[min_idx], arr[i]

print("Sorted array is:", arr)

計算量

• 最悪の場合: (O(n^2))
• 平均の場合: (O(n^2))
• 最良の場合: (O(n^2))

挿入ソート (Insertion Sort)

動作原理

挿入ソートは、未ソート部分から要素を一つずつ取り出し、それを適切な位置に挿入していくことでソートを行います。

実装

arr = [64, 25, 12, 22, 11]

# 挿入ソートの実装
n = len(arr)
for i in range(1, n):
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]
        j -= 1
    arr[j + 1] = key

print("Sorted array is:", arr)

計算量

• 最悪の場合: (O(n^2))
• 平均の場合: (O(n^2))
• 最良の場合: (O(n))

マージソート (Merge Sort)

動作原理

マージソートは、配列を半分に分割し、それぞれを再帰的にソートし、最後に二つのソート済み配列をマージして一つのソート済み配列を作成します。

実装

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

arr = [64, 25, 12, 22, 11]
merge_sort(arr)
print("Sorted array is:", arr)

計算量

• 最悪の場合: (O(n \log n))
• 平均の場合: (O(n \log n))
• 最良の場合: (O(n \log n))

クイックソート (Quick Sort)

動作原理

クイックソートは、基準点（ピボット）を選び、ピボットより小さい要素と大きい要素に分け、再帰的にソートを行います。

実装

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quick_sort(left) + middle + quick_sort(right)

arr = [64, 25, 12, 22, 11]
sorted_arr = quick_sort(arr)
print("Sorted array is:", sorted_arr)

計算量

• 最悪の場合: (O(n^2))
• 平均の場合: (O(n \log n))
• 最良の場合: (O(n \log n))

SWAP

# 難しく考えない
a, b = b, a

リストの列から奇数番目と偶数番目だけの要素を取り出す

スライス表記の構文

list[start:stop:step]

• start: スライスの開始インデックス。省略するとデフォルトは0。
• stop: スライスの終了インデックス（このインデックスの要素は含まれない）。省略するとリストの末尾まで。
• step: スライスのステップ（間隔）。省略するとデフォルトは1。

a = [1, 2, 3, 4, 5]

# 奇数番目
a[1::2]
# 偶数番目
a[::2]