ALDS1_1_A: 挿入ソート
問題
- 挿入ソート | アルゴリズムとデータ構造 | Aizu Online Judge
- ソートに関する問題
解答
問題文に記載されている挿入ソートのアルゴリズムを実装します。出力は、ソート前に 回と、各計算ステップの途中経過を 回の、合計 回行います。
C++
#include <iostream> using namespace std; const int MAX_N = 100; // 配列の要素を出力 void trace(int (&A)[MAX_N], int N) { for (int i = 0; i < N; ++i) { if (i > 0) { cout << " "; } cout << A[i]; } cout << endl; } // 挿入ソート void insertionSort(int (&A)[MAX_N], int N) { for (int i = 1; i < N; ++i) { int v = A[i]; int j = i - 1; while (j >= 0 && A[j] > v) { A[j + 1] = A[j]; j--; } A[j + 1] = v; trace(A, N); } } int main() { int N; int A[MAX_N]; // 入力 cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; } // 配列の要素を出力 trace(A, N); // 挿入ソート insertionSort(A, N); return 0; }
Python
# coding: utf-8 N = int(input()) A = list(map(int, input().split())) print(*A) for i in range(1, len(A)): 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)
Volume0: 0009
以下の素数の個数を求める問題です。
予めエラトステネスの篩を使用して素数のリストを作成しておき、各データセットに対して素数の個数を求めます。
Python
# coding: utf-8 LIMIT = 999999 # 1 から LIMIT までのリスト # 素数(の候補)を 1 、素数でないもを 0 とする # 2 以外の偶数は素数ではない prime = [0, 1] + [0 if i % 2 == 0 else 1 for i in range(3, LIMIT + 1)] # 3 から LIMIT の平方根までを走査 for i in range(3, int(LIMIT ** 0.5) + 1): # 対象が素数である場合 if prime[i - 1] == 1: # 自身の倍数は素数ではない for j in range(i ** 2, LIMIT + 1, i): # 素数ではないので 0 prime[j - 1] = 0 while True: try: n = int(input()) except EOFError: break # 1 から n までの素数の個数を合計して出力 print(sum(prime[:n]))
Ruby
Prime
クラスで素数についてあれこれできます。
# coding: utf-8 require 'prime' while line = gets do n = line.to_i puts Prime.each(n).count end
Volume0: 0008
重複を許す組み合わせの数を求めます。
C++
を より求めることで、for
ループが三重で済みます。
#include <iostream> using namespace std; int n; int main() { while (cin >> n) { int count = 0; for (int a = 0; a <= 9; ++a) { for (int b = 0; b <= 9; ++b) { for (int c = 0; c <= 9; ++c) { int d = n - a - b - c; if (0 <= d && d <= 9) ++count; } } } cout << count << endl; } return 0; }
Python
itertools.product()
を使用することで、直積を求めることができます。
product(range(10), range(10))
は、(x, y) for x in range(10) for y in range(10)
と等価です。
また、product(range(10), range(10))
は、product(range(10), repeat=2)
と等価です。
# coding: utf-8 from itertools import product RANGE = range(10) while True: try: n = int(input()) except EOFError: break print(sum([1 for (a, b, c) in product(RANGE, repeat=3) if n - a - b - c in RANGE]))
Volume0: 0007
以下の操作を 回繰り返せば良いです。
- 借金に利子を加える
- 1000未満を切り上げ
C++
借金の計算は以下の通りです。
- 借金に金利を加える
- 1000未満を切り上げするために、999を加える
- 1000で割って千の位未満の桁を飛ばす
- 1000を掛けて千の位未満の桁を0にする
#include <iostream> using namespace std; int n; int debt = 100000; const int DIGITS = 1000; const float INTEREST_RATE = 1.05; int main() { cin >> n; for (int i = 0; i < n; ++i) { // 借金に利子を加え、1000円未満を切り上げ debt = ((int)((debt * INTEREST_RATE + DIGITS - 1) / DIGITS)) * DIGITS; } cout << debt << endl; return 0; }
Python
math.ceil(x)
関数は、x
以上の最小の整数を返します。
借金を百の位で切り捨てるためには、百の位が小数点第一位となるように調整し、math.ceil()
を使用すれば良いです。
# coding: utf-8 from math import ceil DEBT = 100000 DIGITS = 1000 INTEREST_RATE = 1.05 def calc_debt(n): "n週間後の借金を計算する" # 借金の百の位が小数点第一位となるよう調整 d = DEBT // DIGITS # 毎週利子を加える while n > 0: d = ceil(d * INTEREST_RATE) # 借金の小数点以下を切り捨て n -= 1 # 調整した借金を元に戻して返却する return d * DIGITS n = int(input()) print(calc_debt(n))
Volume0: 0006
文字列を逆順にする問題です。
文字列は文字の配列で表現されているので、配列を後ろから操作すれば良いです。
ただし、ほとんどの言語において、関数reverse
で文字列を逆順にすることができます。
C++
配列を後ろから操作します。
#include <iostream> using namespace std; string s, r; int main() { cin >> s; for (int i = s.size() - 1; i >= 0; i--) { r += s[i]; } cout << r << endl; return 0; }
reverse
を使用します。
#include <iostream> #include <algorithm> using namespace std; string s; int main() { cin >> s; reverse(s.begin(), s.end()); cout << s << endl; return 0; }
JavaScript
'use strict' const fs = require('fs') function main(input) { console.log(input.trim().split('').reverse().join('')) } main(fs.readFileSync('/dev/stdin', 'utf8'))
Python
# coding: utf-8 print(input()[::-1])
Ruby
# coding: utf-8
puts gets.chomp.reverse
Volume0: 0005
最大公約数と最小公倍数 | Aizu Online Judge
最大公約数と最小公倍数を求める問題です。
整数 に対して、最大公約数 と は、 という関係があります。
最大公約数は、ユークリッドの互除法を使って求めることができます。
C++
#include <iostream> using namespace std; long a, b, gcd, lcm; // ユークリッドの互除法より最大公約数を求める long euclideanAlgorithm(long a, long b) { // a > b になるように a と b を入れ替える if (a < b) swap(a, b); // 剰余が0になった時の除数が a と b の最大公約数 if (b == 0) return a; // 剰余が0になるまで、剰余を求める計算を繰り返す return euclideanAlgorithm(b, a % b); } int main() { while (cin >> a >> b) { gcd = euclideanAlgorithm(a, b); // 最大公約数 lcm = a * b / gcd; // 最小公倍数 cout << gcd << " " << lcm << endl; } return 0; }
Python
math.gcd(a, b)
は、a
とb
の最大公約数を返します。
# coding: utf-8 import math while True: try: a, b = [int(i) for i in input().split()] gcd = math.gcd(a, b) # 最大公約数 lcm = a * b // gcd # 最小公倍数 print(f'{gcd} {lcm}') except EOFError: break
Ruby
Integer#gcd
とInteger#lcm
を利用し、最大公約数と最小公倍数を求めることができます。
# coding: utf-8 while line = gets a, b = line.chomp.split.map(&:to_i) gcd = a.gcd(b) # 最大公約数 lcm = a.lcm(b) # 最小公倍数 puts %Q!#{gcd} #{lcm}! end
%Q!STRING!
は、ダブルクォート文字列と同等です。
Volume0: 0004
連立方程式の解を求める問題です
クラーメルの公式を利用します
Python
# coding: utf-8 while True: try: a, b, c, d, e, f = [int(i) for i in input().split()] detA = a * e - b * d detA1 = c * e - b * f detA2 = a * f - c * d # -0.000 を 0.000 にするために 0 を足す print('{:.3f} {:.3f}'.format(detA1 / detA + 0, detA2 / detA + 0)) except EOFError: break
Ruby
# coding: utf-8 while line = gets a, b, c, d, e, f = line.strip.split.map(&:to_f) detA = a * e - b * d detA1 = c * e - b * f detA2 = a * f - c * d # -0.000 を 0.000 にするために 0 を足す puts "%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0] end
文字列の%
演算は、第1引数にフォーマット、第2引数にフォーマットしたい値を指定します
書式に埋め込む値が複数ある場合は、右辺を配列にします
"%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0]