Project Euler #53

Birilerinin Project Euler sorularının cevaplarını yayınladığını öğrendiğimde öfkelenmiştim. Ben adım adım çözerek yükselirken birileri siteye girip “çat çat” cevapları vererek listede yükselebiliyordu. Sonra düşündüm ki, bana ne? Project Euler insanın kendini geliştirebilmesi ve zaman geçirebilmesi için yaratılmış bir site. Ben aşağıda #53’ün cevabını yazacağım. Yani şimdiden bir spoiler ibaresi koyuyorum. 🙂 İstemeyen bakmaz.

Soru #53, bizden 1<= n <= 100 aralığında kaç tane C(n,r)’nin 1 milyondan yukarda olduğunu soruyor. Distinct value bulmaya gerek yok, basit bir brute force ile sonuca gidilebilir. Kombinasyon hesaplama işi bilgisayarı uzun süre meşgul edebiliyor, çünkü kombinasyon belli sayıların faktöriyellerine bakılarak bulunuyor:

C(n,r) = n! / r!(n-r)!

O nedenle gerektiği yerde bu faktöriyel sonuçlarını cachelemeye karar verdim. Sonuç olarak, aşağıdaki kodla çift çekirdekli 2.4 GHz makinede 0.15 saniyelik bir runtime ile cevaba ulaştım. Project Euler’de diğer cevaplara baktığımda daha verimli algoritmalara da ulaştım, bazıları Pascal Triangle kullanmış – ki bence mükemmel bir fikir. Ama benim algoritmam da hızlı bir şekilde sonuca ulaştırdı.

import sys
import math
import time
 
## author: Ekin Ocalan
## date: Mar 14, 2013
## project euler #53
 
fact_results = []
 
def fact(i):
	if i == 1:
		return i
	elif i &lt; 1:
 		return 1
 	else: 		return i * fact(i-1) 
 
def comb( i, j):
 	global fact_results
 	if fact_results[i] == 0:
 		fact_results[i] = fact(i)
 	if fact_results[j] == 0:
 		fact_results[j] = fact(j)
 	if fact_results[i-j] == 0:
 		fact_results[i-j] = fact(i-j) 	return fact_results[i] / (fact_results[j] * fact_results[i-j]) 
 
def main():
 	global fact_results
 	count = 0
 	for i in range(101):
 		fact_results.append(0)
 	for i in range(23,101):
 		for j in range(1,i+1):
 			if comb( i, j) &gt; 1000000:
				count += 1
				print 'found one on %d.C.%d' % (i,j)
 
	print 'finished. total: %d' % (count)
 
if __name__ == '__main__':
	start_time = time.time()
	main()
	print time.time() - start_time, "seconds"

One thought on “Project Euler #53

  1. Ekincim ben seni seker bir cocuk bilirdim sen ustelik dahi ymissin. Supersin super! Senin gibi akli basinda genclerin olmasi ne buyuk cevher su ulke icin. Ama buraya gelebilmeni cok isterdim, Luna ve Atahan senden birseyler ogrenirdi:)

Leave a Reply