資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中計算得到給定目標陣列的最小步數
給定一個包含數字的陣列 target[]，我們必須找到將全零陣列 [0,0,0,0…] 轉換為 target 陣列的最小步數，只允許使用以下兩種操作：
增量操作 - 所有元素都可以加 1，每次增量操作都單獨計入步數。(對n個元素進行n次增量，步數=n)
倍增操作 - 整個陣列翻倍。對所有元素只計算一次。(每次倍增操作使所有元素的值翻倍，步數計為1)
目標是找到達到目標陣列的最小步數。例如，[0,0,0] 可以透過3個增量操作變成 [1,1,1]（對所有元素進行增量操作），再透過一個倍增操作變成 [2,2,2]，總共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' 為輸入，並返回從全零陣列到達目標陣列的最小步數。
變數 count 用於儲存步數，初始值為 0。
變數 max 用於儲存最大元素，初始值為 target[0]。
變數 pos 用於儲存找到的最大元素的索引，初始值為 0。
如果 target[] 陣列全為零，則返回 0，因為不需要任何步數。(for (i=0;i<n;i++) if (target[i]==0) count++; if(count==n)//全為零)
在這個演算法中，我們將從 target[] 陣列反向推導到全零陣列。
透過從奇數元素中減去 1 來使所有元素都變成偶數。對每次減法操作，步數加 1（與增量操作相同）。
現在我們擁有全部偶數。
還在同一個迴圈中找到最大值及其位置，並初始化 max 和 pos。
現在我們開始將整個陣列除以 2，直到最大值不等於1。如果任何數字變成奇數，則減 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
282 次瀏覽
