0905 minimal distance to pi - 편집 역사

2017년 9월 28일 (목) 16:06에 Admin님의 편집

2017-09-28T16:06:23Z

2017년 9월 11일 (월) 13:07에 Admin님의 편집

2017-09-11T13:07:47Z

2017년 9월 11일 (월) 12:55에 Admin님의 편집

2017-09-11T12:55:17Z

2017년 9월 11일 (월) 12:32에 Admin님의 편집

2017-09-11T12:32:35Z

2017년 9월 11일 (월) 10:01에 Admin님의 편집

2017-09-11T10:01:54Z

2017년 9월 7일 (목) 01:21에 Admin님의 편집

2017-09-07T01:21:01Z

2017년 9월 7일 (목) 01:20에 Admin님의 편집

2017-09-07T01:20:49Z

2017년 9월 5일 (화) 10:00에 Admin님의 편집

2017-09-05T10:00:32Z

Admin: 새 문서: 원문: https://www.hackerrank.com/challenges/minimal-distance-to-pi 참조한 블로그 : [http://www.libragold.com/blog/2017/03/minimal-distance-to-pi/ www.libragold.com]...

2017-09-05T10:00:07Z

새 문서: <poem> 원문: https://www.hackerrank.com/challenges/minimal-distance-to-pi 참조한 블로그 : [http://www.libragold.com/blog/2017/03/minimal-distance-to-pi/ www.libragold.com]...

새 문서

<poem>
원문: https://www.hackerrank.com/challenges/minimal-distance-to-pi
참조한 블로그 : [http://www.libragold.com/blog/2017/03/minimal-distance-to-pi/ www.libragold.com]

임의의 무리수에 가장 근접한 유리수를 찾는 문제.
단, 유리수를 \(\frac{p}{q}\)로 나타냈을 때, \(q\)가 가질 수 있는 범위를 한정한다.

일단, Farey sequence[https://en.wikipedia.org/wiki/Farey_sequence]를 알면 좋다.
위키피디아에 들어가서 보면 정렬된 그림이 있는데, 이해하기 좋다.

Farey sequence는 다음 수열을 얻는 과정이 매우 쉽고, 근사하는 속도가 매우 빠르기 때문에
</poem>

@@ 20번째 줄: / 20번째 줄: @@
 </poem>
- #cont.
 <pre>

← 이전 판		2017년 9월 11일 (월) 13:07 판
16번째 줄:		16번째 줄:
	\(r\)의 argument로 (inclusive) range를 허용하면 위는 \(r(1,4), r(1,8)\)이 된다.		\(r\)의 argument로 (inclusive) range를 허용하면 위는 \(r(1,4), r(1,8)\)이 된다.
	구하려고 하는 것은 임의의 \(a\lt b \in \N\)에서 \(r(a,b)\)이다.		구하려고 하는 것은 임의의 \(a\lt b \in \N\)에서 \(r(a,b)\)이다.
		+	\(b-a\)가 매우 크기 때문에 다 해 볼 수는 없고, a와 b사이의 어떤 값이 r(a,b)의 분모가 될 것인지 빨리 알아내는 것이 핵심이다.

← 이전 판		2017년 9월 11일 (월) 12:55 판
20번째 줄:		20번째 줄:
	</poem>		</poem>
	#cont.		#cont.
		+
		+	<pre>
		+	#!/bin/python
		+
		+	import sys
		+
		+	def nextfarey(before,x,C): # real value = x/C
		+	a,b,c,d = before
		+	assert a*C/b <= x
		+	assert c*C/d >= x
		+	mediant = (a+c)*C/(b+d)
		+	if mediant < x:
		+	return a+c, b+d, c, d
		+	else:
		+	return a, b, a+c, b+d
		+
		+	def fareyseq(x, C, denom_max):
		+	seq = ((0,1,1,1),)
		+	while True:
		+	nf = nextfarey(seq[-1], x, C)
		+	seq += (nf,)
		+	if nf[1] >= denom_max or nf[3] >= denom_max:
		+	return seq
		+
		+	def fareypairs(x, C, denom_max):
		+	seq = fareyseq(x, C, denom_max)
		+	seqs = ()
		+	for s in seq:
		+	s1 = (s[0], s[1])
		+	s2 = (s[2], s[3])
		+	if s1 not in seqs:
		+	seqs += (s1,)
		+	if s2 not in seqs:
		+	seqs += (s2,)
		+	return seqs
		+
		+	def err(p, q, r, s, C=10**100):
		+	return abs(pC/q - rC/s)
		+
		+	def sol(lower, upper):
		+	x= 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679
		+	C= 10**100
		+	#closest numerator
		+	q = lower
		+	limit = upper
		+	p = int(x*q/C)
		+
		+	#print seqs
		+	remainlen = limit - q
		+	movecnt = 0
		+	seqs = fareypairs(x, C, limit)
		+	while remainlen > 0:
		+	#print 'remainlen=', remainlen
		+	minerr = err(p, q, x, C)
		+	#print 'minerr = ', minerr
		+	#print 'minerr=',minerr
		+	p1 = 0
		+	q1 = 0
		+	for s in seqs:
		+	#print s
		+	if q+s[1] > limit :
		+	break
		+	newerr = err(p+s[0], q+s[1], x, C)
		+	#print 'newerr = ', newerr
		+	if minerr > newerr:
		+	p1 = s[0]
		+	q1 = s[1]
		+	minerr = newerr
		+	break
		+	if q1 == 0 :
		+	break
		+	else:
		+	#print p1, q1
		+	movecnt += 1
		+	p += p1
		+	q += q1
		+	#print 'add:',p1, q1, 'now:',p, q, 'error =', err(p, q, x, C)
		+	remainlen -= p1
		+	print '%d/%d'%(p+q*3,q)
		+
		+
		+	min,max = raw_input().strip().split(' ')
		+	min,max = [long(min),long(max)]
		+	sol(min, max)
		+
		+	</pre>

@@ 14번째 줄: / 14번째 줄: @@
 \(r(4) = 1/4 \)
 \(r(8) = 1/7\) (\(\because 1/7\)이 \(1/8\)보다 \(\pi-3\)에 더 가깝다. \(8/57\) 이전까지 \(1/7\)의 오차가 가장 작다. )
 </poem>
   #cont.

@@ 9번째 줄: / 9번째 줄: @@
 위키피디아에 들어가서 보면 정렬된 그림이 있는데, 이해하기 좋다.
-#cont.
+    #cont.
 Farey sequence는 수열을 얻는 과정이 매우 쉽고, 근사하는 속도가 매우 빠르기 때문에
 </poem>

@@ 8번째 줄: / 8번째 줄: @@
 일단, Farey sequence[https://en.wikipedia.org/wiki/Farey_sequence]를 알면 좋다.
 위키피디아에 들어가서 보면 정렬된 그림이 있는데, 이해하기 좋다.
 </poem>