ปริศนาคณิตศาสตร์ด้วยวาจาใน C ++

สมมติว่าเรามีสมการ นิพจน์แสดงด้วยคำทางด้านซ้ายและผลลัพธ์ทางด้านขวา เราต้องตรวจสอบว่าสมการแก้ได้ตามกฎต่อไปนี้หรือไม่ -

• อักขระแต่ละตัวจะถูกถอดรหัสเป็นตัวเลขเดียว (0 ถึง 9)

• อักขระที่ต่างกันทุกคู่ต้องจับคู่กับตัวเลขที่ต่างกัน

• แต่ละคำ[i]และผลลัพธ์จะถูกถอดรหัสเป็นตัวเลขที่ไม่มีศูนย์นำหน้า

• ผลรวมของตัวเลขทางด้านซ้ายจะเท่ากับตัวเลขทางด้านขวา

• เราจะตรวจสอบว่าสมการแก้ได้หรือไม่

ดังนั้น ถ้า input เหมือนกับ word =["SEND","MORE"], result ="MONEY" ผลลัพธ์ที่ได้จะเป็น True เช่นเมื่อเราจับคู่ตัวอักษรดังนี้:Map 'S'-> 9, 'E '->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0,'R'->8, 'Y'->'2' จากนั้น "SEND" + "MORE" ="MONEY" เหมือนกับ 9567 + 1085 =10652

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

• กำหนดอาร์เรย์ i2c ที่มีขนาด:10, อาร์เรย์ c2i ที่มีขนาด:26 และอาร์เรย์อื่นที่มี

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ idx, l, sum,

• ถ้า l เท่ากับขนาดของ r แล้ว −

  • คืนค่า จริง เมื่อผลรวมเท่ากับ 0

• ถ้า idx เท่ากับขนาดของ w แล้ว −

  • ถ้า c2i[r[l] - ASCII ของ 'A'] ไม่เท่ากับ -1 แล้ว −

    • ถ้า c2i[r[l] - ASCII ของ 'A'] เหมือนกับผลรวม mod 10 แล้ว -

      • ผลตอบแทนแก้(0, l + 1, ผลรวม / 10)

  • มิฉะนั้นเมื่อ i2c[sum mod 10] เหมือนกับ -1 ดังนั้น −

    • ถ้า l เท่ากับขนาดของ r และ sum mod 10 เท่ากับ 0 ดังนั้น −

      • คืนค่าเท็จ

    • c2i[r[l] - ASCII ของ 'A'] =ผลรวม mod 10

    • i2c[sum mod 10] =r[l] - ASCII ของ 'A'

    • อุณหภูมิ :=แก้(0, l + 1, ผลรวม / 10)

    • c2i[r[l] - ASCII ของ 'A'] =- 1

    • i2c[sum mod 10] =- 1

    • อุณหภูมิกลับ

  • คืนค่าเท็จ

• ถ้า l>=ขนาดของ w[idx] แล้ว −

  • คืนค่าแก้(idx + 1, l, ผลรวม)

• ถ้า c2i[w[idx, l] - 'A'] ไม่เท่ากับ -1 แล้ว −

  • ถ้า l เท่ากับขนาดของ w[idx] และ c2i[w[idx, l] - ASCII ของ 'A'] เท่ากับ 0 ดังนั้น −

    • คืนค่าเท็จ

  • ผลตอบแทนการแก้ (idx + 1, l, ผลรวม + c2i[w[idx, l] - ASCII ของ 'A'])

• สำหรับการเริ่มต้น i :=0 เมื่อ i <10 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า i2c[i] ไม่เท่ากับ -1 แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้าฉันเท่ากับ 0 และ l เท่ากับขนาดของ w[idx] แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • i2c[i] :=w[idx, l] - ASCII ของ 'A'

  • c2i[w[idx, l] - ASCII ของ 'A'] =i

  • temp :=แก้(idx + 1, l, sum + i)

  • i2c[i] :=-1

  • c2i[w[idx, l] - ASCII ของ 'A'] =- 1

  • ถ้าอุณหภูมิไม่เป็นศูนย์ −

    • คืนความจริง

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เติม i2c และ c2i ด้วย -1

• กลับผลลัพธ์อาร์เรย์

• สำหรับการเริ่มต้น i :=0, เมื่อ i <ขนาดของคำ, อัปเดต (เพิ่ม i ขึ้น 1), do−

  • ถ้าขนาดของคำ[i]> ขนาดของผลลัพธ์ −

    • คืนค่าเท็จ

  • กลับคำอาร์เรย์[i]

• r :=ผลลัพธ์ w :=คำ

• คืนค่าแก้(0, 0, 0)

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   char i2c[10];
   int c2i[26];
   vector<string> w;
   string r;
   bool solve(int idx, int l, int sum){
      if (l == r.size()) {
         return sum == 0;
      }
      if (idx == w.size()) {
         if (c2i[r[l] - 'A'] != -1) {
            if (c2i[r[l] - 'A'] == sum % 10) {
               return solve(0, l + 1, sum / 10);
            }
         }
         else if (i2c[sum % 10] == -1) {
            if (l == r.size() - 1 && sum % 10 == 0)
            return false;
            c2i[r[l] - 'A'] = sum % 10;
            i2c[sum % 10] = r[l] - 'A';
            bool temp = solve(0, l + 1, sum / 10);
            c2i[r[l] - 'A'] = -1;
            i2c[sum % 10] = -1;
            return temp;
         }
         return false;
      }
      if (l >= w[idx].size()) {
         return solve(idx + 1, l, sum);
      }
      if (c2i[w[idx][l] - 'A'] != -1) {
         if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
            return false;
         }
         return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
      }
      for (int i = 0; i < 10; i++) {
         if (i2c[i] != -1)
         continue;
         if (i == 0 && l == w[idx].size() - 1)
         continue;
         i2c[i] = w[idx][l] - 'A';
         c2i[w[idx][l] - 'A'] = i;
         bool temp = solve(idx + 1, l, sum + i);
         i2c[i] = -1;
         c2i[w[idx][l] - 'A'] = -1;
         if (temp)
         return true;
      }
      return false;
   }
   bool isSolvable(vector<string>& words, string result){
      memset(i2c, -1, sizeof(i2c));
      memset(c2i, -1, sizeof(c2i));
      reverse(result.begin(), result.end());
      for (int i = 0; i < words.size(); i++) {
         if (words[i].size() > result.size())
         return false;
         reverse(words[i].begin(), words[i].end());
      }
      r = result;
      w = words;
      return solve(0, 0, 0);
   }
};
main(){
   Solution ob;
   vector<string> v = {"SEND","MORE"};
   cout << (ob.isSolvable(v, "MONEY"));
}

อินพุต

{"SEND","MORE"}, "MONEY"

ผลลัพธ์

1