C++

本記事では、線と点の双対変換（Duality Transformation）を示すC++プログラムを紹介します。双対変換とは、平面上の点と直線を互いに対応付ける変換であり、計算幾何学において重要な概念です。この変換には、次の2つの場合が存在します。双対変換の2つのケースケース1： 点 (a, b) を直線 y = ax − b へ変換するケース2： 直線 D（y = cx + d）を点 D’(c, −d) へ変換するこの対応関係により、点に関する問題を直線に関する問題へ（あるいはその逆へ）置き換えて考えることが可能になります。関数と擬似コード関数 LineTransformatio

3点が同一直線上にあるかどうかの判定方法 この記事では、与えられた3点が同一直線上にあるかどうかを判定するC++プログラムを紹介します。判定のポイントは、3点を頂点とする三角形の面積がゼロになるかどうかです。3点が同一直線上に並んでいる場合、三角形はつぶれた形になるため、その面積はゼロになります。 3点 (x1, y1)、(x2, y2)、(x3, y3) からなる三角形の面積は、次の式で計算できます。 0.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) この式は、座標から図形の面積を求める「靴ひも公式(シューレースの公式)」に基づ

N-クイーン問題とは、チェス盤上にN個のクイーンを配置し、どのクイーンも他のクイーンを攻撃できないようにする配置を見つける古典的な組合せ問題です。 チェスのクイーンは、水平・垂直・斜めのあらゆる方向に攻撃できます。そのため、互いに干渉しない配置を見つけるには、単純な全探索ではなく効率的なアルゴリズムが必要になります。 本記事では、0と1からなる二値行列でクイーンの位置を表現し、8クイーン問題を例に、バックトラッキングを用いた解法をC++で実装する方法を解説します。 入力 チェス盤のサイズを指定します。ここでは一般的なチェス盤と同じ8×8を想定しています。 出力 N個のクイーンを配置で

同じテキスト（例えば聖書のような大規模な文書）の中から、指定したパターンを繰り返し検索するC++プログラムを紹介します。このプログラムでは、単純な文字列照合アルゴリズム（力まかせ探索・ナイーブ法）を用いて、パターンが一致するすべての位置を検出し、出現回数をカウントします。 アルゴリズム 開始 検索対象の元の文字列と検索パターンを入力として受け取る org_len ← 元の文字列の長さを格納 pat_len ← パターンの長さを格納 for i = 0 to (org_len - pat_len) for j = 0 to pat_len - 1

これは、有限状態オートマトン(Finite State Automaton)をベースに文字列検索を実行するC++プログラムの解説です。状態の数が有限であるオートマトンは「有限オートマトン(Finite Automaton)」と呼ばれます。ここでは、テキスト text[0 … t-1] とパターン p[0 … p-1] が与えられたとき、テキスト中からパターンを検索し、そのすべての出現位置(インデックス)を出力します。 アルゴリズム まず、与えられたパターンに対して「遷移表(Transition Table)」を構築します。この表は、現在の状態と入力文字の組み合わせに応じて、次に遷移すべき状態

レーベンシュタイン距離（Levenshtein Distance）とは、2つの文字列の間で、一方の文字列をもう一方へ変換するために必要な最小の編集回数を表す指標です。ここでいう編集操作には、1文字の挿入・削除・置換の3つが含まれます。例：「cat」と「mat」のレーベンシュタイン距離は1です。cat → mat（c を m に置換）この記事では、動的計画法を用いてレーベンシュタイン距離を計算するC++プログラムを紹介します。レーベンシュタイン距離は、スペルチェック、DNA配列解析、類似テキスト検索など、幅広い分野で活用されている重要なアルゴリズムです。アルゴリズムの手順開始 文字列を入

シーザー暗号とは シーザー暗号は、平文の各文字を別の文字に置き換えることで暗号文を作り出す「単一換字式暗号（モノアルファベット暗号）」の一種です。換字式暗号の中でも最も基本的でシンプルな方式とされています。 この暗号方式は、一般的に「シフト暗号」とも呼ばれます。その考え方は、各アルファベットを0〜25の範囲内の固定した数だけ「ずらした」別のアルファベットに置き換えるというものです。 この方式では、送信者と受信者があらかじめ「秘密のシフト数」を共有しておきます。この0〜25の間の数値が、暗号化の鍵（キー）として機能します。 特に「3文字ずらす」場合には、このシフト暗号を指して「シーザー暗号」と

Playfair暗号は、単純な単文字置換暗号とは異なり、文字を2文字ずつのペア(ダイグラフ)単位で暗号化する古典暗号の一種です。ペア単位で処理することで単純な頻度分析への耐性が高まり、歴史的にも広く利用されてきました。 Playfair暗号の基本構造 鍵表(キーテーブル)の作成 Playfair暗号では、まず平文を暗号化するための「鍵表」を作成します。鍵表は5×5のアルファベット格子で、25個のマスすべてに異なる文字を配置する必要があります。アルファベットは26文字あるため、1文字(通常はJ)を除外します。平文にJが含まれる場合は、Iに置き換えて処理します。 送信者と受信者は、あらかじ

この方式では、単純な単一文字置換暗号のように1文字ずつではなく、2文字ずつのペア（ダイグラフ）単位で暗号化を行います。 Playfair暗号では、まず「鍵表（キーテーブル）」を作成します。鍵表は5×5のアルファベット格子で、平文を暗号化する際の鍵として機能します。必要なのは26文字ではなく25文字であるため、アルファベットから1文字（通常はJ）を除外し、残りの25文字をすべて重複なく配置します。平文にJが含まれていた場合は、Iに置き換えて処理します。 送信者と受信者は、あらかじめ共通の鍵（ここでは「tutorials」）を取り決めておきます。鍵表には、まず鍵フレーズの文字を重複を除いて左から

RSAは、公開鍵（public key）と秘密鍵（private key）という2つの鍵を使い分ける非対称暗号アルゴリズムです。1977年にRivest、Shamir、Adlemanの3人によって考案され、現在でもSSL/TLSやデジタル署名など、幅広い分野で利用されている代表的な公開鍵暗号方式です。 この記事では、RSAの基本的な仕組みを理解するために、C++でシンプルなRSA暗号を実装する方法を手順とともに解説します。 RSAアルゴリズムの手順 RSAの鍵生成・暗号化・復号化は、以下の手順で行われます。 Begin 1. 2つの素数 p と q を選ぶ。 2. n = p

ヒル暗号（Hill Cipher）は、線形代数を基礎とする多表字換暗号（polygraphic substitution cipher）の一種で、暗号理論における古典的な手法のひとつです。複数の文字をブロックとしてまとめて変換するため、単純な換字暗号よりも高い安全性を持ちます。 暗号化：鍵文字列と平文（メッセージ）をそれぞれ行列形式で表現し、両者を乗算した結果に対して mod 26 を適用することで暗号文を生成します。後から復号を行うためには、鍵行列が逆行列を持つことが前提条件となります。 復号：暗号化に使用した鍵行列の逆行列を暗号文行列に乗算し、mod 26 を計算することで元のメッセージを

ヴィジュネル暗号（Vigenère Cipher）は、アルファベットのテキストを暗号化するための多表式換字暗号の一種です。鍵の各文字に応じて異なる換字表が切り替わる仕組みのため、単純なシーザー暗号などと比べて、頻度分析による解読への耐性が高いという特徴があります。 この方式の暗号化と復号化には「ヴィジュネル暗号表」を使用します。これは、AからZまでのアルファベットを1行ずつ順にずらしながら26行に並べた、26×26の表です。 暗号化の流れ 鍵：WELCOME 平文：Thisistutorialspoint まず、与えられた鍵を平文と同じ長さに達するまで繰り返し、処理用の鍵列を作成します。

アフィン暗号とは？ アフィン暗号（Affine Cipher）は、単一文字置換暗号（モノアルファベティック置換暗号）の一種です。アルファベットの各文字を数値に対応付け、シンプルな数学関数によって暗号化を行い、その結果を再び文字へと変換します。 サイズ m のアルファベットでは、まず各文字を 0 ～ m−1 の範囲の整数にマッピングします。 アフィン暗号の「鍵」は a と b の 2 つの数値から構成されます。このうち a は、m と互いに素（最大公約数が 1）である数を選ぶ必要があります。 暗号化の仕組み 暗号化では、平文の各文字に対応する整数を、合同算術（モジュロ演算）を用いて別の整数へ変換

Kadane（カダネ）のアルゴリズムは、整数配列の中から連続する部分配列の合計が最大になる組み合わせを効率よく見つけるための手法です。本記事では、その基本的な考え方と、C++による実装例、実行結果について詳しく解説します。 Kadaneのアルゴリズムとは 負の数を含む整数配列が与えられたとき、合計値が最大となる連続した部分配列を探す問題は「最大部分配列和問題」と呼ばれます。すべての部分配列を総当たりで調べるとO(n²)〜O(n³)の時間がかかりますが、Kadaneのアルゴリズムを使えばたった1回の走査（O(n)）で答えを求められます。 基本的な考え方はシンプルで、各要素に対して次のどちらか大き

本記事では、複数のシーケンス（文字列）の集合の中から、すべてのシーケンスに共通する最長のサブシーケンス（共通接頭辞）を見つけるC++プログラムについて解説します。この手法は、先頭から順に文字を比較していくことで、共通部分を効率的に抽出できる点が特徴です。アルゴリズムこのプログラムは、2つの文字列間で一致する接頭辞を求める関数と、文字列配列全体にその結果を順次適用していく関数の、2段階構成になっています。開始 文字列の配列を入力として受け取る。 関数 matchedPrefixtill()：文字列 s1 と s2 の間で一致する接頭辞を求める： n1 = 文字列 s1 の長さを格納

本記事では、2つの文字列を部分列（サブシーケンス）として同時に含む、最も短い文字列――すなわち最短共通超列（Shortest Common Supersequence）――を求めるC++プログラムを解説します。この問題は、動的計画法（DP）を活用することで効率的に解くことができます。 最短共通超列とは ある文字列 X が別の文字列 Y の部分列であるとは、Y から一部の文字を取り除いて（文字の順序は保ったまま）X と同じ並びを作れることを意味します。例えば「ACD」は「ABCDE」の部分列です。2つの文字列 A と B の両方を部分列として含む文字列を「超列」と呼び、その中で最も短いものが最

本記事では、複数の文字列が与えられたときに、それらすべてに共通する最長の接頭辞（プレフィックス）を見つけるC++プログラムについて解説します。この手法は、ルーティングテーブルの検索やファイルパスの比較など、さまざまな場面で応用される基本的なアルゴリズムです。 アルゴリズムの考え方 基本的なアプローチはシンプルです。まず最初の文字列を仮の共通接頭辞とし、残りの文字列と順番に照合していきます。照合のたびに共通部分だけを取り出していくことで、最終的にすべての文字列に共通する最長の接頭辞が得られます。 手順1：2つの文字列間の一致する接頭辞を求める（matchedPrefixtill） Begin

本記事では、与えられた文字列を「すべての部分文字列が回文(前から読んでも後ろから読んでも同じになる文字列)」となるように分割する方法をすべて列挙するC++プログラムを紹介します。たとえば「tutorials」という文字列なら、1文字ずつに分割する方法や、先頭の「tut」をひとまとまりにして残りを1文字ずつにする方法などが該当します。 アルゴリズム 処理の基本的な流れは次のとおりです。 Begin 文字列を入力として受け取る。 関数 partitionadd(vector<vector<string>> &u, string &s, vec

本記事では、C++を使ってTrie（トライ木）を実装する方法を詳しく解説します。Trieは木構造ベースのデータ構造で、大量の文字列データセットの中から特定のキーを効率的に検索・取得するために利用されます。 Trieとはどのようなデータ構造か Trieは「プレフィックス木（接頭辞木）」とも呼ばれ、文字列を1文字ずつ枝分かれさせながら格納する木構造です。根からあるノードまでの経路が、1つの文字列の接頭辞に対応します。本記事の実装では英大文字（A〜Z）のみを扱うため、各ノードは最大26個の子ポインタを持ちます。辞書検索やオートコンプリート機能など、文字列を高速に処理したい場面で広く活用されています。

C言語では、標準ライブラリとして提供されている qsort() 関数を使うことで、クイックソートのアルゴリズムによる配列の並べ替えを簡単に行うことができます。この関数を利用する際には、要素同士の大小関係を判定するための「コンパレータ（比較）関数」を自分で定義して渡す必要があります。コンパレータ関数とはコンパレータ関数は、ソート対象となる2つの要素を受け取り、それらの相対的な順序を返す役割を持つ関数です。引数はいずれもポインタ型で、const void* にキャストして受け取るのが特徴です。基本的な構文は以下の通りです。int comparator(const void* p1, const v