AIZU ONLINE JUDGEの問題を解いてみたNo.1

アルゴリズム
2022.07.19

競プロのサイト

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
#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

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

#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;
}

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

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

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

int gcd(int x, int y) {
    int r;
    // xとyの値を比較して、以降y < x であることを保障する
    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
#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
#include <iostream>
using namespace std;


void BubbleSort(int A[], int n) {
    int v;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            v = A[j];
            if (j + 1 < n - i && A[j + 1] < v) {
                A[j] = A[j + 1];
                A[j + 1] = v;
                count++;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << A[i];
        if (i != n - 1) cout << " ";
    }
    cout << endl;
    cout << count << endl;
}

int main() {
    int n;
    int N = 100;

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


    return 0;
}

Selection Sort

// sample input
6 
5 6 4 2 1 3
// sample output
1 2 3 4 5 6
4
// 選択ソート
#include <iostream>
using namespace std;

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

int SearchMin(int A[], int i, int n) {
    int min = A[i];
    int minIndex = -1;
    for (int j = i; j < n; j++) {
        if (min > A[j]) {
            min = A[j];
            minIndex = j;
        }
    }
    return minIndex;
}

void SelectSort(int A[], int n) {
    int count = 0;
    int minIndex;
    int v;
    for (int i = 0; i < n; i++) {
        minIndex = SearchMin(A, i, n);
        if (minIndex != -1) {
            v = A[minIndex];
            A[minIndex] = A[i];
            A[i] = v;
            count++;
        }
    }
    display(A, n, count);
}

int main() {
    int N = 100;
    int A[N];
    int n;

    cin >> n;

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

    SelectSort(A, n);

    return 0;
}

Shell Sort

シェルソートは、挿入ソートを工夫してもっと早くしようソート法

挿入ソートの特徴として、ある程度大小が並んでいるものに対して高速に処理することができるソート法である

しかし、全然並んでいないものに対しては遅くなってしまう。

長所を生かすために開発されたのが、シェルソート

シェルソートは、注目する数値とその左側を１つずつ比較していく挿入ソートに対して、注目した数値の左側に間隔をあけて比較していくソート法である

#include <iostream>
#include <vector>




using namespace std;

long long cnt;

int A[1000000];
int n;

vector<int> G;

void insertSort(int A[], int n, int g) {
    for (int i = g; i < n; i++) {
        int v = A[i];
        int j = i - g;
        while (j >= 0 && A[j] > v) {
            A[j + g] = A[j];
            j -= g;
            cnt++;
        }
        A[j + g] = v;
    }
}

void shellSort(int A[], int n) {
    for (int h = 1; ;) {
        if (h > n) break;
        G.push_back(h);
        h = 3*h + 1; // 挿入ソートの間隔
    }

    for (int i = G.size() - 1; i >= 0; i--) {
        insertSort(A, n, G[i]);
    }
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i];
    cnt = 0;
    shellSort(A, n);

    cout << G.size() << endl;

    for (int i = G.size() - 1; i >= 0; i--) {
        cout << G[i];
        if (i) cout << " ";
    }
    cout << endl;
    cout << cnt << endl;

    for (int i = 0; i < n; i++) cout << A[i] << endl;

    return 0;
}

コメント

タイトルとURLをコピーしました