숫자가 들어 있는 배열 target[]이 제공됩니다. 다음 두 가지 작업만 사용하여 [0,0,0,0...]이 모두 0인 배열을 대상으로 변환할 수 있는 최소 단계를 찾아야 합니다. -
-
증가 연산 - 모든 요소는 1씩 증가할 수 있으며, 각 증가 연산은 개별적으로 단계적으로 계산할 수 있습니다. (n 요소의 n 증분에 대해 steps=n )
-
두 배 연산 - 전체 배열이 두 배가 됩니다. 모든 요소에 대해 한 번 계산됩니다. (각 두 배 연산은 모든 요소의 값을 두 배로 하며, 단계적으로 1로 계산합니다.
목표는 목표에 도달하기 위한 최소 단계 수를 찾는 것입니다. 예를 들어 [0,0,0]은 최소 3단계(모든 요소에 대한 증분 연산)에서 [1,1,1]이 될 수 있고 이번에는 총 4단계( 3 증분, 1 두 배로 ).
입력
target[]= { 1,2,2,3 } 출력
Minimum steps to reach target from {0,0,0,0} : 6 설명
처음에는 { 0,0,0,0 }
3 증분 연산 { 0,1,1,1 } //증가는 개별적으로 발생합니다.
1 더블링 연산 { 0,2,2,2 } // 더블링은 모든 요소에서 발생합니다.
2 증가 연산 { 1,2,2,3 }
총 단계=3+1+2=6
입력
target[]= { 3,3,3 } 출력
Minimum steps to reach target from {0,0,0} : 7 설명
처음에는 { 0,0,0 }
3개의 증가 연산 { 1,1,1 } //증가는 개별적으로 발생합니다.
1 더블링 연산 { 2,2,2 } // 더블링은 모든 요소에서 발생합니다.
3 증분 연산 { 3,3,3 }
총 단계=3+1+3=7
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
정수 배열 target[]은 도달할 대상 요소를 저장합니다.
-
minSteps(int target[],int n) 함수는 대상 배열과 길이 'n'을 입력으로 사용하고 모든 0에서 대상에 도달하는 최소 단계 수를 반환합니다.
-
가변 수는 걸음 수를 저장하는 데 사용되며 초기에는 0입니다.
-
변수 max는 가장 높은 요소인 초기 target[0]을 저장하는 데 사용됩니다.
-
변수 pos는 발견된 max의 인덱스를 저장하는 데 사용되며 처음에는 0입니다.
-
target[] 배열에 모두 0이 있으면 단계가 필요하지 않으므로 0을 반환합니다. ( for (i=0;i
-
이제 이 접근 방식에서 target[]에서 모두 0에 도달합니다.
-
홀수에서 1을 빼서 모든 요소를 짝수로 만듭니다. 각 뺄셈에 대한 증분 카운트(증가 연산과 동일)
-
이제 모든 짝수가 있습니다.
-
또한 동일한 루프에서 최대값과 그 위치를 찾아 최대값과 위치값을 초기화합니다.
-
이제 최대 값이 1이 되지 않을 때까지 전체 배열을 2로 나누기 시작합니다. 임의의 숫자가 홀수이면 1을 감소시키고 카운트를 늘리고 전체 나누기 연산은 1회 증가합니다.
-
결국 모든 요소는 0 또는 1이 되며, 모든 1은 0으로 만들고 다시 카운트를 증가시킵니다.
-
count에 있는 단계로 결과를 반환합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int minSteps(int target[],int n){
int i;
int count=0;
int max=target[0];
int pos=0;
for(i=0;i<n;i++)
if(target[i]==0)
count++;
//if all are zeros, same as target
if(count==n)
return 0;
count=0;
//make all even by sbtracting 1
for(i=0;i<n;i++){
if(target[i]%2==1){
target[i]=target[i]-1;
count++;
}
//find max value and its position
if(target[i]>=max){
max=target[i];
pos=i;
}
}
//diving by 2 till all elements are 1 and increase count once
while(target[pos]!=1){
for(i=0;i<n;i++){
if(target[i]%2==1){
target[i]=target[i]-1;
count++;
}
target[i]=target[i]/2;
}
count++;
}
//whole array is {1} make zeroes and increase count
while(target[pos]!=0){
for(i=0;i<n;i++){
if(target[i]!=0){
target[i]=target[i]-1;
count++;}
}
}
return count;
}
int main(){
int target[]={15,15,15};
cout<<"\nMinimum steps to get the given desired array:"<<minSteps(target,3);
return 0;
} 출력
Minimum steps to get the given desired array:15