2011-02-28

アルゴリズムイントロダクション練習問題5.1-3

問題

0と1をそれぞれ確率1/2で出力する問題を考える。利用できるのは0か1かを出力する手続きBIASED-RANDOMである。BIASED-RANDOMは1を確率p、0を確率1-pで出力する(0

やっぱり実装まで。期待実行時間は出していない。あと証明もまだ(これはたぶんすぐできる)。
発想

PK戦のサドンデスで、先攻が勝ったら1、後攻が勝ったら0を返すとすればよい

public class Utility {
	public static boolean randomBoolean() {
		boolean a = true;
		boolean b = true;
		double p = 0.7;		// Any p is OK. s.t. 0 < p < 1
		while (!(a ^ b) ) {
			a = randomBooleanByProbability(p);
			b = randomBooleanByProbability(p);
		}
		return a;
	}

	// BIASED-RANDOM
	public static boolean randomBooleanByProbability(double p) {
		if (Math.random() < p ) return true;
		else return false;
	}
}

import static org.junit.Assert.*;
import org.junit.Test;
import com.gmail.seizans.algorithm.Utility;

public class UtilityTest {
	@Test
	public void randomBooleanTest() throws Exception {
		int numberOfTrials = 20000;
		double minProb = 0.95;
		double maxProb = 1.05;
		int counter = 0;
		boolean isOk = false;
		for (int i = 0; i < numberOfTrials; i++) {
			if (Utility.randomBoolean() ) counter++;
		}
		if (numberOfTrials * minProb < counter * 2 && counter * 2 < numberOfTrials * maxProb ) {
			isOk = true;
		}
		assertTrue(isOk);
	}
	
	@Test
	public void randomBooleanByProbabilityTest() throws Exception {
		double p = 0.66666;
		int numberOfTrials = 20000;
		double minProb = 0.95;
		double maxProb = 1.05;
		boolean isOk = false;
		int counter = 0;
		for (int i = 0; i < numberOfTrials; i++) {
			if (Utility.randomBooleanByProbability(p) ) counter++;
		}
		if (p * numberOfTrials * minProb < counter && counter < p * numberOfTrials * maxProb) {
			isOk = true;
		}
		assertTrue(isOk);
	}
}

2011-02-27

アルゴリズムイントロダクション練習問題5.1-2

問題：

RANDOM(0,1) に対する呼び出しだけを用いて手続き RANDOM(a,b) を実現せよ。実現された手続きの平均実行時間を a と b の関数として表現せよ。

RANDOM(a,b) とは、a<=x<=bな整数xをランダムに返す関数です。
とりあえず実装まで。

発想：

RANDOM(a,b)を実現するのはRANDOM(0,n)を実現するのと同値だからこれをやる
nが2の累乗ならばRANDOM(0,1)をln(n)回やればOKなんだけどなぁ・・・
あ、無効な値になってしまったときはもう1回やればいいや！

import java.util.Random;

public class Utility {
	// This method means Random(0, 1)
	public static int randomZeroOne() {
		Random random = new Random();
		int result = random.nextInt(2);
		return result;
	}
	
	public static int log2(int n) {
		if (n <= 0) {
			throw new IllegalArgumentException();
		}
		int result = (int) Math.ceil(Math.log(n) / Math.log(2) );
		return result;
	}
	
	public static int random(int a, int b) {
		if (a >= b || a < 0) {
			throw new IllegalArgumentException();
		}
		int result = 0;
		int m = log2(b - a);
		while (true) {
			for (int i = 0; i < m; i++) {
				result += randomZeroOne() * Math.pow(2, i);
			}
			result += a;
			if (result <= b) {
				return result;
			} else {
				result = 0;
			}
		}
	}
}

import com.gmail.seizans.algorithm.Utility;
import static org.hamcrest.CoreMatchers.is;
import static com.gmail.seizans.algorithm.Utility.log2;

public class UtilityTest {
	@Test
	public void log2Test() throws Exception {
		assertThat(log2(1), is(0) );
		assertThat(log2(2), is(1) );
		assertThat(log2(3), is(2) );
		assertThat(log2(4), is(2) );
		assertThat(log2(5), is(3) );
		assertThat(log2(6), is(3) );
		assertThat(log2(7), is(3) );
		assertThat(log2(8), is(3) );
	}
	
	@Test
	public void randomTest() throws Exception {
		int a = 20;
		int b = 30;
		boolean isOk = true;
		int numberOfTrials = 50;
		for (int i = 0; i < numberOfTrials; i++) {
			int r = Utility.random(a, b);
			if (r < a || b < r) {
				isOk = false;
			}
			System.out.println(r);
		}
		assertTrue(isOk);
	}
}

とりあえず動いているかのように見える。
しょっぱい点に気づかれたら教えてくださいませ。どうか。

2011-01-29

練習中

練習中です。

リストの練習
- リスト１１
- リスト１２
リスト２
- リスト２１
- リスト２２

public class HelloWorld {
    public static void main(String args[]) {
        System.out.println("HelloWorld");
    }
}

public class HelloHatena {
	public static void main(String args[]) {
		System.out.println("HelloHatena");
	}
}

double x = x + x

quadruple x = double (double x)

factorial n = product [1 .. n]

average ns = sum ns `div` length ns

last1 :: [a] -> a
last1 xs = xs !! (length xs - 1 )

last2 :: [a] -> a
last2 xs = head (reverse xs )

init1 :: [a] -> [a]
init1 xs = reverse (tail (reverse xs) )

init2 :: [a] -> [a]
init2 xs = take (length xs - 1) xs

type1 = ['a','b','c']
type2 = ('a','b','c')
type3 = [(False,'o'),(True,'1')]
type4 = ([False,True],['0','1'])
type5 = [tail,init,reverse]
type6 = ['1','2','3']

second xs = head (tail xs)
swap (x,y) = (y,x)
pair x y = (x,y)
double1 x = x * 2
palindrome xs = reverse xs == xs
twice f x = f (f x)