Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
10.08.2002, 11:25 Uhr
Bruder Leif
dances with systems
(Operator)

Moin moin!

So, jetzt auch mal was von mir:

Das Programm soll eine Textdatei einlesen, die ausschließlich aus Großbuchstaben besteht, z.B.

ABCBBHMZNGJTUZNABCKZBNJFNABCJZVZT.....

Diese Datei soll auf "Wörter" (häufig wiederholte Buchstabenkombinationen mit mehr als 2 Zeichen Länge) untersucht werden (hier z.B. ABC), und die Abstände dazwischen ausgegeben werden.

Beispiel:

"Wort": "ABC" Abstände: 15, 10
(usw.)

Mit einem solchen Verfahren kann die Länge des Schlüssels ermittelt werden, mit dem ein Text nach dem "Vigenere-Verfahren" verschlüsselt wurde. Dazu mehr im 2. Teil ;-)

Gewonnen hat das Programm, das am schnellsten die verschlüsselte "X-Akte Bielefeld" untersucht.
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
10.08.2002, 11:29 Uhr
virtual
Sexiest Bit alive
(Operator)

Was ist "die verschlüsselte X-Akte Bielefeld" ?
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
10.08.2002, 13:19 Uhr
Bruder Leif
dances with systems
(Operator)

Zitat:

virtual postete
Was ist "die verschlüsselte X-Akte Bielefeld" ?

*g* Ein Text, in dem beschrieben wird, daß es Bielefeld in Wirklichkeit gar nicht gibt. Daß Bielefeld eine Erfindung von DENEN ist. Daß DIE wollen, daß wir glauben, daß Bielefeld existiert. Und so weiter... nicht ernst nehmen ;-)

Und diesen Text hab ich Vigenere-verschlüsselt. Zum hier posten ein bißchen groß, hat über 8000 Zeichen. Aber mal sehen...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
10.08.2002, 16:14 Uhr
Christian
C/C++ Master
(Operator)

Hi!

Die Buchstabenkombination ABC in diesem Fall muss das Programm auch herausfinden können oder ist die vorgegeben?

Grüße
--
Grüße, Christian

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
10.08.2002, 16:35 Uhr
Bruder Leif
dances with systems
(Operator)

Zitat:

Christian postete
Die Buchstabenkombination ABC in diesem Fall muss das Programm auch herausfinden können oder ist die vorgegeben?

Die muß das Programm natürlich auch selbst finden! Alle Kombinationen, die mindestens 3 Buchstaben lang sind und sich mindestens einmal wiederholen, sollen aufgelistet werden.
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
10.08.2002, 20:12 Uhr
mike
Pinguinhüpfer
(Operator)

Hi!
Bezogen auf dein obiges Beispiel müsste es ja so gehen:
Einem String die Ersten 3 Zeichen zuweisen ("ABC"). Nach diesem String mit FindString in der Datei suchen lassen. Dann die nächsten 3 Zeichen einlesen ("BBH") und wieder nach ihnen in der Datei suchen. Das wird dann bis zur Hälfte der Datei fortgesetzt. Und dann beginnt eigentlich wieder alles von vorne. Nur das man alles mit den ersten 4 Zeichen macht ("ABCB");

mfg mike

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
11.08.2002, 01:37 Uhr
virtual
Sexiest Bit alive
(Operator)

@mike
also ich würde sagen, dass der zweite zu testende String "BCB" ist, also beginnend mit dem 2. Zeichen der Datei. Aber ist halt definitionsfrage
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
11.08.2002, 09:20 Uhr
Bruder Leif
dances with systems
(Operator)

Zitat:

virtual postete
@mike
also ich würde sagen, dass der zweite zu testende String "BCB" ist, also beginnend mit dem 2. Zeichen der Datei. Aber ist halt definitionsfrage

Genau, der zweite Teststring wäre BCB, aber zuerst sollte das Programm überprüfen, wie es mit ABCB aussieht. Für ABC wurden ja mehrere Wiederholungen gefunden, vielleicht gibt's für ABCB ja auch einige...

Der Sinn und Zweck des ganzen besteht darin, im verschlüsselten Text Wörter zu finden, die 1. im Klartext übereinstimmen und 2. mit den gleichen Buchstaben des Schlüsselworts verschlüsselt wurden. Wörter wie "die", "und", "der" usw. kommen recht häufig vor, deshalb werden die meisten Kombinationen 3buchstabig sein.

Kleiner Hinweis zur Vigenere-Verschlüsselung an sich:

Man wählt ein Schlüsselwort, z.B. KARO, und schreibt es unter den Klartext.

halloleutswiegehts
karokarokarokaroka
(in Courier-Schrift leichter verständlich)

Jetzt wird jeder Buchstabe des Klartextes nach dem Buchstaben codiert, der unter ihm steht, also "h" mit "k", "a" mit "a" usw. Eine Codierung mit "a" bedeutet, daß der Buchstabe erhalten bleibt, beim Codieren mit "b" wird der nächste im Alphabet genommen, bei "c" geht's zwei Stellen weiter usw. Also so ähnlich wie bei ROT13, nur daß jeder Buchstabe um eine andere Anzahl von Stellen verschoben wird.

Im Beispiel kommt also der Text

raczylvidsnwogvvds

raus. Wenn man jetzt einen genügend langen (!) Geheimtext hat, kann man nach Wiederholungen suchen. Wenn die immer einen gemeinsamen Faktor beinhalten, z.B. die Abstände 10, 15, 25, 35 (= immer Faktor 5 dabei), kann man davon ausgehen, daß das Schlüsselwort ebenso lang ist, wie dieser gemeinsame Faktor. Und genau das soll das Programm automatisch herausfinden ;-)
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Dieser Post wurde am 11.08.2002 um 09:21 Uhr von Leif editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
18.08.2002, 13:36 Uhr
~NemoEimi
Gast

Zitat:

Leif postete

Das Programm soll eine Textdatei einlesen, die ausschließlich aus Großbuchstaben besteht, z.B.

ABCBBHMZNGJTUZNABCKZBNJFNABCJZVZT.....

Diese Datei soll auf "Wörter" (häufig wiederholte Buchstabenkombinationen mit mehr als 2 Zeichen Länge) untersucht werden (hier z.B. ABC), und die Abstände dazwischen ausgegeben werden.

Ok, ich habe jetzt dazu einmal eine Lösung zusammengebastelt:

C++:

using namespace std;
#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <list>

map<string,int> hashtab;
list<int> abstaende;

void file_to_string(ifstream *datei, string *str) {
  string tmp, str2;
  while (!(*datei).eof()) {
    getline(*datei,str2);
    tmp += str2;
    }
  (*str).assign(tmp);
  }

void display(list<int> liste) {
  list<int>::iterator it;
  for (it = liste.begin(); it != liste.end(); it++)
    cout << *it << " ";
  }

int find_reps(string *str, int laenge) {
  string s; map<string,int>::iterator it;
  int l = (*str).length() - laenge; int z = 0;
  for (int i = 0; i < l; i++) {
    s.assign((*str).substr(i,laenge));
    it = hashtab.find(s);
    if (it!=hashtab.end()) {int k = it->second; abstaende.push_back(i-k); z = z + 1;}
    hashtab.insert(make_pair(s,i));
    }
  return(z);
  }

int main(int argc, char *argv[]) {
  string str;
  ifstream datei(argv[1]);
  file_to_string(&datei,&str);
  datei.close();
  int z = 1;
  for (int i = 3; z > 0; i++)
    z = find_reps(&str,i);
  display(abstaende);
  }

Da das bisher ohnehin die einzige Lösung im Angebot ist, habe ich auf Effizienz noch nicht geachtet, will sagen, das Programm ist garantiert noch erheblich beschleunigbar.

Grüße,
NemoEimi

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
10.01.2006, 15:02 Uhr
Eddy Brotherhood

Womit wandelt man das in ein programm um?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: