C++ में मौखिक अंकगणित पहेली

मान लीजिए कि हमारे पास एक समीकरण है, अभिव्यक्तियों को बाईं ओर के शब्दों और दाईं ओर के परिणाम द्वारा दर्शाया गया है। हमें यह जांचना होगा कि निम्नलिखित नियमों के तहत समीकरण हल करने योग्य है या नहीं -

• प्रत्येक वर्ण को एक अंक (0 से 9) के रूप में डिकोड किया जाता है।

• अलग-अलग वर्णों के हर जोड़े को अलग-अलग अंकों में मैप करना चाहिए।

• प्रत्येक शब्द [i] और परिणाम को एक संख्या के रूप में डिकोड किया जाता है जहां कोई अग्रणी शून्य मौजूद नहीं होता है।

• बाईं ओर की संख्याओं का योग दाईं ओर की संख्या के बराबर होगा।

• हम जांच करेंगे कि समीकरण हल करने योग्य है या नहीं।

इसलिए, यदि इनपुट शब्द =["भेजें", "अधिक"], परिणाम ="पैसा" जैसा है, तो आउटपुट सही होगा, जब हम अक्षरों को निम्नानुसार मैप करते हैं:मानचित्र 'एस'-> 9, 'ई '->5, 'एन'->6, 'डी'->7, 'एम'->1, 'ओ'->0,'आर'->8, 'वाई'->'2', फिर "भेजें" + "अधिक" ="पैसा" 9567 + 1085 =10652 के समान है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आकार की एक सरणी i2c परिभाषित करें:10, आकार की एक सरणी c2i:26 और दूसरी सरणी w

• एक फ़ंक्शन हल करें () को परिभाषित करें, इसमें idx, l, sum,

  . लगेगा

• यदि l, r के आकार के समान है, तो -

  • जब योग 0 के समान हो, तो सही लौटें

• यदि idx w के आकार के समान है, तो -

  • अगर c2i[r[l] - 'A' का ASCII] -1 के बराबर नहीं है, तो -

    • अगर c2i[r[l] - 'A' का ASCII] योग मॉड 10 के समान है, तो -

      • वापसी हल (0, एल + 1, योग / 10)

  • अन्यथा जब i2c[sum mod 10] -1 के समान है, तो -

    • यदि l, r के आकार के समान है और योग mod 10, 0 के समान है, तो -

      • झूठी वापसी

    • c2i[r[l] - 'A' का ASCII] =योग मॉड 10

    • i2c[sum mod 10] =r[l] - 'A' का ASCII

    • अस्थायी:=हल (0, एल + 1, योग / 10)

    • c2i[r[l] - 'A' का ASCII] =- 1

    • i2c[योग मॉड 10] =- 1

    • वापसी अस्थायी

  • झूठी वापसी

• अगर l>=w का आकार[idx], तो −

  • वापसी हल (आईडीएक्स + 1, एल, योग)

• अगर c2i[w[idx, l] - 'A'] -1 के बराबर नहीं है, तो -

  • यदि l, w[idx] और c2i[w[idx, l] के आकार के समान है - 'A'] का ASCII 0 के समान है, तो -

    • झूठी वापसी

  • रिटर्न सॉल्व (idx + 1, l, sum + c2i[w[idx, l] - ASCII of 'A'])

• इनिशियलाइज़ करने के लिए मैं :=0, जब मैं <10, अपडेट (i से 1 बढ़ाएँ), करें -

  • अगर i2c[i] -1 के बराबर नहीं है, तो -

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • यदि मैं 0 के समान है और l, w[idx] के आकार के समान है, तो -

    • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

  • i2c[i] :=w[idx, l] - 'A' का ASCII

  • c2i[w[idx, l] - 'A' का ASCII] =i

  • अस्थायी:=हल करें (idx + 1, l, योग + i)

  • i2c[i] :=-1

  • c2i[w[idx, l] - 'A' का ASCII] =- 1

  • यदि तापमान शून्य नहीं है, तो -

    • सही लौटें

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• i2c और c2i को -1 से भरें

• सरणी परिणाम को उलट दें

• इनिशियलाइज़ i :=0 के लिए, जब i <शब्दों का आकार, अपडेट करें (i से 1 बढ़ाएँ), do−

  • यदि शब्दों का आकार [i]> परिणाम का आकार, तो −

    • झूठी वापसी

  • सरणी शब्दों को उलट दें[i]

• आर:=परिणाम, डब्ल्यू:=शब्द

• वापसी हल (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