C++

無向グラフが「弱連結（weakly connected）」か「強連結（strongly connected）」かを判定するには、DFS（深さ優先探索）を利用できます。この記事では、グラフの連結成分を見つけ出し、その連結状態を判定するC++プログラムを紹介します。 この実装は「コサラジュ（Kosaraju）のアルゴリズム」と呼ばれる手法に基づいています。まず1回目のDFSで各頂点の探索完了順をスタックに記録し、続いてすべての辺の向きを反転させた「転置グラフ」を作成します。その後、スタックから頂点を取り出す順に2回目のDFSを実行することで、強連結成分を効率的に抽出できます。 アルゴリズムで使用す

本記事では、グラフの最大カットを求める問題に関連して、グラフの辺連結性を調べるC++プログラムを紹介します。ここで扱うのは「橋（ブリッジ）」と呼ばれる特別な辺の検出です。 橋（ブリッジ）とは何か？ 無向グラフにおける橋（ブリッジ）とは、その辺を取り除いた瞬間にグラフが非連結になってしまう辺のことです。言い換えれば、橋を1本取り除くだけで、グラフの連結成分の数が増加します。この性質を利用すると、ネットワークの中で特に脆弱な箇所（切断されやすいリンク）を特定できます。 アルゴリズムの考え方と擬似コード 橋の検出には、深さ優先探索（DFS）を用いるのが定番です。各頂点に対して「発見時刻（dis）」と

グラフの頂点連結性を調べるには、そのグラフの関節点を特定する必要があります。関節点とは、その頂点（およびそれに接続する辺）を取り除くとグラフが分断されてしまう頂点のことです。非連結な無向グラフの場合、ある頂点を削除したときに連結成分の数が増加するならば、その頂点は関節点であるとみなされます。アルゴリズムここではDFS（深さ優先探索）を用いて関節点を検出します。DFSにおいて、頂点wが次のいずれかの条件を満たすとき、wは関節点となります。wがDFS木の根であり、かつ2つ以上の子を持つ。wがDFS木の根ではなく、子xを持ち、wを根とする部分木内のどの頂点からも、木におけるwの祖先への後退辺が存在し

C++には、あらかじめ用意されている乱数生成関数 rand() があります。この関数は <stdlib.h>（C++では <cstdlib>）ヘッダーファイルで宣言されており、指定した範囲内の乱数を生成するために使用されます。ここで、min_n は乱数の最小値（下限）、max_n は最大値（上限）を表します。次の式を使うことで、min_n 以上 max_n 以下のランダムな整数を取得できます。((rand() % (max_n + 1 - min_n)) + min_n)例えば、下限と上限をそれぞれ 1 と 100 に設定した場合、この式は 1 から 100 までの範囲

C++には、指定した範囲内の乱数を取得できるrand()関数が標準で用意されています。本記事では、このrand()と、整数を任意の基数の文字列に変換できるitoa()関数を組み合わせて、「ランダムな16進数（Hex Byte）」を生成するプログラムを作成します。まずは使用する2つの関数の概要から確認していきましょう。 rand()関数とは rand()は<stdlib.h>ヘッダーで宣言されている事前定義済みの関数で、擬似乱数（整数）を生成します。単体では0以上RAND_MAX以下の値を返すため、実際には次のように剰余演算と組み合わせて、目的の範囲に収まる乱数を作ります。 new_

ソロベイ・シュトラッassen素数性テストとは ソロベイ・シュトラッassen（Solovay–Strassen）素数性テストは、ある数が合成数か、それともおそらく素数であるかを判定するための確率的アルゴリズムです。オイラーの規準とヤコビ記号を利用しており、ランダムな試行を複数回繰り返すことで、誤判定の確率を極めて低く抑えられるのが特徴です。 オイラーの規準によれば、p が素数である場合、任意の整数 a に対して次の関係が成り立ちます。 a(p−1)/2 ≡ (a/p) (mod p) ここで (a/p) はヤコビ記号です。この等式が成立しない数を見つけられれば、その数は確実に合成数だと判断で

```html Baillie-PSW素数判定テストは、Robert Baillie、Carl Pomerance、John Selfridge、Samuel Wagstaffという4人の数学者にちなんで名付けられた素数判定法です。このテストは、与えられた数が合成数であるか、それともおそらく素数であるかを判定します。Baillie-PSWテストの特徴Baillie-PSWテストは、ミラー・ラビン素数判定法と強いルーカス疑似素数判定を組み合わせた手法として知られています。現在までに、このテストが誤って素数と判定してしまう合成数（反例）は一つも発見されていません。そのため、暗号鍵の生成など、大きな

この記事では、C++におけるプライベート静的メンバー変数（private static member）の初期化方法について解説します。C++のクラスには、静的なメンバー関数やメンバー変数を持たせることができます。ただし、静的メンバー変数はクラス定義だけでは実体が確保されないため、クラス定義の外で明示的に初期化する必要があります。静的メンバー変数の初期化方法静的メンバー変数を初期化する際は、次の構文を使用します。データ型 クラス名::変数名 = 初期値;ポイントは以下の通りです。まずクラス名を記述する続けてスコープ解決演算子（::）を付けるその後に変数名を書き、値を代入するこのようにして、クラス

C++のコードを読んでいると、メンバ関数の宣言や定義の最後に「const」キーワードが付けられていることがあります。これはいったい何を意味するのでしょうか？ 関数宣言の末尾に「const」を付けると、その関数は定数メンバ関数（constメンバ関数）として定義されます。定数メンバ関数とは、呼び出し元のオブジェクトの状態（メンバ変数）を変更できない関数のことです。つまり、関数内でメンバ変数への代入や変更を行うとコンパイルエラーになります。 オブジェクトの状態を変更しない参照専用の関数には、積極的にconstを付けることが推奨されています。これにより、コードの意図が明確になり、コンパイラによる誤用の

はじめにC++には、1文字を扱うためのchar型というデータ型があります。その中でも「unsigned char」という型を目にすることがあります。本記事では、unsigned charが何を意味するのか、そしてsigned charとの基本的な違いについて詳しく解説します。char型とASCII値の関係signed charもunsigned charも、どちらも1つの文字を格納するために使用されます。変数には実際には文字のASCIIコード（数値）が保存されます。例えば、「A」を格納した場合、内部的には65という数値が保持される仕組みです。signed charの場合はsignedキーワード

static_castとは static_castは、通常の型変換に使用されるキャストです。コンパイラが行う暗黙の型変換（implicit type coercion）も担当しており、明示的に記述することも可能です。floatからint、charからintへの変換のように、基本的な数値型同士の変換に適しています。また、継承関係にあるクラス間のポインタ変換にも利用できます。ただし、互換性のない型同士の変換を試みると、コンパイル時にエラーが発生します。 コード例 #include<iostream> using namespace std; class Base {}; class

はじめにこの記事では、C/C++においてループ(for文、while文など)や条件分岐(if文など)を一切使わずに、1から1000までの数値を表示する方法を解説します。ループが使えないとなると、真っ先に思いつくのは再帰関数ですが、この問題では条件文も禁止されているため、再帰の終了条件(ベースケース)を設けることができません。そこで、まったく異なるアプローチが必要になります。解決策：静的メンバーとコンストラクタを活用するここでは、クラスの静的メンバー変数(staticメンバー)とコンストラクタを組み合わせることで、この問題をエレガントに解決します。基本的な仕組みは以下の通りです。静的メンバー変数

はじめに C++には、あらかじめ定義された「定義済みマクロ」が複数用意されており、ソースファイル名・行番号・関数名といった情報をプログラムの中で手軽に取得できます。これらを活用すれば、エラーログの出力やデバッグ作業がぐっと効率的になります。本記事では、代表的な3つのマクロである __FILE__、__LINE__、__FUNCTION__ の使い方を、実際のコード例とともに解説します。 __FILE__：現在のファイルパスを取得する __FILE__ は、コンパイル中のソースファイルのパスを文字列リテラルとして展開するマクロです。「どのファイルでエラーが発生したのか」をログに記録したい場合に

C++には、オブジェクトの生成時に自動的に呼び出される特別なメンバ関数「コンストラクタ」が存在します。本記事では、その中でも特に重要な「変換コンストラクタ（Converting Constructor）」について、その定義・動作原理・具体的なコード例を交えて詳しく解説します。 変換コンストラクタとは まず、コンストラクタの基本をおさらいしましょう。コンストラクタはクラスの特殊な関数であり、以下のような特徴を持っています。 関数名がクラス名と同一である 戻り値を持たない（voidですら明示しない） オブジェクト生成時に自動的に呼び出される コンストラクタは引数を受け取ることもあれば、受け取ら

この記事では、CやC++におけるリエントラント関数（再入可能関数）について詳しく解説します。ある関数が実行中に割り込みを受け付け、ISR（Interrupt Service Routine：割り込みサービスルーチン）の処理を完了した後、中断したタスクを安全に再開できる場合、その関数はリエントラント関数と呼ばれます。この種の関数は、再帰処理やハードウェア割り込みハンドリングなど、さまざまな場面で活用されています。リエントラント関数が満たすべき条件関数がリエントラントであるためには、以下の性質を備えている必要があります。グローバル変数や静的変数を使用しない：使用すること自体に言語上の制限はありませ

C++プログラミングでは、現在実行中の関数名を取得するために__FUNCTION__、__func__、__PRETTY_FUNCTION__という3つのマクロ（定義済み識別子）を利用できます。一見よく似ていますが、それぞれ標準規格への準拠状況や返す情報の詳細さに違いがあります。 __func__と__FUNCTION__の違い 基本的に、__FUNCTION__と__func__は同じ働きをし、どちらも「現在の関数名」を文字列として返します。 __func__はC99およびC++11で標準規格に採用された定義済み変数で、移植性が高いのが特徴です。一部の古いバージョンのC/C++コンパイラでは

本記事では、C++におけるvolatile修飾子の意味と役割について詳しく解説します。volatileは変数を宣言する際に指定する修飾子で、「この変数の値はいつでも変更される可能性がある」ことをコンパイラに伝えるために使用されます。volatileキーワードの主な特徴volatileが付与された変数には、以下のような重要な特性があります。コンパイラによる最適化であっても、メモリへの割り当てを削除できない変数をCPUレジスタにキャッシュできない代入処理の順序を勝手に入れ替えることができないつまり、volatileを指定すると、コンパイラはその変数に対する過度な最適化を行わなくなり、常に実際のメモ

シングルトンデザインパターンとは、クラスのインスタンス化を1つのオブジェクトのみに制限するためのソフトウェア設計原則です。システム全体の動作を調整するオブジェクトが1つだけ必要な場面で特に有効です。 代表的な使用例として、ファイルにログを出力するロガーが挙げられます。シングルトンクラスを利用すれば、アプリケーション全体で単一のロガーインスタンスを共有でき、ログの出力先が分散することを防げます。 以下に、C++でシングルトンクラスを実装する基本的なコード例を示します。 実装例 #include <iostream> using namespace std; class Singlet

C/C++における int と const int& の違いとは？ この記事では、C言語およびC++における int と const int& の違いについて、具体例を交えながら詳しく解説します。 int 型の基本 int は、整数型データを表す最も基本的なデータ型です。宣言された変数には整数値を格納でき、プログラム内で自由に読み書きすることができます。 int x = 10; x = 20; // 問題なく変更可能 const int&（定数参照）とは const は、対象を定数として扱うための修飾子です。const int& は「定数整数への参照」を意味し、int const& と完

cin.ignore() は、入力バッファから1つ以上の文字を無視（読み捨て）したり、バッファをクリアしたりするために使われる関数です。 ignore() の動作を理解するには、実際に起こりうる問題とその解決策を見るのが一番早いでしょう。以下に典型例を示します。 入力バッファのクリアが必要な理由 プログラムでは、不要になった入力バッファを事前にクリアしておきたい場面があります。こうすることで、次に入力されたデータが目的の変数へ正しく格納され、以前の変数のバッファに混入することを防げます。 たとえば、cin で整数を読み込んだ直後に、文字配列や文字列を入力したいケースを考えてみます。ここで入力バ