AOJのアルゴリズムとデータ構造入門をPythonで解いていく -Part1-

9014 ワード
アルゴリズム AOJ ALDS1 Python データ構造 Python テキストリンク

はじめに

こんにちは。もちもちもちおです。
AOJのアルゴリズムとデータ構造入門を解いていきます。
学んだ記録として残していこうと思いやす。

僕自身プログラミングに触り始めてまだ半年もたっておらず
AtCoder緑なので、強者ではありましぇん。
一緒に頑張りましょう。

あー　れっつら　ごー

目次

今回はPART１:入門 です。
頑張って最後までやりたいものです。

ALDS1_1_A : 挿入ソート
ALDS1_1_B : 最大公約数
ALDS1_1_C : 素数
ALDS1_1_D : 最大の利益

ALDS1_1_A : 挿入ソート

挿入ソート

n = int(input())
A = list(map(int,input().split()))
print(*A)
for i in range(1,n):
    v = A[i]
    j = i-1
    while j >= 0 and A[j]>v:
        A[j+1] = A[j]
        j -= 1

    A[j+1] = v
    print(*A)

ALDS1_1_B : 最大公約数

最大公約数はユークリッドの互助法で求める

 def gcd(a,b):
    while b:
        a, b = b, a%b
    return a



x,y = map(int,input().split())
print(gcd(x,y))

ALDS1_1_C : 素数

素数か判定するのはO(n**0.5)

n = int(input())
input_list = []

for _ in range(n):
    a = int(input())
    input_list.append(a)

def prime(n):
    if n==1:
        return False
    else:
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                return False 
        else:
            return True


ans = 0
for i in input_list:
    if prime(i):
        ans += 1

print(ans)

ALDS1_1_D : 最大の利益

株予測ダメ絶対

n = int(input())
a = []
for _ in range(n):
    b = int(input())
    a.append(b)

minv = a[0]
maxv = -10**18

for i in range(1,n):
    b = a[i]
    maxv = max(maxv,b-minv)
    minv = min(minv,b)

print(maxv)

おわりに

誤答あったら後藤まで連絡ください

p.s.p Qittaのいいね的なやつ貰ったことないので
記念すべき1つ目親戚一同心待ちにしております。