プログラミング

ハノイの塔（Tower of Hanoi）は、コンピュータサイエンスの教育現場でも古くから親しまれている古典的なパズル問題です。3本の棒（杭）と n 枚の円盤を使って遊びます。最初はすべての円盤が1本目の棒（始点）に積まれており、これらすべての円盤を3本目の棒（目的）へ移動させるのが目標です。途中、2本目の棒は補助用として自由に使えます。ハノイの塔のルール円盤を移動する際には、次の3つのルールを守る必要があります。1回の移動で動かせるのは、1枚の円盤だけ棒から取り出せるのは、最上部にある円盤のみ大きい円盤を小さい円盤の上に載せることは禁止再帰を使った解法の考え方この問題は再帰（リカージョン）を

長さの異なる N 本のロープが与えられます。これらをすべて連結しなければなりませんが、2 本のロープをつなぐコストは「その 2 本の長さの合計」となります。ここでの目的は、N 本すべてのロープを最小のコストで 1 本につなぎ合わせることです。 この問題はヒープ木（優先度付きキュー）を使うと効率よく解けます。まずすべてのロープの長さを最小ヒープに挿入し、ヒープから最も短いロープと 2 番目に短いロープを取り出して連結します。その後、連結後の長さを再びヒープに戻します。この操作を繰り返し、ヒープ内に要素が 1 つだけになった時点で処理を終了すれば、最小コストで連結されたロープが得られます。 この

ローマ数字とはローマ数字は位取り記数法を採らない記数法です。複数の記号を組み合わせることで1つの数値を表現します。たとえば 75 は「75 = 50 + 10 + 10 + 5」と分解できるため、ローマ数字では LXXV と表されます。この記事では、10進形式で与えられた数値をローマ数字の文字列へ変換する方法を、記号の一覧表・アルゴリズムの手順・C++による実装例とともに解説します。ローマ数字の記号とその値ローマ数字で使用される主な記号と、それぞれに対応する値は以下の表の通りです。ここでは 4000 以上の数も扱えるよう、非標準の拡張記号（MMMM、V）も含めています。記号値I1IV4V5IX

問題の概要 有向グラフが1つ与えられ、あわせて2つの頂点 u(始点)と v(終点)が指定されます。この課題では、ちょうど k 本の辺を使って頂点 u から v に到達する「ウォーク(歩行経路)」の総数を求めます。辺の本数 k の値もアルゴリズムへの入力として与えられます。 この問題は動的計画法(DP)で効率よく解くことができます。まず、n × n × (k+1) のサイズを持つ3次元テーブルを作成します。行には始点側の頂点番号 i、列には終点側の頂点番号 j を対応させ、奥行き(第3の次元)は始点から目的地までに使用した辺の本数を記録するために使います。 漸化式としては、「i から j へ e

2つの数が2進数（バイナリ）の文字列として与えられたとき、それらの積をいかに速く、効率的に求めるか。本記事ではその手法を詳しく解説します。 この問題は分割統治法（Divide and Conquer）を用いることで、非常に高い効率で解決できます。基本的なアイデアは、それぞれの数を前半と後半の2つの部分に分割し、部分ごとの結果を組み合わせて全体の積を得ることです。 ここで、最初の数 X を Xleft と Xright に、2番目の数 Y を Yleft と Yright に分割すると、積は次のように表されます。 さらに計算をシンプルにするため、上式は次のように変形できます。 この手法は

このアルゴリズムは、与えられた数値を英語の単語へ変換するものです。例えば、564という数値は「Five Hundred and Sixty-Four」という文字列に変換されます。 変換処理では、あらかじめ定義された文字列のリストを用意し、そこから適切な単語を取り出しながら数値を言葉に組み立てていきます。用意するリストは次の4種類です。 units: 0〜9の数字に対応する単語(Zero、One…Nine)を保持します。 twoDigits: 10〜19の数値に対応する単語(Ten、Eleven…Nineteen)を保持します。 tenMul: 10の倍数(20〜90)に対応する単語(Twe

フラッドフィル（Flood Fill）アルゴリズムとはフラッドフィルは、お絵かきソフトの「塗りつぶし（バケツ）ツール」などでも使われている、領域塗りつぶしのための基本的なアルゴリズムです。ここでは、1つの行列（マトリクス）が1枚の画面（スクリーン）を表すものとします。画面上の各要素 (i, j) は1つのピクセルに対応し、そのピクセルの色は異なる数値で表現されます。このアルゴリズムでは、対象ピクセルが「指定した元の色（前色）」で塗られている場合にのみ、新しい色へと塗り替えます。前色と異なる色のピクセルはそのまま残されます。そして、1つのピクセルを塗り終えるごとに、その上下左右の4方向の隣接ピク

偶数と素数の和の関係4以上のすべての偶数は、2つの素数の和として表すことができます。これは有名な「ゴールドバッハ予想」に関連する性質で、1つの偶数に対して複数の素数の組み合わせが存在する場合もあります。例えば、10という数値は次のように表せます。10 = 5 + 510 = 7 + 3本記事で紹介するアルゴリズムは、与えられた偶数に対して、その数を構成できるすべての素数の和の組み合わせを見つけ出します。基本的な考え方はシンプルで、ある数 x が素数であるときに限り、(対象の数 − x) も素数かどうかを判定します。両方が素数であれば、「x + (対象の数 − x)」がその偶数を表す組み合わせと

凸包（Convex Hull）とは凸包とは、与えられたすべてのデータ点を覆うことができる最小の閉領域のことです。平面上に打たれた点をすべて内側に含むように輪ゴムをかけたとき、輪ゴムが引っかかる外側の点を結んでできる多角形をイメージすると分かりやすいでしょう。グラハムスキャン（Grahams Scan）は、この凸包を構成する角の点（境界点）を効率的に見つけ出す古典的なアルゴリズムで、計算量は O(n log n) です。アルゴリズムの基本的な流れ基準点の決定：まず、最も下にある点（y座標が最小の点）を選びます。y座標が等しい点が複数ある場合は、x座標がより小さい方を採用します。この点が凸包の開始

ジャービスマーチアルゴリズムとは ジャービスマーチ（Jarvis March）アルゴリズムは、与えられた点群から凸包（convex hull）の頂点となる境界点を検出するためのアルゴリズムです。包装紙を包むように凸包の外周を辿っていくことから、「ギフト包装法（Gift Wrapping Algorithm）」とも呼ばれています。 データセットの中で最も左（x座標が最小）にある点を出発点とし、そこから反時計回りに点を辿りながら凸包に含まれる点を順に確定していきます。現在の点から見た各点の向き（外積の符号）を調べることで次の点を選び、最も外側に位置する点を採用します。すべての点を巡り、次の候補が

このアルゴリズムは、与えられたデータ集合の中から、配列の最大要素からK番目に大きい要素までを見つけ出すものです。 この問題は、配列をソートすることで簡単に解決できます。ソートは昇順・降順のどちらでも構いませんが、降順に並べ替えれば、先頭のK個の要素を取り出すだけで目的の結果が得られます。 入力と出力 入力: 配列の要素: {1, 23, 12, 9, 30, 2, 50, 63, 87, 12, 45, 21}, K = 4 出力: 4つの大きい要素: 87 63 50 45 アルゴリズム kthLargestElement(array, n, k) 入力: 配列、配列の要素数 n、順位 k

決定性有限オートマトン（DFA）は、ある整数が別の整数kで割り切れるかどうかを判定するために利用できる強力な手法です。さらに、割り切れない場合には余りの値まで同時に求めることができます。DFAによる除算の基本的な仕組みDFAベースの除算では、まずDFAの遷移表を作成します。この表さえ用意できれば、あとは対象となる数値の各ビットを順に読み込んでいくだけで答えを導き出せます。DFAにおいて、各状態が持つ遷移は「0」と「1」の2種類だけです。遷移のルールは非常にシンプルです。現在の状態をsとすると、・入力ビットが0のとき：次の状態は (2×s) をkで割った余り・入力ビットが1のとき：次の状態は (

問題の概要 この問題では、基数（底）が n である2つの数が与えられます。これらの数を加算し、その結果も同じく n進法で求めることが目的です。 基本的な解き方の流れは以下のとおりです。まず与えられた2つの数をそれぞれ10進数に変換します。10進数に変換できれば、あとは通常の整数演算で簡単に加算できます。最後に、加算結果を再び n進数へ変換して出力します。 ここで注意すべき点は、n進数を文字列として扱うことです。基数が9を超える場合、10以上の値を1桁で表すためにアルファベットを使う必要があるからです。たとえば16進数では、10〜15を表すのに A〜F の6文字が使用されます。 入力と出力の例

バビロニア法（Babylonian method）は、非線形方程式を解くための数値計算法であるニュートン・ラプソン法を基礎とする、平方根を求めるための古典的なアルゴリズムです。古代バビロンで使われていた計算手法に由来することから、この名前が付けられています。 アルゴリズムの基本的な考え方 この方法のアイデアは非常にシンプルです。まず任意の初期値 x（対象となる数値そのもの）と y = 1 を用意します。次に、x と y の平均値を取ることで、平方根のより良い近似値を得ます。その後、y の値を「元の数値 ÷ x」で更新します。この処理を、x と y の相対誤差が十分に小さくなるまで繰り返すことで

コンピュータ上では、変数はメモリ上の決まった領域に格納されます。しかし、そのメモリ領域のサイズは固定されているため、15! や 20! のような大きな値の階乗を求めようとすると、計算結果が変数の表現範囲を超えてしまい、誤った値が返されてしまいます。このような巨大な数を正確に扱うには、結果を配列に格納する方法が有効です。配列の各要素に結果の各桁を1つずつ保存していきます。ただし、配列に対して直接数値を掛けることはできないため、配列内のすべての桁に対して、筆算と同じ要領で手動の掛け算処理を実行する必要があります。入力と出力入力: 大きな数: 50 出力: 指定された数の階乗: 3041409320

問題の概要 この問題では、1つの多角形（ポリゴン）と1つの点Pが与えられます。求めるのは、点Pが多角形の内側にあるのか、それとも外側にあるのかという判定です。 アプローチ：レイキャスティング法 この問題を解くために、点Pから無限遠まで伸びる半直線を引くことを考えます。この直線は水平方向、すなわちx軸に平行なものとします。 次に、この半直線が多角形の辺と何回交差するかを数えます。交差回数が奇数であれば点は多角形の内側にあり、偶数であれば外側にあると判定できます。なお、点Pが多角形のいずれかの辺上に乗っている特殊なケースについては、別途チェックを行い「内側」として扱います。 この手法は「レイキャ

ある数の平方根が整数になるとき、その数は完全平方数（パーフェクトスクエア）と呼ばれます。つまり、平方根が整数値になるような数が完全平方数です。例えば、4 の平方根は 2、25 の平方根は 5 であるため、どちらも完全平方数です。完全平方数を判定する最も基本的な方法は、対象の数の平方根を求め、それが整数に一致するかどうかを繰り返し確認することです。計算した二乗の値が対象の数を超えた時点で一致しなければ、その数は完全平方数ではありません。ただし、この記事では処理を効率化するため、平方根を何度も再計算する方式は採用していません。完全平方数の平方根は必ず整数になるという性質を利用し、候補となる平方根を

概要2次元平面上に4つの点が与えられたとき、このアルゴリズムはそれらの点が正方形を形成しているかどうかを判定します。点が正方形を形成しているかを確認するためには、以下の条件を満たしている必要があります。与えられた4つの点で構成される4つの辺がすべて同じ長さであること隣接する2つの辺がすべて直角（90度）で交わっていること入力と出力入力: 4つの点 {(20, 10), (10, 20), (20, 20), (10, 10)} 出力: 点は正方形を形成しています。アルゴリズムisFormingSquare(p1, p2, p3, p4)この手順では、squareDist(p1, p2) という

2つの集合に共通する要素が1つも存在しないとき、それらは互いに素（disjoint set）であるといいます。言い換えると、2つの集合の積集合（共通部分）を求めた結果が空集合になる場合、その2つの集合は互いに素です。判定方法は非常にシンプルです。このアルゴリズムでは、2つの集合が与えられ、どちらもすでにソート済みであると仮定します。そのうえで、両方の集合の要素を先頭から順番に比較していきます。一致する要素が1つでも見つかれば互いに素ではなく、最後まで一致する要素が存在しなければ、2つの集合は互いに素であると判定できます。入力と出力入力： 2つの集合： set1: {15, 12, 36, 21

ここでは、2つの線分が与えられたときに、それらが交差しているかどうかを判定する方法を解説します。1つ目の線分の両端を点 p1・p2、2つ目の線分の両端を点 q1・q2 とします。2つの線分が交差していると判断できるのは、次の条件が満たされる場合です。(p1, p2, q1) と (p1, p2, q2) の向き（orientation）が異なる、かつ(q1, q2, p1) と (q1, q2, p2) の向きが異なるさらに、(p1, p2, q1)、(p1, p2, q2)、(q1, q2, p1)、(q1, q2, p2) のすべてが同一直線上に乗る（共線：collinear）ケースも特別