Chúng ta được đưa ra với một mục tiêu mảng [] có các số trong đó. Chúng ta phải tìm các bước tối thiểu trong đó mảng có tất cả các số 0 [0,0,0,0…] có thể được chuyển đổi thành đích chỉ bằng hai phép toán sau -
-
Hoạt động tăng dần - tất cả các phần tử có thể được tăng thêm 1, mỗi hoạt động tăng dần có thể được đếm riêng lẻ theo từng bước. (cho n số gia tăng trong n phần tử bước =n)
-
Hoạt động nhân đôi - toàn bộ mảng được nhân đôi. Đối với tất cả các phần tử, nó được tính một lần. (mỗi thao tác nhân đôi nhân đôi giá trị của tất cả các phần tử, tính giá trị đó là 1 trong các bước
Mục tiêu là tìm số bước tối thiểu để đạt được mục tiêu. Ví dụ:[0,0,0] có thể trở thành [1,1,1] trong 3 bước tối thiểu (bằng hoạt động tăng dần trên tất cả các phần tử) và có thể trở thành [2,2,2] bằng hoạt động nhân đôi nhiều hơn, tổng cộng 4 bước lần này ( 3 lần tăng, 1 lần tăng gấp đôi).
Đầu vào
target[]= { 1,2,2,3 } Đầu ra
Minimum steps to reach target from {0,0,0,0} : 6 Giải thích
Ban đầu, chúng tôi có {0,0,0,0}
3 phép toán tăng dần {0,1,1,1} // phép toán tăng dần diễn ra riêng lẻ
1 thao tác nhân đôi {0,2,2,2} // nhân đôi xảy ra trên tất cả các phần tử
2 phép toán gia tăng {1,2,2,3}
Tổng số bước =3 + 1 + 2 =6
Đầu vào
target[]= { 3,3,3 } Đầu ra
Minimum steps to reach target from {0,0,0} : 7 Giải thích
Ban đầu, chúng tôi có {0,0,0}
3 phép toán tăng dần {1,1,1} // phép toán tăng dần diễn ra riêng lẻ
1 thao tác nhân đôi {2,2,2} // nhân đôi xảy ra trên tất cả các phần tử
3 phép toán gia tăng {3,3,3}
Tổng số bước =3 + 1 + 3 =7
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mục tiêu mảng số nguyên [] lưu trữ các phần tử mục tiêu sẽ đạt được.
-
Hàm minSteps (int target [], int n) nhận mảng mục tiêu và độ dài ‘n’ của nó làm đầu vào và quay lại số bước tối thiểu cần đạt được để đạt được mục tiêu từ tất cả các số 0.
-
Số lượng biến được sử dụng để lưu trữ số bước, ban đầu là 0.
-
Giá trị tối đa của biến được sử dụng để lưu trữ phần tử cao nhất, mục tiêu ban đầu là [0].
-
Vị trí biến được sử dụng để lưu trữ chỉ số của tối đa được tìm thấy, ban đầu là 0.
-
Nếu mảng [] đích có tất cả các số 0 thì trả về 0 vì không cần thực hiện bước nào. (for (i =0; i
-
Bây giờ, trong cách tiếp cận này, chúng tôi sẽ tiếp cận từ mục tiêu [] đến tất cả các số không.
-
Làm cho tất cả các phần tử chẵn bằng cách trừ đi 1 từ các phần tử lẻ. Số lượng tăng dần cho mỗi phân số (giống như hoạt động cộng dồn)
-
Bây giờ chúng ta có tất cả các số chẵn.
-
Đồng thời tìm giá trị tối đa và vị trí của nó trong cùng một vòng lặp và khởi tạo giá trị tối đa và vị trí.
-
Bây giờ chúng ta bắt đầu chia toàn bộ mảng cho 2 cho đến khi giá trị lớn nhất không trở thành 1. Nếu số bất kỳ trở thành số lẻ, hãy giảm 1 và tăng số lượng, cho toàn bộ hoạt động chia sẽ đếm một lần.
-
Cuối cùng, tất cả các phần tử sẽ là 0 hoặc 1, đối với tất cả các phần tử sẽ là 0 và số tăng dần.
-
Trả về kết quả dưới dạng số bước hiện diện.
Ví dụ
#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;
} Đầu ra
Minimum steps to get the given desired array:15