Cプログラミング

0より大きい数値は正の数、0より小さい数値は負の数と呼ばれます。この正負の概念は数論において極めて重要であるだけでなく、プログラミングの世界でも同様です。大小の比較や符号の判定など、多くの計算処理はこの概念を基礎として成り立っています。入力: 0 出力: 0 はゼロです解説条件分岐（if文）を使うことで、任意の数値が0より大きいか、0より小さいかを順番にチェックできます。両方の条件に当てはまらない場合は、その数値がちょうど0であることになります。この仕組みにより、数値を「正」「負」「ゼロ」の3つに分類することが可能です。サンプルコード#include <iostream> usin

このプログラムは、3つの数値を受け取り、その中で最も大きい数値（最大値）を見つけます。3つの数値を互いに比較することで、どの数値が最大なのかを判定するシンプルな仕組みです。 入力：a=2、b=4、c=7 出力：7 最大の数値 処理の流れ（解説） このプログラムでは、if文だけを使って最大値を求めます。処理の流れは以下のとおりです。 まず「a」と「b」を比較します。 aがbより大きい場合 → 次に「a」と「c」を比較し、aが大きければaが最大値、そうでなければcが最大値になります。 aがb以下の場合 → 次に「b」と「c」を比較し、bが大きければbが最大値、そうでなければcが最大値になります

概要 本記事では、10進数（基数10）で表された整数を2進数（基数2）に変換するC言語のプログラムを解説します。整数は32ビットであると仮定し、対象の数値を基数である2で繰り返し割ることで変換を行います。この変換処理は、コンピュータが整数値をバイト列（バイナリデータ）へ変換する際にも使われる、非常に基本的な仕組みです。 入力： 10 出力： 1010 アルゴリズムの解説 ここでは、10進数の「10」を例に、変換の具体的な手順を見ていきましょう。 10 を 2 で割ると余りは 0。よって「0」を記録します。 続いて 10 ÷ 2 = 5 を新しい数値として扱います。 5 を 2 で割ると余り

順列（nPr、P(n,r) とも表記されます）は、n 個の要素の中から r 個を選んで一列に並べる方法が何通りあるかを求めるための数学的な公式です。P(n, r) を求める公式は次のように表されます。 P(n, r) = n! / (n − r)! n 個の要素からなる集合に対する順列の総数は n! で与えられます。ここで「!」は階乗（1 からその数までの積）を意味します。 入力：n=5; r=4; 出力：120 計算の流れ n=5、r=4 の場合、次のように計算できます。 P(5, 4) = 5! / (5−4)! = 120 / 1 = 120 5! = 1 × 2 × 3 × 4 × 5

連結リストによる数値の表現とは連結リストで数値を表現する場合、リストの各ノードが数値の1桁に対応します。リストの先頭ノードが最上位の桁を、末尾ノードが最下位の桁を保持する構造になっています。例えば、数値「202345」は連結リストでは (2→0→2→3→4→5) のように表されます。このように表現された数値に1を加えるには、まず最下位の桁の値を確認します。その値が9未満であれば単純に1を足すだけで済みますが、9であった場合は繰り上がりが発生するため、一つ前の桁（上位の桁）の処理へと進む必要があります。具体例例として「1999」という数値を考えてみましょう。これは連結リストでは (1→9→9→9

BST（二分探索木：Binary Search Tree）は二分木の一種で、「根の値より小さい値を持つノードがすべて左側に、大きい値を持つノードがすべて右側に配置される」という性質を持つデータ構造です。本記事で扱うのは、そのBSTに対して「現在のノードより大きい値をすべて加算する」という古典的なアルゴリズム問題です。つまり、BST内の各ノードについて、そのノードの値より大きい値を持つすべてのノードの合計を、そのノード自身の値に足し合わせていく処理を行います。問題の定義与えられた二分探索木（BST）の各ノードに対して、そのノードより大きい値を持つすべてのノードの合計値を加算してください。入力例

この問題では、2つの配列の要素を加算する際に特定の制約が設けられており、その制約に基づいて加算結果の格納方法が変わります。2つの配列 a[] と b[] の対応する要素同士の合計を、3つ目の配列 c[] に格納していきます。ただし、格納される各要素は必ず1桁の数値でなければならず、もし合計が2桁以上になった場合は、その数値を桁ごとに分割して個別の要素として格納します。例えば、ある要素の合計が27となった場合、3つ目の配列には「2」と「7」という2つの要素として保存されます。Input: a[] = {1, 2, 3, 7, 9, 6}      

0-1 BFS（二値重みグラフの最短経路問題）とはいくつかの頂点と辺から構成されるグラフを考えます。このグラフの各辺には0または1の二値のみの重みが割り当てられています。始点となる頂点が与えられたとき、始点から他のすべての頂点への最短距離を求めるのが本記事の目的です。通常の幅優先探索（BFS）は、すべての辺の重みが同一である場合に有効な手法です。しかし、重みが0と1で混在している場合、単純なBFSでは正しい最短経路を求めることができません。そこで登場するのが0-1 BFSです。このアルゴリズムでは、両端キュー（deque）を使用して頂点を管理します。各ステップで最適な距離条件をチェックしながら

オシリス数（Osiris Number）とは？オシリス数とは、自分自身の桁の数字から作られる部分順列の総和が、元の数とちょうど等しくなる特殊な数のことです。例として「132」という数を見てみましょう。この数の各桁から作られる2桁の組み合わせは {12 + 21 + 13 + 31 + 23 + 32} ですが、これらをすべて足し合わせると132になります。つまり、132はオシリス数だということです。この記事では、与えられた3桁の整数がオシリス数かどうかを判定するプログラムをC++で紹介します。判定のアプローチ一見複雑そうに思えますが、この問題は非常にシンプルに解けます。ポイントは、3桁の数にお

ここに、サイズが4バイト（32ビット）の整数型変数と、サイズが8バイトのポインタ変数があると仮定します。このとき、以下のC++コードを実行すると、どのような出力になるでしょうか？ サンプルコード #include<iostream> using namespace std; main() {    int a[4][5][6];    int x = 0;    int* a1 = &x;    int** a2 = &a1;    int*** a3 = &am

問題の概要下図のようなグラフを考えます。これは有名なピーターセングラフです。頂点には0から9までの番号が振られており、各頂点には特定の文字が割り当てられています。このグラフ上のウォーク（歩行）Wを考えます。WはL個の頂点を使用します。長さLの文字列SがウォークWによって実現されるとは、Wで訪問した頂点に割り当てられた文字の並びがSと一致することを指します。なお、同じ頂点を何度訪問しても構いません。例えば、文字列Sが「ABBECCD」の場合、これはウォーク(0, 1, 6, 9, 7, 2, 3)によって実現されます。私たちのタスクは、与えられた文字列を実現するウォークを見つけることです。そのよ

LCS問題とは本記事では、LCS（最長共通部分列：Longest Common Subsequence）問題を解くための、空間計算量を最適化したアプローチを紹介します。LCSとは、2つの文字列に共通して現れる部分列のうち、最も長いものを指します。例えば、「BHHUBC」と「HYUYBZC」という2つの文字列の場合、最長共通部分列の長さは4になります。従来の動的計画法（DP）によるアプローチでもLCSは求められますが、この方法では大きなメモリ領域が必要になります。具体的には、1つ目の文字列の文字数をm、2つ目の文字列の文字数をnとすると、m×nのサイズを持つ2次元テーブルを用意しなければなりませ

本記事では、クイックソートの改良版である「3-Wayクイックソート（スリーウェイクイックソート）」について詳しく解説します。基本的なクイックソートでは、まずピボット（基準値）となる要素を1つ選び、そのピボットを境に配列を分割します。その後、ピボットの左側と右側にある部分配列それぞれに対して、再帰的に同じ処理を繰り返すことで全体を整列させます。 一方、3-Wayクイックソートも同様の考え方に基づいていますが、配列を3つの領域に分割する点が大きな特徴です。配列 arr[1 to n] は以下のように分けられます。 arr[1 to i]：ピボットより小さい要素の集まり arr[i + 1, j

今回は、C言語のパズル問題を1つ紹介します。2つの数値「48」と「96」が与えられたとしましょう。ここで、1つ目の数値を2つ目の数値の後ろに連結して、「9648」という結果を得たいと思います。 問題の条件 ただし、この問題には厳しい制約があります。 論理演算を使用してはならない 算術演算（加算・乗算など）を使用してはならない 文字列に関する操作を使用してはならない 定義済みのライブラリ関数も呼び出せない 一見すると不可能に思えますが、実はとても簡単に解決できるのです。 解決策：トークン連結演算子（##） 鍵となるのが、C言語のトークン連結演算子（Token Pasting Operator

ポリモーフィズム（多態性）とは、同じインターフェースでありながら、扱う型に応じて異なる動作を実現できるオブジェクト指向プログラミングの重要な概念です。ポリモーフィズムには主に以下の4つの種類があります。アドホック多相（Ad-Hoc Polymorphism）包含多相（Inclusion Polymorphism）パラメトリック多相（Parametric Polymorphism）型強制多相（Coercion Polymorphism）1. アドホック多相（オーバーロード）アドホック多相は「オーバーロード（多重定義）」とも呼ばれます。同じ名前の関数が、引数の型に応じて異なる動作を行えるようにする

本記事では、二分探索木（BST）の各ノードに対して、「そのノードより大きい値を持つすべてのノードの値の合計」を加算して更新するという興味深い問題を取り上げます。処理前後の木は、以下の図のように変化します。例えば、元の木で値 50 のノードは、それより大きい値（60、70、80）の合計 210 を加算して 260 に更新されます。一方、最大値である 80 のノードは、それより大きい値が存在しないため 80 のまま変わりません。アルゴリズムの考え方この問題は、通常の通り順（inorder）走査を逆にした「右部分木 → 根 → 左部分木」の順序で木を走査することで、効率的に解くことができます。この順

C/C++のプリプロセッサディレクティブとは？ CやC++のソースコードには、#（シャープ）記号で始まる行が見られることがあります。これらは「プリプロセッサディレクティブ」と呼ばれるもので、コードのコンパイル前に実行される前処理（プリプロセス）の段階で処理されます。 本記事では、特によく使われる以下の3種類のプリプロセッサディレクティブについて詳しく解説します。 条件付きコンパイル（Conditional Compilation） 行制御（Line Control） エラーディレクティブ（Error Directive） 1. 条件付きコンパイル（#ifdef / #elif / #el

本記事では、第n項が n2 − (n−1)2 で表される級数の総和を求める方法を解説します。級数の一般項は次のように定義されます。 Tn = n2 − (n−1)2 級数の形を確認する n = 1, 2, 3, … と順に代入すると、この級数は次のように展開されます。 S = 1 + 3 + 5 + 7 + … つまり、これは「最初のn個の奇数」を足し合わせた級数です。 一般項の簡単化 一般項を展開して整理すると、 Tn = n2 − (n2 − 2n + 1) = 2n −

本記事では、マルチスレッド環境を活用して行列（マトリックス）の加算と減算を行う方法を解説します。C/C++では、POSIXスレッド（pthread）を使用することで、複数のスレッドを同時に実行でき、大規模な行列演算の処理時間を短縮できます。 基本的な考え方 ここでは2つの行列AとBを用意し、それぞれのサイズは m × n とします。各スレッドが担当する行を受け持ち、その行に対して加算または減算を計算します。サンプルコードでは、コア数を3（CORE=3）とし、加算用に3スレッド、減算用に3スレッドの合計6スレッドを生成して、行列全体を3分割して並列処理しています。 サンプルコード #incl

問題の概要ここでは、配列に関する興味深い問題を扱います。n 個の要素からなる配列と、目標となる合計値 S が与えられます。このとき、次の条件を満たす値 K を配列の中から見つける必要があります。「配列内の K より大きい要素をすべて K に置き換えたとき、最終的な配列の全要素の合計がちょうど S と等しくなる」。もし条件を満たす K が存在しない場合は、-1 を返します。例として、配列 {12, 6, 3, 7, 8} と合計値 15 が与えられたケースを考えてみましょう。このときの出力は 3 になります。なぜなら、3 より大きい要素をすべて 3 に置き換えると、配列は {3, 3, 3, 3