콜라츠 추측 (Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불린다. 콜라츠 추측은 임의의 자연수가 다음 조작을 거쳐 항상 1이 된다는 추측이다.
- 짝수라면 2로 나눈다.
- 홀수라면 3을 곱하고 1을 더한다.
- 1이면 조작을 멈추고, 1이 아니면 첫 번째 단계로 돌아간다.
예를 들어, 6 에서 시작한다면, 차례로 6, 3, 10, 5, 16, 8, 4, 2, 1 이 된다.
<출처 : https://ko.wikipedia.org/wiki/%EC%BD%9C%EB%9D%BC%EC%B8%A0_%EC%B6%94%EC%B8%A1 >
두 수를 입력받아 그 두 수 사이에서 가장많은 수자를 거치는 수와 거치는 수의 개수를 출력.
관련문제 : https://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=309151599
#include <stdio.h> int collatz(long long n); int main(void) { int max_num = 0, max_len = 0; int first_num, last_num; int i; int len; // len을 내부 변수로 선언 printf("두 수 : "); scanf("%d %d", &first_num, &last_num); for (i = first_num; i <= last_num; i++) { len = collatz(i); if (len > max_len) { // 현재 수자의 길이가 더 길면 max_num = i; // 현재 수자 저장 max_len = len; // 현재 수자의 길이 저장 } } printf("가장 긴 수 : %d, 길이 : %d\n", max_num, max_len); return 0; } int collatz(long long n) // n의 값이 long의 범위를 벗어나므로 long long으로 선언 { if (n == 1) return 1; // n이 1이면 재귀 호출 종료 if (n % 2 == 0) n /= 2; // 짝수일 때 else n = 3 * n + 1; // 홀수일 때 return (collatz(n) + 1); // n이 1 이상인 동안 재귀 호출 } | cs |
다음검색