C++

はじめに このチュートリアルでは、グループ化されたデータ(度数分布データ)の標準偏差を求めるC++プログラムについて解説します。 グループ化されたデータでは、個々の数値の代わりに「階級(クラス区間)」と「度数(頻度)」が与えられます。本プログラムの目的は、これらの情報をもとにデータ全体の標準偏差を計算することです。 計算の手順 グループ化されたデータの標準偏差は、以下のステップで求めることができます。 1. 各階級の中央値(級中央値)を計算する:中央値 = (階級下限 + 階級上限) ÷ 22. 中央値と度数から平均値を求める:平均 = Σ(中央値 × 度数) ÷ 度数の合計3. 標準偏差の

はじめに本記事では、連結リスト（Linked List）を用いてランレングス符号化（Run Length Encoding：RLE）を実装するC++プログラムについて解説します。連結リストが与えられたとき、その各要素をランレングス符号化の手法で変換することが課題となります。例えば、連結リストの要素が「a → a → a → a → a」と並んでいる場合、ランレングス符号化ではこれが「a → 5」に置き換えられます。これは、同じ値が連続して現れる区間を「値 ＋ 連続回数」の組み合わせで表現することで、データ量を削減できるシンプルかつ効果的な圧縮手法です。アルゴリズムの流れ連結リストを先頭から順に

平均の標準誤差とは平均の標準誤差(Standard Error of Mean)とは、標本平均が母平均からどれほど散らばっているかを推定するための統計量です。標本調査の結果から母集団全体の平均を推定する際に、その信頼性を評価する指標として重要な役割を果たします。また、平均値のおおよその信頼区間を求める際にも利用されます。標準誤差は、次の式で求められます。標準誤差 = 標準偏差 ÷ √(標本サイズ)標本サイズが大きくなるほど標準誤差は小さくなり、標本平均は母平均に近づいていきます。プログラムの計算手順このプログラムでは、以下の3つのステップで標準誤差を計算します。1. 配列内のデータから標本平均

このチュートリアルでは、t検定（スチューデントのt検定）を実装するC++プログラムについて詳しく解説します。 t検定とは？ t検定は、2つのデータセットの平均値を比較し、それらが統計的に類似しているのか、それとも有意に異なるのかを判定するために用いられる手法です。 さらに、t検定では差がどの程度大きいのかを数値として把握できるため、その変化が何に起因しているのかを考察する際にも役立ちます。 C++によるt検定の実装例 以下のコードでは、大きく分けて3つの関数を実装しています。 calc_mean()：配列内のデータの平均値を計算します。 calc_deviation()：不偏標準偏差（n-1

n個の要素を持つソート済み配列Aがあるとします。この中から、指定された整数に最も近い値を見つけたいと思います。配列には重複した値や負の数が含まれている場合もあります。例えば、配列が [2, 5, 6, 7, 8, 8, 9] で目標値が 4 の場合、最も近い要素は 5 となります。解決のアプローチ配列を先頭から順に走査し、各要素と目標値の絶対差を記録しておき、最後に差が最小となる要素を返すという線形探索の方法もあります。しかし、配列がすでにソートされているため、二分探索（バイナリサーチ）を使えば O(log n) の時間計算量でより効率的に解くことができます。二分探索を用いた手順は以下の通りで

三角形の各辺の中点の座標が3つ与えられ、そこから元の三角形の頂点座標を逆算することを考えます。例えば、入力が (5, 3)、(4, 4)、(5, 5) の場合、出力は (4, 2)、(4, 6)、(6, 4) となります。 この問題を解くには、X座標とY座標をそれぞれ独立に扱います。頂点のX座標を x1、x2、x3 とすると、各辺の中点のX座標は (x1 + x2)/2、(x2 + x3)/2、(x3 + x1)/2 で表されます。ここで重要なのは、これら3つの式を足し合わせると頂点のX座標の合計と一致するという点です。つまり、「3つの変数の合計」と「ペアごとの合計を表す3つの式」が分かって

特別な二分木とは本記事で扱うのは、葉ノード（リーフノード）が循環双方向連結リストとして接続された特別な二分木です。この構造では、最も左側にある葉ノードの左ポインタが連結リストの「前（previous）」ポインタとして機能し、右ポインタが「次（next）」ポインタとして機能します。このような木の高さを求める方法を解説します。高さを求めるアルゴリズムの考え方高さを求める基本的な戦略は、通常の二分木の場合と同様です。各ノードについて左部分木と右部分木の高さを再帰的に計算し、そのノードの高さを「2つの子ノードの高さの最大値 + 1」として決定します。ただし、この問題では葉ノードが循環双方向連結リストの

バイナリ文字列 bin があるとします。この文字列に対して n 回の反復処理を適用します。各反復では、0 は「01」に、1 は「10」に変換されます。そして、n 回目の反復後の文字列における i 番目の文字を求めるのがこの問題です。 例えば、バイナリ文字列が「101」で、n = 2、i = 3 の場合を考えてみましょう。1 回目の反復後は「100110」になり、2 回目の反復後は「100101101001」になります。したがって、i 番目のインデックスに格納されている文字は「1」です。 解決の手順 この問題を解くには、以下の手順に従います。 n 回ループを実行し、各反復内で文字列に対してさら

原子価（valence number）とは、ある原子が他の原子と何本の結合を形成しなければならないかを定義する数値です。この記事では、3つの原子それぞれの原子価が与えられたとき、それらが1つの分子を形成できるかどうかをC++で判定する方法を解説します。なお、原子同士は複数の結合を形成できる点に注意してください。例えば、原子価が「2, 4, 2」である場合、以下のような結合が可能なので、答えはYESとなります。1 – 2、1 – 2、2 – 3、2 – 3分子を形成できない条件3つの原子価を a、b、c とし、c が最大値であると仮定します。このとき、分子を形成できないのは次の2つの場合です。a

問題の概要エンコードされた文字列を考えてみましょう。この形式では、部分文字列の繰り返しが「部分文字列 + 繰り返し回数」で表現されます。たとえば、ab2cd2 という文字列は ababcdcd を意味します。ここで k = 4 が与えられた場合、復号化後の文字列の4番目の文字、つまり b を返すことになります。解法のアプローチこの問題は、以下の手順で解くことができます。まず空の復号化用文字列を用意します。元の文字列を先頭から読み込み、英小文字が続く限り部分文字列として抽出します。続いて数字が続く限り読み取り、繰り返し回数として記録します(複数桁の数値にも対応)。抽出した部分文字列を、記録した回

スタックに格納されている要素の中から最大値をO(1)の時間で取得できるスタックを実装したいと考えます。ただし、ここには重要な制約があります。補助スタックなどの追加データ構造を使用してはならず、追加スペースはO(1)でなければなりません。アルゴリズムのポイントこの問題は、ユーザー定義のスタッククラスに現在の最大値を保持する変数を持たせ、push時に数式を使って値を「エンコード」することで解決できます。各操作は次のように処理します。push操作：挿入する要素xが現在の最大値より大きい場合は「2 * x − max」をスタックにプッシュし、最大値をxに更新します。そうでなければ、xをそのままプッシュ

問題概要 ある金額が与えられたとき、その金額ちょうどになるように、異なる額面の紙幣の最小枚数を求めます。基本的な考え方は、最も高額な紙幣から順に、残りの金額に対してできる限り多くの枚数を充てていくというものです。 ここでは、{2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} の各額面が無限に用意されているものとします。例えば、金額が 800 の場合は「500 × 1枚、200 × 1枚、100 × 1枚」の計 3 枚が答えになります。 解き方：貪欲法（Greedy） この問題は貪欲法を使うことで効率的に解くことができます。手順は以下の通りです。 額面を大きい

問題の概要 医師とエンジニアからなる特別な家系を考えてみましょう。この家系には、以下のようなルールが存在します。 全員が必ず2人の子どもを持ちます エンジニアの第1子はエンジニア、第2子は医師になります 医師の第1子は医師、第2子はエンジニアになります すべての世代は必ずエンジニアから始まります 例えば、レベル4・位置2の人物の職業を求めた場合、答えは「医師（Doctor）」となります。 解法のアイデア ある人物の職業は、次の2つの要素によって決定されます。 親の職業 ノードの位置：位置が奇数の場合、その人物の職業は親と同じになります。偶数の場合は、親とは異なる職業になります。 この性

C++で2つのソート済み配列の相対補集合を求める方法2つのソート済み配列 arr1 と arr2 があり、それぞれのサイズを m、n とします。ここで求めたいのは、この2つの配列の「相対補集合（相対的な差）」です。つまり、arr1 には存在するものの、arr2 には存在しないすべての要素を見つけるということです。例えば、配列が次のような場合を考えてみましょう。A = [3, 6, 10, 12, 15]B = [1, 3, 5, 10, 16]この場合、A には存在するが B には存在しない要素は 6、12、15 なので、結果は [6, 12, 15] となります。解決アプローチ：set_di

問題の概要 正整数 L が与えられ、これは完全二分木（パーフェクト・バイナリツリー）のレベル数を表しているとします。この木の葉ノードには、1 から n までの番号が順に割り当てられています（n は葉ノードの総数）。また、各親ノードの値は、その 2 つの子ノードの値の合計となります。 今回の課題は、この完全二分木に含まれるすべてのノードの値の合計を出力するプログラムを作成することです。 例として、次のような木を考えてみましょう。 この木の場合、すべてのノードの合計は 30 になります。 解法のアプローチ この問題を注意深く観察すると、求めるべきは全ノードの値の総和です。葉ノードには 1 から

長半径と短半径の長さがそれぞれ 2a・2b である楕円を考えます。この楕円に内接できる最大の円の面積を求めてみましょう。例えば a = 5、b = 3 の場合、その面積は 28.2734 になります。考え方図からも分かるように、楕円に内接する円のサイズは、楕円の中で最も幅が狭い短軸方向によって制限されます。つまり、内接円の直径は短軸の長さ 2b を超えることができないため、最大の内接円の半径は短半径「b」に等しくなります。したがって、求める面積 A は次の式で表せます。A = π × b × bサンプルコード#include<iostream> using namespace st

要素数 n の配列 A が与えられたとき、その中に含まれる「連続した偶数」の最大個数を求める問題を考えてみましょう。例えば、配列が A = [1, 2, 3, 4, 6, 8, 7] の場合、4・6・8 と偶数が3つ続いているため、答えは 3 となります。アルゴリズムの考え方この問題は非常にシンプルな方法で解くことができます。ポイントは2つのカウント変数を用意することです。max_current: 現在進行中の連続する偶数の個数max_till_now: これまでに見つかった最大の連続偶数の個数配列を先頭から順に走査し、偶数を見つけたら max_current を1増やして、max_till_

直線上にN個の局(ステーション)が並んでおり、それぞれが同じ非負の放射パワーを持っているとします。各局は、自分の放射パワーに応じて、隣接する局の放射パワーを次のルールで増加させます。 例えば、局iの放射パワーがRである場合、(i−1)番目の局の放射パワーを「R−1」だけ、(i−2)番目の局の放射パワーを「R−2」だけ増加させます。同様に、(i+1)番目の局の放射パワーを「R−1」だけ、(i+2)番目の局の放射パワーを「R−2」だけ増加させ、これを繰り返します。つまり、局から離れるほど影響が1ずつ減っていく仕組みです。 計算例 配列が Arr = [1, 2, 3] の場合、出力は 3, 4,

問題の概要 円周上に n 個のガソリンスタンドがあるとします。このとき、次の2種類のデータが与えられます。 各ガソリンスタンドが保有しているガソリンの量 あるガソリンスタンドから次のガソリンスタンドまでの距離 求めたいのは、トラックが出発して円を一周できる最初の出発地点です。なお、1リットルのガソリンで1単位の距離を走行できるものとします。 例として、4つのガソリンスタンドがあり、各スタンドの「ガソリン量と次のスタンドまでの距離」が [(4, 6), (6, 5), (7, 3), (4, 5)] となっている場合を考えます。このとき、トラックが一周を完走できる最初の出発地点は2番目のガソ

最初に増加し、その後減少していく配列(ビトニック配列と呼ばれます)から最大値を見つける方法を解説します。例えば、配列の要素が A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1] の場合、最大値は 450 となります。この問題は線形探索でも解けますが、二分探索(バイナリサーチ)を活用すれば、O(log n) という高速な計算量で最大値を効率的に求めることができます。二分探索による解法のポイント二分探索では、中央の要素(mid)とその隣接要素との大小関係に注目し、以下の3つの条件で場合分けを行います。mid が両隣の要素よりも大きい場合 → mid が