Cプログラミング

C++では、UTF-32などの32ビット文字表現を扱うことができます。c32rtomb()関数は、このような32ビットの文字（char32_t）を、ナローマルチバイト文字表現へ変換するための関数です。この関数は<uchar.h>ヘッダーファイルで定義されており、C++11以降で利用可能です。 c32rtomb()関数の基本構文 size_t c32rtomb(char* s, char32_t c32, mbstate_t* ps); パラメータについて この関数は、以下の3つの引数を受け取ります。 変換結果の格納先：マルチバイト文字が書き込まれる文字配列へのポインタ 変換対象の

コインを三角形（ピラミッド状）に積んだときの最大の高さ この記事では、少し頭を使う興味深い問題を紹介します。N枚のコインが与えられたとき、それらをピラミッド状に並べた場合に作れる最大の高さを求めるという問題です。この配置方法では、1段目に1枚、2段目に2枚、3段目に3枚というように、段が下がるごとにコインを1枚ずつ増やしながら積み上げていきます。 図の例を見てみましょう。高さ3のピラミッドを作るには、最低でも6枚のコインが必要です。同様に、高さ4のピラミッドには10枚のコインが必要になります。つまり、コインが13枚あれば高さ4までは作れますが、高さ5に必要な15枚には届かないため、最大の高さ

この記事では、下図のようなピラミッド状の三角形を作るために必要なマッチ棒の本数を求める方法を解説します。ピラミッドの底辺のサイズが与えられたとき、そのサイズに応じて必要なマッチ棒の総本数を計算します。例えば、底辺のサイズが1の場合は3本、底辺が2の場合は9本、底辺が3の場合は18本のマッチ棒が必要になります。必要なマッチ棒の本数を求める公式この問題を解くには、以下の公式を使用します。必要なマッチ棒の本数 = 3 × x × (x + 1) ÷ 2ここで、x はピラミッドの底辺のサイズです。この公式を使えば、ループで一つずつ数え上げることなく、O(1)の計算量で即座に答えを求められます。C++で

転倒（反転）とは？ 配列の「転倒（inversion）」とは、その配列をソート済みの状態に変換するために必要な入れ替えの回数を表す指標です。配列がすでに昇順にソートされている場合、転倒数は0になります。逆に、配列が完全に逆順（降順）になっている場合、転倒数は最大となります。 この問題を、隣接するすべてのペアを総当たりで調べる素朴な方法で解くと、計算量はO(n²)になります。そこで本記事では、マージソートの仕組みを利用した分割統治法（Divide and Conquer）を採用し、計算量をO(n log n)まで抑える効率的なアプローチを紹介します。 入出力例 入力 数値の列：（1, 5, 6,

本記事では、整数を2進数で表したときに「1」となっているビット（セットビット）の個数を数える方法を解説します。セットビットとは、数値のバイナリ表現における1のビットのことです。たとえば、13は2進数で「1101」と表されるため、セットビットは3個になります。この問題を解くには、数値を右シフトしながら最下位ビット（LSb）を調べ、1であればカウントを増やします。これを数値が0になるまで繰り返すことで、セットビットの総数を求められます。アルゴリズムcountSetBit()begin count := 0 while n is not 0, do if LSb of

配列内で奇数回出現する数を見つける方法このプログラムでは、配列内で奇数回出現する数を求める方法を解説します。アプローチはいくつかありますが、その中でも最も簡単な方法の一つがXOR（排他的論理和）演算を利用する方法です。XOR演算には以下のような性質があります。ある数をそれ自身とXORすると、結果は0になります（A XOR A = 0）ある数を0とXORすると、結果はその数自体になります（A XOR 0 = A）したがって、配列内のすべての要素を順番にXORしていくと、偶数回出現する要素は互いに打ち消し合って0になり、最終的に残るのは奇数回出現する要素だけです。ただし、この解法には一つ注意点があ

この記事では、シンプルなC/C++のコードを書くだけでコンピュータをシャットダウンする方法を解説します。シャットダウンの手順はOSによって異なるため、ここではLinuxとWindowsそれぞれの場合について説明します。Linuxの場合Linuxユーザーなら、ターミナルから以下のコマンドを実行するだけでシステムをシャットダウンできます。shutdown –P now「-P」オプションはシャットダウン後に電源を切断することを意味し、「now」は即時実行を指定しています。Windowsの場合Windowsシステムでは、次のコマンドを使用します。c:\windows\system32\shutdown

整数の配列が与えられたとき、連続する要素の合計の中で最も大きくなるものを見つけ、その値を出力する問題です。これは「最大部分配列和問題」として知られる古典的なアルゴリズム課題の一つです。この問題は動的計画法（DP）を使うことで効率的に解くことができます。各位置において「現在の位置までの最大合計」を記録していき、それを更新しながら全体の最大値を求めます。これにより、配列内の連続する要素の最大和を線形時間 O(n) で計算できます。入力：整数の配列 {-2, -3, 4, -1, -2, 1, 5, -3} 出力：部分配列の最大合計：7アルゴリズムmaxSum(array, n)入力： メインの配列

本記事では、2つの数の最大公約数（GCD: Greatest Common Divisor）を求めるための「ユークリッドの互除法」について解説します。ユークリッドの互除法を利用すれば、GCDを簡単かつ効率的に計算することが可能です。実装方法には大きく分けて反復型（ループ処理）と再帰型の2つのアプローチがありますが、ここでは再帰的なユークリッドの互除法を取り上げます。 アルゴリズムの考え方 ユークリッドの互除法は、「2つの数のGCDは、一方を他方で割った余りと小さい方の数のGCDに等しい」という性質を利用します。具体的な流れは以下のとおりです。 a が 0 の場合、b がそのまま GCD と

「卵落としパズル（Egg Dropping Puzzle）」は、動的計画法（DP）を学ぶうえで有名な古典的なアルゴリズム問題です。n階建ての建物とm個の卵が与えられたとき、卵が割れずに落とすことのできる「安全な階」を見つけるために必要な最小の落下回数を求めます。 この問題を解くうえで、次の重要なポイントを押さえておきましょう。 ある階で卵が割れなかった場合、それより下のどの階から落としても割れることはありません。 ある階で卵が割れた場合、それより上のすべての階から落としたときには必ず割れます。 割れてしまった卵は廃棄しなければなりません。一方、割れなかった卵は何度でも再利用できます。 入

C言語やC++では、#defineによるマクロが広く使われています。しかし、従来のマクロには型チェックの仕組みが存在しないという大きな弱点があります。そのため、マクロにはint・float・charなど、どんな型の引数でも渡せてしまいます。次の例で、この挙動を確認してみましょう。例：従来のマクロの場合#include<stdio.h>#define INCREMENT(X) ++Xmain() {    int x = 5; float y = 2.56; char z = A;    printf(I

関数指定子とは CおよびC++には、関数の性質をコンパイラに指示するための「関数指定子（function specifier）」が用意されています。関数指定子を使うことで、その関数がどのような振る舞いをするのかを明示的に宣言できます。 C++：inline 関数指定子を持つ C（C11以降）：_Noreturn 関数指定子を持つ _Noreturnは、その関数が呼び出し元へ制御を返さないことをコンパイラに伝えるための指定子です。本来はexit()やabort()のようにプログラムを終了させる関数に対して使用します。 通常の関数の例 #include<stdio.h> int m

この記事では、バックトラッキングの考え方を応用して、nビットのグレイコードを生成する方法を解説します。 グレイコード（Gray Code）とは、0から 2n − 1 までの各数値をビットパターンで表した際、隣接するパターン同士が必ず1ビットだけ異なるという性質を持つ符号体系です。デジタル回路設計や誤り検出など、さまざまな分野で活用されています。 たとえば n = 2 の場合、グレイコードは (00, 01, 11, 10) となり、これらを10進数に変換すると (0, 1, 3, 2) に相当します。本プログラムでは、生成されたグレイコードの10進数表現を出力します。 アルゴリズム 再帰関数

本記事では、順列に関する興味深いアルゴリズム問題を取り上げます。長さ n の配列が与えられたとき、「各要素の値が、その要素より前にある要素の個数、または後ろにある要素の個数のいずれかと一致する」ような順列が存在するかどうかを判定します。 例として、配列が {2, 1, 3, 3} の場合を考えてみましょう。条件を満たす順列の一つは {3, 1, 2, 3} です。 先頭の 3 … 自分より後ろに3つの要素があることを示しています。 2番目の 1 … 自分より前に1つの要素があることを示しています。 3番目の 2 … 自分より前に2つの要素があることを示しています。 最後の 3 … 自分より前

二分探索（バイナリサーチ）は線形探索よりも優れたアルゴリズムであり、O(log n) の時間で実行できることで知られています。しかし、世の中に出回っている実装の多くには、実は共通の欠陥が潜んでいます。次のような二分探索関数のコードを見てみましょう。 問題のあるコード例 int binarySearch(int array[], int start, int end, int key){     if(start <= end){         int mid =

本記事では、2つの文字列が互いに回転関係にあるかどうかを判定できるプログラムを紹介します。 文字列の回転とは 文字列の「回転」とは、先頭の文字を末尾へ移動させる操作（またはその逆）を繰り返すことで得られる文字列のことです。例として、S1 = HELLO、S2 = LOHEL という2つの文字列を考えてみましょう。HELLO を左方向に3文字分回転させると LOHEL になるため、この2つの文字列は互いの回転であるといえます。 解法のアプローチ この問題は、とてもシンプルな考え方で解決できます。手順は以下の通りです。 1つ目の文字列を、それ自身と連結します。 連結後の文字列の中に、2つ目の文字

ここでは、選択ソートに少し手を加えた改良版アルゴリズム「双方向選択ソート（Two-way Selection Sort）」を紹介します。通常の選択ソートは、配列から最小値（または最大値）を取り出して正しい位置へ配置することで並べ替えを行います。本手法ではこれを発展させ、最大値と最小値を同時に取得し、配列を両端から同時に整列させていきます。それでは、理解を深めるためにアルゴリズムの流れを見てみましょう。 アルゴリズム twoWaySelectionSort(arr, n) begin for i := 0, j := n-1 とし、i を 1 ずつ増加、j を 1 ずつ減少させながら i

この記事では、四次方程式における「根の和」と「根の積」の絶対差を求める方法について解説します。四次方程式と解と係数の関係四次方程式は一般に次のような形で表されます。𝑎𝑥4＋𝑏𝑥3＋𝑐𝑥2＋𝑑𝑥＋𝑒＝0方程式を実際に解いて根を求め、その後で和と積を計算する方法もありますが、四次方程式の求解は複雑で時間がかかるため、あまり効率的とは言えません。そこで役立つのが「解と係数の関係（ヴィエタの定理）」です。これを使えば、方程式を解かずとも根の和と積は係数から直接求められます。根の和 ＝ −𝑏∕𝑎根の積 ＝ 𝑒∕𝑎したがって、求めるべき値は次の式だけで表せます。∣−𝑏∕𝑎 −

ここでは、整数 N の先頭X桁と末尾X桁の絶対差を求める方法を解説します。解き方の流れは以下のとおりです。まず数値の桁数を求め、剰余演算子（%）を使って末尾X桁を取り出します。その後、10で割る操作を繰り返して先頭X桁以外の桁をすべて取り除き、最後に両者の差の絶対値を計算して結果を返します。 例として、N = 568424、X = 2 の場合を考えてみましょう。先頭2桁は「56」、末尾2桁は「24」であるため、差は 56 − 24 = 32 となります。 アルゴリズム diffFirstLastDigits(N, X) begin p := 10^X last := N mod

本記事では、配列に含まれるすべての素数の積と、すべての非素数（合成数）の積との間の絶対差を求める方法を解説します。この問題を解くには、まず各要素が素数かどうかを判定する必要があります。素数判定の代表的な手法の一つとして、「2 からその数の平方根までのどの整数でも割り切れないこと」を確認する方法があります。ある数 n が合成数であれば、必ず √n 以下の約数を持つため、√n まで調べれば十分であり、判定にかかる計算量は O(√n) で抑えられます。すべての要素について素数かどうかを判定したら、それぞれのグループごとに積を計算し、最後に両者の差の絶対値を求めます。アルゴリズムdiffPrimeNo