Cプログラミング

本記事では、数値Nが素数でない場合に、2から始まる素数を順番に加算していき、最も近い素数を見つけ出す問題について解説します。 入力：N=6出力：11 処理の流れ まず、入力された数値Nが素数かどうかを判定します。例としてN=6を考えてみましょう。6は素数ではないため、最初の素数である2を加算します。すると6+2=8となりますが、8もまた素数ではありません。そこで、2の直後の素数である3を加算すると、8+3=11となります。11は素数であるため、これが出力結果となります。 アルゴリズム 処理の全体像は、以下の擬似コードのとおりです。外側のループで候補となる数kが素数かどうかを判定し、素数であれば

GCD（最大公約数）とは GCDは「Greatest Common Divisor（最大公約数）」の略で、0以外の2つ以上の整数に共通する約数の中で最も大きいものを指します。 例として、48と180の最大公約数を求めてみましょう。 48 = 2 × 2 × 2 × 2 × 3 180 = 2 × 2 × 3 × 3 × 5 両方の数に共通する素因数は「2 × 2 × 3」であるため、最大公約数は次のように計算できます。 最大公約数 = 2 × 2 × 3 = 12 問題の概要 本記事で扱う問題では、指定された値Kを最大公約数とする要素を含むN行の数列を出力します。各行に含まれるどの2つの数

プログラミングの定番問題の一つに、「2つの整数 x と y が与えられたとき、それらに共通する約数(公約数)のうち、小さい方から数えて k 番目の値を出力する」というものがあります。この記事では、その考え方と具体的な実装方法をわかりやすく解説します。問題の例たとえば x = 9、y = 18、k = 2 が入力として与えられた場合を考えてみましょう。9 の約数 : 1, 3, 918 の約数 : 1, 2, 3, 6, 9, 18公約数 : 1, 3, 9→ 2番目の公約数は「3」このように、まず両方の数の約数を確認し、共通して現れる値を小さい順に並べれば、k番目の公約数が求まります。なお、最

ニューマン・コンウェイ数列とはニューマン・コンウェイ数列(Newman-Conway Sequence)は、以下のような整数列を生成するために用いられる数列です。1 1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10 11 12この数列は、漸化式によって定義される点が大きな特徴です。各項は、それ以前の項を再帰的に参照して求められます。生成に使う漸化式n番目のニューマン・コンウェイ数列を求めるための式は次のとおりです。P(n) = P(P(n - 1)) + P(n - P(n - 1))ただし、P(1) = P(2) = 1初期条件として最初の2項が1であることが決まっており

k個の要素からなる配列が与えられたとき、プログラムはその中からn個（ここではk個）の最小要素を見つけ出し、配列に現れた元の順序のまま出力する必要があります。例えば、入力が arr[] = {1, 2, 4, 3, 6, 7, 8} で k=3 の場合、配列の中から3つの最小要素を元の順序で、すなわち 1、次に 2、そして 3 の順に表示します。入力 : arr[] = {1, 2, 4, 3, 6, 7, 8}, k=3 出力 : 1, 2, 3アルゴリズムこの問題は、挿入ソートの考え方を応用することで効率よく解くことができます。基本的な発想は次のとおりです。配列の先頭k個を「暫定の最小k要素

この記事では、「a ＋ b ≤ n」かつ「a ＋ b が x で割り切れる」という2つの条件を同時に満たす「a」の値を求める方法を解説します。 具体的には、b、x、n の3つの値が与えられたとき、次の条件に当てはまるすべての a を出力するプログラムを作成します。 a ＋ b が n 以下であること a ＋ b が x で割り切れること（x の倍数であること） アルゴリズム 手順は以下の通りです。 START Step 1 -> 変数 b=10、x=9、n=40、flag=0、divisible を宣言する Step 2 -> divisible = (b / x + 1) *

ここでは、与えられたパターンを再帰的アプローチを用いて出力する方法について解説します。再帰関数とは、自分自身を複数回呼び出す関数のことです。1つのプログラムの中に、いくつでも再帰関数を定義することができます。ただし、再帰関数を使う際の課題は、その計算の複雑さにあります。呼び出しが深くなりすぎるとパフォーマンスに影響を与えるため、終了条件を正しく設計することが重要です。アルゴリズム 0 ならば pattern(n-1) を呼び出す IF 終了 printpattern(n) を呼び出す 改行（\n）を出力する End STOPサンプルコード#include

問題の概要今回は行列（マトリクス）に関する確率問題を取り上げます。長方形の行列が与えられ、現在のセルからは上下左右の4方向へ等しい確率で移動できるものとします。このとき、位置 M[i, j] から N 回移動した後に、行列の内側に留まっている確率を求めるのが目的です。解法のアプローチ：DFSを活用この問題は、深さ優先探索（DFS）の考え方を使って解くことができます。具体的には、現在のセルから移動可能な4方向それぞれに対して再帰的に探索を行い、残りの移動回数を1ずつ減らしながら確率を計算していきます。4つの方向の移動確率はすべて等しいため、各方向は全体の確率に対して 0.25 ずつ寄与します。再

この記事では、興味深いプログラミングの問題を紹介します。ネストされた二重ループを含む2つのコード断片を比較し、どちらがより速く実行されるかを考えてみましょう。なお、ここではコンパイラによる最適化は行われないものと仮定します。 セグメント1 for(int i = 0; i < 10; i++){ for(int j = 0; j<100; j++){ //code } } セグメント2 for(int i = 0; i < 100; i++){ for(int j = 0; j<10; j++){ //code

この記事では、「パンケーキソート（Pancake Sort）」と呼ばれるもう一つのソート問題について解説します。この問題は非常にシンプルです。与えられた配列をソートすることが目的ですが、使用できるのは rev(arr, i) という一つの操作だけです。この操作は、配列 arr の先頭（0番目）から i 番目までの要素を反転させるものです。パンケーキソートの発想は選択ソートに似ています。最大の要素を繰り返し配列の末尾に移動させ、そのたびに扱う配列のサイズを一つずつ減らしていくことで、全体をソートします。それでは、アルゴリズムの流れを見ていきましょう。アルゴリズムpancakeSort(arr,

今回は興味深いパズルを紹介します。次のようなプログラムがあったとき、出力はどうなるか、そしてその理由は何かを考えてみてください。 例 #include<iostream> using namespace std; int main() { int x = 0xab; ~x; cout << hex << x; } さて、出力はどうなるでしょうか？「~x」はビット反転（1の補数）演算を行っています。では、反転された結果が16進数で表示されるのでしょうか？ 実際の出力は次のとおりです。 出力 ab 結果はまったく変わりません。では、なぜこ

「迷路のネズミ問題」は、バックトラッキング（探索の戻り）アルゴリズムを学ぶ上で最もよく知られた古典的な問題の一つです。この記事では、その問題に少し変化を加えたバージョンを扱います。N×N の迷路 M が与えられ、スタート地点は左上隅の M[0, 0]、ゴール地点は右下隅の M[N – 1, N – 1] とします。ネズミはスタート地点に配置され、私たちの目標は、ネズミがスタートからゴールまで到達できる経路を見つけることです。ここでのバリエーションは「ネズミがジャンプできる」という点です。ただし、以下の制約があります。ネズミは右方向または下方向にのみ移動できます。セルの値が 0 の場合、そのセル

問題概要今回は興味深い問題を取り上げます。サイズn（n > 3）のバイナリ配列が与えられているとします。値が1（true）は「アクティブ」状態を、0（false）は「非アクティブ」状態を表します。さらに、日数を表す整数kも与えられ、k日後における各セルの状態を求めることが目的です。毎日の更新ルールは次のとおりです。i番目のセルは、その左隣と右隣のセルの状態が異なる場合にアクティブ（1）となり、同じ場合には非アクティブ（0）となります。なお、最も左端と右端のセルには外側に隣接するセルが存在しないため、これらは常に0として扱われます。具体例例を使って動作を確認してみましょう。配列が {0,

本記事では、連結リスト（リンクリスト）に格納された数値に対して1を加算する方法について詳しく解説します。この手法では、数値の各桁が連結リストの各ノードに一つずつ格納されます。例えば、数値が512の場合、以下のように表現されます。512 = (5)-->(1)-->(2)-->NULLこのリストをインクリメント関数に渡すと、1を加算した結果として新しいリストが返されます。ここでは、C++のSTL（Standard Template Library）が提供するlistコンテナを使用して実装します。まず、処理の流れを理解しやすくするために、アルゴリズムを見ていきましょう。アルゴリズ

この記事では、興味深い問題を一つ取り上げます。それは「与えられた数値に1を加算する」というものです。これは非常に単純な作業ですが、ここでは数値を配列として扱う点がポイントになります。数値の各桁は、配列の各要素として格納されます。たとえば、数値が512であれば、{5, 1, 2} のように保存されます。さらに、この加算処理を再帰的アプローチで実装する必要があります。それでは、アルゴリズムを見ていきましょう。アルゴリズムincrement(arr, n, index)初期状態では、indexのデフォルト値は0です。begin if index < n, then if

この記事では、2つの配列の要素を加算し、その結果を別の配列に格納するという問題を扱います。ただし、単純な加算ではなく、以下のような制約条件に従う必要があります。 加算は、両方の配列の0番目のインデックス（先頭）から開始する 和が2桁以上の数になった場合は、桁ごとに分割し、各桁を順番に出力配列に格納する 長い方の入力配列に残った要素は、そのまま出力配列に格納する それでは、処理の流れを理解するために、アルゴリズムから見ていきましょう。 アルゴリズム addArrayConstraints(arr1, arr2) 開始 空のベクトル out を定義する i := 0 i

概要 本記事では、n個の数値を含む配列が与えられたとき、そのすべての要素を連結して1つの整数を作った場合に、その数が3で割り切れるかどうかを判定する方法を解説します。 例えば、配列の要素が {15, 24, 23, 13} である場合、これらを順に並べて「15242313」という整数を作ることができます。この数は3で割り切れます。 アルゴリズムのポイント 3の倍数の判定には、「ある数の各桁の数字の合計が3で割り切れるならば、その数自身も3で割り切れる」という有名な性質を利用します。 配列の要素を連結してできる数の各桁の和は、元の各数値の桁の和と一致します。また、任意の整数は「その値を3で割った

本記事では、任意の整数 n の階乗（n!）の結果に含まれる「末尾のゼロ」の個数を効率的に計算する方法を解説します。 例えば、n = 5 の場合、5! = 120 となるため、末尾のゼロは 1 個です。また、20! = 2432902008176640000 の場合、末尾のゼロは 4 個になります。 素朴なアプローチとその問題点 最も単純な方法は、実際に階乗を計算してから末尾のゼロを数えることです。しかし、この方法では n が大きくなると階乗の値が急激に巨大化し、オーバーフローしてしまうため実用性がありません。 そこで、数学的な性質を利用した別のアプローチを採用します。階乗の結果に末尾のゼロが現

この記事では、別々の連結リスト（リンクリスト）に格納された2つの数値を加算する方法について解説します。連結リストでは、数値の各桁が1つのノードとして格納されます。例えば、512という数値は以下のように表現されます。512 = (5)-->(1)-->(2)-->NULLこのような形式の2つのリストが与えられたとき、それらを足し合わせて合計を求めるのが課題となります。ここでは、C++のSTLに含まれるstd::list（双方向連結リスト）を使用します。まず、処理の流れをつかむためにアルゴリズムから見ていきましょう。アルゴリズムaddListNumbers(l1, l2)Begi

ここでは、シンプルな問題を取り上げます。与えられたリスト（配列）の中から、回文数（上から読んでも下から読んでも同じになる数）をすべて見つけ出す方法を解説します。アプローチは非常に簡単です。リストから各数値を順番に取り出し、その数が回文であるかどうかを判定します。回文であれば、その数を出力するだけです。アルゴリズムgetAllPalindrome(arr, n)Begin for each element e in arr, do if e is palindrome, then print e end if done En