นับขั้นตอนขั้นต่ำเพื่อให้ได้อาร์เรย์ที่ต้องการใน C++

เราได้รับอาร์เรย์เป้าหมาย[] ซึ่งมีตัวเลขอยู่ในนั้น เราต้องค้นหาขั้นตอนขั้นต่ำที่อาร์เรย์ที่มีค่าศูนย์ทั้งหมด [0,0,0,0…] สามารถแปลงเป็นเป้าหมายโดยใช้การดำเนินการสองรายการต่อไปนี้เท่านั้น -

• การดำเนินการที่เพิ่มขึ้น - องค์ประกอบทั้งหมดสามารถเพิ่มได้ 1 การดำเนินการที่เพิ่มขึ้นแต่ละครั้งสามารถนับทีละรายการเป็นขั้นตอน ( สำหรับการเพิ่มขึ้น n ใน n องค์ประกอบ steps=n )

• การดำเนินการเป็นสองเท่า - ทั้งอาร์เรย์จะเพิ่มเป็นสองเท่า สำหรับองค์ประกอบทั้งหมดจะถูกนับครั้งเดียว (การดำเนินการสองเท่าแต่ละครั้งจะเพิ่มค่าขององค์ประกอบทั้งหมดเป็นสองเท่า นับเป็น 1 ในขั้นตอน

เป้าหมายคือการหาจำนวนขั้นตอนขั้นต่ำเพื่อให้บรรลุเป้าหมาย เช่น [0,0,0] สามารถกลายเป็น[1,1,1] ได้อย่างน้อย 3 ขั้นตอน ( โดยการเพิ่มการดำเนินการในทุกองค์ประกอบ ) และจะกลายเป็น [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

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เป้าหมายอาร์เรย์จำนวนเต็ม[] เก็บองค์ประกอบเป้าหมายที่จะไปถึง

• ฟังก์ชัน minSteps(int target[],int n) ใช้อาร์เรย์เป้าหมายและความยาว 'n' เป็นอินพุตและส่งกลับจำนวนขั้นตอนขั้นต่ำที่จะไปถึงเป้าหมายจากศูนย์ทั้งหมด

• การนับตัวแปรใช้เพื่อเก็บการนับก้าว เริ่มแรกเป็น 0

• ตัวแปร max ใช้เพื่อเก็บองค์ประกอบสูงสุด เริ่มต้นเป้าหมาย[0].

• pos ตัวแปรใช้เพื่อเก็บดัชนีของ max found เริ่มแรก 0

• หากอาร์เรย์ target[] มีศูนย์ทั้งหมด ให้คืนค่า 0 เนื่องจากไม่มีขั้นตอนที่จำเป็น ( สำหรับ (i=0;i

• ในแนวทางนี้ เราจะเข้าถึงจากเป้าหมาย[] ไปยังศูนย์ทั้งหมด

• สร้างองค์ประกอบทั้งหมดได้โดยการลบ 1 จากคี่ จำนวนที่เพิ่มขึ้นสำหรับแต่ละการลบ (เช่นเดียวกับการดำเนินการที่เพิ่มขึ้น)

• ตอนนี้มีเลขคู่ครบแล้ว

• หาค่าสูงสุดและตำแหน่งของมันในลูปเดียวกันและเริ่มต้น max และ pos

• ตอนนี้ เราเริ่มหารทั้งอาร์เรย์ด้วย 2 จนกว่าค่าสูงสุดจะไม่กลายเป็น 1 หากจำนวนใดกลายเป็นเลขคี่ ให้ลดค่า 1 และเพิ่มจำนวน สำหรับการดำเนินการหารทั้งหมด การเพิ่มขึ้นจะนับหนึ่งครั้ง

• ในตอนท้ายองค์ประกอบทั้งหมดจะเป็น 0 หรือ 1 สำหรับ 1 ทั้งหมดทำให้เป็น 0 และนับเพิ่มขึ้นอีกครั้ง

• ส่งคืนผลลัพธ์ตามขั้นตอนที่มีอยู่ในการนับ

ตัวอย่าง

#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