AIZU ONLINE JUDGEで問題を解いてみた

競プロのサイト

AIZU ONLINE JUDGEというサイトの問題を解いていきます。

Insert Sort

1行目 入力数
2行目 入力

sample input

6
5 2 4 6 1 3

sample output

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

code1.cpp

#include <iostream>
using namespace std;

void trace(int A[], int n) {
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << A[i];
    }
    cout << endl;
}

void InsertSort(int A[], int n) {
    for (int i = 0; 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 N = 100;
    int A[N];

    cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i];

    InsertSort(A, n);
    return 0;
}

Greatest Common Divisor

sample input

54 20

sample output

2

直感的に、最大公約数を求めてみる
どちらでも割り切れる最大の数を求める

code2_1.cpp

#include <iostream>
using namespace std;
int a, c;

int mmcm() {
    int result = 0;
    if (a > c) {
        for (int i = c; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else if (a < c) {
        for (int i = a; i >= 1; i--) {
            if (a % i == 0 && c % i == 0) return i;
        }
    } else {
        result = a;
    }
    return result;
}

int main() {
    cin >> a >> c;
    int result;
    result = mmcm();
    cout << result << endl;
    return 0;
}

数が大きくなると、処理時間が長くなるので改良

ユークリッド互除法を用いてコードを書く

code2_2.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y) {
    int r;
    if (x < y) swap(x, y);
    while (y > 0) {
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

Prime Numbers

1行目 入力数
2行目以降 入力

sample input

7
1
2
3
4
5
6
7

sample output

4

code3.cpp

#include <iostream>

using namespace std;

int MAX = 10000;

int pm_bool(int p) {
    int r = 0;
    int i = 2;
    bool key = true;
    if (p <= 1) {
        return r;
    }
    while (key) {
        if (p % i == 0) {
            if (p == i) {
                r = 1;
            }
            key = false;
        }
        i++;
    }
    return r;
}

int main() {
    int n;
    int p[MAX];
    cin >> n;
    int result = 0;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        result = result + pm_bool(p[i]);
    }
    cout << result << endl;
    return 0;
}

Bubble Sort

sample input

5
5 3 2 4 1

sample output

1 2 3 4 5
8

code4.cpp

#include <iostream>
using namespace std;

int BubbleSort(int A[], int N) {
    int sw = 0;
    bool flag = 1;
    for (int i = 0; flag; i++) {
        flag = 0;
        for (int j = N - 1; j >= i + 1; j--) {
            if (A[j] < A[j - 1]) {
                swap(A[j], A[j -1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main() {
    int A[100], N, sw;

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    sw = BubbleSort(A, N);
    for (int i = 0; i < N; i++) {
        if (i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;

    return 0;

    return 0;
}

続きはこちら