골롬 시퀀스

콜롬비아 수열 - 콜럼버스 수열은 감소하지 않는 정수 수열입니다. 여기서 n번째 항목의 값은 정수 n이 수열에 나타나는 횟수입니다.

콜럼버스 수열의 일부 용어는 다음과 같습니다.

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9 , 9, 10, 10, 10, 10, …

여기서 5번째 항목이 3이고, 5도 순서대로 3번 나타나는 것을 볼 수 있습니다.

6번 항목은 4번이고, 6번 항목도 순서대로 4번 등장합니다.

콜럼버스 수열의 성질 - 수열의 첫 번째 항은 1이고 n번째 항은 1 + n - n번째 항보다 작거나 같은 수열의 항 수입니다.

문제 설명

정수 n이 주어졌습니다. 콜럼버스 수열의 처음 n개 항을 찾습니다.

예 1

으아악 으아악

예 2

으아악 으아악

방법 1: 재귀 사용

콜럼버스 수열의 속성을 사용하면 수열의 첫 번째 항은 1입니다. n번째 항을 찾기 위해 다음 속성을 사용합니다. n번째 항은 1 + 수열에서 n - n번째 항보다 작거나 같은 항의 수입니다.

재귀 함수에 이 방법을 적용하면, n번째 항목이 시퀀스에서 n - golomb(n - 1))번보다 이전에 나타나지 않는 가장 작은 양의 정수인 경우 이 속성이 충족되는지 확인하세요. 여기서 golomb( )는 콜럼버스 수열의 n번째 항의 재귀 함수를 찾는 것입니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 재귀를 사용하여 콜럼버스 수열을 찾습니다.

으아악

출력

으아악

시간 복잡도 - O(n^2) 왜냐하면 각 항목은 이전 항목을 재귀적으로 계산하여 계산되기 때문입니다.

공간 복잡성 - O(n)

방법 2: 메모를 이용한 재귀

재귀적 코드를 기억하기 위해 위 코드에서 이전에 재귀적으로 계산한 값을 저장하는 맵을 생성합니다. 그런 다음 각 숫자를 계산할 때 먼저 이전 숫자가 계산되었는지 확인하고, 그렇다면 이전 계산 결과를 취하고, 그렇지 않으면 계산을 수행합니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 항목 계산 시 접근하는 맵에 이전 계산 결과가 저장됩니다.

으아악

출력

으아악

시간 복잡도 - O(nlogn)

공간 복잡성 - O(n)

방법 3: 동적 프로그래밍

동적 프로그래밍을 사용하여 n+1 * 1 크기의 dp 테이블을 만듭니다. 그런 다음 n번째 숫자가 1 + golomb(n - golomb(golomb(n - 1)))인 위에서 사용된 속성을 사용하여 시퀀스의 모든 숫자를 계산하고 이를 벡터에 저장합니다.

의사코드

으아악

예: C++ 구현

아래 프로그램에서는 이 문제를 해결하기 위해 동적 프로그래밍 방법을 사용합니다.

으아악

출력

으아악

결론

요약하자면, 콜럼버스 수열을 찾기 위해 우리는 콜럼버스 수열의 n번째 수의 ​​속성을 사용하여 수열의 모든 수를 구하며, 시간 복잡도가 O(n^2)부터 O(n)까지 다양한 방법을 사용합니다. .

위 내용은 골롬 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!