C++

挿入ソートは、トランプの手札を並べ替えるときの動きに似ているソートアルゴリズムです。カードを整理するときと同じように、データセットから1つの要素を取り出し、その要素を挿入できる適切な位置を作るために他の要素をずらしてから、元の位置に戻すという手順を繰り返します。挿入ソートの計算量時間計算量：最良ケースは O(n)、平均ケースおよび最悪ケースは O(n²)空間計算量：O(1)入力 − ソート前のリスト：9 45 23 71 80 55 出力 − ソート後の配列：9 23 45 55 71 80アルゴリズムinsertionSort(array, size)入力：データの配列と、配列内の要素の総数

シェルソート（Shell Sort）は、挿入ソートを改良した整列アルゴリズムです。通常の挿入ソートでは、要素を正しい位置に挿入するために大量のデータをまとめてシフト（移動）する必要がある場合があります。シェルソートでは、あらかじめ一定の間隔（ギャップ）ごとに離れた要素同士を比較・交換することで、大規模なシフト処理を大幅に減らすことができます。整列は特定の間隔で行われ、各パスが終了するたびにギャップを半分に縮小していき、最終的にギャップが1になれば完全に整列された状態になります。シェルソートの計算量時間計算量：最良ケースは O(n log n)。その他のケースでは、採用するギャップ列（間隔の選び

カウントソートとは カウントソート（計数ソート）は安定なソート手法の一つで、小さな整数値をキーとするデータを並べ替えるために用いられるアルゴリズムです。キー値が同じ要素の個数を数え、その情報をもとに整列を行うのが大きな特徴です。キー同士の差（値の範囲）がそれほど大きくなければ非常に高い効率を発揮しますが、範囲が広すぎる場合は空間計算量が増大する点に注意が必要です。 カウントソートの計算量 時間計算量：O(n+r) 空間計算量：O(n+r) ※ n は要素数、r はキーの最大値（値の範囲）を表します。 入力： ソートされていないデータ列： 2 5 6 2 3 10 3 6 7 8出力： ソー

補間探索とは二分探索では、リストを毎回等しい大きさの部分に分割しながら探索ら探索範囲を絞り込んでいきます。一方、補間探索では補間公式を使い、キーが存在すると推定されるおおよその位置を直接計算で求めます。推定位置が判明したら、その位置を基準にリストを分割して探索を進めます。毎回キーの正確な位置に近づこうとするため、探索にかかる時間を大幅に短縮できます。この手法は、データがソート済みであり、かつ値ができるだけ一様に分布している場合に特に高い効果を発揮します。キーの推定位置は次の式で求められます。estimate = start + ((key - array[start]) / (array[en

グラフの連結性チェックの基本概念 グラフが連結しているかどうかを調べるには、何らかの探索アルゴリズムを用いてすべてのノードを巡回してみます。探索が完了した時点で、まだ一度も訪問されていないノードが残っていれば、そのグラフは連結ではないと判断できます。 有向グラフの場合のポイント 無向グラフと異なり、有向グラフの場合はすべてのノードを起点として探索を行う必要があります。理由は、あるエッジが外向きの辺しか持たず、内向きの辺を持たないケースが存在するためです。そのようなノードは、他のどのノードを出発点としても到達できない可能性があります。 本記事では、探索アルゴリズムとして再帰的なDFS（深さ優先

有向グラフにおいて、ある成分内の任意の頂点ペア同士の間に経路が存在するとき、その成分は「強く接続されている（強連結）」といいます。このような成分のことを強連結成分（SCC: Strongly Connected Components）と呼びます。この問題を解くには、まずDFS（深さ優先探索）を使って各頂点の完了時刻（finish time）を求めます。次にグラフを転置し、完了時刻をもとに頂点を降順に並べる（トポロジカルソート）ことで、強連結成分を一つずつ取り出します。これは有名なKosarajuのアルゴリズムに基づいた手法です。入力： グラフの隣接行列001101000001000000010

オイラー閉路（オイラー回路）とは、グラフ上のすべての辺をちょうど1回ずつ通過できる経路のことです。このとき、同じ頂点を何度通っても構いません。オイラー閉路はオイラー路（Euler Path）の特別な形であり、オイラー路の始点がそのまま終点ともつながっている場合を指します。 ある有向グラフがオイラー閉路を持つかどうかを判定するには、次の2つの条件を満たしている必要があります。 グラフが連結であること（任意の頂点から他のすべての頂点へ到達できること）。 すべての頂点において、入次数と出次数が等しいこと。 入力 − グラフの隣接行列 01000 00100 00011 10000 0010

本記事では、一風変わったトリッキーな解法を紹介します。それはセミコロンを一切使わずに、1からNまでの数字を出力するC言語プログラムです。この問題は主に2つのアプローチで解くことができます。1つ目は反復処理（ループ）を使う方法、2つ目は再帰呼び出しを使う方法です。方法1：while文を使った反復処理printf()関数は、出力した文字列の長さ（文字数）を戻り値として返します。正常に出力された場合、この値は0以外（真）になります。この性質を利用し、論理AND演算子（&&）と組み合わせることで、条件判定と出力を同時に実行できます。その後、カウンタの値をインクリメントします。サンプルコ

線形合同法（LCG）とは線形合同法（Linear Congruential Generator：LCG）は、乱数生成器のごく単純な例であり、最も古くから知られている疑似乱数生成アルゴリズムの一つです。この手法では、次の漸化式を用いて疑似乱数列を生成します。Xn+1 = (aXn + C) mod mここで X は生成される疑似乱数の列を表し、以下の整数定数によって生成器の特性が決まります。m, 0 < m …… 「法（モジュラス）」 a, 0 < a < m …… 「乗数」 c, 0 < c < m …… 「増分」 X0, 0 < X0 < m ……

この記事では、複数のステートメントを書かずに、数値の各桁の合計を求める方法を解説します。つまり、わずか1つのステートメントだけで桁の合計を計算するテクニックです。基本的な考え方桁の合計を求める一般的な手順はご存じのとおりです。まず、数値を10で割った余りを取ることで最下位の桁（一の位）を取り出し、次にその数値を10で割って、これを数値が0になるまで繰り返します。この処理を1つのステートメントで実現するには、forループを活用します。forループには3つのセクションがあります。初期化フェーズ：このケースでは何もしません（空のままにします）条件判定フェーズ：数値が0より大きいかどうかをチェックしま

ミドルスクエア法とはミドルスクエア法(中央二乗法)は、乱数を生成する最も単純な手法の一つです。「現在の数値を2乗し、その中央の桁を取り出す」という操作を繰り返すことで次々と乱数を作り出します。この手法は計算機科学の父として知られるジョン・フォン・ノイマンによって考案され、初期のコンピュータ時代に擬似乱数生成の方法として使われていました。基本的な仕組み例えば4桁の乱数を生成する場合、「1234」を2乗すると 1522756 となります。桁数を揃えるため先頭に0を付けて8桁の「01522756」にし、中央の4桁である「5227」を次の乱数として採用します。この操作を繰り返すことで乱数列が得られます

確率密度関数（PDF）とは確率密度関数（Probability Density Function：pdf）とは、ある確率変数が特定の値をとる相対的な尤度（もっともらしさ）を表す関数です。連続型確率変数の「密度」とも呼ばれます。確率変数がある値の範囲内に収まる確率は、その範囲における密度関数の積分によって求められます。これは図形的には、横軸より上・密度関数より下・範囲の最小値から最大値までの領域の面積に相当します。確率分布は、この確率密度関数をもとに構成されます。アルゴリズム開始 変数 n を宣言する pdf = 0 を代入する i = 0 から n まで繰り返す：

Park-Miller乱数生成アルゴリズムは、擬似乱数列を生成する古典的な手法の一つです。乗算と剰余演算のみを用いて乱数を生成できるシンプルな構造が特徴で、1988年にStephen ParkとKeith Millerによって発表されたことから「Lehmer型乱数生成器」としても知られています。 Park-Millerアルゴリズムの基本式 このタイプの乱数生成器(RNG)の一般式は次のように表されます。 Xk+1 = g × X(k) mod n この式が正しく機能するためには、各パラメータが以下の条件を満たす必要があります。 法(modulus)n:素数、または素数のべき乗であるこ

Naor-Reingold擬似ランダム関数は、乱数を生成するためのもう一つの強力な手法です。本記事では、その数学的な背景とアルゴリズムを解説し、実際にC++で実装する方法を紹介します。 Naor-Reingold擬似ランダム関数とは 1997年、Moni Naor（モニ・ナオール）とOmer Reingold（オメル・ラインゴールド）は、共通鍵暗号および公開鍵暗号の両分野において、さまざまな暗号プリミティブの効率的な構成方法を提唱しました。 p と l を素数とし、l | p−1（つまり l が p−1 を割り切る）であるとします。さらに、乗法位数が l である元 g ∈ Fp* を選択しま

キャリー付き乗算法（MWC法）とはキャリー付き乗算法（Multiply-With-Carry、略称MWC法）は、1991年にMarsagliaとZamanによって提案されたキャリー付き加算法（Add-With-Carry）ジェネレータの変種です。この手法の最大の利点は、コンピュータが最も得意とする単純な整数演算だけで動作するため、非常に高速に乱数列を生成できる点にあります。さらに、生成される乱数列の周期は約260から22000000にまで及ぶ、きわめて長い周期を持つことも大きな特徴です。MWC法では、基数bはコンピュータのワードサイズと一致するように選ばれ、乗数aとラグr（遅延量）によって法p

本記事では、N個のサイコロを振る動作（Nダイスローラー）をエミュレートするC++プログラムを紹介します。サイコロの目は、1から6までの範囲の乱数を生成することで再現できます。アルゴリズムBegin Declare n Read n For i = 0 to n-1 do Generate sequence with rand() mod 6 + 1 Print the sequence Done Endサンプルコード#include <iostream> #include <cstdlib> using n

ホイールふるい（Wheel Sieve）法は、指定された範囲内の素数を見つけるために用いられる手法です。ホイール因数分解（Wheel Factorization）は、エラトステネスのふるいの前処理を手作業で行うための図式的な方法であり、素数と合成数を効率的に分離します。 この手法では、最も内側の円に配置された素数は、外側の各円の同じ相対位置にその倍数を持つことになります。その結果、素数とその倍数が車輪のスポークのように放射状に並びます。内側の円にある素数の倍数は、外側の円において合成数のスポークを形成するのです。 アルゴリズム 開始 最大値（max number）を定義する

本記事では、エラトステネスのふるい（Sieve of Eratosthenes）を実装し、指定された範囲内の素数を生成するC++プログラムを紹介します。エラトステネスのふるいとはエラトステネスのふるいは、古代ギリシャの数学者エラトステネスによって考案された、素数を効率的に求めるための古典的なアルゴリズムです。ある範囲内のすべての素数を見つけたい場合に特に有効な手法として知られています。この手法では、まずすべての要素を0で初期化した整数型の配列を用意します。続いて、ネストされた二重ループの中で、素数ではない数（合成数）に対応するインデックスを1としてマークしていきます。そして最後に、インデックス

なぜeof()によるループ制御が問題なのか ストリームのeof()をループ条件に使うことが好ましくない最大の理由は、「まだEOFに達していない」という状態は「次の読み込みが必ず成功する」ことを意味しないからです。 C++でfstream（ファイルストリーム）を使ってファイルを読み込む際、while文の中でstream.eof()によって終端を判定すると、実際には「ファイルの末尾に到達したかどうか」を確認しているだけにすぎません。 eof()のフラグは、実際にEOFを超えて読み込みを試みた後でなければセットされません。つまり、最後のデータを読み終えた直後の時点ではeof()はまだfalseのま

Linuxプラットフォームには、C++プログラムのパフォーマンスを分析するための優れたプロファイリングツールが数多く存在します。その中でも特に広く使われているのがValgrindです。Valgrindはメモリデバッグ、メモリリーク検出、プロファイリングを目的としたプログラミングツールで、バイナリを渡してツールをcallgrindに設定するだけで利用できます。 Valgrind（Callgrind）を使ったプロファイリング 1. プログラムのコンパイル まず、デバッグ情報を含めてプログラムをコンパイルし、実行可能なバイナリを生成します。 $ g++ -o abc abc.cpp -g 2.