daum2

오일러 프로젝트 26번

comments

http://euler.toepeu.net/26

단위분수는 분자가 1입니다. 분모가 2부터 10까지의 단위분수를 10진수로 표현하면 아래와 같습니다.
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
0.1(6)은 0.166666... 이라는 뜻이며 순환마디는 1자리입니다. 1/7의 순환마디는 6자리입니다.
d < 1000 에서 10진 소수 부분에서 순환마디가 가장 긴 1/d 의 d는 얼마인가요?

접기

....답은 나왔으니 상관없긴한데 뒷걸음 치다 소잡은 코드. -...-

버퍼크기에따라 결과값이 다르게나온다

기교욕심에 재귀로 풀어보려고 삽질한 흔적도 좀 있고 해쉬에 집어넣다가 꺼내지 못한 부분도있고.

하지만 결국 정규표현식으로 풀었음 -..-

code

# $h = Hash.new { |hash, key| 

# 	hash[key] = [key[0],key[1]*10%key[0]]

# }

# $table = Array.new 1001,""

# def d divider,remainder=1,i=1

# 	$table[divider] += "#{i==1&&"0."||""}%d"%(remainder*10/divider)

# 	unless remainder*10%divider == 0 || i > 10

# 		d divider,remainder*10%divider,i+1

# 	end

# 	

# 	# if $h[[divider,remainder]][1] == 0 || i > 10

# 	# 		$h[[divider,remainder]][1]

# 	# 	else

# 	# 		d divider,$h[[divider,remainder]][1],i+1

# 	# 	end

# end

# def srch_cycle n

# 	a = []

# 	i = 0

# 	while $h[loc]

# 	end

# end

def d divider

	str=""

	remainder,i = 1,1

	until remainder == 0 || i > 100

		str += "#{i==1&&"0."||""}%d"%(remainder*10/divider)

		remainder = remainder*10%divider

		i += 1

	end

	str

end

p (1..1000).map{|e|[(d e).gsub(/0[.][0-9]*([0-9]+)\1+/,'\1').size,e]}.max[1]

test code

none

output

983







==========================

1/d ( 2 <= d < 1000) 인 경우 recurring cycle 이 가장 긴 d 를 구하라




- 나눗셈을 계산하는중 피제수가 반복하여 나타나면 그 위치 까지가 recurring cycle 임을 이용한다

1. def getCycleLength(n):  
2.     numerator = 1  
3.     denumerator = n  
4.     l = []  
5.     length = 0  
6.     while numerator < denumerator:  
7.         numerator *= 10  
8.   
9.     while numerator not in l:  
10.         l.append(numerator)  
11.         length += 1  
12.         numerator %= denumerator  
13.         if numerator == 0:  
14.             length = 0  
15.             break  
16.         while numerator < denumerator:  
17.             numerator *= 10  
18.   
19.     return length  
20.   
21. def solve(limit = 1000):  
22.     max_length = 0  
23.     max_d = 0  
24.     for d in range(2, limit):  
25.         tmp = getCycleLength(d)  
26.         if tmp > max_length:  
27.             max_d = d  
28.             max_length = tmp  
29.     print 'Answer #26 : %s' % max_d  
30.   
31. if __name__ == '__main__':  
32.     solve()