Рубрики

C ++ программа для решения криптарифметических задач

Газеты и журналы часто имеют загадочно-арифметические загадки вида:
Примеры:

Input : s1 = SEND, s2 = "MORE", s3 = "MONEY"
Output : One of the possible solution is:
         D=1 E=5 M=0 N=3 O=8 R=2 S=7 Y=6  
Explanation:
The above values satisfy below equation : 
  SEND
+ MORE
--------
 MONEY
-------- 

Настоятельно рекомендуется обратиться к Backtracking | Задайте 8 (Решение Криптарифметических Пазлов) для решения этой проблемы.

Идея состоит в том, чтобы присвоить каждой букве цифру от 0 до 9, чтобы арифметика работала правильно. Перестановка — это рекурсивная функция, которая вызывает функцию проверки для каждой возможной перестановки целых чисел.
Функция проверки проверяет, равна ли сумма первых двух чисел, соответствующих первым двум строкам, третьему числу, соответствующему третьей строке. Если решение найдено, распечатайте решение.

// CPP программа для решения криптографических головоломок
#include <bits/stdc++.h>

using namespace std;

  
// вектор хранит 1, соответствующий индексу
// номер, который уже присвоен
// на любой символ, в противном случае хранит 0

vector<int> use(10);

  
// структура для хранения char и соответствующего ему целого числа

struct node

{

    char c;

    int v;

};

  
// проверка функции на правильное решение

int check(node* nodeArr, const int count, string s1,

                               string s2, string s3)

{

    int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;

  

    // вычисляем число, соответствующее первой строке

    for (i = s1.length() - 1; i >= 0; i--)

    {

        char ch = s1[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

  

        val1 += m * nodeArr[j].v;

        m *= 10;

    }

    m = 1;

  

    // вычисляем число, соответствующее второй строке

    for (i = s2.length() - 1; i >= 0; i--)

    {

        char ch = s2[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

  

        val2 += m * nodeArr[j].v;

        m *= 10;

    }

    m = 1;

  

    // вычисляем число, соответствующее третьей строке

    for (i = s3.length() - 1; i >= 0; i--)

    {

        char ch = s3[i];

        for (j = 0; j < count; j++)

            if (nodeArr[j].c == ch)

                break;

  

        val3 += m * nodeArr[j].v;

        m *= 10;

    }

  

    // сумма первых двух чисел равна третьей возвращаемое значение true

    if (val3 == (val1 + val2))

        return 1;

  

    // еще вернуть false

    return 0;

}

  
// Рекурсивная функция для проверки решения для всех перестановок

bool permutation(const int count, node* nodeArr, int n,

                 string s1, string s2, string s3)

{

    // Базовый вариант

    if (n == count - 1)

    {

  

        // проверяем все неиспользуемые номера

        for (int i = 0; i < 10; i++)

        {

  

            // если не используется

            if (use[i] == 0)

            {

  

                // присваиваем char по индексу n целому числу i

                nodeArr[n].v = i;

  

                // если решение найдено

                if (check(nodeArr, count, s1, s2, s3) == 1)

                {

                    cout << "\nSolution found: ";

                    for (int j = 0; j < count; j++)

                        cout << " " << nodeArr[j].c << " = "

                             << nodeArr[j].v;

                    return true;

                }

            }

        }

        return false;

    }

  

    for (int i = 0; i < 10; i++)

    {

  

        // если i-е целое число еще не используется

        if (use[i] == 0)

        {

  

            // присваиваем char по индексу n целому числу i

            nodeArr[n].v = i;

  

            // пометить его как недоступный для других символов

            use[i] = 1;

  

            // вызов рекурсивной функции

            if (permutation(count, nodeArr, n + 1, s1, s2, s3))

                return true;

  

            // возвращаемся назад для всех других возможных решений

            use[i] = 0;

        }

    }

    return false;

}

  

bool solveCryptographic(string s1, string s2,

                                   string s3)

{

    // рассчитывать на номер уникального символа

    int count = 0;

  

    // Длина всех трех строк

    int l1 = s1.length();

    int l2 = s2.length();

    int l3 = s3.length();

  

    // вектор для хранения частоты каждого символа

    vector<int> freq(26);

  

    for (int i = 0; i < l1; i++)

        ++freq[s1[i] - 'A'];

  

    for (int i = 0; i < l2; i++)

        ++freq[s2[i] - 'A'];

  

    for (int i = 0; i < l3; i++)

        ++freq[s3[i] - 'A'];

  

    // посчитаем количество уникальных символов

    for (int i = 0; i < 26; i++)

        if (freq[i] > 0)

            count++;

  

    // решение не возможно для счета больше 10

    if (count > 10)

    {

        cout << "Invalid strings";

        return 0;

    }

  

    // массив узлов

    node nodeArr[count];

  

    // сохраняем все уникальные символы в nodeArr

    for (int i = 0, j = 0; i < 26; i++)

    {

        if (freq[i] > 0)

        {

            nodeArr[j].c = char(i + 'A');

            j++;

        }

    }

    return permutation(count, nodeArr, 0, s1, s2, s3);

}

  
// Функция драйвера

int main()

{

    string s1 = "SEND";

    string s2 = "MORE";

    string s3 = "MONEY";

  

    if (solveCryptographic(s1, s2, s3) == false)

        cout << "No solution";

    return 0;

}

Выход:

Solution found:  D=1 E=5 M=0 N=3 O=8 R=2 S=7 Y=6

Рекомендуемые посты:

C ++ программа для решения криптарифметических задач

0.00 (0%) 0 votes