Ugly Numbers/남훈

Difference between r1.4 and the current

@@ -41,5 +41,56 @@

print "The " + `goal` + "(st/nd/th) ugly number is " + `ugly2(goal)`
}}}

=== 문제 ===

리커시브 콜 하다가 뻗어버림

== 다음 ==

=== 접근 ===

동일한 아이디어를 유지하되, 반복으로 처리

=== 코드 ===

{{{

def is_ugly2(num):

while True:

if num == 1:

return True

elif num % 2 == 0:

num /= 2

elif num % 3 == 0:

num /= 3

elif num % 5 == 0:

num /= 5

else:

return False

def ugly3(num):

if num < 1:

return 0

prev = iter = 1

while True:

if iter == num:

return prev

guess = prev + 1

while True:

if is_ugly2(guess):

prev = guess

break

guess += 1

iter += 1

goal = 1500

print "The " + `goal` + "(st/nd/th) ugly number is " + `ugly3(goal)`

}}}

=== 문제 ===

느림.

----
[UglyNumbers]

처음 ¶

접근 ¶

1500 "번째" ugly number 를 알기 위해서는 1499 번째 ugly number 보다 큰 수 중에 해당되는 수가 있는지 조사하면 된다. 그런 간단한 아이디어로 구현

코드 ¶

ver. 1

def exponent(num, div):
	expo = 0
	while True:
		if num % div != 0:
			return expo
		num /= div
		expo += 1

def is_ugly(num):
	two = exponent(num, 2)
	three = exponent(num, 3)
	five = exponent(num, 5)

	if num == (2 ** two) * (3 ** three) * (5 ** five):
		return True
	
	return False

def ugly(num):
	if num <= 0:
		return 0
	
	prev = ugly(num - 1)
	guess = prev + 1

	while True:
		if is_ugly(guess):
			return guess
		guess += 1


goal = 1500

print "The " + `goal` + "(st/nd/th) ugly number is " + `ugly2(goal)`

문제 ¶

리커시브 콜 하다가 뻗어버림

다음 ¶

접근 ¶

동일한 아이디어를 유지하되, 반복으로 처리

코드 ¶

def is_ugly2(num):
	while True:
		if num == 1:
			return True
		elif num % 2 == 0:
			num /= 2
		elif num % 3 == 0:
			num /= 3
		elif num % 5 == 0:
			num /= 5
		else:	
			return False
		
def ugly3(num):
	if num < 1:
		return 0

	prev = iter = 1
	
	while True:
		if iter == num:
			return prev
		
		guess = prev + 1

		while True:
			if is_ugly2(guess):
				prev = guess
				break
			guess += 1

		iter += 1


goal = 1500

print "The " + `goal` + "(st/nd/th) ugly number is " + `ugly3(goal)`

문제 ¶

느림.

UglyNumbers