ตัวดำเนินการน้อยที่สุดเพื่อแสดงจำนวนใน C ++

สมมติว่าเรามีจำนวนเต็มบวก x เราจะเขียนนิพจน์ของรูปแบบ x (op1) x (op2) x (op3) x ... โดยที่ op1, op2 ฯลฯ เป็นโอเปอเรเตอร์ และตัวดำเนินการเหล่านี้สามารถเป็นได้ทั้งการบวก การลบ การคูณ หรือหาร ตัวอย่างเช่น ด้วย x =3 เราอาจเขียน 3 * 3 / 3 + 3 - 3 ซึ่งมีค่าเท่ากับ 3 มีกฎอยู่สองสามข้อดังนี้ -

• ตัวดำเนินการหาร (/) ส่งกลับจำนวนตรรกยะ

• ไม่มีวงเล็บอยู่ตรงไหน

• เราใช้ลำดับการดำเนินการตามปกติ - การคูณและการหารมีลำดับความสำคัญสูงกว่าการบวกและการลบ

• ไม่อนุญาตให้ใช้โอเปอเรเตอร์การปฏิเสธแบบเอกนารี

เราต้องเขียนนิพจน์ด้วยตัวดำเนินการจำนวนน้อยที่สุดเพื่อให้นิพจน์เท่ากับเป้าหมายที่กำหนด ดังนั้นเราจะหาจำนวนตัวดำเนินการน้อยที่สุด

ดังนั้น หากอินพุตเท่ากับ x =4, เป้าหมาย =15 ผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถแสดง 15 เป็น 4*4- 4/4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้าเป้าหมายเหมือนกับ x แล้ว −

  • ถ้า x> เป้าหมาย แล้ว −

    • ส่งกลับขั้นต่ำของ (x - เป้าหมาย) * 2 และ (เป้าหมาย * 2) - 1

• ผลรวม :=x, t :=0

• ในขณะที่ผลรวม <เป้าหมาย ทำ -

  • ผลรวม :=ผลรวม * x

  • (เพิ่มขึ้น t โดย 1)

• หากผลรวมเท่ากับเป้าหมาย −

  • กลับ t

• l :=inf, r :=inf

• ถ้าผลรวม - เป้าหมายเป้าหมาย แล้ว -

  • r :=littleOpsExpressTarget(x, sum - target)

• l :=littleOpsExpressTarget(x, target - (sum / x))

• คืนค่า 1 + ขั้นต่ำของ l และ r

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int leastOpsExpressTarget(int x, int target) {
      if(target == x) return 0;
      if(x > target){
         return min((x - target) * 2, (target * 2) - 1);
      }
      lli sum = x;
      int t = 0;
      while(sum < target){
         sum *= x;
         t++;
      }
      if(sum == target) return t;
      int l = INT_MAX;
      int r = INT_MAX;
      if(sum - target < target){
         r = leastOpsExpressTarget(x, sum - target) + t;
      }
      l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
      return min(l, r) + 1;
   }
};
main(){
   Solution ob;
   cout << (ob.leastOpsExpressTarget(4, 15));
}

อินพุต

4, 15

ผลลัพธ์

3