C++によるO(nlogn)の実装で最も近い点のペアを見つける方法
アルゴリズムの概要は以下の通りです。入力として、二次元平面上の点の集合が与えられるとします。まず、入力点集合をx座標に基づいてソートします。これにより、後の処理で点の組み合わせを効率的に処理することができます。>>More
Home > 分割統治法
Karatsubaのアルゴリズムを使った高速な整数乗算
まず、Karatsubaのアルゴリズムの基本的な考え方を説明します。大きな整数AとBを乗算する場合、それぞれを2つの部分に分割します。例えば、AをA1とA0に、BをB1とB0に分割します。ここで、A1とB1はAとBの上位の桁、A0とB0は下位の桁となります。>>More
分割統治法を使用したべき乗の計算方法
#include <iostream> double power(double x, int n) { if (n == 0) { return 1.0; // x^0 = 1 } if (n < 0) { return 1.0 / power(x, -n); // x^-n = 1 / x^n } double halfPower = power(x, n / 2); // x^(n/2) if (n % 2 == 0) { return halfPower * halfP>>More