피보나치 수열은 각 항이 바로 앞 두 항의 합으로 이루어지는 수열로, 흥미로운 수학적 성질을 많이 가지고 있습니다. 그중 하나는 배수 관련 성질입니다. 이 글에서는 자바(Java)를 사용하여 피보나치 수열에서 특정 숫자의 n번째 배수가 나타나는 위치를 구하는 프로그램을 살펴보겠습니다.
핵심 아이디어
피보나치 수열에는 다음과 같은 중요한 성질이 있습니다. 어떤 수 k의 배수가 피보나치 수열에서 처음으로 등장하는 위치가 p라면, k의 n번째 배수는 정확히 n × p 번째 위치에 나타납니다. 예를 들어, 9의 배수 중 가장 작은 피보나치 수는 12번째 항인 144이므로, 9의 10번째 배수에 해당하는 피보나치 수는 10 × 12 = 120번째 항에 존재하게 됩니다.
아래 자바 코드는 이 원리를 활용하여 문제를 해결합니다.
예제 코드
public class Demo {
public static int position(int pos, int num) {
long val_1 = 0, val_2 = 1, val_3;
int i = 2;
while (i != 0) {
val_3 = val_1 + val_2;
val_1 = val_2;
val_2 = val_3;
if (val_2 % pos == 0) {
return num * i;
}
i++;
}
return 0;
}
public static void main(String[] args) {
int n = 10;
int k = 9;
System.out.print("피보나치 수열에서 9의 10번째 배수가 나타나는 위치는 ");
System.out.println(position(k, n));
}
}실행 결과
피보나치 수열에서 9의 10번째 배수가 나타나는 위치는 120
코드 상세 설명
position 메서드
Demo 클래스 내부의 position 메서드는 피보나치 수열을 순차적으로 생성하면서 원하는 조건을 만족하는 위치를 찾습니다.
- 초기화: 변수
val_1과val_2를 각각 0과 1로 설정하여 피보나치 수열의 시작점을 만듭니다. - 반복 계산: while 루프 안에서 세 변수를 이용해 다음 피보나치 수를 계산하고 값을 갱신합니다.
- 배수 판별: 새로 계산된 피보나치 수(
val_2)를pos(여기서는 9)로 나눈 나머지가 0이면, 해당 수가 pos의 첫 번째 배수임을 의미합니다. - 결과 반환: 첫 배수가 발견된 위치 i에 n(
num)을 곱한 값을 반환합니다. 이것이 바로 n번째 배수가 등장하는 위치입니다.
main 메서드
main 메서드에서는 찾고자 하는 배수의 개수 n = 10과 목표 숫자 k = 9를 정의한 뒤, position 메서드를 호출하여 결과를 콘솔에 출력합니다.
동작 과정 요약
이 프로그램은 피보나치 수열을 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 순서로 생성하며 진행됩니다. 12번째 항인 144가 처음으로 9로 나누어떨어지는 피보나치 수이므로, 프로그램은 10 × 12 = 120을 반환합니다. 즉, 피보나치 수열의 120번째 항이 9의 10번째 배수가 되는 것입니다.
이처럼 피보나치 수열의 배수 성질을 활용하면, 실제로 매우 큰 피보나치 수를 일일이 계산하지 않고도 원하는 배수의 위치를 효율적으로 구할 수 있습니다.