C++

整数値と変数 x が与えられ、それらをもとに二分木を構築し、ノードの値の合計が指定値 x と等しくなるペアの個数を求めるのが課題です。 例 入力 int x = 5 の場合、値を入力して作成される二分木は次のようになります − 出力 合計が指定値 x と等しい二分木内のペアの数: 2 説明 整数値の配列から二分木を作成し、 合計が指定値 x(この場合は 5)と等しくなる ペアが木の中に存在するかどうかを確認します。 形成されるペアは (2, 3) と (1, 4) の 2 つです。 入力 int x = 8 の場合、値を入力して作成される二分木は次のようになります − 出力 合計が指定値

問題概要二分木の中順走査（インオーダー走査）の結果が格納された整数型配列 arr[] が与えられます。この配列をもとに「特殊な二分木」を構築することが本記事の目的です。ここでいう特殊な二分木とは、根ノードの値が、その左の子ノードおよび右の子ノードの値よりも常に大きいという条件を満たす二分木を指します。入力例と出力例入力1int arr[] = {10, 20, 28, 40, 32, 31, 30}上記の中順走査から構築される特殊な二分木は以下の通りです。解説整数値の配列、すなわち木の中順走査が与えられています。これをもとに構築される特殊な木は「10, 20, 28, 40, 32, 31,

入力として二分木が与えられ、その内部に部分木として存在する二分探索木（BST：Binary Search Tree）の個数を求めるのが本記事の目的です。二分探索木とは、次の性質を満たす二分木のことです。左の子ノードの値は、親ノード（根）の値より小さい右の子ノードの値は、親ノード（根）の値より大きい入力例1入力された値から構築される二分木は以下の通りです。出力Count the Number of Binary Search Trees present in a Binary Tree are: 2解説整数値の配列から二分木を構築し、その中に二分探索木が存在するかどうかを確認します。すべての葉ノ

はじめにC++で配列から特定の要素を削除する場合、「検索」と「詰め替え（シフト）」をどのタイミングで行うかによって、主に2つのアプローチがあります。1つは検索とシフトを別々に行う「2回の走査」、もう1つは両方を同時に処理する「1回の走査」です。ここでは、それぞれの考え方と実装方法をサンプルコード付きで解説します。その1：2回の走査で削除するまず、元の配列と、検索・削除したい要素を定義します。int ele = 5; int arr[] = {1, 2, 3, 4};次に、forループで配列を先頭から走査し、目的の要素が格納されている位置を特定します。for (i = 0; i < len

C++では、指定したインデックス範囲 [L–R] に含まれる要素を配列から効率的に取り除くことができます。本記事では、その基本的な考え方と具体的な実装方法を解説します。アルゴリズムの考え方まず、元の配列と削除対象となる排他的な範囲を定義し、配列の長さを求めます。int arr[] = { 2,4,6,8,10,12,14,16,18,20}; int L = 2, R = 6; int length = sizeof(arr) / sizeof(arr[0]);次に、配列を先頭から順に走査します。インデックス i が L 以下、または R 以上である場合（つまり削除範囲の外側にある場合）は、変

C++で値がxの葉ノードを削除するには？ 本記事では、C++を使って二分木から「値がxと等しい葉ノード（リーフノード）」を削除する方法を解説します。ノード構造体の定義から、ノード生成用の関数、再帰的な削除処理、そして結果の表示まで、順を追って見ていきましょう。 1. ツリーノード構造体の定義 まず、ノードのデータと左右の子ノードへのポインタを保持する、木のノードを表す構造体を定義します。最初に作成されるノードはルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。 struct Node { int data; struct Node *leftChild

C++で二分木を扱う際、「特定の値kを持つ葉ノード（リーフノード）だけを削除したい」というケースがあります。本記事では、再帰処理を活用して値kの葉ノードを削除する方法を、サンプルコードとともにわかりやすく解説します。 1. ノード構造体の定義 まず、データと左右の子ノードへのポインタを保持する、ツリーノードを表す構造体を定義します。最初に生成したノードがルートノードとなり、それ以降に生成されるノードは子ノードとして扱われます。 struct Node { int data; struct Node *leftChild, *rightChild; }; 2. 新しいノードを生成

本記事では、C++を使って単方向連結リスト（Singly Linked List）の中央にあるノードを削除する方法を解説します。まずは基本となるノード構造体の定義から始め、ノード生成・削除・表示のための各関数を実装していきましょう。1. ノード構造体の定義最初に、データ（data）と次のノードへのポインタ（next）を持つ連結リストのノードを定義します。struct Node { int data; struct Node* next; };2. ノードを生成する createNode 関数次に、createNode(int data) 関数を作成します。この関数は int 型

本記事では、C++におけるリンクリスト（連結リスト）の先頭からM個のノードを残し、その直後のN個のノードを削除するアルゴリズムについて解説します。リンクリストの定義まず、データ（data）と次のノードへのポインタ（next）を持つリンクリストの構造体を定義します。struct Node {    int data;    struct Node* next; };リスト生成用関数 createList次に、Nodeへのダブルポインタとint型の値を受け取る createList(Node **headPtr, int new_data) 関数を作成します

C++では、デストラクタとdeleteキーワードを組み合わせることで、二分木（バイナリツリー）全体を再帰的に解放できます。まずは、int型のデータと左右の子ノードへのポインタを持つクラスで二分木を定義してみましょう。ここでは、クラスのすべてのメンバをpublicとしています。class btree_node {    public:       int data;       btree_node* leftChild;       btree_node* rightChild; };

「01010110011」のようなバイナリ文字列に対して、隣接する「01」または「10」を繰り返し削除することを考えます。「01」や「10」が文字列から完全になくなるまで削除を行うとき、最大で何回削除できるかを求めるのが本問題です。この記事では、C++による効率的な解法をわかりやすく解説します。 アルゴリズムのポイント 「01」または「10」を1回削除するたびに、「0」と「1」が必ず1文字ずつ減少します。つまり、削除できる最大回数は文字列に含まれる「0」の個数と「1」の個数のうち小さい方（min）に等しくなります。この性質を利用すれば、実際に削除操作をシミュレートする必要はなく、各文字の出現回

デムロ数（Demlo Number）とはデムロ数とは、11…1 のような形の数（レピュニット）を2乗したときに生成される回文数のことです。ただし、対象となる数は10桁未満である必要があります。例えば、以下のように美しく対称的な数字の並びが現れます。11 × 11 = 121111 × 111 = 123211111 × 1111 = 1234321C++での実装手順まず、文字列型の変数を宣言します。string demNum = 1111; string square = ;続いて、demNum 文字列の長さ分だけループ処理を行います。ループ内では、インデックス値 i を文字に変換し、squa

正七角形（すべての辺と角度が等しい7つの辺を持つ多角形）の対角線の長さは、次の公式を使って求めることができます。対角線 = 2 × 辺 × sin(900° ÷ 14)ここで、sin(900° ÷ 14) = sin(64.29°) の値はおよそ 0.9 となるため、この式は「2 × 辺 × 0.9」と簡略化できます。つまり、正七角形の対角線の長さは、辺の長さの約1.8倍になるということです。例それでは、辺の長さから正七角形の対角線を求めるC++の実装例を見てみましょう。#include <iostream> using namespace std; int main(){ &nb

二分木における削除処理の概要二分木からのノード削除は、削除したいノードを「木の中で最も深い位置にある右端のノード」で置き換えることによって行われます。この手法では、まず削除対象ノードの値を最深ノードの値で上書きし、その後、最深ノードを木から切り離してメモリを解放します。まず、データ本体と左右の子ノードへのポインタを保持する、ツリーノードを表す構造体を定義します。最初に作成されたノードはルートノードとなり、それ以降に作成されたものは子ノードとして扱われます。struct Node {   int data;   struct Node

二分木の密度とは、木のサイズ（ノードの総数）を高さで割った値として定義されます。二分木の密度 ＝ サイズ ÷ 高さノード構造体の定義まず、データおよび左右の子ノードへのポインタを保持する、木のノードを表す構造体を定義します。最初に作成されるノードがルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。struct Node { int data; struct Node *leftChild, *rightChild; };ノード生成関数（createNode）次に、createNode(int data) 関数を作成します。この関数はint型の値を受け取り

N分木（N-Aryツリー）とは、各ノードが最大N個の子ノードを持つことができる木構造です。この記事では、C++を使ってN分木の深さ（ルートノードから最も深い葉ノードまでの階層数）を再帰的に求める方法を解説します。ツリーノードを表す構造体の定義まず、文字型のキーと子ノードへのポインタを格納するvectorを持つ、木のノードを表す構造体を定義します。struct Node{    char key;    vector<Node *> children;};ノード生成用の関数を作成する次に、キー値を受け取っ

二分木の中で「奇数レベル」に存在する葉ノードのうち、最も深い位置にあるものの深さを求めるアルゴリズムを、C++のコード例とともに解説します。ツリーノード構造体の定義まず、int型のキーと左右の子ノードへのポインタを持つ、ツリーノードを表す構造体を定義します。最初に作成されたノードはルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。struct Node { int data; struct Node *leftChild, *rightChild;};createNode関数の実装次に、createNode(int key)関数を作成します。この関数はint

Disarium数とは？各桁の数字を、その桁の位置（最上位を1として左から順に1、2、3…）でべき乗し、その合計が元の数そのものと等しくなるような数をDisarium数（ディザリウム数）と呼びます。例えば、518は次のように計算できます。5^1 + 1^2 + 8^3 = 5 + 1 + 512 = 518合計が元の数と一致しているため、518はDisarium数です。他にも 89、135、175、598 などがDisarium数の例として知られています。noOfDigits関数：桁数を求めるnoOfDigits(int num) 関数は、引数として受け取った数値の桁数を返します。数値を10で

行列式とは？行列式は正方行列に対してのみ計算できる値です。1行目の各要素に、それに対応する余因子（小行列）の行列式を掛け合わせ、符号を交互につけながら足し合わせることで最終的な結果が得られます。この手法は「余因子展開（cofactor expansion）」と呼ばれます。3×3の行列Aに対する行列式は、次のように表されます。$$A = \begin{bmatrix}a & b & c\\d & e & f \\g & h & i\end{bmatrix}$$$$|A| = a(ei-fh) - b(di-gf) + c(dh-eg)$$この記事では、C++を使って再帰処理により任意の次元の正方

概要本記事では、2つの端点 (x1, y1) と (x2, y2) が与えられたときに、その2点を結ぶ直線が通過する単位面積の正方形（マス）の数を求める方法を解説します。アルゴリズム直線が通過するマスの数を求めるには、次の値を計算します。x座標の差（dx）＝ x2 − x1y座標の差（dy）＝ y2 − y1答え ＝ dx + dy − gcd(dx, dy)つまり、dx と dy の合計から、両者の最大公約数（GCD）を引いた値が求める結果となります。unitSquares(int x1, int y1, int x2, int y2) 関数は、4つの値 x1、y1、x2、y2 を引数として