C++

本記事では、コイントス（コイン投げ）の原理を応用して、配列の中からランダムな部分集合を生成するC++プログラムを紹介します。各要素に対してコインを1回ずつ投げるイメージで、「表（1）」が出た要素だけを選んで部分集合を作るというシンプルな手法です。 アルゴリズム このプログラムの処理の流れは以下のとおりです。 配列に格納する要素を入力として受け取ります。 rand() 関数を使って、ランダムな0または1の二値列を生成します。 コイントスのように0か1をランダムに決定し、値が「1」だった場合のみ、その位置の配列要素を出力します。 サンプルコード #include<iostream>

本記事では、与えられた数値の配列または文字列から、ランダムな分割（ランダムパーティション）を生成するC++プログラムを紹介します。このプログラムは、rand()関数を活用して、要素の総数をランダムなサイズのグループに分割していく仕組みです。アルゴリズムの流れプログラムの処理手順は以下のとおりです。数値配列か文字列のどちらを扱うか、選択肢として入力を受け取ります。選択が「1」（整数配列）の場合：要素数 n と、n 個の整数からなる配列を入力します。配列を走査するためのインデックス変数 l を 0 で初期化します。rand() を使って、n をランダムな整数分割に分解します。各分割サイズ i に対

この記事では、与えられた文字の集合からちょうどk個の要素を含むすべての部分集合（組み合わせ）を生成するC++プログラムを紹介します。再帰によるバックトラッキングを用いることで、指定した長さの組み合わせを漏れなく列挙できます。アルゴリズムこのアルゴリズムの考え方はシンプルです。各要素について「部分集合に含める」か「含めない」かの2つの選択肢を順に試します。現在の部分集合の要素数（currLen）が要求された長さ（reqLen）に達した時点で、その組み合わせを出力します。Begin function PossibleSubSet(char a[], int reqLen, int s, in

ハノイの塔は、3本の杭と複数の円盤を使った古典的なパズルです。本記事では、2進数（バイナリ値）を活用してハノイの塔の移動手順を出力するC++プログラムを紹介します。再帰呼び出しを使わず、ビット演算だけで解を導ける点が大きな特徴です。バイナリ値による解法の考え方この手法では、各円盤に1桁の2進数（ビット）を対応させます。n枚の円盤がある場合、全体の状態はn桁のビット列で表現できます。最上位ビットが最大の円盤を表します。値が 0 なら最大の円盤は初期の杭にあり、1 なら最終の杭にあることを意味します。ビット列は左から右へ読み進め、各ビットから対応する円盤の位置を特定できます。あるビットが直前のビッ

この記事では、a、b、c、d、eの5つの文字から考えられるすべての組み合わせを生成するC++プログラムを紹介します。再帰呼び出しを利用したシンプルな手法で、長さ1から5までの全パターン（合計31通り）を出力します。アルゴリズム組み合わせの生成は、各要素について「選ぶ／選ばない」の2択を順番に決めていくことで実現できます。全体の流れを擬似コードで表すと次のようになります。開始 要素数と各要素を入力として受け取る。 関数 Combi(char a[], int reqLen, int s, int currLen, bool check[], int l) （与えられた配列

本記事では、安定結婚問題（Stable Marriage Problem）と呼ばれるマッチング問題を、特定のケースについて解決するC++プログラムを紹介します。ここでは、N人の男性とN人の女性が与えられ、それぞれが異性全員を好みの順にランク付けしているものとします。その上で、「お互いが現在のパートナーよりも相手の方を望む」というような男女の組み合わせが一切存在しない形で結婚を実現します。この条件を満たすとき、すべての結婚は「安定（stable）」していると言えます。 アルゴリズムの流れ このプログラムで採用しているのは、ゲールとシャプレーが1962年に提案したGale–Shapleyの安定結

本記事では、2つの部分集合の和集合がもとの集合（上位集合）と完全に一致するような、すべての部分集合ペアを生成するC++プログラムを紹介します。基本的な考え方はシンプルです。各要素について「左の集合に入れるか」「右の集合に入れるか」の2択を考えることで、n個の要素から 2^(n-1) 通りのペアが導き出せます。どのペアを選んでも、2つの集合を足し合わせれば必ずもとの集合に戻る仕組みです。アルゴリズム開始 関数 UnionSet(): 引数: a[] = 配列 n = 要素数 処理内容: 1) 0 から 2^(n-1)-1 ま

グラフにおいて「ある頂点から別の頂点へ到達できるか」を判定する問題は、経路探索やネットワーク解析など、さまざまな場面で登場する基本的な課題です。本記事では、C++を用いて、指定した2つのノード（頂点）間にパス（経路）が存在するかどうかを確認するプログラムを紹介します。 アルゴリズム このプログラムでは、幅優先探索（BFS）をベースとした関数 isReach() を使い、始点 s から終点 d への到達可能性を調べます。処理の手順は以下の通りです。 開始 　　isReach() は、d が s から到達可能かどうかを判定する再帰的な関数である： 　　A) すべての頂点を「未訪問」としてマーク

これは、グラフ理論における支配集合問題(Dominating Set Problem)を解決するためのC++プログラムです。支配集合とは、グラフの頂点部分集合のうち、集合に含まれないすべての頂点が集合内のいずれかの頂点と隣接しているようなものを指します。本記事では、貪欲法を用いたシンプルな実装例をわかりやすく紹介します。 アルゴリズム 本プログラムで採用している貪欲法の流れは以下の通りです。 Begin 頂点の数と辺の数、および各辺の端点を入力として受け取る。 関数 dominant(): ベクター Set を宣言する。 頂点 X と Y をつな

本記事では、有名な4色問題(Four Color Problem)をC++で実装する方法を解説します。4色問題とは、平面上の任意の地図を塗り分ける際に、隣接する領域同士が同じ色にならないようにするために必要な色は最大4色である、という有名な定理(四色定理)に基づく問題です。この問題はグラフ理論における「グラフ彩色問題」として定式化でき、ここではバックトラッキング法を用いて解きます。 アルゴリズム Begin 関数issafe()を作成し、現在の色の割り当てが頂点vにとって安全かどうか、 すなわち辺が存在するかどうかを確認する。 辺が存在する場合は、

ビジングの定理（Vizings Theorem）とは、グラフ理論における重要な定理の一つです。この定理によると、単純グラフの彩色指数（chromatic index）は「最大次数」または「最大次数＋1」のいずれかに必ずなります。ここで彩色指数とは、グラフの辺彩色（edge coloring）に必要な色数の最小値を指します。 つまり、隣接する辺同士が同じ色にならないように全ての辺を塗り分ける場合、必要な色の数は最大でも「グラフの最大次数＋1」種類で足りるということです。本記事では、このビジングの定理をC++で実装するプログラムを紹介します。 アルゴリズム プログラムの流れは以下の通りです。 開始

Treap（ツリープ）は、二分探索木（BST）とヒープの性質を兼ね備えたランダム化データ構造です。各ノードは「キー」と「優先度」の2つの値を持ち、キーについては二分探索木の規則（左の子 ＜ 親 ＜ 右の子）、優先度についてはヒープの規則（親の優先度 ≥ 子の優先度）が常に保たれます。優先度を乱数で決定することで木のバランスが偏りにくくなり、すべての操作を期待計算量 O(log n) で実行できます。 この記事では、C++を用いてTreapを実装し、挿入（insert）・削除（delete）・探索（search）の3つの基本操作を行うプログラムを紹介します。 使用する関数とその役割 rotLef

C++を使えば、12時間形式（am/pm付き）で入力された時刻を24時間形式へ簡単に変換できます。この記事では、変換の基本ルール、アルゴリズム、実際に動作するサンプルコード、そして実行結果の順にわかりやすく解説します。 時刻変換の基本ルール 12時間形式から24時間形式への変換は、午前（am）か午後（pm）かによって処理が変わります。 pm（午後）の場合：時間が12未満なら12を加算します（例：午後1時→13時）。時間がちょうど12の場合はそのまま12とします（正午は24時間制でも「12時」）。 am（午前）の場合：時間が12未満ならそのまま使います。時間が12の場合は「00」に置き換えます

本記事では、C++を使って「Happy Birthday」という文字列を出力するプログラムを紹介します。このプログラムは、ASCIIコードの性質を利用したちょっとしたトリックを使ったユニークな手法が特徴です。 アルゴリズム 開始 出力したい各文字の「1つ前の文字」からなる文字列str1を用意する（例：「H」なら「G」、「a」なら「`」）。 文字列の先頭アドレスをポインタpに代入する。 *pがNULL（\0）でない間、whileループを繰り返す。 現在の文字をインクリメント（+1）して目的の文字へ変換し、ポインタを次の位置へ進める。 変換後の文字列

本記事では、コンソールに菱形（ダイヤモンド型）の星形パターンを出力するC++プログラムを紹介します。行数を入力すると、その大きさに応じた菱形が表示される、定番のアルゴリズム演習問題です。二重ループの考え方を学ぶのに最適な題材なので、ぜひ参考にしてください。アルゴリズム菱形の出力は「上半分」と「下半分」の2段階に分けて考えるのがポイントです。まず上向きの三角形を作り、次に同じ処理を逆順に実行することで、対称的な菱形が完成します。Begin 行数 n を入力として受け取る（nは菱形の寸法を表す）。 変数 i、j を宣言し、space = 1 で初期化する。 space =

本記事では、指定された辺数と頂点数をもとに、グラフの構築が可能かどうかを確認し、ランダムな無向グラフを生成するC++プログラムを紹介します。与えられた条件(頂点数・辺数)から実際にグラフを構築できるかをチェックしながら、隣接関係を出力するまでの一連の流れを、アルゴリズムとサンプルコードを通してわかりやすく解説します。 入力 プログラムへの入力は、グラフの頂点数(vertexes)と辺数(edges)です。 出力 出力としては、生成されたグラフの各頂点に接続している頂点番号(隣接リスト形式)が表示されます。どの頂点とも接続していない孤立した頂点については、その旨が明示されます。 アルゴリズム 処

トポロジカルソートとは 有向非巡回グラフ(DAG:Directed Acyclic Graph)では、トポロジカルソートを利用してすべての頂点を線形の順序に並べ替えることができます。トポロジカルソートは有向非巡回グラフに対してのみ適用できる手法であり、1つのDAGに対して複数の妥当な並び順が存在する場合もあります。 本記事では、トポロジカルソートを応用して、グラフの中にサイクル(閉路)が存在するかどうかを判定するC++プログラムを紹介します。 サイクル検出の基本的な考え方 まず、深さ優先探索(DFS)によって各頂点の「発見時刻(S_Time)」と「完了時刻(L_Time)」を記録しながらトポロ

有向非巡回グラフ(DAG)では、トポロジカルソートを使うことで頂点を線形の順序に並べ替えることができます。トポロジカルソートは、有向非巡回グラフ(DAG)に対してのみ機能します。また、DAGにおいてはトポロジカルソートの結果が一意になるとは限らず、複数の妥当な順序が存在することもあります。以下のC++プログラムでは、トポロジカルソートを実行し、その結果からグラフ内に閉路(サイクル)が存在するかどうかを確認します。DAGであれば必ずトポロジカル順序が求まりますが、閉路を含むグラフでは全ての頂点を並べることができません。アルゴリズムTopo_Sort関数の手順開始 関数 Topo_Sort

この記事では、深さ優先探索（DFS）を利用して、有向グラフ内のすべてのフォワードエッジ（前向き辺）を検出するC++プログラムを解説します。 フォワードエッジとは？ DFSでグラフを探索する際、各頂点に「発見時刻（S_Time）」と「完了時刻（L_Time）」を記録すると、グラフのエッジは次の4種類に分類できます。 木エッジ（Tree Edge）：DFSの探索木を構成する辺 後退エッジ（Back Edge）：祖先の頂点へ戻る辺（サイクルの存在を示します） フォワードエッジ（Forward Edge）：子孫の頂点へ向かうものの、探索木には含まれない辺 交差エッジ（Cross Edge）：上記のい

スレッド化二分木（Threaded Binary Tree）は、特定の順序で木を走査する機能を提供する二分木の一種です。この構造を用いると、スタックや再帰を使用せずに中順走査（inorder traversal）を高速に行うことができます。 スレッド化二分木の種類 単一スレッド（Single Threaded） 各ノードが左または右のいずれか一方にスレッドを持つ構造です。つまり、中順走査における前駆ノード（inorder predecessor）または後続ノード（inorder successor）へのポインタを保持します。すべての右のNULLポインタが中順後続を指すか、またはすべての左の