Câu đố số học bằng lời nói trong C ++

Giả sử chúng ta có một phương trình, các biểu thức được biểu diễn bằng các từ ở phía bên trái và kết quả ở phía bên phải. Chúng ta phải kiểm tra xem phương trình có thể giải được theo các quy tắc sau hay không -

Mỗi ký tự được giải mã dưới dạng một chữ số (0 đến 9).
Mỗi cặp ký tự khác nhau phải ánh xạ đến các chữ số khác nhau.
Mỗi từ [i] và kết quả được giải mã dưới dạng số không có số 0 ở đầu.
Tổng các số ở bên trái sẽ bằng số ở bên phải.
Chúng tôi sẽ kiểm tra xem phương trình có thể giải được hay không.

Vì vậy, nếu đầu vào là words =["SEND", "MORE"], result ="MONEY", thì đầu ra sẽ làTrue, như khi chúng ta ánh xạ các chữ cái như sau:Map 'S' -> 9, 'E '-> 5,' N '-> 6,' D '-> 7,' M '-> 1,' O '-> 0,' R '-> 8,' Y '->' 2 ', sau đó "SEND" + "MORE" ="MONEY" giống với 9567 + 1085 =10652.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một mảng i2c có kích thước:10, một mảng c2i có kích thước:26 và một mảng khác w
Xác định một hàm giải quyết (), hàm này sẽ nhận idx, l, sum,
nếu l bằng với kích thước của r, thì -
- trả về true khi tổng bằng 0
nếu idx bằng với kích thước của w, thì -
- nếu c2i [r [l] - ASCII của 'A'] không bằng -1, thì -
  - nếu c2i [r [l] - ASCII của 'A'] giống với sum mod 10, thì -
    - trả về giải quyết (0, l + 1, sum / 10)
- ngược lại khi i2c [sum mod 10] giống -1, thì -
  - nếu l bằng với kích thước của r và tổng mod 10 bằng 0, thì -
    - trả về false
  - c2i [r [l] - ASCII của 'A'] =sum mod 10
  - i2c [sum mod 10] =r [l] - ASCII của 'A'
  - tạm thời:=giải quyết (0, l + 1, sum / 10)
  - c2i [r [l] - ASCII của 'A'] =- 1
  - i2c [sum mod 10] =- 1
  - trở lại nhiệt độ
- trả về false
nếu l> =kích thước của w [idx], thì -
- trả về giải quyết (idx + 1, l, sum)
nếu c2i [w [idx, l] - 'A'] không bằng -1, thì -
- nếu l bằng với kích thước của w [idx] và c2i [w [idx, l] - ASCII của 'A'] bằng 0, thì -
  - trả về false
- trả về giải quyết (idx + 1, l, sum + c2i [w [idx, l] - ASCII của 'A'])
để khởi tạo i:=0, khi tôi <10, hãy cập nhật (tăng i lên 1), thực hiện -
- nếu i2c [i] không bằng -1, thì -
  - Bỏ qua phần sau, chuyển sang phần tiếp theo
- nếu tôi giống với 0 và l bằng với kích thước của w [idx], thì -
  - Bỏ qua phần sau, chuyển sang phần tiếp theo
- i2c [i]:=w [idx, l] - ASCII của 'A'
- c2i [w [idx, l] - ASCII của 'A'] =i
- tạm thời:=giải quyết (idx + 1, l, sum + i)
- i2c [i]:=-1
- c2i [w [idx, l] - ASCII của 'A'] =- 1
- nếu nhiệt độ khác 0, thì -
  - trả về true
trả về false
Từ phương thức chính, hãy làm như sau -
điền i2c và c2i bằng -1
đảo ngược kết quả mảng
để khởi tạo i:=0, khi tôi
- nếu kích thước của các từ [i]> kích thước của kết quả, thì -
  - trả về false
- đảo ngược các từ mảng [i]
r:=result, w:=words
trả về giải quyết (0, 0, 0)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"));
}

Đầu vào

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

Câu đố số học bằng lời nói trong C ++

Ví dụ

Đầu vào

Đầu ra