Cプログラミング

今回は少しユニークな問題を紹介します。ある配列を受け取り、各要素を直前の要素で除算した値の合計を求めるというものです。 例として、配列 {5, 6, 7, 2, 1, 4} を考えてみましょう。この場合、計算結果は次のようになります。 5 + (6 / 5) + (7 / 6) + (2 / 7) + (1 / 2) + (4 / 1) = 12.15238 それでは、この問題を解くための手順を確認していきましょう。 アルゴリズム divSum(arr, n) begin sum := arr[0] for i := 1 to n-1, do sum := su

今回は少し変わったアルゴリズムの問題を紹介します。N個の要素からなる集合が与えられたとき、「その配列の任意の部分集合を取り出した際のGCD（最大公約数）が、必ず元の集合の要素のいずれかに一致する」という性質を持つ配列を生成します。さらに、生成する配列の長さはGCDの集合の長さの3倍を超えてはならないという制約も課せられています。例えば、{2, 4, 6, 12} という4つの数値が与えられた場合、答えの一つは {2, 2, 4, 2, 6, 2, 12} となります。この配列からどのような部分集合を選んでも、そのGCDは必ず {2, 4, 6, 12} の中に存在することが確認できます。解法の

本記事では、半円に内接する正方形の中に内接する最大のルーロー三角形の面積を求める方法を解説します。半円の半径を R、正方形の一辺の長さを a、ルーロー三角形の高さを h として考えます。数学的な導出まず、半径 R の半円に内接する正方形の一辺の長さは、次の式で表されます。a = 2R / √5次に、ルーロー三角形の高さは、この正方形の一辺と等しくなります。したがって、a = h が成り立ちます。一般に、高さ h のルーロー三角形の面積は、以下の公式で求められます。面積 = ((π − √3) × h²) / 2ここに h = 2R / √5 を代入すると、最終的な面積の式は次のようになります。

この記事では、正三角形に内接する正方形の内部に収まる最大のルーローの三角形の面積を求める方法を解説します。正三角形の一辺の長さを「a」、内接する正方形の一辺を「x」、ルーローの三角形の高さを「h」とします。 数学的な導出 一辺が a の正三角形に内接する正方形の一辺 x は、幾何学的な計算により次の値になります。 𝑥 = 0.464𝑎 ルーローの三角形の高さ h は、正方形の一辺 x と等しくなります。つまり、x = h という関係が成り立ちます。 高さ h のルーローの三角形の面積は、次の公式で求められます。 面積 = ((π − √3) × h²) / 2 この公式に h = 0.46

この記事では、正六角形に内接する正方形の中に内接する最大のルーロー三角形の面積を求める方法を解説します。 まず用語を整理しましょう。ルーロー三角形とは、正三角形の各頂点を中心として、残りの頂点を通る円弧を描くことで得られる曲線三角形で、「どの方向から測っても幅が一定」という性質を持つ代表的な定幅図形です。 ここでは、正六角形の一辺の長さを a、その内部に収まる正方形の一辺を x、ルーロー三角形の高さ（幅）を h とします。 正六角形に内接する正方形の一辺 一辺 a の正六角形に内接する正方形の一辺 x は、幾何学的な導出により次の式で表されます。 𝑥 = 1.268𝑎 ルーロー三角形の面

概要本記事では、「楕円に内接する正方形」の中に収まる最大のルーロー三角形（Reuleaux Triangle）の面積を求める方法を解説します。ルーロー三角形とは、正三角形の3つの頂点をそれぞれ中心として、ほかの頂点を通る円弧をつなぎ合わせてできる幅一定の曲線三角形で、マンホールの蓋などにも使われることで知られる形状です。ここでは、楕円の長軸の長さを 2a、短軸の長さを 2b とし、内接する正方形の一辺を x、ルーロー三角形の高さを h として考えます。ステップ1：楕円に内接する正方形の一辺を求める長軸が 2a、短軸が 2b の楕円に内接する正方形の一辺は、次の式で与えられます。ステップ2：ルー

この記事では、直角三角形に内接する正方形の中に描ける最大のルーロー三角形の面積を求める方法を解説します。 まず前提となる条件を整理しましょう。正方形の一辺の長さを「a」、ルーロー三角形の高さを「x」、外側の直角三角形の底辺を「b」、高さを「l」、斜辺を「h」とします。 なお、ルーロー三角形とは、正三角形の各頂点を中心として対向する頂点を通る円弧を3つ描くことで得られる図形です。どの方向から測っても幅が一定になる「定幅曲線」として知られており、その高さは生成元となる正三角形の一辺と等しくなります。 正方形の一辺の長さを求める 高さ l、底辺 b の直角三角形に内接する正方形の一辺 a は、相似

この記事では、円に内接する正方形の内部に収まる最大のルーロー三角形の面積を求める方法を解説します。正方形の一辺の長さを「a」、円の半径を「r」とします。前提となる幾何学的な関係まず押さえておきたいのは、正方形の対角線の長さが円の直径と一致するという点です。この関係を利用すると、正方形の一辺 a を半径 r を使って表すことができます。2r = a√2a = r√2ルーロー三角形の面積の導出ルーロー三角形の高さを h とすると、その高さは正方形の一辺と等しくなるため、a = h という関係が成り立ちます。ルーロー三角形の面積は、3つの扇形の面積の合計から中央の正三角形の面積を差し引いたものとして

この記事では、正方形の中に描ける最大のルーロー三角形（Reuleaux Triangle）の面積の求め方を解説します。正方形の一辺の長さを a、ルーロー三角形の高さを h とします。 ルーロー三角形とは ルーロー三角形は、正三角形の各頂点を中心として、対向する頂点までの距離を半径とする円弧を3本描くことで得られる曲線三角形です。どの方向から測っても幅が一定となる「等幅図形」の代表例として知られており、機械部品やペン型ドリルなどにも応用されています。 面積の導出 正方形内に収まる最大のルーロー三角形を考えるとき、その高さ h は正方形の一辺 a と一致します。つまり、a = h が成り立ちます。

正三角形に内接できる最大の正方形とは？ 本記事では、一辺の長さが a の正三角形の中に描ける最大の正方形について解説します。正方形の一辺の長さを x とし、その面積を幾何学的な関係から求めていきます。 一辺 x を求める式の導出 一辺 a の正三角形の高さは、三平方の定理より (√3/2)a となります。 底辺の上に置かれた正方形の上方には、元の三角形と相似な小さな正三角形が現れます。この小さな三角形の一辺は正方形の一辺 x に等しいため、「全体の高さ ＝ 正方形の高さ ＋ 小さな正三角形の高さ」という関係から次の式が成り立ちます。 (√3/2)a = x + (√3/2)x = x(1

今回は、M個の範囲トグル（反転）コマンドを適用した後のバイナリ配列の最終状態を求める問題を解説します。 まず、n個の要素からなるバイナリ配列を用意します。各要素は0または1の値を持ち、初期状態ではすべての要素が0です。続いて、M個のコマンドが与えられます。各コマンドは開始インデックスaと終了インデックスbを含みます。つまり、command(a, b)は、位置aの要素から位置bの要素までの範囲に対して適用されることを意味します。コマンドが実行されると、その範囲内のすべての値がトグルされます（0は1に、1は0に切り替わります）。 アルゴリズム toggleCommand(arr, a, b) Be

DFA（決定性有限オートマトン）とは DFA（Deterministic Finite Automata：決定性有限オートマトン）とは、定義された受理条件に基づいて文字列を受理または拒否する有限状態機械です。 本記事では、「a」で始まり「a」で終わる文字列を受理するDFAを作成します。入力として使用できるのは、集合 {a, b} に含まれる文字のみです。この条件をもとにDFAを設計していきます。まず、DFAが受理する有効なケースと拒否する無効なケースについて確認しましょう。 受理される文字列の例 ababba aabba aa a 拒否される文字列の例 ab b aabab プログラ

正四面体とは 正四面体（Tetrahedron）は、三角形を底面とする角錐の一種で、すべての面が正三角形で構成された立体図形です。底面となる1つの三角形と、側面を構成する3つの三角形が、それぞれ1つの頂点に収束する形をしています。 正四面体の表面積の公式 一辺の長さを a とすると、正四面体の表面積は以下の式で求められます。 表面積 = √3 × a2 この公式が成り立つ理由は、1つの正三角形の面積が (√3/4) × a2 であり、正四面体には同じ大きさの正三角形が4つあるため、(√3/4) × a2 × 4 = √3 × a2 となるからです。 C言語での実装例 以下のサンプルコードで

配列のビトニック性（Bitonicity）とは？ 配列のビトニック性（Bitonicity）とは、隣り合う要素同士を比較した結果をもとに算出される指標です。配列全体が「増加傾向にあるのか」「減少傾向にあるのか」をひとつの数値で表すことができます。 具体的な定義は以下の通りです。初期値を0とし、現在の要素 arr[i] を直前の要素 arr[i-1] と比較することで、値を更新していきます。 Bitonicity = 0 （初期状態：arr[0]） i が 1 から n まで繰り返し： 　Bitonicity = Bitonicity + 1 ; もし arr[i] > arr[i-1]

0-1ナップサック問題とはナップサック（knapsack）とは、背負い袋のことです。ナップサック問題は、価値と重さがそれぞれ異なる複数のアイテムの中から、容量に制限のある袋へ入れる品物を選び出し、袋の中の価値の合計を最大化することを目指す古典的な最適化問題です。特に「0-1ナップサック問題」では、各アイテムについて「入れる（1）」か「入れない（0）」かのどちらかしか選べません。アイテムを分割して一部だけ入れるという概念は存在しない点が大きな特徴です。例題アイテムの価値 = {20, 25, 40} アイテムの重さ = {25, 20, 30} ナップサックの容量 = 50重さの組み合わせの検証

二分木（バイナリツリー）とは、各ノードが最大2つの子ノードを持つ木構造のデータ構造です。2つの子ノードはそれぞれ「左の子」「右の子」と呼ばれます。BST（二分探索木）は、左部分木に含まれるすべてのノードの値が根より小さく、右部分木に含まれるすべてのノードの値が根より大きくなるという性質を持つ木構造です。この記事では、与えられた二分木がBSTであるかどうかを判定するプログラムを紹介します。二分木がBSTかどうかを判定する考え方判定を行うには、木に含まれるすべてのノードに対してBSTの条件を満たしているかを確認します。具体的には、各ノードについて「左の子の値はそのノードの値より小さいこと」「右の子

変形ニムゲームとは？ 変形ニムゲーム（Modified Game of Nim）は、配列を対象とした最適化ゲームの一種です。先攻プレイヤーの存在と、両者が取る最適な手に基づいて、最終的な勝者を予測します。 ゲームのロジック このゲームでは、複数の要素を含む配列が与えられます。プレイヤー1（Player 1）とプレイヤー2（Player 2）の2人が対戦し、それぞれ自分が担当する数値を配列から取り除いていきます。具体的なルールは次のとおりです。 プレイヤー1： 3で割り切れる数値をすべて取り除く プレイヤー2： 5で割り切れる数値をすべて取り除く 両プレイヤーが最適な戦略で要素を取り除いたと

配列とは、同じデータ型の複数の値をまとめて格納するためのデータ構造です。実際の開発では、「3、3、3、3、3」のように、まったく同じ値を連続して格納したい場面によく遭遇します。このようなケースに備えて、C言語（GCC／Clangなどのコンパイラ拡張）では、範囲を指定して繰り返し値をまとめて初期化できる便利な省略表記が用意されています。これを活用すれば、一つひとつ値を書く必要がなくなり、プログラマーの負担を大幅に軽減できます。基本構文[開始インデックス ... 終了インデックス] = 値 例：「3」を5回繰り返して格納する場合 [0 ... 4] = 3この記法では、指定した範囲内のすべての要

過剰数（Abundant Number）とは？ 過剰数（abundant number、excessive number とも呼ばれます）とは、数論における概念の一つで、「その数自身を除く約数（真の約数）の総和が、元の数よりも大きくなる自然数」を指します。 例として 12 を見てみましょう。12 の真の約数は 1, 2, 3, 4, 6 であり、その合計は 16 です。16 は 12 より大きいため、12 は過剰数だと言えます。 また、真の約数の総和と元の数との差は過剰度（abundance）と呼ばれます。上の例では 16 − 12 = 4 となるため、12 の過剰度は 4 です。 過剰数には

C言語のブール配列パズルとは？ これは配列を使った有名なパズルです。2つの要素を持つ整数型配列のすべての要素を0に変更することが課題となります。ただし、配列の片方の要素は必ず0であり、もう片方の要素は0である場合も、0以外の場合もあります。 このパズルを解くには、プログラムが0以外の要素を見つけ出し、それを0に書き換える必要があります。 パズルを解くための制約条件 このブール配列パズルを解く際には、以下の厳しい制約を守らなければなりません。 許可されているのは補数（complement）演算のみで、その他の演算は使用できません。 ループ文や条件分岐文（if文など）は使用禁止です。 直接代入（