新・アルゴリズムとデータ構造入門 Java編15:有理数二分探索

import java.util.function.Function;

class Rational { // 分数型
    int n; // 分子
    int d; // 分母

    Rational(int n, int d) {
        this.n = n;
        this.d = d;
    }
}


public class Main {
    static Rational rationalSearch(Function<Rational, Integer> f) {
        Rational l = new Rational(0, 1);
        Rational r = new Rational(1, 0);

        while (true) {
            Rational m = new Rational(l.n + r.n, l.d + r.d);
            int res = f.apply(m);
            if (res == 0) {
                return m;
            }
            if (res == -1) {
                l = m;
            } else {
                r = m;
            }
        }
    }

    static int f(Rational x) {
        int d = 3 * x.n - 2 * x.d;
        if (d > 0) // 超えている
            return 1;
        if (d < 0) // 足りない
            return -1;
        return 0;
    }

    public static void main(String[] args) {
        Rational x = rationalSearch(Main::f);
        System.out.printf("%d/%d\n", x.n, x.d);
    }
}

import java.util.function.Function;

class Rational { // 分数型
    int n; // 分子
    int d; // 分母

    Rational(int n, int d) {
        this.n = n;
        this.d = d;
    }
}


public class Main {
    static Rational rationalSearch(Function<Rational, Integer> f) {
        Rational l = new Rational(0, 1);
        Rational r = new Rational(1, 0);

        while (true) {
            Rational m = new Rational(l.n + r.n, l.d + r.d);
            int res = f.apply(m);
            if (res == 0) {
                return m;
            }
            if (res == -1) {
                l = m;
            } else {
                r = m;
            }
        }
    }

    static int f(Rational x) {
        int d = 3 * x.n - 2 * x.d;
        if (d > 0) // 超えている
            return 1;
        if (d < 0) // 足りない
            return -1;
        return 0;
    }

    public static void main(String[] args) {
        Rational x = rationalSearch(Main::f);
        System.out.printf("%d/%d\n", x.n, x.d);
    }
}

import java.util.function.Function;
import java.util.Scanner;

class Rational { // 分数型
	int n; // 分子
	int d; // 分母

	Rational(int n, int d) {
		this.n = n;
		this.d = d;
	}
}


public class Main {
	static Rational rationalSearch(Function<Rational, Integer> f) {
		// ここにコードを追加
	}

	static int a, b;

	static int f(Rational x) {
		int d = a * x.n + b * x.d;
		if (d > 0)
			return 1;
		if (d < 0)
			return -1;
		return 0;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();

		Rational x = rationalSearch(Main::f);
		System.out.printf("%d/%d\n", x.n, x.d);
	}
}

import java.util.function.Function;
import java.util.Scanner;

class Rational { // 分数型
	int n; // 分子
	int d; // 分母

	Rational(int n, int d) {
		this.n = n;
		this.d = d;
	}
}


public class Main {
	static Rational rationalSearch(Function<Rational, Integer> f) {
		// ここにコードを追加
	}

	static int a, b;

	static int f(Rational x) {
		int d = a * x.n + b * x.d;
		if (d > 0)
			return 1;
		if (d < 0)
			return -1;
		return 0;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		a = sc.nextInt();
		b = sc.nextInt();

		Rational x = rationalSearch(Main::f);
		System.out.printf("%d/%d\n", x.n, x.d);
	}
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「有理数二分探索」

引数の値によって、その値が大きければ 1, 小さければ -1, ちょうどよければ 0 を返す関数 f が与えられます。
この関数を二分探索して、f(x) = 0 となるような x を、約分された分数の形で求めてください。
右側のコードエリアには、入出力のためのコードがすでに記述されています。このコードにアルゴリズムを実装し、正しく答えを求めてください。

入力される値

1 -1

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

1/1

Tips

動画へ戻る

前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃06:有理数二分探索

このチャプターでは、分数を二分探索するアルゴリズムについて学習します。

関数 f(x) を用いて求めたい値を分数で二分探索するアルゴリズム

・探索範囲 l, r をそれぞれ 0/1, 1/0 で初期化
・以下の処理を繰り返す
・1. 中間値 m を l と r の分母同士、分子同士を足し合わせた分数とする
・2. f(m) に応じて分岐する
・2.1. m が求めたい値より小さい場合は、l を m に更新
・2.2. m が求めたい値より大きい場合は、r を m に更新
・2.3. m が求めたい値と一致した場合は、探索を終了

スターン・ブロコット木の性質

・以下の 3 つの性質が成り立つ
・A. 0 以上のすべての分数をちょうど 1 回ずつ生成する
・B. 生成される分数は 2 つの分数の間の分数である
・C. 生成される分数は既約分数である
・具体的な証明については、https://www.cut-the-knot.org/blue/Stern.shtml (英語) などを参照

・上に述べたアルゴリズムでは、答えが大きな整数やその逆数の場合には、答えの大きさに比例して時間計算量が増えてしまう（スターン・ブロコット木の左端には 1/n, 右端には n/1 が並んでいる）
・これは左右どちらか同じ方向に進み続ける場合に遅くなることが原因である
・そこで、同じ方向に何回進むかを二分探索することで、各ステップでの計算量を O(T log M) に抑えることができ、向きを変えるごとに分子分母の和はほぼ 2 倍以上になるため、全体で O(T log^2 M) に改善される（M は答えの分母分子の最大値、T は関数 f(x) の計算量）

プログラミング学習 > Java > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編15: 二分探索関連アルゴリズム・三分探索 > 有理数二分探索

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

1 -1

新・アルゴリズムとデータ構造入門 Java編15: 二分探索関連アルゴリズム・三分探索