TIL #09 - 3.09



Sort関数:Sortedまたはa.sordedを使用してリストをソートします.
Default値は昇順で返されます
降順で値を表示するには、a.sort(reverse=true)またはsorded(a,reverse=true)を行うだけです.
さらに、lambda関数を使用して、リスト内のリスト基準に基づいて昇順と降順を決定できます.
複数の条件を与えたい場合はtuple形式の前を優先条件とすることができる.
sorted(c, lambda x: (x[0], x[1]))
バイナリ検索-バイナリ検索
  • Big O - O(log N)
  • 並べ替えた資料を半分に分けて閲覧する方法
  • 資料は昇順または降順で並べ替えなければならない.
  • のパフォーマンスは非常に良く、実装ではダイナミックプログラミング、再帰が見られる.
  • を参照すると、insert sort(挿入ソート)、bubble sort、selection sortはO(n^2)の性能を有する.
  • ソートアルゴリズム-O(n^2)
  • 挿入ソート:小さいときから左に挿入タイル
  • 選択ソート:最小値を選択し、一番前の位置からソート(挿入ソートと非常に類似)
  • を行います.
  • Bubbleソート:2つの要素を比較して最大値を送信し、アレイ要素の数でソート(繰り返し)
  • アルゴリズム実行時間タイプN
  • アルゴリズム解析の結果,入力したN個のデータに対して実行時間は関数関係である.
    1(タイプ)
    1つのアルゴリズムで、どれだけのデータを入力しても、一定の実行時間があります.
    運転時間は定数です.(数回しか実行しない場合は試してみるアルゴリズム)
    LogN(タイプ)
    入力資料数log Nによる関係が満たされると、入力資料数の増加に伴って実行時間が徐々に増加する.
    主に、大規模な問題を一定のサイズの問題に分割する場合に発生するタイプです.
    効率の良いアルゴリズムはLogNタイプです.
    N(タイプ)
    入力された資料の数に応じて入力時間を線形に増加させる形式.
    納得できる実行時間を持つ.
    N log N(タイプ)
    巨大な問題をそれぞれ独立した問題に分解し,独立して解決した部分を集中する.
    線形N型より少し時間がかかります.
    n^^2(タイプ)
    二重ループを使用する場合に発生するタイプ.非常に時間がかかるタイプ
    白俊の問題.

    ハノイの塔


    3本の棒があり、1本目の棒にはn個の半径の異なる円板が積み上げられている.各円板は半径の大きい順に積み上げられている.現在、修道僧たちは以下の規則に従って、最初の棒から3番目の棒に移動します.
    一度に1枚の原版を別の塔に移すしかない.
    積み上げられたフィルムはいつも上のほうが下のより小さい.
    プログラムを作成し、この操作を実行するために必要な移動順序を出力します.ただし、移動回数を最小限に抑える必要があります.
    下図は5枚のバックグラウンドの例です.
    入力
    第1行は、第1の棒に積まれた円板の個数N(1≦N≦20)を与える.
    しゅつりょく
    1行目に移動した回数出力K.
    2行目から実行プロセスの出力を開始します.2行目から、2つの整数A BをK行に分けて出力します.これは、A番タワーの一番上の円板をB番タワーの一番上に移動することを意味します.
    def hanoi_top(n, start, end, middle):
        if n == 1:
            print(f'{start} -> end')
            return
        else:
            hanoi_top(n-1, start, middle, end)
            print(f'{start} -> end')
            hanoi_top(n-1, middle, end, start)        
    ハノイ塔の移動過程を再帰関数の形で解くとよい.
    hanoi topが1つなら、1番から直接3番に移動すればいいです.そうでなければ、真ん中でn-1個移動し、最後に第1セット移動します.最後の2つを右に移動するプロセスです
    質問する
    2 D平面上のN個の点を与える.座標がy座標のインクリメンタルである場合、x座標のインクリメンタルでソートし、プログラム出力を記述します.
    入力
    第1行は、点の個数N(1≦N≦100000)を与える.2行目から、N行においてi番点の位置xiとyiが与えられる.(−1000≦xi,yi≦100000)座標は常に整数であり、2つの位置が同じ点はない.
    しゅつりょく
    最初の行からN行の位置合わせの結果を出力します.
    num = int(input())
    list1 = list()
    for i in range(num):
        k = list(map(int, input().split()))
        list1.append(k)
    
    final_list = sorted(list1, key = lambda x: (x[1], x[0]))
    for i in final_list:
        x = i[0]
        y = i[1]
        print(x, y)