プログラミング

はじめに三角形の3つの頂点と、判定対象となる点Pが与えられたとき、その点Pが三角形の内側に存在するかどうかを判定する問題について解説します。この問題は「面積比較法」と呼ばれる手法で効率よく解くことができます。三角形の頂点をA、B、Cとするとき、次の等式が成り立てば、点Pは三角形の内部にあると判断できます。ΔABC ＝ ΔABP ＋ ΔPBC ＋ ΔAPCつまり、元の三角形ABCの面積が、点Pを共有する3つの小さな三角形（ABP・PBC・APC）の面積の合計と一致すれば、点Pは三角形の中にあるということです。逆に点Pが外側にある場合は、これらの面積の合計が元の三角形の面積よりも大きくなります。入

割線法（セカント法）とは割線法（セカント法）は、非線形方程式を解くために用いられる数値解法の一つです。この手法はニュートン・ラプソン法とよく似ていますが、関数 f(x) の微分を解析的に求める必要がない点が大きな特徴です。f(x) の値のみを用いて、ニュートンの差分公式（除算差分公式）により f(x) を数値的に近似することができます。まず、ニュートン・ラプソン法の公式は次のようになります。ここで差分公式を適用すると、f(x) を次のように近似できます。ニュートン・ラプソン法の公式に含まれる f(x) を、この新しい近似式で置き換えることで、非線形方程式を解くための割線法の公式が導かれます。注

台形公式による定積分の概要定積分は、台形公式（Trapezoidal Rule）を使うことで数値的に求めることができます。関数 f(x) を区間 a から b まで積分するということは、x = a から x = b の範囲における曲線の下側の面積を求めることを意味します。この面積を求めるには、領域を n 個の台形に分割します。各台形の幅を h とすると、(b − a) = nh という関係が成り立ちます。分割する台形の数が増えるほど、面積の計算結果はより正確になります。この考え方をもとに、以下の公式で積分を求めます。入力と出力Input: 関数 f(x): 1-exp(-x/2.0)、積分区間

シンプソンの1/3則とは シンプソンの1/3則（Simpsons 1/3 Rule）は、台形則と同様に、区間 [a, b] における定積分の値を数値的に近似する手法です。台形則との主な違いは、台形則では区間全体を複数の台形に分割するのに対し、シンプソンの1/3則ではさらに各部分を2つに細分化し、放物線で関数を近似する点にあります。このため、台形則よりも高い精度で積分値を求められるのが特徴です。 シンプソンの1/3則の公式 この手法では、次の公式を使用します。 ここで、h は各区間の幅、n は区間の分割数を表します。h は以下の式から求めることができます。 入力と出力 入力： 関数 f(x)

線形回帰（Linear Regression）は、与えられたデータ点の集合から、それらの点に最もよく当てはまる直線の方程式を求める統計的手法です。求められた直線をもとにすれば、現在のデータセットに存在しない新しい点の値を予測することも可能になります。線形回帰の基本公式いくつかのデータ点から線形回帰の問題を解くには、以下の公式を使用します。m = (n・Σxy − Σx・Σy) / (n・Σx² − (Σx)²)c = (Σy − m・Σx) / nここで、m は直線の傾き（slope）、c は y切片（y-intercept） を表します。これらの値を求めることで、次の形式の直線の方程式が得ら

ルンゲ・クッタ法（Runge-Kutta法）は、常微分方程式（ODE）を数値的に解くために広く使われている手法です。この方法では、x と y を含む導関数 dy/dx を用い、初期値 y(0)（x=0 のときの y の値）が必要になります。これらをもとに、任意の x に対する y の近似値を高精度に求めることができます。 常微分方程式を解くには、以下の公式に従います。 ここで h は区間の幅（刻み幅）を表します。 補足： これらの公式のうち、最初の2つの k1 と k2 だけを使えば、2次のルンゲ・クッタ法として ODE を解くことも可能です。 k1〜k4 の役割 4次ルンゲ・クッタ法では、

ラグランジュ補間とは離散的に与えられた一連のデータ点の範囲内で、新たなデータ点を求める際には「補間（インターポレーション）」という手法が用いられます。ラグランジュ補間はその代表的な手法の一つであり、与えられたデータ点が等間隔に並んでいない場合でも適用できる点が大きな特徴です。ラグランジュ補間では、すべての既知のデータ点を通る多項式 P(x) を構成します。このとき、次の式に従って計算を行います。ここでは、各データ点 (xi, f(xi)) ごとに「基底多項式」と呼ばれる項を作り、それらを f(xi) で重み付けして総和を取ることで、目的の点における関数値を求めます。i = j のとき分母が 0

ラッキーナンバー（幸運数）とは ラッキーナンバーとは、特別な性質を持つ整数のことです。1から始まる自然数列に対して、数値そのものの大小ではなく位置（順番）に基づいて特定の数を取り除いていき、最後まで消されずに残った数がラッキーナンバーとなります。 削除は次のルールに従って行われます。まず2番目ごとの数をすべて削除し、続いて3番目ごとの数を削除します。以降も同様に、段階的に間隔を広げながら削除を繰り返していきます。 具体例：1〜25の場合 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 （1〜25のすべて） 1

10進数は2進数へ変換することができます。10進数を2進数に変換するには、対象の数値が0または1になるまで2で割り続けます。そして、各ステップで得られた余りを記録しておき、それらを逆順に並べることで2進数表現が完成します。本記事で紹介するアルゴリズムでは、再帰的なアプローチを採用します。再帰を利用することで、スタックデータ構造を明示的に実装することなく問題を解決できます。関数の再帰呼び出しは内部的にコールスタックを使用するため、この仕組みをそのまま活かして処理を行うのがポイントです。入力と出力の例入力:10進数 56出力:2進数表現: 111000アルゴリズムdecToBin(decimal)

数学において、最小公倍数（LCM：Least Common Multiple）とは、2つの数値のどちらによっても割り切れる最小の正の整数のことです。LCMは素因数分解など、さまざまな方法で計算できます。この記事で紹介するアルゴリズムでは、大きい方の数値に 1、2、3…n と順に掛けていき、もう一方の数値で割り切れる数が見つかった時点で、それをLCMとして返すというシンプルなアプローチを採用しています。入力と出力入力： 2つの数値：6 と 9 出力： LCMは：18アルゴリズム手続きは LCMofTwo(a, b) として定義します。入力： 2つの数値 a と b（a > b

数学において、最大公約数（GCD：Greatest Common Divisor）とは、2つの整数をどちらも割り切ることができる整数のうち、最も大きいものを指します。なお、GCDを求める対象となる数はゼロ以外である必要があります。本記事では、古典的かつ効率的な手法であるユークリッドの互除法（Euclidean Algorithm）を用いて、2つの数のGCDを求める方法を解説します。入力と出力の例まず、プログラムの動作イメージをつかむために、具体的な入力と出力の例を見てみましょう。入力: 2つの数 51 と 34 出力: GCDは: 17この例では、51と34の両方を割り切れる最大の整数は17で

長さ n の一本の棒（ロッド）が与えられ、それと同時に「長さごとの価格表」も提供されます。この問題では、棒をいくつかに切断して市場で売却したときに得られる最大の利益を求めます。最適な価格を得るためには、さまざまな位置で切断を試み、それぞれの場合の売上を比較する必要があります。ここで、長さ n の棒を切断したときの最大価格を返す関数を f(n) とします。この f(n) は次のように定義できます。f(n) := price[i] + f(n − i − 1) の最大値（i は 0 から n − 1 の範囲）これは典型的な動的計画法（DP）の問題であり、短い棒から順に最適解を求めていき、それを利用

最短共通超部分列（Shortest Common Supersequence、略称：SCS）とは、与えられた2つの列のすべての要素が含まれる列のことです。言い換えると、元となる2つの文字列がどちらも、この超部分列の部分列となっている関係です。2つの文字列に共通する文字が1つもない場合には、単純に連結するだけで超部分列が得られます。しかし、共通の文字が含まれている場合は、まず最長共通部分列（LCS）を見つけたうえで、もう一方の文字列の残りの文字を付け足していく必要があります。なお、SCSの長さは次の式でも求められます。SCSの長さ = len(str1) + len(str2) − LCSの長さ

非減少数とは非減少数（non-decreasing number）とは、上位の桁から順に見て、どの桁も直前の桁より小さくない（＝各桁がひとつ前の桁以上になっている）数のことです。たとえば、111、112、123、789、569 などはすべて非減少数です。この記事では、N 桁の数の中に非減少数がいくつ存在するかを、動的計画法（DP）を使って求めるアルゴリズムを解説します。漸化式による定式化count(n, d) を「長さ n で末尾の桁が d である非減少数の個数」と定義すると、次のような関係式が成り立ちます。$$count(n,d)=\displaystyle\sum\limits_{i=0}

頂点被覆問題とは無向グラフにおける頂点被覆（Vertex Cover）とは、グラフのすべての辺 (u, v) に対して、u または v の少なくとも一方が必ずその集合に含まれるような頂点の部分集合のことを指します。二分木を利用することで、頂点被覆問題を動的計画法によって効率的に解くことができます。解法の考え方この問題は、根（ルート）ノードに着目して、次の2つの場合に分割して考えることができます。ケース1：根を頂点被覆に含める場合根が頂点被覆に含まれると、根から子へ伸びるすべての辺が自動的に覆われます。したがって、左部分木と右部分木それぞれの最小頂点被覆サイズを求め、根自身の分として「1」を加算

醜い数（アグリー・ナンバー）とは、素因数が2、3、5のみで構成される数のことです。1から15の範囲には、1、2、3、4、5、6、8、9、10、12、15の11個の醜い数が存在します。一方、7、11、13はそれ自体が素数であるため醜い数には含まれません。また、14は素因数分解すると7が現れるため、これも醜い数ではありません。この記事では、n番目の醜い数を求めるプログラムを、アルゴリズムの考え方から実際のC++コードまで詳しく解説します。入力と出力Input: 項番号を入力する。例：10 Output: 10番目の醜い数は12アルゴリズムgetUglyNumbers(n)入力： 項の個数。出力：

開始時刻・終了時刻・利益が与えられた複数のジョブの中から、互いに時間帯が重ならないジョブの組み合わせを選び、合計利益を最大化するのが「重み付きジョブスケジューリング」問題です。このアルゴリズムでは動的計画法（DP）を活用し、テーブルに部分問題の結果を保存しながら、ボトムアップ方式で全体の問題を解いていきます。基本的な実装での計算量は O(n²) ですが、二分探索を使って競合しないジョブを検索することで、O(n log n) まで高速化することも可能です。アルゴリズムの考え方各ジョブについて「そのジョブを採用する場合」と「採用しない場合」の利益を比較し、大きい方をテーブルに記録します。あらかじめ

ワードラップ（Word Wrap）問題は、一連の単語と「1行に入力できる最大文字数」が与えられたとき、どこで改行すればテキストがもっとも見やすくなるかを求める、動的計画法の古典的な応用例です。 ポイントとなるのは行のバランスです。余分な空白が多い行と、ぎりぎりまで詰め込まれた行が混在すると、文章全体の見た目が悪くなります。このアルゴリズムでは、各行の余白の量をコストとして評価し、その合計が最小になるように改行位置を決めることで、余白が均等に分散した美しい整形を実現します。 アルゴリズムを実行すると、「1行あたり何個の単語を配置できるか」と「全体で何行必要か」が得られます。 入力と出力 入力

コンピュータで数式を処理・評価する場合、式を後置記法（ポーランド逆記法）か前置記法（ポーランド記法）のどちらかに変換しておくのが一般的です。この記事では、私たちが普段使う中置記法（インフィックス記法）の式を、前置記法へ変換する手順を詳しく解説します。 前置記法への変換の基本の流れ 変換は大きく分けて次の3ステップで行います。 式を反転する … 中置記法の式全体を逆順に並べ替えます。このとき、開き括弧「(」と閉じ括弧「)」も一緒に反転されてしまう点に注意が必要です。 後置記法に変換する … 反転した式の括弧を正しい向きに修正してから、通常の「中置記法→後置記法」変換アルゴリズムで処理します

中置記法（インフィックス記法）は、人間にとって読みやすく理解しやすい数式の表現形式です。私たちは演算子の優先順位を容易に判別できるうえ、括弧を使えば先に計算すべき部分を明示することもできます。一方、コンピュータにとっては演算子や括弧の区別が簡単ではありません。そのため、計算機で効率よく処理するには後置記法（ポストフィックス記法）への変換が必要になります。中置記法から後置記法への変換には、スタックというデータ構造を使用します。中置式を左から右へ走査しながら、オペランド（被演算子）を見つけたらそのまま後置式へ追加します。演算子や括弧が出てきた場合は、それぞれの優先順位を保ちながらスタックに積んでい