Criptografiamo?
Descrizione del Problema
La decriptazione è il processo con cui si cerca di interrompere qualcun'al-
tro che sta scrivendo in codice (criptografando). Tale processo comporta a
volte alcuni tipi di analisi statistiche del passaggio di un testo (criptato). Il
tuo obiettivo consiste nello scrivere un programma che realizzi una semplice
analisi di un testo dato in input.
Dati di input
La prima riga del file input.txt contiene soltanto un intero positivo n.
Questo è il numero delle righe successive. Le successive n righe conteran-
no zero o più caratteri (possibilmente anche lo spazio). Questo è il testo che
deve essere analizzato. Nota che le lettere accentate compaiono come singole
lettere seguite dal simbolo '.
Dati in output
Ogni riga del file output.txt contiene una sola lettera maiuscola, seguita da
uno spazio e da un intero positivo. Tale intero indica quante volte la cor-
rispondente lettera appare nel testo in input. Le lettere maiuscole e minuscole
sono considerate uguali. Non deve essere contato alcun altro carattere. L'out-
put deve essere ordinato in ordine decrescente rispetto al conteggio, ovvero
la lettera piµu frequente deve comparire nella prima riga e l'ultima riga deve
contenere la lettera meno frequente. Se due lettere hanno la stessa frequenza
allora la lettera che viene per prima nell'alfabeto deve comparire per prima
nell'output. Se una lettera non appare nel testo non deve apparire neppure
nell'input.
Esempio di input
Questo e' un testo.
Contiamo 1 2 3 4 5
Wow!!!! E' una domanda facile?
Esempio di output
O 6
A 5
E 5
N 4
T 4
U 3
C 2
D 2
I 2
M 2
S 2
W 2
F 1
L 1
Q 1
Soluzione proposta da: TheKaneB
program project1;
uses SysUtils;
type cella = record
c: char;
f: integer;
end;
t_alfabeto = array[1..26] of cella;
var fin, fout: textfile;
alfabeto: t_alfabeto;
i,n: integer;
c: char;
procedure merge(var x:t_alfabeto; sx, c, dx: integer);
var t: t_alfabeto;
i,j,k: integer;
begin
i:=sx;
j:=c + 1;
k:=1;
while (i<=c) and (j<=dx) do begin
if x[i].f >= x[j].f then begin
t[k]:=x[i];
inc(i);
end
else begin
t[k]:=x[j];
inc(j);
end;
inc(k);
end;
while i<=c do begin
t[k] := x[i];
inc(i);
inc(k);
end;
while j<=dx do begin
t[k] := x[j];
inc(j);
inc(k);
end;
for k:=1 to ((dx - sx) + 1) do begin
x[k+sx-1] := t[k];
end;
end;
procedure mergesort(var x: t_alfabeto; sx, dx: integer);
var c: integer;
begin
if (dx > sx) then begin
c := (sx + dx) div 2;
mergesort(x, sx, c);
mergesort(x, c+1, dx);
merge(x, sx, c, dx);
end;
end;
begin
{apertura files}
if fileexists('input.txt') then begin
assignfile(fin,'input.txt');
reset(fin);
assignfile(fout, 'output.txt');
rewrite(fout);
{inizializzazione}
for i:=1 to 26 do begin
alfabeto[i].c := chr(i + 64);
alfabeto[i].f := 0;
end;
{Lettura del file e popolazione dell'array di frequenze}
readln(fin,n);
for i:=1 to n do begin
while not EOLn(fin) do begin
read(fin, c);
c:=upcase(c);
case c of
'A'..'Z': alfabeto[ord(c) - 64].f := alfabeto[ord(c) - 64].f + 1;
end;
end;
readln(fin);
end;
{ordinamento: ordino gli elementi secondo le frequenze delle lettere.
Siccome MergeSort è un algoritmo stabile, gli elementi con la stessa
frequenza rimarranno nell'ordine originale, cioè in ordine alfabetico.}
mergesort(alfabeto, 1, 26);
{presentazione dell'output, salta gli ultimi elementi che hanno frequenza 0}
i:=1;
while (alfabeto[i].f > 0) and (i<=26) do begin
writeln(fout, alfabeto[i].c, ' ',alfabeto[i].f);
i := i + 1;
end;
close(fin);
close(fout);
end;
end.
--
Torna all'indice
Non ci sono commenti in questa pagina. [Scrivi commento]