C++

二分探索（バイナリサーチ）とは二分探索（Binary Search）は、ソート済みの配列から目的の要素を効率的に見つけ出すアルゴリズムです。探索範囲を繰り返し半分に絞り込んでいくことで、先頭から順に調べる線形探索よりもはるかに高速に検索できます。具体的な手順は以下の通りです。まず配列全体を探索対象とする配列の中央にある要素と目的の値を比較する目的の値が中央の要素より大きければ上半分を、小さければ下半分を次の探索範囲とする目的の値が見つかるか、探索範囲が空になるまで手順2〜3を繰り返すこの手法により計算量は O(log n) に抑えられ、大量のデータでも高速に探索できます。C++による二分探索の

ソート済み配列とは、数値順やアルファベット順など、何らかの基準に従ってすべての要素が整列された配列のことです。配列をソートするためのアルゴリズムには、バブルソート、挿入ソート、選択ソート、マージソート、クイックソート、ヒープソートなど、さまざまな種類があります。本記事では、その中でも「選択ソート」を使って配列をソートする方法について、サンプルコードを交えながら詳しく解説します。選択ソートとは選択ソートは、未ソート部分の中から最小の要素を繰り返し見つけ出し、それを未ソート部分の先頭にある要素と入れ替えることで、徐々にソート済み配列を作り上げていく手法です。実装がシンプルで理解しやすいことが特徴で

スパース行列とは？スパース行列（疎行列）とは、行列を構成する要素の大部分が「0」である行列のことです。画像処理、機械学習、グラフ理論などの分野では、大規模なデータの多くが0で占められるケースが珍しくなく、そうした行列を効率的に扱うためにスパース行列という概念が重要となります。例として、次の3×3の行列を見てみましょう。この行列には0が5個含まれています。全要素数は9個なので、0の数が半分を超えており、この行列はスパース行列であると言えます。5 0 0 3 0 1 0 0 9ここからは、与えられた行列がスパース行列かどうかを判定するC++プログラムを紹介します。スパース行列を判定するC++プログ

単方向リンクリスト（Singly Linked List）は、自己参照構造体を使って作成されたノード群から構成されるデータ構造の一種です。各ノードは「データ」と「次のノードへの参照（ポインタ）」という2つの要素で構成されています。リンクリスト全体へアクセスするために必要なのは、先頭ノードへの参照のみです。この先頭ノードは「ヘッド（head）」と呼ばれます。また、リストの末尾のノードは次のノードを持たないため、参照部分にはNULLが格納されます。ここでは、C++で単方向リンクリストを実装するサンプルプログラムを紹介します。サンプルコード#include <iostream> usin

循環単方向リンクリスト(Circular Singly Linked List)は、自己参照構造体を用いて作成されたノードから構成されるデータ構造の一種です。各ノードは「データ」と「次のノードへの参照(ポインタ)」という2つの部分で構成されています。リンクリスト全体へアクセスするには、先頭ノードへの参照だけがあれば十分です。この先頭ノードは「ヘッド(head)」と呼ばれます。そして、リストの最後のノードは先頭ノード(ヘッド)を指します。このようにリストが輪のように閉じていることから、「循環リンクリスト」と呼ばれています。以下に、循環単方向リンクリストを実装するC++プログラムの例を示します。サ

双方向リンクリスト（Doubly Linked List）とは双方向リンクリストは、自己参照構造体を用いて作成されたノードから構成されるデータ構造の一種です。各ノードは「データ」「次のノードへのポインタ」「前のノードへのポインタ」という3つの要素を持っています。リンクリスト全体へアクセスするには、先頭ノードへの参照が1つあれば十分です。この先頭ノードは「ヘッド（head）」と呼ばれます。リストの末尾ノードは次のノードを持たないため、nextポインタにはNULLが格納されます。また、各ノードが前後両方のノードを指しているため、双方向リンクリストは前方向にも後方向にも走査（トラバース）できるのが大

スタック（Stack）は、要素の集合を管理するための抽象データ構造の一つです。最大の特徴はLIFO（Last In, First Out：後入れ先出し）方式を採用している点で、最後に追加された要素ほど最初に取り出されます。本記事では、C++の配列を使ってスタックを実装する方法を、完全なサンプルコードとともにわかりやすく解説します。スタックの主な操作スタックに対して行える基本的な操作には、次の3つがあります。Push（プッシュ） … スタックの頂上（トップ）に新しいデータを追加するPop（ポップ） … スタックのトップからデータを取り除くPeek（ピーク） … スタックのトップにあるデータを参照

スタック（Stack）は、要素の集合を管理するための抽象データ構造の一つです。スタックはLIFO（Last In First Out：後入れ先出し）という仕組みに基づいて動作し、最後に追加した要素が最初に取り出されます。スタックにおける主な操作は以下の通りです。 Push（プッシュ）：スタックの先頭にデータ値を追加します。 Pop（ポップ）：スタックの先頭にあるデータ値を削除します。 Peek（ピーク）：スタックの先頭にあるデータ値を参照します（削除は行いません）。 本記事では、連結リスト（リンクリスト）を使用してスタックを実装するC++プログラムを紹介し、その動作の仕組みを詳しく解説しま

C++ STLのacos()関数とはacos()関数は、ラジアン単位で与えられた値に対する逆余弦（アークコサイン）を返す関数で、C++のSTLに標準で組み込まれています。この関数は<cmath>ヘッダで定義されています。acos()関数の構文acos(var)構文から分かるように、acos()関数はfloat、double、long doubleのいずれかのデータ型を持つ引数varを1つ受け取ります。引数の値は-1から1の範囲内でなければなりません。範囲外の値を渡した場合はNaN（非数）が返される点に注意が必要です。戻り値は、-πからπの範囲におけるvarの逆余弦（ラジアン単位）で

atan2()関数は、座標yとxから逆正接（アークタンジェント）を求めるための関数です。ここでいうyとxは、それぞれy座標とx座標の値を指します。atan2()はC++のSTL（標準テンプレートライブラリ）に組み込まれている関数で、<cmath>ヘッダをインクルードすることで利用できます。通常のatan()関数と異なり、atan2()はxの符号も考慮して正しい象限の角度を返すため、実務でも広く使われています。atan2()関数の構文atan2(dataType var1, dataType var2)構文を見ると分かるように、atan2()関数はfloat型、double型、lon

キューとは？FIFO方式の基本キュー（Queue）とは、複数の要素を格納する抽象的なデータ構造です。キューはFIFO（First In First Out：先入れ先出し）方式を採用しており、最初に挿入された要素が最初に取り出されます。言い換えれば、最も古く追加された要素から順に削除されていくのがキューの大きな特徴です。日常の行列（待ち列）と同じ動きをするイメージを持つと分かりやすいでしょう。ここでは、配列を使用してキューを実装するC++プログラムを紹介します。C++によるキュー実装の完全なコード例次のプログラムは、配列をベースにキューの「挿入」「削除」「表示」を行うメニュー形式のコンソールアプ

キュー（queue）とは、複数の要素を格納するための抽象データ構造のひとつです。キューは「FIFO（First In First Out：先入れ先出し）」と呼ばれる仕組みに基づいて動作し、最初に挿入された要素が最初に削除されます。言い換えれば、キューの中では最も早く追加された要素から順に取り除かれることになります。ここでは、連結リスト（リンクリスト）を用いてキューを実装するC++プログラムを紹介します。サンプルプログラム#include <iostream> using namespace std; struct node { int data; struct no

1つの変数を含む一次方程式とは 1つの変数を含む任意の一次方程式（線形方程式）は、次のような形式で表すことができます。 aX + b = cX + d ここでの目的は、a、b、c、d の値が与えられたときに、変数 X の値を求めることです。 X の求め方 方程式を変形すると、X の値は次の公式で求められます。 aX − cX = d − bX(a − c) = d − bX = (d − b) / (a − c) 一次方程式を解くC++プログラム 以下に、1つの変数を含む一次方程式を解くC++プログラムを示します。 例 #include<iostream> using names

複素数とは、a+bi の形式で表される数のことです。ここで、i は虚数単位、a と b は実数を表します。複素数の例をいくつか挙げます。2+3i 5+9i 4+2i2つの複素数の積は、次の公式で求められます。(x1 + y1i) × (x2 + y2i) = (x1×x2 − y1×y2) + (x1×y2 + y1×x2)iこの公式を用いて、複素数の乗算を実行するC++プログラムは以下の通りです。サンプルコード#include<iostream> using namespace std; int main(){ int x1, y1, x2, y2, x3, y3;

2つの数の最大公約数（GCD：Greatest Common Divisor）とは、その両方を割り切ることができる最大の数のことです。例として、63と21という2つの数を考えてみましょう。63 = 7 × 3 × 3 21 = 7 × 3この場合、63と21に共通する因数は7と3なので、GCDは次のようになります。GCD = 7 × 3 = 21再帰的ユークリッドの互除法とは再帰的ユークリッドの互除法では、正の整数aとbのペアを受け取り、「b」と「a % b（aをbで割った余り）」を引数として自分自身を再帰的に呼び出し、bが0になった時点でaを返すことでGCDを求めます。このアルゴリズムを使っ

Fisher-Yatesアルゴリズムは、配列の要素に対してランダムな順列を生成するアルゴリズムです。すなわち、配列内の全要素をランダムにシャッフルします。このアルゴリズムは偏り（バイアス）を持たないため、考えられるすべての順列が等しい確率で現れるという特徴があります。 以下は、C++でFisher-Yatesアルゴリズムを実装し、配列をシャッフルするプログラム例です。 C++での実装例 #include <iostream> #include <cstdlib> using namespace std; int main() {    int n;

行列のLU分解とは、ある行列を下三角行列（L）と上三角行列（U）の積として表現する手法です。名前の「LU」は「Lower（下三角）」「Upper（上三角）」の頭文字に由来しています。LU分解は、連立一次方程式の求解や逆行列の計算など、数値計算の分野で広く活用されている重要なアルゴリズムです。LU分解の例以下に、3×3の行列をLU分解した具体例を示します。元の行列 A： 1 1 0 2 1 3 3 1 1 下三角行列 L： 1 0 0 2 -1 0 3 -2 -5 上三角行列 U： 1 1 0 0 1 -3 0 0 1このとき、L × U = A が成立します。この分解を実際に行うC++プロ

2進数と8進数とは コンピュータシステムでは、2進数は二進法(基数2)で表現され、8進数は八進法(基数8)で表現されます。つまり、2進数は「0」と「1」のみを使う記数法であり、8進数は「0」から「7」までの数字を使う記数法です。 2進数と、それに対応する8進数の例は以下の表の通りです。 2進数8進数 0101012 001117 1100131 1000020 例えば2進数「1011」は、各桁に2の累乗(8+0+2+1)を掛けて足し合わせると10進数の「11」となり、さらにこれを8進数に直すと「13」になります。このような変換を行うC++プログラムを以下に示します。 サンプルプログ

コンピュータシステムにおいて、2進数は2を基数とする記数法（二進法）で表現され、8進数は8を基数とする記数法（八進法）で表現されます。2進数は0と1のみを使用するのに対し、8進数は0から7までの数字を使用します。 2進数とそれに対応する8進数の例は以下の通りです。 2進数8進数 0110115 001015 1011026 0101012 以下に、8進数を2進数に変換するC++プログラムを示します。 サンプルプログラム #include <iostream> #include <cmath> using namespace std; int OctalToBi

並列配列（Parallel Array）とは、複数の配列を組み合わせて1つのデータ構造として扱う手法です。各配列はすべて同じサイズを持ち、同じインデックス位置にある要素同士が互いに関連付けられています。つまり、各配列の対応する要素は、共通のエンティティ（実体）を表します。並列配列の基本概念並列配列の具体例を見てみましょう。employee_name = { Harry, Sally, Mark, Frank, Judy } employee_salary = {10000, 5000, 20000, 12000, 5000}この例では、5人の従業員について、名前と給与という2種類の情報がそれぞ