본문 바로가기
반응형

개발/알고리즘 문제56

[Project Euler 27] 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식 구하기 오일러는 다음과 같은 멋진 2차식을 제시했습니다. n2 + n + 41 이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다. 하지만 n = 40일 때의 값 402 + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다. 컴퓨터의 발전에 힘입어 n2 − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다. 아래와 같은 모양의 2차식이 있다고 가정했을 때, n2 + an + b (단 | a | < 1000, | b | < 1000) 0부터 시.. 2016. 3. 16.
(미완)[Project Euler 26] 1000 이하의 d 중에서 1/d 이 가장 긴 순환마디를 갖는 수는? 분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다. 숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다. d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까? 되다 말다 함...뭐지... 2016. 3. 16.
[Project Euler 25] 피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째? 피보나치 수열은 아래와 같은 점화식으로 정의됩니다. Fn = Fn-1 + Fn-2 (단, F1 = 1, F2 = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 수열의 값은 F12에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까? 어...찾아보니까 피보나치 관련 모듈이 있다. 써보진 않았다. https://pypi.python.org/pypi/fibonacci/1.0.0 2016. 3. 1.
[Project Euler 24] 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은? 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다. 012 021 102 120 201 210 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까? 순열 찾는 함수인 permutations. itertools 모듈을 받아 가져올 수 있다. 2016. 3. 1.
반응형

티스토리툴바