입력으로 정수 Number가 제공됩니다. 목표는 입력 수를 1로 줄이는 데 필요한 최소 단계 또는 작업 수를 찾는 것입니다. 수행할 수 있는 작업은 다음과 같습니다.
-
숫자가 짝수이면 2로 나눕니다.
-
Number가 홀수이면 1씩 증가 또는 감소합니다.
예시
입력 − 숫자=28
출력 − 28을 1:6으로 줄이기 위한 최소 단계
설명 -
28은 짝수입니다. 2로 나누기 =14
14는 짝수입니다. 2로 나누기 =7
7은 홀수입니다 - 1씩 증가 =8
8은 짝수입니다. 2로 나누기 =4
4는 짝수입니다. 2로 나누기 =2
2는 짝수입니다. 2로 나누기 =1
입력 − 숫자=9
출력 − 9를 1:4로 줄이기 위한 최소 단계
설명 -
9는 홀수입니다 - 1만큼 감소 =8
8은 짝수입니다. 2로 나누기 =4
4는 짝수입니다. 2로 나누기 =2
2는 짝수입니다. 2로 나누기 =1
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서는 재귀적 접근 방식을 사용하여 Number를 1로 줄이는 데 필요한 최소 작업을 확인합니다. 단순히 2로 나누는 경우에도 Number+1 또는 Number-1 중 더 작은 값에 대한 최소 방법을 재귀적으로 확인합니다.
-
입력된 숫자를 정수로 사용합니다.
-
함수 minWays(int num)는 num을 입력으로 사용하고 num을 1로 줄이는 데 필요한 최소 작업 수를 반환합니다.
-
변수 tmp1, tmp2 및 min을 정수로 사용합니다.
-
num이 0이면 1을 반환합니다.
-
num%2==0이면 짝수이고 num=num/2
로 설정합니다. -
num이 홀수이면 tmp1=minWays(num-1) 및 tmp2=minWays(num+1)로 설정합니다.
-
최소 설정은 tmp1 및 tmp2의 최소값입니다.
-
1+분을 반환합니다.
-
결국 우리는 원하는 결과를 얻을 것입니다.
-
메인에서 결과를 출력하세요.
예시
#include <iostream>
using namespace std;
int minWays(int num){
int tmp1,tmp2,min;
if (num == 1){
return 0;
}
else if (num % 2 == 0){
tmp1=minWays(num/2);
return (1 + tmp1);
}
else{
int tmp1=minWays(num - 1);
int tmp2=minWays(num + 1);
int min=tmp1<tmp2?tmp1:tmp2;
return (1 + min);
}
}
int main(){
int Number = 21;
cout <<"Minimum steps to reduce "<<Number<<" to 1: "<<minWays(Number);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Minimum steps to reduce 21 to 1: 6