Links ::  | DEV web management system | Katalóg | Webhosting | Recepty
  
 Index | Registrácia | Hľadať | Galéria | BoardNeprihlásený užívateľ  //Piatok, 15. Decembra 2017 
Navigation
Index
Top 10 autorov
Top 20 článkov
Hľadať
Galéria

Zones
Asp.(NET)
C/C++
Flash
Grafika+Design
Hardware
Hry
Html/Css/Xml
Java
Linux
Networks
Operačný systém
Pascal/Delphi
PHP
Security
Software
SQL
Visual Basic
Wap/Wml
Windows
Zóna iné

Links
Script index Interval.cz Pc.sk Regedit.sk TipyaTriky.sk Builder.cz Asp.cz Živě.sk Zoznam.sk Code.box.sk Root.cz Quant&Financial

Odkazy

Sessions
Stránky Developer.sk si práve číta 482 čitateľov, z toho je 0 zaregistrovaných

BackEnd
Odkazy na nové články je možné preberať pomocou backend.php

kuk

    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


Autor : Dev, čítané 9052x, komentárov: 0
Hodnotenie :    |  Streda, 3. Decembra 2003

Pridať nový komentár/Komentáre
Login
Login:
Heslo:

Hľadať
 
v článkoch
v diskusiach
v komentároch

Top read
PHP Coder

DEV web management system

Priklady v C. 1.čast.

Php a bezpečnosť skriptov

Autorun CD

Top discuss
Jednoduchý web formulár (ASP.NET)

Delphi seriál: (1.časť)

Velmi rychla grafika v Pascale

DEV web management system

Naša ikona
Páčia sa Vám naše stránky ? Ak áno, podporte nás prosím a umiestnite si na svoju stránku našu ikonku:





Copyright (c) Developer.sk, All rights reserved.
Powered by DEV web management system