遺伝的アルゴリズムは、進化と同じやり方で候補解の集団を改良します。適応度の高い親を選び、組み合わせ、ランダムな突然変異を加えます。ここでは候補はビット列で、適応度は 1 の個数です (OneMax 問題)。
テストできるように、ランダムな選択はすべて与えられます。N 本の文字列 (N は偶数) から、ペアごとに N 個の子を作ります。ペア k = 0, 1, …, N/2 - 1 について:
- 選択: parent1 はトーナメント
tournaments[2k]の勝者、parent2 はtournaments[2k + 1]の勝者です。トーナメント[i, j]はpopulation[i]とpopulation[j]のうち 1 の多い方が勝ち、同数ならpopulation[i]が勝ちます。 - 交叉 (c =
crossover_points[k]): 子 2k = parent1[0:c] + parent2[c:]、子 2k + 1 = parent2[0:c] + parent1[c:]。
その後、各突然変異 [child, position] を順に適用し、その子のそのビットを反転します。
ga_generation(population, tournaments, crossover_points, mutations) を実装してください。
入力
population: 長さ L の N 本のビット列。
tournaments: 集団のインデックスの N 個のペア。
crossover_points: N/2 個の切断点。それぞれ 1 以上 L - 1 以下。
mutations: [child, position] のペア (空の場合もあります)。
出力
N 個の子を順に返します。
制約
2 ≤ N ≤ 200 (N は偶数)、2 ≤ L ≤ 64
0 ≤ 突然変異の数 ≤ 1,000
例
入力：
mutations = [
[0, 0]
]
population = ["0000", "1111", "1100", "0011"]
tournaments = [
[0, 1],
[2, 3],
[1, 2],
[0, 3]
]
crossover_points = [2, 1]
期待される出力：
["0100", "1111", "1011", "0111"]解説
ペア 0: "1111" が "0000" に勝ち、"1100" と "0011" は同数なので前者が勝ちます。2 ビット目の後で切ると "1100" と "1111"。ペア 1: 親は "1111" と "0011"、1 ビット目の後で切ると "1011" と "0111"。最後に子 0 のビット 0 を反転して "0100"。
入力：
mutations = []
population = ["10", "01"]
tournaments = [
[0, 1],
[1, 0]
]
crossover_points = [1]
期待される出力：
["11", "00"]解説
両方とも 1 が 1 つなので、各トーナメントは最初のインデックスが勝ちます: parent1 = "10"、parent2 = "01"。1 ビット目の後で切ると "11" と "00"。
参考資料
-
例 1 未実行入力：
mutations = [ [0, 0] ] population = ["0000", "1111", "1100", "0011"] tournaments = [ [0, 1], [2, 3], [1, 2], [0, 3] ] crossover_points = [2, 1]期待される出力：["0100", "1111", "1011", "0111"]あなたの出力 -
例 2 未実行入力：
mutations = [] population = ["10", "01"] tournaments = [ [0, 1], [1, 0] ] crossover_points = [1]期待される出力：["11", "00"]あなたの出力
提出時に非公開テスト4件も実行されます。
C++オンラインコンパイラ＆デバッガー
サーバーモードのGDBでブレークポイント、変数確認、ステップ実行を使ってC++をデバッグできます。
トピックから探す
実践コード、出力、メモリモデル、データ構造、アルゴリズム、モダンC++を通してCとC++を比較しながら学びます。
💻 このC++オンライン実行ツールについて
CodeUtility C++ Executor を使えば、ブラウザ上で直接C++コードを書いて実行できます — インストールやコンパイラ設定は一切不要です。安全なサンドボックスで動作し、 C++11、C++14、C++17から最新バージョンまでの実際のC++標準に対応しています。
このツールはクラウド上で動作する本物のC++コンパイラでコードをコンパイル・実行し、 バージョン間で正確かつ一貫した挙動を保証します。変数、関数、ループ、条件分岐、 オブジェクト指向といったC++の基本概念を自由に試せます。
面接の準備、モダンC++の学習、アルゴリズムのロジック検証など、どんな用途でも、 CodeUtility C++ Executor は、どのデバイスからでもすぐにコードを実行できるシンプルかつ強力な環境を提供します。
同じ実行環境で、複数ファイル対応エディター、分離された実行ターミナル、ランタイム別ライブラリ、永続ワークスペース、共有、リアルタイム共同作業を利用できます。
この実行環境の使い方
ランタイムを選択し、ファイルを開くか作成してコードを記述し、［実行］を選択します。出力はターミナルに表示されます。サインインしたユーザーは、ワークスペースにファイルを保存し、ライブラリをインストールして、共有を通じて共同作業できます。
- バージョンを選択して現在のファイルを編集するか、ワークスペース内の別のファイルを開きます。
- コードを実行し、求められた場合はターミナルに入力して、保存された実行履歴を確認します。
- 複数のコードスニペットが必要な作業では、ライブラリ、ワークスペースツール、共有、チャットを利用します。
💡 上で試せるC++の基本とサンプル
1. 変数と定数の宣言
C++では、各変数の型を宣言する必要があります。constを使うと、初期化後に変更できない読み取り専用の値を定義できます。
int age = 30;
double pi = 3.14159;
char grade = 'A';
std::string name = "Alice";
bool isActive = true;
// 定数
const int MAX_USERS = 100;
const std::string COMPANY = "CodeUtility";
// const を変更しようとするとコンパイル時エラーになります
// MAX_USERS = 200; // ❌ エラー
2. 条件分岐（if / switch）
分岐にはif、else if、elseを使います。複数の値を扱う場合はswitchを使います。
int x = 2;
if (x == 1) {
std::cout << "1\n";
} else if (x == 2) {
std::cout << "2\n";
} else {
std::cout << "その他\n";
}
// switch文
switch (x) {
case 1:
std::cout << "1\n";
break;
case 2:
std::cout << "2\n";
break;
default:
std::cout << "その他\n";
}3. ループ
for、while、do-whileでコードブロックを繰り返します。
for (int i = 0; i < 3; i++) {
std::cout << i << "\n";
}
int n = 3;
while (n > 0) {
std::cout << n << "\n";
n--;
}4. 配列
配列は同じ型の要素を複数格納します。
int numbers[3] = {10, 20, 30};
std::cout << numbers[1] << "\n";5. 配列/ベクターの操作
動的配列にはstd::vectorを使います。
#include <vector>
std::vector nums = {1, 2, 3};
nums.push_back(4);
nums.pop_back();
for (int n : nums) {
std::cout << n << " ";
} 6. コンソール入出力
入力にはstd::cin、出力にはstd::coutを使います。
std::string name;
std::cout << "あなたの名前を入力してください: ";
std::cin >> name;
std::cout << "こんにちは、" << name << "\n";7. 関数
関数は再利用可能な処理をまとめます。引数と戻り値の型を指定します。
int add(int a, int b) {
return a + b;
}
std::cout << add(3, 4);8. マップ
std::map は辞書のようにキーと値のペアを格納します。
#include <map>
std::map ages;
ages["Alice"] = 30;
std::cout << ages["Alice"]; 9. 例外処理
try と catch を使って実行時エラーを処理します。
try {
throw std::runtime_error("エラーが発生しました");
} catch (const std::exception& e) {
std::cout << e.what();
}10. ファイル入出力
fstream を使ってファイルの読み書きを行います。
#include <fstream>
std::ofstream out("file.txt");
out << "こんにちは、ファイル";
out.close();
std::ifstream in("file.txt");
std::string line;
getline(in, line);
std::cout << line;
in.close();11. 文字列操作
C++の文字列は length()、substr()、find() といったメソッドをサポートしています。
std::string text = "Hello World";
std::cout << text.length();
std::cout << text.substr(0, 5);
std::cout << text.find("World");12. クラスとオブジェクト
C++はクラスを使ったオブジェクト指向プログラミングをサポートしています。
class Person {
public:
std::string name;
Person(std::string n) : name(n) {}
void greet() { std::cout << "こんにちは、私は " << name; }
};
Person p("Alice");
p.greet();13. ポインタ
ポインタは別の変数のメモリアドレスを保持します。アドレスを取得するには &、
参照外し（そのアドレスの値にアクセス）には * を使います。
int x = 10;
int* ptr = &x;
std::cout << "x の値: " << x << "\n";
std::cout << "x のアドレス: " << ptr << "\n";
std::cout << "ポインタ経由の値: " << *ptr << "\n";
// ポインタ経由で x を変更
*ptr = 20;
std::cout << "更新後の x: " << x << "\n";🐞 %{language}コードをオンラインでデバッグする方法
オンライン%{language}デバッガーなら、コンパイラやIDEをインストールせずに実行時エラーやロジックエラーを調査できます。サーバーモードはデバッグ情報付きでコンパイルし、GDBで実行します。
- 行番号の横にブレークポイントを設定します。
- Debugを選択してコンパイルし、最初のブレークポイントで停止します。
- 現在行、コールスタック、変数を確認します。
- Continue、Step Over、Step Into、Step Outで実行を制御します。
- 終了するときはStopを選択します。
再現可能な小さなコードから始め、想定外の動作が起きる直前にブレークポイントを置きましょう。