C++

循環リンクリストとは 循環リンクリスト（Circular Linked List）は、リンクリストの変形版であり、最初の要素が最後の要素を指し、最後の要素が最初の要素を指す構造を持つデータ構造です。片方向リンクリスト（Singly Linked List）でも双方向リンクリスト（Doubly Linked List）でも、循環リンクリストとして実装することができます。 双方向リンクリストの場合、末尾ノードのnextポインタが先頭ノードを指し、先頭ノードのprevポインタが末尾ノードを指すことで、両方向に循環する構造になります。 上図のように、押さえておくべき重要なポイントは以下の2点です。

本記事では、スレッド付き二分木（Threaded Binary Tree）というデータ構造について詳しく解説します。二分木の各ノードは最大2つの子を持ちますが、子が1つしかない、あるいはまったく存在しない場合、通常の連結リスト表現ではそのリンク部分はNULLのまま無駄になってしまいます。スレッド付き二分木では、この空きリンクを「スレッド」として再利用することで、メモリを有効活用しながら効率的な走査を実現できます。ノードの左または右の子領域が空いている場合、その領域がスレッドとして利用されます。スレッド付き二分木には大きく分けて片側スレッド木（シングルスレッド）と完全スレッド木の2種類が存在しま

キュー（queue）は、先に入れた要素から順に取り出される「FIFO（First In First Out：先入れ先出し）」方式のデータ構造です。キューにはいくつかの派生形があり、その代表例がデック（Deque：両端キュー）と優先度付きキュー（Priority Queue）です。 優先度付きキューとは 優先度付きキューでは、キュー内の各要素がそれぞれ固有の優先度を持ちます。要素を挿入する際に優先度を割り当てておき、取り出すときは最も優先度の高い要素から順に削除されます。この性質により、「重要なタスクから順に処理する」ような場面で非常に役立ちます。 優先度付きキューを実装する最も簡単な方法のひと

キュー(Queue)は、要素の集合を格納する抽象データ構造の一つです。キューはFIFO(First In, First Out:先入れ先出し)方式を採用しており、最初に挿入された要素が最初に取り出されるという特性を持ちます。キューは本来、線形データ構造として実装されます。しかし、配列を使ってキューを実装した場合、いくつかの問題が発生することがあります。挿入(insert)と削除(delete)の操作を繰り返すうちに、front(先頭ポインタ)とrear(末尾ポインタ)の位置が徐々に後方へ移動していきます。その結果、配列の後ろ側に空き領域が残っているにもかかわらず、論理上の制約によりその領域を利

本記事では、C++ STLにおけるmultimap::find()関数の動作、構文、および具体的な使用例について詳しく解説します。C++ STLにおけるmultimapとは？multimapは連想コンテナ（associative container）の一種で、mapコンテナと非常によく似た性質を持っています。キー値とマップされた値（mapped value）の組み合わせからなる要素を、特定の順序で格納することができます。mapとの最大の違いは、同じキーに対して複数の要素を関連付けられるという点です。また、コンテナ内のデータは、内部で常にキーに基づいて自動的にソートされるという特徴もあります。m

関数オーバーロードの基本 関数のオーバーロード（多重定義）は、メソッドのオーバーロードとも呼ばれます。オブジェクト指向プログラミングで広く活用されるポリモーフィズム（多態性）を実現する重要な機能で、同じ名前の関数に対して、引数の構成に応じて異なる処理を定義できます。 オーバーロードが成立するための条件 関数名が同一であること 引数（パラメータ）の型または個数が互いに異なること 戻り値の型だけが異なる関数は、オーバーロードとして区別されないこと オーバーロードできる例・できない例 // ○ オーバーロード可能：引数の型が異なるため int display(int a); int disp

2つの異なる配列が与えられたとき、そこからランダムに選んだペアが「最大加重ペア」となる確率を求めるのが本記事のテーマです。 ここでの「ペア」とは、片方の配列(仮にarray1と呼びます)から1つの要素を取り出し、もう片方の配列(array2)からもう1つの要素を取り出して組み合わせたものを指します。プログラムは、第1要素がarray1の最大値であり、かつ第2要素がarray2の最大値であるペア――すなわち最大加重ペア――が選ばれる確率を計算する必要があります。 入出力の例 例1 入力: arr1[] = { 2, 23 } arr2[] = { 10, 3, 8 } 出力: probabil

問題概要サイズ「n」の配列が与えられ、その配列内に指定された要素 k が存在する場合に、その出現確率を求めることが課題です。配列の要素数と等しい「n」まで配列全体を走査し、指定された要素(キー)「k」を検索します。要素が配列内に存在する場合はその確率を計算して返し、存在しない場合は 0 を出力します。入力arr[] = { 1, 2, 3, 4, 5, 6} K = 5出力配列におけるキー 5 の確率 : 0.166入力arr[] = { 1,2,3,4,5,6,7 } K = 8出力配列におけるキー 8 の確率 : 0考え方上記はサイズ 7 の配列とキー 2 を例とした説明です。この場合、配

2人のプレイヤーAとBが、試合の勝敗をかけたペナルティキックに挑む場面を考えてみましょう。4つの整数変数 a、b、c、d が与えられており、Aが先にペナルティを成功させる確率は a/b、Bが先に成功させる確率は c/d で表されます。 先にペナルティを決めた方が試合に勝利します。本記事では、この条件のもとで「Aが試合に勝つ確率」を求めるプログラムをC++で実装する方法を解説します。 入出力例 入力 a = 10, b = 20, c = 30, d = 40 出力 probability is 0.5333 入力 a = 1, b = 2, c = 10, d = 11 出力 probabi

はじめに 文字列形式で表現された二分木が与えられたとき、k番目のレベルに存在するノードの値の積を求めるのが本記事の目的です。二分木の各ノードは、データ部分・左部分木を指すポインタ・右部分木を指すポインタの3つの要素で構成されています。 二分木のレベルは0から始まり、任意の正の整数nまで続きます。ここでは、レベル「k」が与えられ、そのレベルにあるノードの値の積をプログラムで計算します。 例えば、次のような二分木に対してk=2が与えられた場合を考えてみましょう。 レベル2のノードは − 40、50、60 です。 積 = 40 × 50 × 60 = 120,000 入力例1 (1(2(3()()

ノードから構成される二分木が与えられたとき、その二分木に含まれるすべての葉ノードの値の積を求めるのが本記事のテーマです。 葉ノードとは、子ノードを持たない末端のノードのことを指します。木構造では、ルートノード以外の各ノードは親ノードにも子ノードにもなり得ますが、ルートノードは親としてのみ存在します。つまり、左ポインタと右ポインタがどちらもNULLになっているノードこそが葉ノードだと判定できます。 入力 出力 葉ノード -: 23, 34, 25 積 -: 23 × 34 × 25 = 19550 アプローチ ノードのデータを入力する ルートノードから出発し、左部分木または右部分木へ再帰的に

ノードからなる二分木（バイナリツリー）が与えられ、その二分木に含まれるすべてのノードの値の積を求めるのが本記事の課題です。 二分木には、木全体の頂点となる「ルートノード」が存在します。各ノードはデータ部分を持ち、さらに左部分木を形成するための左ポインタと、右部分木を形成するための右ポインタを保持しています。木を走査する際には、一時的なポインタを用意し、左ポインタをたどって左部分木へ、右ポインタをたどって右部分木へと移動することで、木全体を効率的に巡回できます。 入力 出力 Nodes are-: 10, 20, 30, 40, 50, 60 積 = 10 × 20 × 30 × 40 ×

単一リンクリストが与えられたとき、値が素数になっているノードをすべて見つけ出し、それらの値の積を計算して出力するのが本稿のテーマです。ここで「素数ノード」とは、データ部分に素数を格納しているノードを指します。 入力例 85 → 6 → 7 → 2 → 10 出力例 14 説明 リストを先頭から順に調べると、85 は 5×17 に分解できるため素数ではなく除外されます。6 も 2×3 であり除外、続く 7 は素数なので採用、2 も素数なので採用、最後の 10 は 2×5 であるため除外されます。したがって積は 7 × 2 = 14 となります。 解決のた

2つの2進数を表す文字列が与えられたとき、それらを加算した結果を求め、その結果を2進数の文字列として返すことを考えます。2進数とは、0か1のいずれかで表現される数値のことです。2進数同士を足し合わせる際には、以下のような2進数特有の加算ルールに従う必要があります。0+0 → 0 0+1 → 1 1+0 → 1 1+1 → 0（繰り上がり1）入力例str1 = {11}, str2 = {1}出力例100入力例str1 = {110}, str2 = {1}出力例111問題を解くためのアプローチ両方の文字列を末尾（最下位桁）から走査する対応する桁の2進数同士を加算する1と1を足した場合は、その桁

長さNの整数配列 arr[N] が与えられたとき、その平均値を求めるのが本記事のテーマです。この問題は、反復処理（イテレーティブ）と再帰処理（リカーシブ）のどちらのアプローチでも解くことができます。ここでは両方の実装方法をわかりやすく紹介します。 配列の平均値とは、「配列内の全要素の合計」を「要素数」で割った値のことです。 反復法（Iterative Method） 反復法では、forループ、whileループ、do-whileループといった繰り返し構文を使用します。これらのループは、条件が真である限り文を実行し続けます。 まず具体例を見てから、反復法でどのように求めるのかを説明します。 入力

N個の整数からなる配列 arr[N] が与えられたとき、その配列がビトニック配列であるかどうかを判定するのが本記事のテーマです。ビトニック配列であれば「Yes its a bitonic array」と出力し、そうでなければ「No its not a bitonic array」と出力します。ビトニック配列とは、まず厳密に増加し、その後厳密に減少するような配列のことです。たとえば arr[] = {1, 2, 3, 4, 2, -1, -5} という配列は、4までは厳密に増加しており、4以降は厳密に減少しているため、ビトニック配列といえます。入力例と出力例入力arr[] = {1, 3, 5,

ある正の整数「n」が与えられたとき、その数がプロス数（Proth数）であるかどうかを判定し、結果を出力するのが本記事のテーマです。 プロス数とは？ プロス数とは、次の形で表される数のことです。 N = k × 2n + 1 ここで、n は正の整数、k は奇数の正の整数です。 最初のいくつかのプロス数は以下の通りです。 3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97....... 入力 number: 17 出力 its a proth number（プロス数です） 入力 number: 18 出力 its not a proth number（

本記事では、正の整数「n」が与えられたとき、その数値がバズナンバー（Buzz Number）であるかどうかを判定し、結果を出力するC++プログラムを紹介します。バズナンバーとは？ある数値がバズナンバーとみなされるためには、以下の2つの条件のうちどちらか一方を満たしている必要があります。数値の末尾（1の位）が7であること。例：27、657 など数値が7で割り切れること。例：63、49 など入出力例入力：number: 49出力：its a buzz number解説： この数値は7で割り切れるため、バズナンバーです。入力：number: 29出力：its not a buzz number解説：

3つの異なる座標を持つ点が与えられ、それらの点が同一直線上に並んでいるかどうか(共線性・コリニア)を判定するのが本記事のテーマです。3つの点がすべて同じ直線上に乗っている場合、これらの点は「共線(collinear)」であるといいます。逆に、異なる直線上に配置されている場合は共線ではありません。以下の図は、共線な点と共線でない点の違いを示したものです。入力例と出力例入力1x1 = 1, x2 = 2, x3 = 3, y1 = 1, y2 = 4, y3 = 5出力1no points are not collinear入力2x1 = 1, y1 = 1, x2 = 1, y2 = 4, x3

整数 n 個からなる配列 arr[n] が与えられたとき、「その配列は回文（パリンドローム）か？」を判定するのが本稿のテーマです。C++ の STL（標準テンプレートライブラリ）を活用して、この問題をシンプルに解いていきます。 STLとは STL（Standard Template Library）は、C++ に用意されたテンプレートクラスの集合体で、スタック・キュー・リストといったデータ構造や、ソート・反転などの便利な関数を提供します。これらを活用するには、テンプレートクラスに関する基本的な知識が必要です。本稿では、STL の reverse() 関数を使って配列を反転させています。 回文と