基本的なアルゴリズム問題集

1. 立方体の体積計算

辺の長さa, b, cが与えられた時、立方体の体積を計算します。

#include <iostream>
using namespace std;

int main() {
    int length, width, height;
    cin >> length >> width >> height;
    cout << length * width * height;
    return 0;
}

2. 指数計算

与えられたnに対して2のn乗を計算します。

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

int main() {
    int exponent;
    cin >> exponent;
    cout << "2^" << exponent << " = " << pow(2, exponent);
    return 0;
}

3. 文字列繰り返し

与えられた回数分"Wang!"という文字列を繰り返し出力します。

#include <iostream>
using namespace std;

int main() {
    int countA, countB;
    cin >> countA >> countB;
    for(int i=0; i<countA+countB; i++) {
        cout << "Wang!";
    }
    return 0;
}

4. 身長変換

性別と身長に基づいて身長を変換します。

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

int main() {
    int n;
    cin >> n;
    while(n--) {
        char gender;
        double height;
        cin >> gender >> height;
        if(gender == 'M') {
            cout << fixed << setprecision(2) << height/1.09 << endl;
        } else {
            cout << fixed << setprecision(2) << height*1.09 << endl;
        }
    }
    return 0;
}

5. 数字の性質チェック

数字の各倍数の桁和が同じかどうかを確認します。

#include <iostream>
using namespace std;

int digitSum(int num) {
    int sum = 0;
    while(num) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int main() {
    int number;
    cin >> number;
    int baseSum = digitSum(number);
    bool consistent = true;
    
    for(int i=2; i<=9; i++) {
        if(digitSum(number*i) != baseSum) {
            consistent = false;
            break;
        }
    }
    
    if(consistent) cout << baseSum << endl;
    else cout << "NO" << endl;
    
    return 0;
}

6. 文字列検索

複数行のテキストから特定のフレーズを検索します。

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

int main() {
    string line, target = "chi1 huo3 guo1";
    int lineCount = 0, firstMatch = 0, matchCount = 0;
    
    while(getline(cin, line) && line != ".") {
        lineCount++;
        if(line.find(target) != string::npos) {
            if(!firstMatch) firstMatch = lineCount;
            matchCount++;
        }
    }
    
    cout << lineCount << endl;
    if(matchCount) {
        cout << firstMatch << " " << matchCount << endl;
    } else {
        cout << "-_-#" << endl;
    }
    
    return 0;
}

7. グラフ探索

与えられたグラフを深さ優先探索で探索します。

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

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    cout << " " << node;
    visited[node] = true;
    
    for(int neighbor : graph[node]) {
        if(!visited[neighbor]) {
            dfs(neighbor, graph, visited);
            cout << " " << node;
        }
    }
}

int main() {
    int nodes, edges, start;
    cin >> nodes >> edges >> start;
    
    vector<vector<int>> graph(nodes+1);
    vector<bool> visited(nodes+1, false);
    
    for(int i=0; i<edges; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    for(int i=1; i<=nodes; i++) {
        sort(graph[i].begin(), graph[i].end());
    }
    
    visited[start] = true;
    cout << start;
    dfs(start, graph, visited);
    
    return 0;
}

8. 最小全域木

Kruskalのアルゴリズムを使用して最小全域木を構築します。

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

struct Edge {
    int u, v, weight;
};

class UnionFind {
    vector<int> parent;
public:
    UnionFind(int size) : parent(size+1) {
        for(int i=0; i<=size; i++) parent[i] = i;
    }
    
    int find(int x) {
        if(parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x != y) parent[y] = x;
    }
};

int main() {
    int nodes, edges;
    cin >> nodes >> edges;
    
    vector<Edge> edgeList(edges);
    for(int i=0; i<edges; i++) {
        cin >> edgeList[i].u >> edgeList[i].v >> edgeList[i].weight;
    }
    
    sort(edgeList.begin(), edgeList.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });
    
    UnionFind uf(nodes);
    int totalWeight = 0;
    
    for(Edge e : edgeList) {
        if(uf.find(e.u) != uf.find(e.v)) {
            uf.unite(e.u, e.v);
            totalWeight += e.weight;
        }
    }
    
    for(int i=2; i<=nodes; i++) {
        if(uf.find(1) != uf.find(i)) {
            cout << "Impossible" << endl;
            return 0;
        }
    }
    
    cout << totalWeight << endl;
    return 0;
}