数据结构
网络
关系数据库管理系统 (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 次浏览
