Algoritmické riešenie kryptogramov

Kryptogram je špeciálna rovníca, ktorá pozostáva pseudo-čísel, v ktorých sú číslice vyjadrené pomocou znakov. Takto sa každá číslica stáva neznámou. Našou úlohou je zistiť všetky možné kombinácie číslic, pre ktoré rovnica platí.

Kryptogramatickou rovnicou môže byť napríklad rovnica v tvare:

ABB + ABB + ABB + CBA = BDAE

V rovnici písmená A, B, C, D, E predstavujú päť rôznych číslic, z ktorých môže byť kryptogram zostavený. Hodnoty A, B, C, D, E musia byť teda tiež rôzne, pričom platí: A != B != C != D != E

Žiadne číslo nesmie začínať nulou. Z toho vyplýva skutočnosť, že v horeuvedenej rovnici číslice A, B, C nesmú byť nuly.

Ak má kryptogram x-roznych číslic (neznámych), voláme ho kryptogram x-tého rádu. Horeuvedená rovnica teda predstavuje kryptogram 5-teho rádu, kedže má 5 neznámych.

Napíšme si funkciu, ktorá bude zisťovať rovnosť kryptogramu pre konkrétne hodnoty neznámych. Neznáme budú rovnici odovzdávané prostredníctvom poľa. Pre číslice A, B vypočítame hodnotu pozičného výrazu ABB podľa vzťahu 100 * A + 10 * B + 1 * C a pod.

bool kryptogram (int* pole) {
if (
100 * A + 10 * B + C +
100 * A + 10 * B + C +
100 * C + 10 * B + A ==
1000 * B + 100 * D + 10 * A + E
) return true; else return false;
}

Funkcia preberie konkrétne hodnoty premenných A, B, C, D, E v poli "pole". Pomocou makra v c++ definujeme, že výraz A zastupuje vo funkcií výraz pole[0], výraz B je ekvivalentný výrazu pole[1], atď:

#define A pole[0]
#define B pole[1]
...
#define Z pole[25]

Po zavolaní funkcie kryptogram budú konkrétne hodnoty v poli pole[] konvertované na premenné A, B, C ... Ak rovnosť platí, kryptogram vracia hodnotu true.

Ako teda nájsť všetky riešenia kryptogramu ? Jediným riešením je použitie hrubej sily v zmysle dostadzovania všetkých možných kombinácií číslic do kryptogramatickej funkcie. Pre statický počet rôznych číslic môžeme navrhnúť veľmi jednoduchý systém vnorených cyklov. Toto riešenie však je značne primitívne a viazané iba na konkrétny kryptogram. Ak pridáme ďalšie neznáme do kryptogramu - zmeníme jeho rád, treba ručne pridať aj ďalšie vnorené cykly.

Pre kryptogram 5-teho stupňa (neznáme A, B, C, D, E) by sme museli použiť 5 návzájom vnorených cyklov:

for (int A=0; B<=9; a++)
for (int B=0; B<=9; a++)
for (int B=0; B<=9; a++)
for (int B=0; B<=9; a++)
for (int B=0; B<=9; a++)
// telo cyklu sa zopakuje
// 10n krát, pričom
// n je stupeň kryptogram. funkcie

Ak dopredu nepoznáme rád kryptogramu, a teda aj počet vnorených cyklov, je vnodné použiť oveľa sofistikovanejšiu metódu, ktorá spočíva vo rekurzných vlastnostiach funkcií. Rekurzívna funkcia je taká, ktorá vo svojom "vnútry" obsahuje volanie samej seba. Vnodnou rekurzivnou funkciou možno dosiahnuť to, že kód obsiahnutý vo funkcií sa bude vykonávať tak, ako by bol umiestnený v systéme vnorených cyklov.

Definujme si teda rekurzivnu funkciu "cyklus":

void cyklus (int z, int k, int rad) {
for (int a=z; a<=k; a++) {
arr[rad]=a;
if (rad<c_rad-1) {
if (kryptogram (arr)) vypis (arr);
cyklus (0,9,rad+1);
}
else
if (kryptogram (arr)) vypis (arr);
}
}

V rámci jedného volania funkcie cyklus sa vykoná cyklus od z po k na číslici rádu rad, tak ako je to dané parametrami pri volaní funkcie. Pole arr[n] obsahuje aktuálne hodnoty pre každú číslicu, pričom n je rád kryptogramu.

Všimnime si, že z jednej pôvodnej "rodičovskej" funkcie sa volá k-z nových funkcií. Pri kryptograme n-tého stupňa teda vzniká tiež 10n opakovaní tela funkcie. Nová funkcia sa rekurzívne volá vždy s argumentom rádu vyšším o 1. Vo vnútri rekurzívnej funkcie sa volá funkcia kryptogram, ktorá vracia, či platí rovnosť pre konkrétne hodnoty číslic práve vykonávaného cyklu. Ak rovnosť platí, volá sa funkcia vypis (aktuálnych hodnôt).

Pozrime sa teda bližšie na funkciu vypis:

void vypis (int arr[]) {
if (!zhoda(arr)) {
for (int x=0; x<c_rad; x++)
cout << alphabet[x] << "="
<< arr[x] << " ";
cout << endl;
}
}

Funkcia vypíše obsah poľa arr, ktorá nesie hodnoty neznámych A, B, C, atď. Na začiatku bolo spomenuté, že číslice A, B, C, ... musia byť rôzne. Ináč povedané, každý prvok poľa arr[] musí byť jedninečný. Funkcia zhoda vracia boolean hodnotu false, ak sú všetky prvky poľa arr rôzne, v opačnom prípade vracia true.

Funkcia zhoda pre analýzu pola využíva funkcie add_to_vektor, check_vektor a erase_all, ktoré tu rozvádzať nebudem, nakoľko princíp ich činnosti nie je podstatný pre pochopenie problematiky kryptogramov.

Nasleduje kompletný algoritmus c++, ktorý vypočíta všetky možné hodnoty cifier kryptogramu:

#include <iostream>
#include <cstdlib>
#include <vector>
#define A pole[0]
#define B pole[1]
#define C pole[2]
#define D pole[3]
#define E pole[4]
#define F pole[5]
#define G pole[6]
#define H pole[7]
#define I pole[8]
#define J pole[9]
#define K pole[10]
#define L pole[11]
#define M pole[12]
#define N pole[13]
#define O pole[14]
#define P pole[15]
#define Q pole[16]
#define R pole[17]
#define S pole[18]
#define T pole[19]
#define U pole[20]
#define V pole[21]
#define W pole[22]
#define X pole[23]
#define Y pole[24]
#define Z pole[25]

const int c_rad = 5;
// Stupeň kryptogramu (počet neznámych)
bool kryptogram (int* pole) {
if (
// Sem definujte kryptogram
// Pre správne fungovanie algoritmu neznáme označujte
// veľkými písmenami od "A", "B", atď...
100 * A + 10 * B + C +
100 * A + 10 * B + C +
100 * C + 10 * B + A ==
1000 * B + 100 * D + 10 * A + E
) return true; else return false;
}

const char alphabet[] = {'A','B',' C','D','E' ,'F','G',
'H','I','J ','K','L', 'M','N',
'O','P','Q ','R','S', 'T','U',
'V','W','X ','Y','Z'} ;
int n;
vector<int> vektor;
int arr[30];

void add_to_vektor(int num) {
bool flag = false;
for (int x=0; x<vektor.size(); x++)
if (vektor[x]==num) flag = true;
if (!flag) vektor.push_back(num);
}

bool check_vektor() {
if (vektor.size()==c_rad) return false;
else return true;
}

void erase_all(vector<int>& vect) {
for (int a=vect.size()-1; a>=0; a--)
vect.erase(vect.begin()+a);
}

bool zhoda(int arr[]) {
for (int x=0; x<c_rad; x++)
add_to_vektor(arr[x]);
bool flag = check_vektor();
erase_all(vektor);
return flag;
}

void vypis (int arr[]) {
if (!zhoda(arr)) {
for (int x=0; x<c_rad; x++)
cout << alphabet[x] << "=" << arr[x] << " ";
cout << endl;
}
}

void cyklus (int z, int k, int rad) {
for (int a=z; a<=k; a++) {
arr[rad]=a;
if (rad<c_rad-1) {
if (kryptogram (arr)) vypis (arr);
cyklus (0,9,rad+1);
}
else
if (kryptogram (arr)) vypis (arr);
}
}

int main() {
cyklus(0,9,0);
cout << "Hotovo\n";
system("PAUSE");
return 0;
}

Pozn.: Keďže program nemá implementovaný parsing reťazcov, kryptogram treba zadať ručne vo funkcii kryptogram