우리에게 숫자 N이 주어졌습니다. 목표는 다음 규칙에 따라 숫자를 1로 줄이는 데 필요한 단계 수를 계산하는 것입니다 -
-
숫자가 2의 거듭제곱이면 절반으로 줄입니다.
-
그렇지 않으면 N-(N보다 작은 2의 가장 가까운 거듭제곱)으로 줄입니다.
1단계에서는 ceil(log2(N)), floor(log2(N))이 동일한 결과를 반환하는지 확인하여 N이 2의 거듭제곱인지 확인합니다. 그렇다면 N=N/3, 작업 횟수를 증가시킵니다.
1단계의 결과가 거짓이면 2단계를 수행하고 N에서 N보다 작은 2의 가장 가까운 거듭제곱을 뺍니다. N보다 작은 2의 가장 가까운 거듭제곱은 -
로 계산됩니다.x=floor(log2(N)) → N이 2의 거듭제곱이 아닐 때 log2(N)은 부동 소수점 값을 제공하고 floor는 N보다 작은 가장 가까운 정수로 감소시킵니다.
이제 N=N-pow(2,x) → pow(2,x)는 N보다 작은 2의 가장 가까운 거듭제곱을 제공합니다. N을 줄입니다.
예를 들어 이해합시다.
입력 - N=20
출력 -:필요한 단계 수 - 3
설명 - N=20
20 is not power of 2. Step 2. Reduce nearest power of 2 less than N from N. N=20- 16=4. Count=1. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=2. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=3. N is 1 total step count=3.
입력 - N=32
출력 필요한 단계 수 - 5
설명 - N=32
32 is power of 2. Step 1. Reduce N to its half. N=32/2=16. Count=1. 16 is power of 2. Step 1. Reduce N to its half. N=16/2=8. Count=2. 8 is power of 2. Step 1. Reduce N to its half. N=8/2=4. Count=3. 4 is power of 2. Step 1. Reduce N to its half. N=4/2=2. Count=4. 2 is power of 2. Step 1. Reduce N to its half. N=2/2=1. Count=5. N is 1 total step count=5.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 값을 저장하기 위해 정수 N을 사용합니다.
-
함수 stepCount(int n)는 N을 취하고 이를 1로 줄이는 데 필요한 단계 수를 반환합니다.
-
초기 단계 수를 0으로 간주합니다.
-
이제 while(n!=1) n 값에 따라 1단계와 2단계를 모두 수행합니다.
-
n이 2의 거듭제곱이면( ceil(log2(n))==floor(log2(n)) is true ), n을 절반으로 줄입니다. 증분 수.
-
2의 거듭제곱이 아니면 n을 pow(2,x)로 줄입니다. 여기서 x는 floor(log2(n))입니다. 증분 수.
-
루프가 끝나면 count에 수행된 작업 수가 표시됩니다.
-
원하는 결과로 카운트를 반환합니다.
예시
#include <iostream>
#include <math.h>
using namespace std;
// Function to return number of steps for reduction
int stepCount(int n){
int count=0;
while(n!=1){
if(ceil(log2(n))==floor(log2(n))) //if n is power of 2 then this is true{
n=n/2; //reduce n to half
count++;
} else {
int x=floor(log2(n)); //floor value
n=n-(pow(2,x)); //2^x is nearest power of 2 which is less than n
count++;
}
}
return count;
}
int main(){
int N = 96;
cout <<"Count of steps required to reduce N to 1:"<<stepCount(N);
return 0;
} 출력
위의 코드를 실행하면 다음 출력이 생성됩니다 -
Count of steps required to reduce N to 1:6