[오일러프로젝트] 53번문제

1,2,3,4,5 다섯 숫자 중에서 세 개를 고르는 것에는 다음과 같은 10가지 경우가 있습니다.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345

조합론이라는 분야에서는 이것을 ₅C₃ = 10 이라고 표시하며, 일반적인 식은 아래와 같습니다.

nCr =

n! r!(n−r)!

,   단 r ≤ n 이고, n! = n×(n−1)×...×3×2×1 이며 0! = 1.

이 값은 n = 23 에 이르러서야 ₂₃C₁₀ = 1144066 으로 처음 1백만을 넘게 됩니다.

1 ≤ n ≤ 100 일때 _nC_r의 값이 1백만을 넘는 경우는 모두 몇 번입니까? (단, 중복된 값은 각각 계산합니다)

문제는 길지만 어렵지않은 문제..
그냥 구하면됨..

	import math
	def get_number_of_cases(n, r):
	r = (math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))
	return r
	cnt = 0
	for n in range(23, 101):
	for r in range(1, n-1):
	if get_number_of_cases(n, r) > 1000000:
	cnt += 1
	print (cnt)

view raw 53.py hosted with ❤ by GitHub

Ruby

	def fact(n)
	if n<= 1
	1
	else
	n * fact( n - 1 )
	end
	end
	def get_number_of_cases(n, r)
	r = fact(n) / (fact(r) * fact(n-r))
	end
	cnt = 0
	(23..100).each do |n|
	(1..n-1).each do |r|
	if get_number_of_cases(n, r) > 1000000
	cnt += 1
	end
	end
	end
	puts cnt

view raw 53.rb hosted with ❤ by GitHub

Perl

	sub fact {
	my ($n) = @_;
	if ($n == 1) {
	return 1
	}
	my $result = 1;
	foreach my $d ((1..$n)) {
	$result = $result * $d;
	}
	return $result;
	}
	sub get_number_of_cases {
	my ($n, $r) = @_;
	my $result = fact($n) / (fact($r) * fact($n-$r));
	return $result;
	}
	my $cnt = 0;
	foreach my $n ((23..100)) {
	foreach my $r ((1..$n-1)) {
	if (get_number_of_cases($n, $r) > 1000000) {
	$cnt += 1;
	}
	}
	}
	print "$cnt";

view raw 53.pl hosted with ❤ by GitHub