Cプログラミング

本記事では、指定された桁数 n に対して、「2進数を前半と後半に分割したとき、両方のビットの合計が等しくなる」ようなすべての2進数を生成する方法を解説します。 例えば「100001」という6桁の2進数を見てみましょう。前半は「100」、後半は「001」であり、どちらもビットの合計が1で等しいため、この数は条件を満たします。以下では、このような性質を持つすべての2進数を効率よく列挙するアルゴリズムを紹介します。 アルゴリズムの基本アイデア 再帰関数 genAllBinEqualSumHalf(n, left, right, diff) を使用します。left と right は最初は空文字列で、

この記事では、指定された範囲 [L, R] の中から互いに素な数のペアを数える方法を紹介します。ただし、各数値は最大でも1つのペアにしか使われないものとします。 互いに素な数とは？ ロジックの説明に入る前に、「互いに素な数（コプライム）」という概念を確認しておきましょう。互いに素な数とは、共通の正の約数が 1 だけであるような2つの数の組み合わせのことです。言い換えると、2つの数の最大公約数（GCD）が 1 である関係を指します。 ここでは下限と上限が与えられます。たとえば、下限が 1、上限が 6 の場合、成立するペアは次の3組です。 (1, 2)、(3, 4)、(5, 6) 解法のアプローチ

本記事では、次のような問題を扱います。整数Nと基数Bが与えられたとき、先頭（最上位桁）が0ではないN桁のB進数が何通りあるかを数えます。例えば、N=2、B=2の場合、2桁の2進数は「00」「01」「10」「11」の4通り存在しますが、このうち先頭が0でない有効な数は「10」と「11」の2つだけです。 考え方 基数がBである場合、使用できる数字は0からB−1までのB種類です。したがって、先頭ゼロを含む場合、N桁の数は全部でBN通り生成できます。そのうち、先頭の桁が0になるものは、残りのN−1桁だけで決まるためBN−1通りあります。よって、先頭ゼロを含まないN桁のB進数の総数は、次の式で求められま

この記事では、与えられた文字列から構成できる任意の長さのすべての文字列を生成する方法を解説します。これは、各文字の組み合わせ(部分列)とその順列をすべて求める問題です。 例えば、入力文字列が「ABC」の場合、次のような文字列が生成されます。 {A, B, C, AB, BA, BC, CB, CA, AC, ABC, ACB, BAC, BCA, CAB, CBA} それでは、具体的な手順を見ていきましょう。 アルゴリズムの考え方 基本的なアイデアは次の通りです。 長さ n の文字列に対して、ビットフラグを用いて 2n - 1 通りの部分列を作成します(カウンタの j ビット目が立っていれば

この記事では、C言語やC++で使えるsystem()関数を活用して、ちょっとした驚きの動作を実現する方法を紹介します。system()関数は、Windows・Linux・macOSなど主要なオペレーティングシステムに標準で用意されている関数です。この関数を使うと、通常はコマンドライン（コマンドプロンプトやターミナル）から入力するシステムコマンドを、C/C++のプログラム内から直接実行できるようになります。system()関数とは？system()関数は、cstdlibヘッダー（C言語ではstdlib.h）に定義されており、引数として渡した文字列をOSのコマンドとしてシェルに渡して実行します。戻

ここでは、n番目のフィボナッチ数が10の倍数かどうかを、数列を実際に計算することなく効率的に判定する方法を紹介します。 例として、フィボナッチ数列を {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987} とします。このとき、15番目（0から数えて）の項である 610 は10で割り切れます。つまり、n が15の倍数であれば判定結果は true になります。 素朴なアプローチとその課題 最も単純な方法は、指定された項までフィボナッチ数を順に生成し、その値が10で割り切れるかを確認することです。しかし、この方法は項の位

ここでは、1からnまでの2進数を生成するための興味深い手法を紹介します。このアルゴリズムのポイントはキュー（queue）を活用するところにあります。基本的な考え方は非常にシンプルです。まず、キューの初期状態として最初の2進数「1」を格納します。その後、以下の操作を繰り返します。キューの先頭から要素を取り出す（デキュー）取り出した要素を出力する先頭要素の末尾に「0」を付けたものをキューに挿入する先頭要素の末尾に「1」を付けたものをキューに挿入するこの処理をn回繰り返すことで、1からnまでの2進表現が順番に得られます。それでは、具体的なアルゴリズムを見ていきましょう。アルゴリズムgenBinary

本記事では、nより小さいすべての素数を効率的に生成する方法を紹介します。このアプローチではウィルソンの定理（Wilsons theorem）を活用します。ウィルソンの定理によれば、ある数kが素数であるとき、((k - 1)! + 1) mod k の計算結果は必ず0になります。つまり、この性質を利用することで、素数判定を行うことができるのです。ただし、この手法には注意点があります。CやC++のような言語でそのまま実装すると、階乗の計算によって非常に大きな数が生じるため、標準の整数型では大きな整数を扱えず、正しく動作しません。実際に使用する場合は、多倍長整数（ビッグナンバー）ライブラリの導入や、

はじめに：反時計回りのスパイラル走査とは 本記事では、二分木を反時計回りにスパイラル状（渦巻き状）に走査するという興味深い問題を取り上げます。通常のレベル順走査（幅優先探索）とは異なり、レベルごとに走査方向を切り替えながら、木の外周から内側へとノードを訪問していくのが特徴です。 走査のイメージは以下の図の通りです。 この木を反時計回りに走査すると、出力順序は次のようになります。 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7 アルゴリズムの考え方 基本となるアイデアはシンプルです。上位レベルと下位レベルから同時に攻めていき、交互に方向を変え

この記事では、円の半径と中心角が与えられたときに、弧の長さを求める方法を解説します。プログラミング（C++）を使った具体的な実装例もあわせて紹介するので、数学的な考え方とコードの両方を一度に理解できます。弧の長さとは？円周上の一部分を「弧」と呼びます。円全体の円周の長さは 2πr で表されますが、中心角が360度未満の場合、その角度に対応する部分だけの長さ、つまり弧の長さを求める必要があります。たとえば、下図のように半径 r の円があり、中心角 x（度数法）が与えられているとします。ここで求めたいのは、この角に対応する弧の長さ L です。弧の長さを求める公式中心角が360度のとき、弧の長さは円

半径 R の半円が与えられているとします。この半円の中に、長さ l、幅 b の長方形が内接しており、さらにその長方形の中に半径 r の円が内接しています。本記事では、この内側の円の面積を求める手順を、数式の導出からC++による実装例までわかりやすく解説します。 半円に内接する最大の長方形 半円に内接する長方形は、底辺が半円の直径上にあり、上側の2つの頂点が半円周上にあります。このとき、三平方の定理（ピタゴラスの定理）より、l と b の間には次の関係が成り立ちます。 (l / 2)2 + b2 = R2 長方形の面積 A = l × b を最大化する条件を求めると、微分計算により次の値が

ここでは、正方形ABCDの内部に存在する、下図のような葉の形（リーフ形状）の面積を求める方法を解説します。正方形の各辺の長さは「a」とします。この葉の形は、互いに等しい2つの部分で構成されています。各部分の面積を p とすると、次のようになります。したがって、葉全体の面積は 2p となります。計算式葉の形は半径 a の円弧によって囲まれた領域から成り立っているため、その面積は以下の公式で求められます。葉の面積 = a2 × (π/2 − 1)実装例（C++）#include <iostream> using namespace std; float leafArea(float a

本記事では、半径が与えられたn辺の正多角形の面積を求める方法を解説します。ここでいう「半径」とは、多角形の中心から任意の頂点までの距離のことです。考え方:多角形を三角形に分割するこの問題を解くために、中心から一辺へ垂線を引きます。一辺の長さを「a」とすると、垂線はこの辺を2等分し、それぞれの長さはa/2になります。また、垂線と半径がなす角をx、半径の長さをrとします。図からわかるように、正多角形はN個の同一の三角形に分割できます。つまり、N辺の多角形は必ずN個の三角形に分けられるのです。中心における全角度は360°なので、これをN等分すると、各三角形の中心角は360°/Nとなります(例:N=6

本記事では、下図のようなルーロー三角形の面積を求める方法を解説します。ルーロー三角形の内部には一辺の長さが等しい正三角形が含まれており、その高さを h とします。この図形は、正三角形の各頂点を中心とした3つの円が重なり合った部分（共通部分）として作られます。ルーロー三角形とはルーロー三角形は、正三角形の3つの頂点をそれぞれ中心とし、頂点間の距離を半径とする3つの円の交わりでできる図形です。どの方向から測っても幅が一定になる「定幅図形」の最も簡単な例として知られており、マンホールの蓋や一部の工具などにも応用されています。面積の導出方法ルーロー三角形の面積は、3つの扇形（おうぎ形）に分解して考える

問題の概要1からNまでの最初のN個の自然数が与えられます。この中から、隣接する2つの要素の絶対差がすべて1より大きくなるような順列を1つ求めるのが課題です。そのような順列が存在しない場合は -1 を返します。解き方のアプローチこの問題は貪欲法（グリーディアルゴリズム）を使うことで簡単に解けます。考え方は次の通りです。まず、すべての奇数を降順（または昇順）に並べます。奇数同士は必ず2以上離れているため、隣接要素間の絶対差は1より大きくなります。次に、すべての偶数を降順（または昇順）に並べます。こちらも偶数同士の差は2以上あるため条件を満たします。境界部分では、最小の奇数「1」と最大の偶数が隣接し

n個の要素（n < 10）からなる文字列が与えられたとします。ここで求めたいのは、母音と子音それぞれの相対的な位置関係を崩さずに、この文字列を並べ替える方法が何通りあるかという問題です。 解き方は非常にシンプルです。まず、与えられた文字列に含まれる母音と子音の個数をそれぞれ数えます。次に、母音だけを並べ替えた場合の組み合わせ数を求め、同じように子音だけを並べ替えた場合の組み合わせ数を求めます。最後に、この2つの値を掛け合わせることで、並べ方の総数が得られます。 アルゴリズム arrangeWayCount(str) Begin 頻度を格納するための配列「freq」を定義する

1からnまでの数字がシャッフルされた順で並んだ長さnの配列と、整数Kが与えられます。n人のプレイヤーがバドミントンを行うために列に並んでいます。最初の2人が対戦し、負けたプレイヤーは列の末尾に移動します。勝ったプレイヤーは列の先頭に残り、次のプレイヤーと対戦します。この流れを繰り返し、誰かがK回連続で勝利した時点で、そのプレイヤーが勝者となります。具体例列が [2, 1, 3, 4, 5]、K = 2 の場合を考えてみましょう。出力は 5 になります。以下に対戦の流れを示します。(2, 1) が対戦し、2が勝利 → 1は列の末尾へ。列は [3, 4, 5, 1](2, 3) が対戦し、3が勝利

今回は非常に興味深いアルゴリズムの問題を取り上げます。N 個の要素を持つ配列「a」が与えられたとき、次の式で表される絶対差の合計を最小化するような要素 x を求め、そのときの最小値を計算します。|a[0] − x| + |a[1] − x| + … + |a[n−1] − x|具体例たとえば、配列が {1, 3, 9, 6, 3} の場合を考えてみましょう。このとき最適な x は 3 です。実際に計算すると以下のようになります。|1 − 3| + |3 − 3| + |9 − 3| + |6 − 3| + |3 − 3| = 2 + 0 + 6 + 3 + 0 = 11解法のポイント：中央値を

問題の概要本記事では、配列の中から出現回数が2回以上の要素をすべて見つける問題を解説します。例として、次の配列を考えてみましょう。{1, 5, 2, 5, 3, 1, 5, 2, 7}この場合、1は2回、5は3回、2は2回出現しており、それ以外の要素（3と7）はそれぞれ1回しか登場しません。したがって、求める出力は {1, 5, 2} となります。アルゴリズムこの問題は、ハッシュマップ（連想配列）を利用することで効率的に解けます。基本的な流れは以下の通りです。moreFreq(arr, n)Begin    キーと値がともに int 型のマップを定義する

ある配列が与えられたとき、その中に素数回出現している要素がいくつあるかを数える問題を考えてみましょう。例として、次の配列を見てください。{1, 2, 2, 0, 1, 5, 2, 5, 0, 0, 1, 1}この場合、各要素の出現回数は以下のようになります。1 → 4回（素数ではない）2 → 3回（素数）0 → 3回（素数）5 → 2回（素数）したがって、素数回出現している要素は {2, 0, 5} の3つとなり、答えは 3 です。アルゴリズムcountPrimeOccurrence(arr, n)Begin count := 0 キーと値がint型のマップを定義する