숙제를 위해 작성한 프로그램

Hypergeometric Random Variable

Hypergeometric Random Variable은 다음과 같이 정의된다.

The probability of having exactly k objects of Type A, for max(0, r – (N-n)) <= k <= min(r, n) is

P(X = k) = C(n, k)*C(N-n, r-k) / C(N, r) .

P{X = i}를 P{X = i-1}에서 유도해낸 다음 프로그램으로 짜는 것이 통계 숙제였다.

public class MyMath
{
	// Factorial
	public static decimal Factorial(decimal n)
	{
		decimal result = 1;

		for (decimal i = 2; i <= n; ++i)
			result *= i;

		return result;
	}

	// Combination
	public static decimal Choose(decimal n, decimal k)
	{
		decimal result = 1;

		for (decimal i = Math.Max(k, n - k) + 1; i <= n; ++i)
			result *= i;

		for (decimal i = 2; i <= Math.Min(k, n - k); ++i)
			result /= i;

		return result;
	}

	// Hypergeometric Random Variable
	public static decimal Hypergeometric(decimal n, decimal m, decimal i, decimal k)
	{
		if (i == 0)
			return Choose(n, i) * Choose(m, k - i) / Choose(n + m, k);

		return (n-i+1)/i*(k-i+1)/(m-k+i)*Hypergeometric(n, m, i - 1, k);
	}
}

Modular Exponentiation

이산 구조 교재에 Modular Exponentiation 알고리즘이 제시되어 있었다. 문제는 특정 입력값에 따른 상태 변화를 적어서 제출하는 것이었다. 손으로 계산하고 나서 검증 차원에서 간단히 프로그램을 작성했다.

class Program
{
	static void Main(string[] args)
	{
		Console.WriteLine(mpower(2, 1, 7));
		Console.WriteLine(mpower(2, 2, 7));
		Console.WriteLine(mpower(2, 5, 7));
		Console.WriteLine(mpower(2, 10, 7));
	}

	static double mpower(double b, double n, double m)
	{
		if (n == 0)
			return 1;
		if(n % 2 == 0)
			return Math.Sqrt(mpower(b, n/2, m))%m;
		return (Math.Sqrt(mpower(b, Math.Floor(n/2), m))%(m*b)%m)%m;
	}
}

최 재훈

블로그, 페이스북, 트위터 고성능 서버 엔진, 데이터베이스, 지속적인 통합 등 다양한 주제에 관심이 많다.
Close Menu