计算在 C++ 中获得给定所需数组的最小步骤

2023-06-21 15:58:03 284

我们得到了一个数组target[]，其中包含数字。我们必须找到可以仅使用以下两个操作将全零数组[0,0,0,0...]转换为目标的最小步骤-

递增操作-所有元素都可以递增1，每个递增操作都可以分步单独计数。（对于n个元素中的n个增量step=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(inttarget[],intn)将目标数组及其长度'n'作为输入，并返回从所有零到达目标的最小步数。

变量计数用于存储步数，最初为0。

变量max用于存储最高元素，最初为target[0]。

变量pos用于存储maxfound的索引，最初为0。

如果target[]数组全为零，则返回0，因为不需要步骤。(for(i=0;i

现在在这种方法中，我们将从target[]到达所有零。

通过从奇数中减去1使所有元素偶数。每次减法的递增计数（与递增操作相同）

现在我们都有偶数了。

还要在同一个循环中找到最大值及其位置，并初始化max和pos。

现在我们开始将整个数组除以2，直到最大值不再为1。如果有任何数字变为奇数，则减1并增加计数，对于整个除法运算，计数会增加一次。

最后，所有元素都将是0或1，因为所有1使它们成为0并再次增加计数。

将结果作为计数中存在的步数返回。

示例

#include 
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=max){
         max=target[i];
         pos=i;
      }
   }
   //减2直到所有元素都为1并增加一次计数
   while(target[pos]!=1){
      for(i=0;i输出结果Minimum steps to get the given desired array:15

计算在 C++ 中获得给定所需数组的最小步骤

输入

解释

输入

解释

下面程序中使用的方法如下

示例

热门推荐

随机推荐