shokosブログ

プログラミング

乱数を使用したアルゴリズム

こちらの本を勉強しはじめました!

amazon:アルゴリズムイントロダクション

第5章の練習問題を解いてみました。

【問題】
RANDOM(0,1)に対する呼び出しだけを用いて、手続きRANDOM(a,b)を実現せよ。
※RANDOM(a, b)とは、a〜bの整数のこと。

package jp.ne.hatena.syoko_sasaki;

import static java.lang.Math.*;

import java.util.Random;

public class RandomOriginal {

	private static Random random = new Random();


	public static int rundumAtoB(int a, int b) {
		if(a < 0 || b < 0 || a > b) throw new IllegalArgumentException("引数に問題があるんじゃなイカ?");
		int m = (int) floor((log(b - a)) / (log(2)));
		int result = 0;
		for (int i = 0; i <= m; i++) {
			result += (random.nextInt(2)) * (pow(2, i));
		}
		return result > (b - a) ? rundumAtoB(a, b) + a : result + a;
	}
}

2進数つかってごねごねしています。
プログラマ中二病なので、三項演算子とか再帰とか大好きです!やたら使いたくなります。



テスト

package jp.ne.hatena.syoko_sasaki;

import java.util.Random;
import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;


public class RandomOriginalTest {

	@Test
	public void randomTest() throws Exception {
		for (int j = 0; j < 100; j++) {
			Random random = new Random();
			int target = random.nextInt(4) + 10;
			int per = 0;
			for (int i = 0; i < 10000; i++) {
				int result = RandomOriginal.rundumAtoB(10, 13);
				assertThat((result >= 10 && result <= 13), is(true));
				if (result == target) {
					per++;
				}
			}
			assertThat(per > 2200 && per < 2800, is(true));
		}
	}
}

確率論よくわからないので、4通りの答え(10〜13)が返ってくると想定して10000回まわして、登場回数が2200〜2800くらいだったらおkかなーと、ここらへんは正直適当に書きました。

【追記】
一応値チェックを入れました。
エラーが出るようなテストも追加。

	@Test(expected = IllegalArgumentException.class)
	public void errorTest() throws Exception {
		RandomOriginal.rundumAtoB(-3, 2);
		fail();
	}


なにかアドバイスあったらお願いしますー。