2, 3, 5, 7로 구성된 숫자에서 n의 위치는 무엇입니까?

문제 설명은 n의 위치를 ​​2, 3, 5, 7로 구성된 숫자로 인쇄하는 것으로 구성됩니다. 여기서 n은 사용자가 지정한 양수일 수 있습니다.

2, 3, 5, 7로 구성된 숫자는 처음 4개의 소수인 2, 3, 5, 7만 포함하는 숫자의 엄격하게 증가하는 수열임을 의미합니다. 모든 숫자가 2, 3, 5, 7, 22, 23, 25, 27, 32, 33, 35, 37 등이므로 모든 숫자가 2,3,5, 7인 시퀀스의 처음 몇 숫자 .

기본적으로 시퀀스의 각 숫자는 이 4개의 숫자(예: 2, 3, 5 또는 7)의 조합이며 시퀀스는 오름차순으로 배열됩니다.

이 질문에서는 숫자가 2, 3, 5, 7인 숫자 N이 주어집니다. 시퀀스에서 주어진 숫자의 위치를 ​​찾아 인쇄해야 합니다. 이것이 원하는 숫자 출력이 됩니다.

아래 예를 통해 이 문제를 더 잘 이해해 봅시다.

으아아아

설명 - 입력에 2, 3, 5 또는 7만 포함된 주어진 숫자는 33입니다. 숫자 2, 3, 5, 7만 있는 숫자 시퀀스에서 위치 33은 10번째 위치입니다. 따라서 우리의 출력은 10입니다.

으아아아

Explanation - 입력된 숫자는 52입니다. 시퀀스의 패턴을 따르면 각 숫자의 숫자는 2, 3, 5 또는 7이고 시퀀스는 엄격하게 증가하는 순서대로 13번째 위치에서 52를 찾습니다. 따라서 우리가 원하는 출력은 13입니다.

전체 시퀀스를 생성하지 않고 주어진 숫자의 위치를 ​​직접 찾는 알고리즘을 이해해 봅시다.

알고리즘

숫자가 2, 3, 5, 7만 있는 숫자 시퀀스를 살펴보면 특정 숫자와 함께 4개의 숫자 조합만 형성할 수 있다는 것을 알 수 있습니다. 우리는 이 논리를 사용하여 주어진 숫자 N의 위치를 ​​알아낼 것입니다.

처음 4개 숫자의 위치는 다음과 같습니다.

2: 1위

3: 2위

5: 3위

7: 4위

순서가 오름차순이므로 특정 숫자로는 4개의 숫자만 구성할 수 있으므로 다음 4개의 숫자는 2자리가 되며 첫 번째 숫자는 2가 됩니다.

왼쪽 첫 번째 숫자의 위치에 4를 곱하고 해당 숫자의 위치를 ​​더하면 임의의 숫자의 위치를 ​​찾을 수 있습니다.

예: N=52

초기 위치는 0이 됩니다.

왼쪽 숫자부터 순서대로 5의 위치가 위치*4+5, 즉 0*4+3=3의 위치가 됩니다. 현재 위치는 3입니다.

다음 숫자는 2이므로 숫자의 위치는 3*4+1이 됩니다. 현재 위치는 3 곱하기 4이므로 현재 숫자의 위치를 ​​더하면 위치 13이 됩니다. 이는 순서대로 52개의 위치입니다. 숫자.

이 문제를 해결하려면 위치를 0으로 초기화하면 됩니다. 그런 다음 숫자의 마지막 자리까지 각 숫자를 계속 확인하고 그에 따라 위치를 업데이트하세요 -

2번의 경우 위치는 위치*4+1이 됩니다.

3번의 경우 위치는 *4+2가 됩니다.

5번의 경우 위치는 *4+3이 됩니다.

7번의 경우 위치는 *4+4가 됩니다.

각 가능한 숫자에 대해 4개의 조합만 만들 수 있으므로 4를 곱하여 위치를 업데이트합니다. 따라서 위치에 4를 곱하고 현재 숫자의 위치를 ​​더할 때마다 숫자 N의 위치를 ​​얻게 되는데, 이는 단지 2, 3, 5 또는 7입니다.

우리는 문제를 효율적으로 해결하기 위해 이 알고리즘을 접근 방식에 사용할 것입니다.

방법

2, 3, 5 또는 7로만 구성된 숫자 N의 위치를 ​​인쇄하는 방법에서 알고리즘을 구현할 때 따라야 할 단계 -

• 2, 3, 5, 7 중 주어진 숫자의 위치를 ​​가져오는 함수를 만들어 보겠습니다.

• 입력 숫자 N을 문자열 형태로 얻습니다.

• 그래서 i=0부터 i

• 첫 번째 경우, i번째 숫자가 2라면 1은 2의 위치이므로 해당 위치에 4와 1을 곱합니다. 마찬가지로, 알고리즘 섹션에서 설명한 i번째 숫자를 기준으로 i번째 위치까지 숫자의 위치를 ​​계산하는 공식을 사용합니다.

• 각 반복에서 위치는 현재 i번째 숫자를 기준으로 지속적으로 업데이트됩니다.

• 전체 문자열에 대한 반복이 끝나면 해당 위치에 저장된 값, 즉 필요한 출력을 반환합니다.

예

이 방법에 대한 C++ 코드:

으아아아

출력

으아아아

시간 복잡도 - O(n), 여기서 n은 문자열의 길이 또는 숫자의 자릿수입니다. for 루프에서 주어진 위치 시퀀스의 숫자를 계산하기 위해 n번 반복하기 때문입니다

Space Complexity - O(1) 문제를 해결하기 위해 추가 공간을 사용하지 않기 때문입니다.

결론

이 문서에서는 2, 3, 5 또는 7의 숫자 시퀀스에서 숫자 N의 위치를 ​​찾는 알고리즘에 대해 설명합니다. 우리는 이 알고리즘을 사용하지 않고 O(n) 시간 C++에서 효율적으로 문제를 해결하기 위해 방법에 구현했습니다. 추가 공간.

이 기사를 읽은 후 이 문제와 C++를 사용하여 해결하는 방법을 이해할 수 있기를 바랍니다.

위 내용은 2, 3, 5, 7로 구성된 숫자에서 n의 위치는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!