異端開発室

1. はじめに 再帰は、関数型言語のみならず、あらゆるプログラミングパラダイムにおいて極めて重要な概念である。本稿では、数学的帰納法との関連性を踏まえながら、再帰関数の設計手法について体系的解説していく。 2. 再帰と数学的帰納法 2.1 数学的帰納法の原理 数学的帰納法は、自然数に関する命題を証明するための手法である。その原理は以下の2つのステップから ...

二分木の根ノード root が与えられたとき、中順走査（In-order Traversal）の結果を返す。 中順走査の順序は：左部分木 → 根ノード → 右部分木 二分木ノードの定義 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { ...

二分木の基礎知識（概念、特性、走査方法）について前回の記事で学びました。今回は主にコードの実装に焦点を当てます。 目次 二分木の疑似作成 二分木の走査 二分木のノード数の取得 二分木の葉ノード数の取得 二分木の第Kレベルのノード数の取得 二分木の高さの取得 二分木での要素検索 二分木の疑似作成 なぜ疑似作成と呼ぶのでしょうか。二分木の作成は非常に複雑なプ ...

二分探索木の中間順走査は昇順シーケンスを生成します。問題で与えられた配列は昇順でソートされているため、この配列は二分探索木の中間順走査シーケンスであることが保証されます。 1. 二分探索木の中間順走査が与えられた場合、二分探索木を一意に決定できるか？ 答えは否定的です。もし二分探索木の高さバランスを要求しない場合、任意の数字を根ノードとして選択で ...

1. 関数 コードを書くアプローチは、手続き型プログラミングから関数型プログラミング、そしてオブジェクト指向プログラミングへと進化してきました。 1.1 関数の基本 関数は、特定のタスクを実行するためのコードブロックです。引数を受け取り、結果を返すことができます。 def sample_function(param1, param2): # 関数の処理 pass result = sample_function(1 ...

関数の必要性と利点 プログラムが複雑化し、コード量が増加するにつれて、すべての処理をmain関数内で実装すると、保守性や可読性が著しく低下します。また、同じ処理を複数回書く必要がある場合、コードが冗長になるだけでなく、修正や拡張も困難になります。 こうした問題を解決するには、よく使う処理を関数として独立させ、必要に応じて呼び出すモジュール化プログラミ ...

基本原理： 深さ優先探索は、開始ノードから出発し、一つの分岐を深く進み続けます。葉ノードまたは進めなくなったノードに到達するまで探索を続けます。 探索が葉ノードまたは進めなくなったノードに到達した場合、未探索の前のノードに戻り、他の分岐の探索を続けます。 既に訪問したノードをマークすることで、同じ経路での重複訪問を避けます。 DFSアルゴリズムのス ...

Javaにおけるリスト要素の順列生成 与えられたリストの全要素を使用する順列（全ての可能な並び順）を生成する方法について解説します。ここでは再帰的アプローチを用いた実装を示します。 実装コード import java.util.ArrayList; import java.util.List; public class PermutationGenerator { public static List<List<Integer>> generateAllPerm ...

リンクリストのノード交換 反復解法 ListNode* swapPairs(ListNode* head) { if(!head || !head->next) return head; ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; ListNode* curr = head; while(curr && curr->next) { ListNode* nextNode = curr->next; // ノード交換 prev->n ...

1.バックトラッキングの理論的基礎 1.1バックトラッキングとは何か バックトラッキングは探索アルゴリズムの一種であり、再帰処理に基づいて動作します。 再帰呼び出しの結果としてバックトラッキングが発生するため、再帰があれば必ずバックトラッキングも存在します。 1.2バックトラッキングの性能 バックトラッキングは計算効率が悪いという特徴があります。これは、す ...