Algorithmus

[Curby]

Kann jemand diese Frage beantworten?
Ich versteh zwar die Frage, weiß aber nicht, wie man sowas proggt.

Erstellen Sie einen Algorithmus, der in einem übergebenen Text die Häufigkeit eines übergebenen Zeichens bestimmt und zurückliefert. Schreiben Sie den Algorithmus als Pascal-Unterprogramm (Funktion und Prozedur)!
Notieren Sie zu beiden Unterprogrammen jeweils einen Aufruf in einem anderen Programmteil und die dazu notwendigen Variablendeklarationen.

[neolithos]

Zitat:

Notieren Sie zu beiden Unterprogrammen jeweils einen Aufruf in einem anderen Programmteil und die dazu notwendigen Variablendeklarationen.

Wieso beiden ich sehe bloß eines!

[Phoenix]

Hrm. Ich würde da auch nur eine einzelne Funktion draus machen:

Delphi-Quellcode:

function GetCharCount(source: string; token: char): integer;
var
   i: integer;
begin
   result := 0;
   for i := 0 to length(source) - 1 do
      if source[i] = token then
         inc(result);
end;

[negaH]

Delphi-Quellcode:

type
  TCharEntropie = array[Char] of Integer;

function CharEntropie(const Value: String): TCharEntropie;
var
  I: Integer;
begin
  FillChar(Result, SizeOf(Result));
  for I := 1 to Length(Value) do
    Inc(Result[Value[I]]);
end;

begin
  WriteLn( 'Häufigkeit von A ist ', CharEntropie('hAllAlilo')['A'] );
end;

Gruß Hagen

[Chewie]

Zitat:

Zitat von neolithos

Zitat:

Notieren Sie zu beiden Unterprogrammen jeweils einen Aufruf in einem anderen Programmteil und die dazu notwendigen Variablendeklarationen.

Wieso beiden ich sehe bloß eines!

Auch wenns recht sinnlos ist, ich nehme an, das ist gemeint:

Zitat:

Schreiben Sie den Algorithmus als Pascal-Unterprogramm (Funktion und Prozedur)!

[neolithos]

Wer lesen kann ist klar im Vorteil:

Delphi-Quellcode:

function CountChar(const asValue : String; acCh : Char) : Integer;
var I : Integer;
begin
  Result := 0;
  for I := 1 to Length(asValue) do
      if asValue[I] = acCh then
         Inc(Result);
end;

und

Delphi-Quellcode:

procedure CountChar(const asValue : String; acCh : Char; var iCount : Integer);
var I : Integer;
begin
  iCount := 0;
  for I := 1 to Length(asValue) do
      if asValue[I] = acCh then
         Inc(iCount);
end;

[Curby]

Ist "acCh" eine Variable oder ein fester Begriff?

"acCh : Char" --> "acCh := Char"
Fehlt da nicht das Gleichheitszeichen?

[RomanK]

Hoi,
acCh ist ein Zeichen(Char) und dieses wird deiner Funktion/Procedure übergeben.

[himitsu]

:arrow: Erstellen Sie einen Algorithmus, der in einem übergebenen Text die Häufigkeit eines übergebenen Zeichens bestimmt und zurückliefert. Schreiben Sie den Algorithmus als Pascal-Unterprogramm (Funktion und Prozedur)!

Delphi-Quellcode:

Function CountChar(asValue: String; acCh: Char): Integer;
  Var I: Integer;

  Begin
    { Zeichen zählen }
    Result := 0;
    For I := 1 to Length(asValue) do
      If asValue[I] = acCh Then Inc(Result);
  End;

Procedure CountChar(asValue: String; acCh: Char; Var iCount: Integer);
  Var I: Integer;

  Begin
    { Zeichen zählen }
    iCount := 0;
    For I := 1 to Length(asValue) do
      If asValue[I] = acCh Then Inc(iCount);
  End;

:arrow: Notieren Sie zu beiden Unterprogrammen jeweils einen Aufruf in einem anderen Programmteil und die dazu notwendigen Variablendeklarationen.

Delphi-Quellcode:

Procedure Test:
  Var asValue: String;  { Variablendeklarationen }
    acCh: Char; 
    iCount: Integer;

  Begin
    asValue := 'Test Test Test...'; { zu testender String  }
    acCh := 't';                    { zu zählendes Zeichen }

    { Aufruf der Funktion }
    iCount := CountChar(asValue, acCh);

    { Aufruf der Prozedur }
    CountChar(asValue, acCh, iCount);

    { iCount = Anzahl der Zeichen }
  End;

***
Da aber nicht gesag wird, das auf Groß-/Kleinschreibung geachtet werden soll. Ist hier noch eine andere Lösung.
(Wenn z.B. nach "a" gesucht wird, werden alle "a" und "A" gezählt)

Delphi-Quellcode:

Function CountChar(asValue: String; acCh: Char): Integer;
  Var I: Integer;

  Begin
    { in Kleinschreibung umwandeln }
    acCh := LowerCase(acCh);
    asValue := LowerCase(asValue);
    { Zeichen zählen }
    Result := 0;
    For I := 1 to Length(asValue) do
      If asValue[I] = acCh Then Inc(Result);
  End;

Procedure CountChar(asValue: String; acCh: Char; Var iCount: Integer);
  Var I: Integer;

  Begin
    { in Kleinschreibung umwandeln }
    acCh := LowerCase(acCh);
    asValue := LowerCase(asValue);
    { Zeichen zählen }
    iCount := 0;
    For I := 1 to Length(asValue) do
      If asValue[I] = acCh Then Inc(iCount);
  End;

Procedure Test:
  Var asValue: String;  { Variablendeklarationen }
    acCh: Char; 
    iCount: Integer;

  Begin
    asValue := 'Test Test Test...'; { zu testender String }
    acCh := 't';                    { zu suchendes Zeichen }

    { Aufruf der Funktion }
    iCount := CountChar(asValue, acCh);

    { Aufruf der Prozedur }
    CountChar(asValue, acCh, iCount);

    { iCount = Anzahl der Zeichen }
  End;

:idea: Das "VAR" in der Variablendeklarationen der Prozedur bestimmt das der nachfolgende Parameter geändert und übergeben werden kann. Das ist dazu, um den Wert (hier ist es Anzahl der gefunden Zeichen) aus der Prozedur heraus zu bekommen.
Wenn das "VAR" fehlt kannst du den Wert ändern wie du willst, bekommst ihn aber nie zurückgeliefert.

[Jens Schumann]

Hallo,
ich habe hier noch einen Vorschlag

Delphi-Quellcode:

TSignArray = Array [0..255] of Double; // Entspricht dem Ordinalwert der ASCII-Zeichen

procedure TForm1.DoIt(aText: TStrings; var aArray: TSignArray);
var
  iCnt : Integer;
begin
  // Array löschen
  For iCnt:=Low(aArray) to High(aArray) do
    aArray[iCnt]:=0.0;
  // Berechne über den Ordinalwert des ASCII-Zeichens den Index im Array
  // und erhöhe den Wert an dieser Stelle um 1
  For iCnt:=1 to Length(aText.Text) do
    aArray[Ord(aText.Text[iCnt])]:=aArray[Ord(aText.Text[iCnt])]+1.0;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  MyArray : TSignArray;
  iCnt    : Integer;
  Gesamt  : Double;
begin
  DoIt(Memo1.Lines,MyArray);
  Gesamt:=0.0;
  // Berechne die Anzahl der Zeichen im Text
  Gesamt:=Length(Memo1.Lines.Text);
  // Die Anzahl eines einzelnen Zeichen geteilt durch die Gesamtanzahl
  // ergibt die Häufigkeit
  For iCnt:=Low(MyArray) to High(MyArray) do
    MyArray[iCnt]:=MyArray[iCnt]/Gesamt;
  // TChart befüllen
  Series1.Clear;
  For iCnt:=Low(MyArray) to High(MyArray) do
    Series1.Add(MyArray[iCnt],IntToStr(iCnt),clRed);

  Gesamt:=0.0;
  // Test, ob die Summe der Häufigkeiten 1 ergibt
  For iCnt:=Low(MyArray) to High(MyArray) do
    Gesamt:=Gesamt+MyArray[iCnt];
  ShowMessage(FloatToStr(Gesamt));

  // Rechne die Häufigkeiten in Prozent um
  For iCnt:=Low(MyArray) to High(MyArray) do
    MyArray[iCnt]:=MyArray[iCnt]*100;
  Gesamt:=0.0;
  // Test, ob die Summe der Häufigkeiten 100% ergibt
  For iCnt:=Low(MyArray) to High(MyArray) do
    Gesamt:=Gesamt+MyArray[iCnt];
  ShowMessage(FloatToStr(Gesamt));
end;

Der Algorithmus verwendet ein Array um die Anzahl der einzelnen zu ermitteln.
Dabei entspricht der Index im Array dem Ordinalwert des ASCII-Zeichens.
Jetzt kann für jedes Zeichen im Text der Ordinalwert berechnet werden. Dieser Ordinalwert wird als
Index für das Array verwendet, um den Wert an der Position um 1 zu erhöhen. Anschließend wird jedes Element im Array durch die Gesamtanzahl der Zeichen geteilt. Damit steht im Array die Häufigkeit des jeweiligen Zeichens. Über MyArray[Ord('a')] erhält man dann die Häufigkeit des Zeichens a.
Wüsste evt. jemand wie es noch schneller gehen könnte alle Häufigkeiten in einem Text zu berechnen?

[himitsu]

@Curby
jetzt lass dich bloss nich verwirren.
Diese beiden Einträge (von "Jens Schumann" + diesen) sind zu Ermittlung der Häufigkeit aller Zeichen im Text.
Kannst es also als zusätzliche Lektüre betrachten.


@Jens Schumann - schneller:
keine reellen Variablen (Double) verwenden. Die Interger-Typen sind schneller.
Da viele Systeme auf 32-Bit ausgelegt und optimiert sind, läuft's mit dem Interger (32 Bit/4 Byte) an schnellsten.

Mit Integer läufter es bei mit etwa 3-mal schneller. (< 10 Sekunden)
Hab dein Prog entsprechend erweitert. Ausser der neuen Zeitmessung wurden nur deine Deklaration mit ins Butten1-Ereigniss verschoben (ändert aber nichts an der Geschwindigkeit)

Deine Test nach der Berechnung kannste auch weg lassen, ergeben immer 1/100. (wurden daher nicht mit in die Zeitmessung einbezogen)

> die Berechnungen laufen jeweils 10-mal durch, um Messungenauigkeiten... zu elliminieren.

[Jens Schumann]

Hallo himitsu,
Häufigkeiten haben die Eigenschaft kleiner zu sein als 1.
Wie soll ich solch eine Wert in einem Integer speichern.
Ich könnte die Häufigkeiten *100 o. *1000 nehmen und dann als Integer speichern und
bei der Ausgabe wieder durch 100 o. 1000 teilen. Dann gehen mir aber Kommastellen verloren.

Die Tests habe ich mit Absicht eingefügt. Ersetze mal Double durch Single !!!

[Dannyboy]

Zitat:

Zitat von Phoenix

Hrm. Ich würde da auch nur eine einzelne Funktion draus machen:

Delphi-Quellcode:

function GetCharCount(source: string; token: char): integer;
var
   i: integer;
begin
   result := 0;
   for i := 0 to length(source) - 1 do           
     if source[i] = token then
       inc(result);
end;

Be careful, Phoenix!!!!!
Bei Strings gilt immer Index (1 bis n) und NICHT Index (0 bis n-1) !!!
Ich erlaube mir mal, das zu korriegieren:

Delphi-Quellcode:

function GetCharCount(source: string; token: char): integer;
var
   i: integer;
begin
   result := 0;
   for i := 1 to length(source)  do   // von 1 bis n
      if source[i] = token then
         inc(result);
end;

[negaH]

@Jens Schumann, schau dir mein Posting mal genauer an :)

Hagen

[himitsu]

@Jens
Das man die Interger noch scallieren muß, ist mir schon klar. War hier aber nicht nötig (Ist der Geschwindigkeitsoptimierung zum Opfer gefallen).

Delphi-Quellcode:

Series1.Add(MyArray[iCnt] / Gesamt, IntToStr(iCnt), clRed);

Zitat:

Die Tests habe ich mit Absicht eingefügt. Ersetze mal Double durch Single !!!

Brauch ich nicht. Selbst mit Double bekommt man einige Probleme, wenn die Dateien gösser werden.

Der Faktor fürs Scallieren kann ja frei gewählt werden. Bei 1000 liegt der Fehler unter 1 Promille.
Mit 1000 ist 'ne 2 MB Datei noch locker zu bearbeiten.
Mit Int64 (wird ja bald Standard, ist aber auch so schon schneller als reelle Typen) ist 'ne 2 GB Datei mit einer Genauikeit von 0,000001 möglich.

[negaH]

@himitsu: die Notwendigkeit den Text mit AnsiUpperCase()/AnsiLowerCase() umzuwandeln besteht nicht. Statt dessen wird zB. mit meinem obigen Code einfach die Anzahl aller Zeichen ermittelt. Bei der Auswertung dieser Entropie werden nun einfach die Anzahlen von "a" und "A" addiert.
Eine vorherige Umwandlung mit AnsiUpper/LowerCase() ist inefizient.

Eine 2Gb Datei ist auch ohne Int64 möglich, es reicht Integer.

Gruß Hagen

[himitsu]

2 MB = 2097152
2097152 * 1000 = 2097152000 (Skalierung mit 1000)

2097152000 (skalierte Anzahl der Zeichen in der Datei)
2147483647 (größter Integer)
2147483648000 (skalierte Anzahl der Zeichen einer 2 GB Datei)

[negaH]

2 MB = 2.097.152

somit können in dieser Datei maximal nur 2.097.152 Zeichen im gesamten vorkommen.
Da ein Integer bis 2.147.483.647 geht also 2 Giga Byte, können mit ihm 2Gb Dateien bestehend aus einem einzigsten Zeichen zB. "A" eingelesen werden ohne Überlauf.
Nimmt man statt Integer einen Cardinal dann wären es sogar 4 Gb große Dateien.
Würde jedes der 256 möglichen Zeichen gleichverteilt vorkommen so könnte man sogar 1 Terra Byte große Dateien einlesen.

Deine Rechnungen sind inkorrekt, und ich verstehe nicht warum du mit 1000 skalieren willst ??

Wenn eine Datei 2 Mb groß ist und ein Zeichen 1 Byte, dann enthält die Datei 2.097.152 Bytes. Wenn diese Datei nur aus dem Zeichen 'A' besteht, also 2.097.152 mal 'A', dann wird man beim zählen der 'A's exakt auf 2.097.152 kommen. Wenn ein Integer bis 2.147.483.647 ohne Überlauf funktioniert dann heist dies das man diese "A" Datei 1024 mal nacheinander zählen könnte bis zum Überlauf. Selbst mit Skalierung von 1000 würde also kein Überlauf auftreten.
Will man wenig mehr dann nimmt man Cardinals und verdoppelt so nochmals die Auflösung. Dies wären dann 4 Giga Byte große Dateien.

Sorry, aber wenn ich was behaupte dann habe ich das nach 15 Jahren Programmeirerfahrung mindestens hundert mal durchgerechnet.


Gruß Hagen

[himitsu]

War mir schon klar, aber Jens wollte halt mit Kommastellen rechnern.

Hast aber recht, habs mir nochmal durch den Kopf gehen lassen.
Wenn der Integer mit der Dateigrösse scalliert wird, gehen keine Kommastellen verloren und es passt eine 2 GB - 1 B Datei in den Integer rein.

:oops: Immer diese fehlgeleiteten Gedankengänge.

[negaH]

No Problem :), das was mich ein leichtes bischen gestört hat, sorry für meine harschen Worte, ist das man manchmal erst schwatzt und dann nachdenkt ;)

Gruß Hagen