C++

C++の仮想関数（virtual function）は、基底クラスのポインタを使って、派生クラスのオブジェクトの具体的な型を意識することなく、その派生クラスのメソッドを呼び出すために利用されます。これにより、基底クラスのポインタのリストを作成し、そこに格納されたさまざまな派生クラスのオブジェクトに対して、統一的な方法でメソッドを呼び出すことが可能になります。仮想関数の大きな特徴は、コンパイル時ではなく実行時（ランタイム）に遅延解決（レイトバインディング）される点です。実際にどの関数が呼ばれるかは、ポインタが指しているオブジェクトの実際の型によって決まります。仮想関数のサンプルコード以下は、C+

この記事では、C++を使って直接アドレス指定テーブル（Direct Addressing Table）を実装する方法を解説します。直接アドレス指定テーブルは、各要素が普遍集合 S = {0, 1, ..., n−1} のいずれかのキーを持ち、n がそれほど大きくなく、すべてのキーが一意である場合に有効なデータ構造です。キーをそのまま配列の添字として扱うため、挿入・検索・削除をすべて O(1) の時間で行えるのが最大の特徴です。 基本となる操作と擬似コード 直接アドレス指定テーブルでは、次の3つの基本操作を定義します。 Begin insert(): テーブル変数 wor

素集合データ構造（Disjoint Set）とは、ある要素が複数の集合に同時に属することはない、互いに重ならない集合の集まりを表すデータ構造です。このデータ構造は、部分集合に対して「Union（結合）」と「Find（探索）」という2つの基本操作をサポートしており、グラフアルゴリズムにおける連結成分の管理やサイクル検出など、さまざまな場面で活用されています。主な操作Find()：要素の所属を調べる特定の要素がどの部分集合に属しているかを調べ、その集合の代表元（根）を返します。Union()：2つの集合を統合する異なる2つの部分集合を1つの集合に統合します。統合後は、一方の集合の代表元がもう一方の

Freivaldsアルゴリズムとは Freivalds（別名：Coppersmith–Freivalds）のアルゴリズムは、行列の掛け算の結果が正しいかどうかを高速に検証するための確率的アルゴリズムです。試行回数 k を選ぶことで、誤判定の確率を 2-k 未満に抑えながら、O(kn²) の計算量でチェックできます。 n×n 行列の積を素直に計算して照合すると O(n³) の計算量が必要ですが、このアルゴリズムでは「ランダムなベクトルとの積」だけで検証を行うため、1回あたり O(n²) という低いコストで済むのが大きな特徴です。 アルゴリズムの手順 入力として同じ次元 n の3つの行列 matr

この記事では、ガウス・ジョルダン消去法(Gauss-Jordan Elimination)をC++で実装するプログラムを紹介します。この手法は連立一次方程式を解析するために用いられるもので、行基本変形(掃き出し操作)によって方程式系を対角行列の形へと変形し、解を直接導出できる点が大きな特徴です。 ガウス・ジョルダン消去法とは ガウス・ジョルダン消去法は、連立一次方程式を解くための代表的な数値計算手法のひとつです。方程式系を拡大係数行列として表現し、「ある行を定数倍する」「別の行との和を取る」といった行基本変形を繰り返すことで、係数部分を対角成分だけが残る形(対角行列)に近づけていきます。最終

ガウス・ザイデル法（Gauss–Seidel法）は、連立一次方程式を反復計算によって数値的に解くための古典的な手法の一つです。ヤコビ法と並ぶ代表的な反復法であり、各反復ステップで更新したばかりの新しい近似値を、そのまま同じ反復内の次の計算に利用できる点が大きな特徴です。この記事では、ガウス・ザイデル法を実装したC++プログラムを紹介します。 ガウス・ザイデル法の基本原理 n元の連立一次方程式 Ax = b を解く場合、ガウス・ザイデル法では各変数を次の式で順番に更新していきます。 xi = (bi − Σj≠i aij xj) / aii ポイントは、右辺に現れる他の変数 xj のうち、す

本記事では、連立一次方程式を行列形式で表現するC++プログラムを紹介します。n個の変数を含むn本の一次方程式からなる連立方程式は、係数行列A・変数ベクトルx・定数ベクトルbを用いて「Ax = b」という形にまとめて表せます。このプログラムでは、ユーザーが入力した変数の個数と各係数を読み込み、それを見やすい行列形式で標準出力に表示します。 アルゴリズム 処理の流れは以下のとおりです。 開始 1) 変数の個数 n と、各変数の係数を入力として受け取る。 2) 行列 matrix[n][n] と定数配列 constant[n][1] を宣言する。 3) 二重ループ(i = 0〜n-1、

本記事では、電気回路における配線長(ワイヤ長)を最適化するC++プログラムを紹介します。このプログラムは、グラフ理論の代表的なアルゴリズムであるダイクストラ法を応用し、起点となる部品から各電子部品までの最短距離を求めることで、回路全体の配線を効率化します。アルゴリズムの概要配線長の最適化は、以下の手順で行われます。距離を格納する配列 dist[N] を宣言します。sptSet[i] は、部品 i が最短経路木に含まれているか、あるいは始点 src から i までの最短距離が確定している場合に true となるフラグです。すべての距離を無限大(INT_MAX)で初期化し、sptSet[] をすべ

本記事では、動的計画法（Dynamic Programming）を用いて、行列連鎖乗算における最適なかっこ付け（Optimal Parenthesization）を求めるC++プログラムを紹介します。 複数の行列を連続して掛け合わせる場合、計算の順序（どのペアから先に掛けるか）によって必要なスカラー乗算の回数が大きく変化します。動的計画法を活用すれば、すべての順序を総当たりすることなく、乗算回数が最小となる分割位置を効率的に求めることができます。 アルゴリズム まず、使用する変数と配列の意味を確認しておきましょう。 a[i][j]：行列 A[i]A[i+1]…A[j]（= A[i..j]）を

本記事では、行列の基底(basis)と次元(dimension)を求めるためのC++プログラムを紹介します。 基底と次元とは 線形代数における基底とは、ベクトル空間全体を張る線形独立なベクトルの集合のことです。そして次元とは、その基底に含まれるベクトルの個数を指します。 n個のベクトルがR^n(n次元実ベクトル空間)の基底を成すかどうかは、それらを並べてできるn次正方行列の行列式を計算すれば判定できます。行列式が0でなければベクトル群は線形独立であり、R^nの基底となります。逆に行列式が0であれば、ベクトル群は線形従属のため基底にはなりません。 アルゴリズム このプログラムでは、determi

この記事では、(x1 + x2 + x3 + … + xa) × (y1 + y2 + … + yb) という形式の代数式の最小値を求めるC++プログラムを紹介します。合計 (a + b) 個の整数が与えられたとき、「a 個の数で左辺を構成し、残りの b 個の数で右辺を構成する」すべての組み合わせを考え、それぞれの値を計算することで最小値を導き出せます。しかし、全組み合わせを素朴に試すと計算量が膨大になってしまうため、本プログラムでは動的計画法（DP）を用いて効率的に解きます。アルゴリズム処理の流れは以下の擬似コードの通りです。Begin function MinValue() :

この記事では、(x₁ + x₂ + … + xₐ) × (y₁ + y₂ + … + y_b) という形式で表される代数式の最大値を求めるC++プログラムを紹介します。合計 (a + b) 個の整数が与えられたとき、その中から a 個を左辺のグループに、残りの b 個を右辺のグループに割り当てるすべての組み合わせを検討し、それぞれの値を計算することで最大値を導き出します。 全組み合わせを総当たりで調べることも可能ですが、ここでは動的計画法（DP）を活用し、より効率的に解く手法を解説します。 アルゴリズム 開始 関数 MaxValue() : 引数: a[]

この記事では、べき乗剰余（Modular Exponentiation、モジュラーべき乗）アルゴリズムを実装するC++プログラムを紹介します。べき乗剰余とは、(base^exp) % mod のような巨大な数の計算を効率的に求める手法で、暗号理論や競技プログラミングなど幅広い分野で活用されています。アルゴリズムの考え方単純に base を exp 回掛け合わせる方法では、計算量が O(exp) となり、指数が大きい場合は現実的ではありません。そこで「二進べき乗法（バイナリ法）」と呼ばれる手法を使用します。これは指数を2進数として捉え、底を繰り返し二乗しながら、指数の各ビットが1のときだけ結果に

本記事では、指定した長さMのパスワードをN個生成するC++プログラムを紹介します。まず rand() 関数を使ってランダムな数字列を生成し、その後、順列（パーミュテーション）アルゴリズムによって、その数字列のすべての並び替えパターンをパスワード候補として出力します。 アルゴリズム プログラム全体の処理の流れは、以下の擬似コードのとおりです。 開始 　　パスワードの長さを入力として受け取る。 　　関数 permutation() がランダムなパスワードを生成する。 　　/* 引数 　　　 ポインタ配列 a 　　　 乱数の総数 m 　　　 パスワードの長さ s 　　*/ 　　// 関数本体： 　　

本記事では、ランダムに選択された頂点と辺から構成されるランダムグラフをC++で生成するプログラムを紹介します。このプログラムの計算量は O(v×e) です。ここで v は頂点数、e は辺数を表します。 ランダムグラフとは、頂点間の接続が確率的に決定されるグラフのことで、ネットワーク解析やアルゴリズムの性能評価など、さまざまな分野で活用されています。本プログラムでは、rand() 関数を使って辺の両端となる頂点番号をランダムに決定し、自己ループ（同一頂点同士を結ぶ辺）や重複する辺を除外しながら、単純な無向グラフを構築します。 アルゴリズム 開始 　　GenRandomGraphs() 関数を作成

ハミルトン閉路（Hamiltonian Cycle）とは、ハミルトン経路の一種であり、経路の最後の頂点から最初の頂点へ戻る辺がグラフ内に存在するものを指します。無向グラフにおけるハミルトン閉路とは、グラフのすべての頂点をちょうど一度だけ訪問し、最後に起点の頂点へ戻ってくる閉路のことです。使用する関数とその役割Begin 1. 関数 isSafe()：追加しようとする頂点が、直前に追加した 頂点と隣接しており、かつまだ追加されていないことをチェックします。 2. 関数 hamiltonianCycle()：ハミルトン閉路問題を解決します。 3. 関数 ham

本記事では、グラフの辺連結性に関わる「橋（ブリッジ）」を検出するC++プログラムを紹介します。グラフにおける橋とは、その辺を1本取り除くだけでグラフが非連結（切断状態）になってしまう辺のことです。無向グラフから橋を取り除くたびに連結成分の数が増加するため、「グラフを切断するために必要な最小のカット辺を見つける」という問題は、この橋の検出に他なりません。 アルゴリズムの考え方 橋の検出には、DFS（深さ優先探索）をベースとしたタージャン（Tarjan）のアルゴリズムを使用します。各頂点に対して次の2つの値を管理するのがポイントです。 disc[]： DFSでその頂点を発見した時刻 low[]：

有向グラフにおいて、特定の辺を取り除くだけでグラフが非巡回有向グラフ（DAG：Directed Acyclic Graph）に変わるような辺の集合は、「フィードバックアークセット（Feedback Arc Set）」と呼ばれます。本記事では、C++を使ってグラフからこのフィードバックアークセットを見つけるプログラムを紹介します。 フィードバックアークセットとは 有向グラフに閉路（サイクル）が含まれている場合、その閉路を構成する辺をいくつか取り除くことで、グラフをDAGへと変換できます。このとき取り除いた辺の集合がフィードバックアークセットです。スケジューリング問題や依存関係の解析など、循環参照

ハミルトン閉路とは？ ハミルトン閉路（Hamiltonian Cycle）とは、グラフ上のすべての頂点をちょうど一度ずつ通過する閉じた経路のことです。ハミルトン路の終点から始点へ戻る辺がグラフ内に存在するとき、その経路はハミルトン閉路と呼ばれます。本記事では、重み付けのない無向グラフを対象に、バックトラッキング法を用いてハミルトン閉路を検出するC++プログラムを紹介します。 使用する関数とその役割 このプログラムは、次の3つの関数で構成されています。 isSafe()：追加候補の頂点が「直前に追加した頂点と隣接しているか」「すでに経路に含まれていないか」をチェックします。 hamiltoni

強連結成分（SCC）とは 有向グラフにおいて、任意の2つの頂点 u と v の間で「u から v への経路」と「v から u への経路」がどちらも存在するとき、そのグラフは強連結（strongly connected）であるといいます。グラフ全体が強連結でない場合でも、互いに到達し合える頂点同士でグループ化すると、グラフを複数の強連結成分（SCC: Strongly Connected Components）に分解できます。 強連結成分の検出には、DFS（深さ優先探索）を2回実行するコサラジュ（Kosaraju）のアルゴリズムが広く知られています。検出された強連結成分が1つだけであればグラフは