Sono qui riportati 4 problemi
– “Stringhe Strane”, “Codice”, “La dieta di Poldo” e “Camelot” - svolti in
Pascal
1) - Stringhe
Strane (quoziente difficoltà 3)
Dato un insieme di
stringhe di lunghezza 6 formate dai caratteri ‘A’, ‘B’, ‘C’, e ‘D’ bisogna
distinguere le stringhe buone da quelle cattive.
Una stringa è buona
se soddisfa i seguenti requisiti:
Il file di input
contiene:
1.
un
numero intero N che rappresenta il numero di stringhe
2.
le
successive N righe contengono ciascuna una sequenza di lunghezza 6
Il file di outputr
contiene una riga per ogni sequenza in input. Ogni riga è costituita da un
carattere:
‘C’ se la stringa è
cattiva
‘B’ se la stringa è
buona
Assunzioni: si usino
i file di text.
Attenzione: i file
sono generati, se non specificato diversamente, nella directory ove si trova
dev-pascal.
Il nome del file
nell’assign è completo dell’estensione .txt. Invece il file è generato del tipo
txt (ad esempio con l’applicazione blocco-note) e il nome è privo
dell’estensione .txt
Ricordarsi di
chiudere i file usati.
program
stringhestrane (input,output);
uses
crt;
var fin, fout:
text;
var n, i, length,
cres, cons: integer;
var prec,cur,tipo:
char;
begin
assign(fin,'inpu.txt');
reset(fin);
readln(fin,N);
writeln(N);
assign(fout,'output.txt');
rewrite(fout);
for i:=1
to N do
begin
cres:=1;
cons:=1;
length:=1;
read(fin,cur);
tipo:='B';
while ((tipo='B')and
(length < 6)) do
begin
prec:=cur;
read(fin,cur);
length:= length+1;
if cur=prec then begin cons:=cons+1; cres:=1 end
else begin
cons:=1;
if prec<cur then cres:= cres+1
else
cres:=1;
end;
if ((cres=3) or (cons=3)) then tipo:='C';
end;
writeln(fout,tipo);
writeln('tipo
stringa', i, tipo, 'cres', cres, 'cons', cons);
readln(fin);
end;
close(fin);
close(fout);
end.
|
Esempio Input 5 AABBCC AAABCB ACDDDD ABCDDD ABABAB |
Esempio Output B C C C B |
2) - Esercizio Codice (coefficiente
difficoltà 3)
È stata proposta una nuova codifica dei
numeri che non usa separatori. Se vogliamo scrivere un numero $x$, per prima
cosa si calcola il numero $n$ di cifre che occorrono per scrivere $x$. La
rappresentazione di $x$ si ottiene come segue:
1.
scriviamo tanti zeri quante sono le cifre
necessarie per esprimere $n$, seguiti da ‘1’
2.
scriviamo $n$ (con la consueta
rappresentazione decimale)
3.
scriviamo $x$
Esempio: $x$ = 42011
$n$ =
5
Rappresentazione
di $x$ =
01542011
Usando questa rappresentazione si possono
concatenare più numeri senza bisogno di separatori
Esempio
La stringa 001121122334455660110
rappresenta 112233445566 e 0.
Infatti
$x$= 112233445566
$n$=12
001-12-112233445566
Mentre x=0, n=1 à 0110
Il file di input contiene una sequenza di
cifre terminate da un asterisco *
Il file di output contiene un intero su ogni
riga. La prima riga deve contenere in decimale il primo intero rappresentato
nell’input, la seconda riga il secondo e così via.
Esempio input:
001121122334455660110
Esempio output:
112233445566
program
CODICE(input,output);
uses
crt;
var
zeri,numcifra,j:integer;
var
i:byte;
var
temp:char;
var fin,
fout:text;
function
convert(a:char):integer;
begin
if a =
'1' then convert:=1
else if a='2' then convert:=2
else if a ='3' then convert:=3
else if a='4' then convert:=4
else if a
='5' then convert:=5
else if a='6' then convert:=6
else if a ='7' then convert:=7
else if a='8' then convert:=8
else
if a ='9' then convert:=9
else if a='0' then convert :=0
else writeln('errorè)
end;
begin
clrscr;
assign(fin,'input.txt');
assign(fout,'output.txt');
rewrite(fout);
reset(fin);
read(fin,temp);
while
temp <> '*' do
begin
zeri:=0;
while
temp <> '1' do
begin
zeri:=zeri+1;
read(fin,temp);
end;
writeln('ho contato', zeri,
'zero');
numcifra:=0;
while
zeri > 0 do
begin
read(fin,temp);
j:=convert(temp);
writeln('j',j);
readln;
numcifra:=numcifra*10+j;
zeri:=zeri-1;
end;
writeln('il numero ha ', numcifra,
'cifrè);
for j:=1
to numcifra do begin
read(fin,temp);
write(fout,temp);
end;
writeln(fout);
read(fin,temp);
if temp <> '*' then
writeln('attendi un nuovo numero')
else writeln(temp);
readln;
end;
close(fin);
close(fout);
end.
3) - Esercizio ‘La dieta di Poldo’
(Coefficiente di difficoltà 3)
Poldo deve seguire una dieta. A Poldo viene
offerto un menu, composto da una lista di panini che verranno serviti
nell’ordine in cui appiaiono nel menu stesso. Ad ogni panino, Poldo può
accettare il panino o rifiutarlo. Il panino rifiutato non gli sarà più servito.
Poldo vuole mangiare il maggior numero di panini, ma per seguire la sua dieta,
Poldo può mangiare un panino se e solo se:
1.
il
panino è il primo che mangia in indeterminato pasto
2.
il
panino ha un peso mino dell’ultimo panino che Poldo ha
mangiato.
Scrivere un programma che aiuta Poldo a
trovare il numero massimo di panini che può mangiare in un menu senza violare la
regola della sua dieta.
File di input
Il file di input contiene il menu. La prima
riga contiene il numero $m$ di panini proposti nel menu. Le successive $m$ righe
rappresentano ciascuna il peso di un panino. Precisamente, la riga $i$-esima
contiene il peso dell’i-esimo panino servito nel menu.
File di output
Il file di output contiene il massimo numero
di panini che Poldo può mangiare rispettando la dieta
|
File di input 8 389 207 155 300 299 170 158 65 File di output 6 |
File di input 22 15 14 15 389 201 405 204 130 12 50 13 26 190 305 25 409 3011 43 909 987 1002 900 File di output 6 |
Si suggerisce di memorizzare il menu in un
vettore.
Assunzioni: un menu non contiene più di 100
panini.
La soluzione proposta legge il menu da
video.
(Suggerimento: trasformarla in modo da
leggere il menu da file)
program
panini (input,output);
uses
crt;
var
max,temp,num,i,j:integer;
var
panino: array [1..100] of integer;
var sol:
array [1..100] of integer;
begin
clrscr;
writeln('numero
panini=');
readln(num);
for i:=1 to num do
begin
write('peso ', i ,'-esimo
panino
');
readln(temp);
panino[i]:=temp;
sol[i]:=1;
end;
for
i:=(num-1) downto 1 do
for j:=(i+1) to num
do
begin
if panino[j]<panino[i] then
begin
temp:= 1 + sol[j];
if temp> sol[i] then
sol[i]:= temp;
end
end;
max:=1;
for i:=1
to num do
begin
writeln('sol', i , '
', sol[i]);
if
max<sol[i] then max := sol[i];
end;
writeln('max', max);
readln;
end.
4) - Esercizio Camelot (quoziente di
difficoltà 3)
A Camelot, nel periodo di maggior splendore,
ogni cavaliere è amico di oltre la metà dei suoi compagni d’arme, ossia se $N$ è
il numero dei cavalieri ciascuno di essi può contare su
almeno
N/2 validi amici.
Ogni cavaliere pretende di essere seduto
con a fianco due dei suoi amici,
altrimenti si rifiuta di sedersi al tavolo. Scrivi un programma per disporre i
cavalieri intorno al tavolo in modo che ogni cavaliere abbia amici ai suoi
lati.
File di input:
Il file di input contiene nella prima riga N
il numero dei cavalieri della tavola rotonda. Nella
i-esima
riga, vi sono $N$ interi. Il
$j$-iesimo intero è 1 se i cavalieri
i e j sono amici, 0 altrimenti.
Vi sono pertante $N$ righe, una per ogni
cavaliere. (In altre parole, il file rappresenta la matrice dell’adiacenze del
grafo dell’amicizia fra i cavalieri). Si assume che il cavaliere i non è amico
con se stesso in quanto i non può avere i al suo fianco.
File di output
Il file di output contiene una sola riga
contenente una sequenza di $N$ interi separati da uno spazio per rappresentare
la disposizioni dei cavalieri alla tavola rotonda,
|
Esempio file
input 5 0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 |
Esempio file
output 5 1 2 4 3 trovato
ciclo |
Abbiamo implementato una visita dfs a partire
da una sorgente qualsiasi.
Infatti se il ciclo hamiltoniano esiste (e
siamo sicuri perchè ogni vertice ha almeno N/2 archi),
tutti i nodi sono raggiungibili a partire da
ciascun vertice.
program
Camelot (input,output);
uses
crt;
type
grafo = array[1..4000,1..4000] of integer;
var
fin,fout:text;
var
table:array[1..4000] of integer;
g: grafo;
n,i,j:
integer;
sorgente:
integer;
procedure DFSnode(var G: grafo;s :
integer);
var procedo: boolean;
var i,j: integer;
begin
readln;
writeln('dfs con sorgentè,
s);
readln;
procedo:=false;
table[s]:=1;
for j:=1
to n do
begin
writeln(j);
if ((G[s,j]=1) and
(table[j]=0)) then begin
procedo := true;
writeln('prec',s,'succ',j);
write(fout,’
‘, j,’ ‘);
DFSnode(G,j);
end;
end;
writeln('chiusura sorgentè, s);
i:=1;
while
table[i]=1 do i:=i+1;
if (i
> N)and (not procedo) and (G[s,sorgente]=1) then begin
writeln('prec',s,'succ',sorgente,'trovato
ciclo'); writeln(fout, 'trovato ciclo')
end else
writeln('errorè)
end;
begin
assign(fin,'input.txt');
reset(fin);
readln(fin,N);
for i:=
1 to N do
for j:=1
to N do
read(fin,g[i,j]);
readln(fin);
close(fin);
assign(fout,'output.txt');
rewrite(fout);
readln;
sorgente:=5;
write(fout, sorgente);
for i:=
1 to n do table[i]:=
0;
writeln('ok2');
readln;
DFSnode(g,sorgente);
readln;
close(fout);
end.