AOJの アルゴリズムとデータ構造入門 トピック1にチャレンジしました。
アルゴリズムとデータ構造入門 トピック1
「プログラミング入門」編が完了したので「アルゴリズムとデータ構造入門」をやってみました。トピック1は入門編で、1_Aから1_Dまでの4問です。
1_A：Insertion Sort
入力データをソートして昇順に並べる問題です。
昇順とは時の通り、数字が上に登っていくので、小さい値→大きな値のソートになります。
挿入ソートのプログラミング例がすでに記述されているので、この通りに実行すればPASSできました。
「Post note」の一般解説を読むと挿入ソートが図でも説明されていますので比較的容易に解決できました。
1_B：Gratest Common Driver
1_Bは最大公約数を求める問題です。
これもヒントとして以下のように記載されているので、この通りに記述すれば、PASSできました。
ユークリッドの互除法は「 のとき と は等しい」という定理を用いて と の最大公約数を高速に求めるアルゴリズムです。
例えば、54 と 20 の最大公約数は以下のように求めることができます。
a,b=(int(x) for x in input().split())
if a>=b:
aa = a
bb = b
else:
aa = a
bb = b
cc = 1
while cc !=0:
cc = aa%bb
if cc ==0:
print(bb)
aa = bb
bb = cc
1_C：Prime Numbers
いくつかの数値が素数かどうかを求め、素数がいくつあるのかを求める問題です。
一般解説をみると「素数判定では、「合成数 は を満たす素因子 をもつ」」と記載されており、素数を見つけるには√xからx-1までで十分となっています。
ルートはmathモジュールで対応しました。
また、平方根のデータを整数にするため、math.ceilで小数点以下を切り上げました。
import math
#1回目の入力データの取得
num = int(input())
list_a = # 入力データを保存するため、空のリストを作成
#1回目に取得した入力データnum回分、データを取得し、リストに保存
for iii in range(num):
list_a.append(int(input()))
#素数をカウントした値を保存する変数
count=0
#2からルートxまで ＋1して割り切れるかチェック
for iii in range(num):
data = list_a[iii]
root_x = math.sqrt(data)
data_ceil = math.ceil(root_x)
if data == 2 :
count+=1
for jjj in range(2,data_ceil+1):
if jjj==2 and data%2==0: #2で割り切れたら偶数なのでbreak
break
elif data%jjj==0 and jjj%2!=0 : #jjjで割り切れたらbreak
break
elif jjj==data_ceil and data%jjj!=0:
count+=1
print(count)
1_D：Maximum Profit
入力データの値の差分がmaxになる値を求める問題です。
今までのMAX値と差分データの大きいほう、
今までのMIN値と差分データの小さいほう、 を実行することでPASSできました。
num = int(input())
list_a=
for iii in range(num):
list_a.append(int(input()))
minv = list_a[0]
maxv = -10**10
for jjj in range(1,num):
if maxv < list_a[jjj] - minv:
maxv =list_a[jjj]-minv
if minv > list_a[jjj]:
minv = list_a[jjj]
print(maxv)
