MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_NextPart_01C84615.8BF66F20" Questo documento è una pagina Web in file unico, nota anche come archivio Web. La visualizzazione di questo messaggio indica che il browser o l'editor in uso non supporta gli archivi Web. Scaricare un browser che supporti gli archivi Web, come Microsoft Internet Explorer. ------=_NextPart_01C84615.8BF66F20 Content-Location: file:///C:/2588CA37/Esercizi_170107.htm Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset="us-ascii"
Sono qui riportati 4 problemi – “Stringhe Strane”, “Codi= ce”, “La dieta di Poldo” e “Camelot” - svolti in Pascal<= o:p>
1) - Stri=
nghe
Strane (quoziente difficoltà 3)
Dato un insi=
eme di
stringhe di lunghezza 6 formate dai caratteri ‘A’, ‘BR=
17;,
‘C’, e ‘D’ bisogna distinguere le stringhe buone da
quelle cattive.
Una stringa =
è
buona se soddisfa i seguenti requisiti:
Il file di i=
nput
contiene:
1. un numero intero N che rappresenta il n=
umero
di stringhe
2. le successive N righe contengono ciascu=
na una
sequenza di lunghezza 6
Il file di o=
utputr
contiene una riga per ogni sequenza in input. Ogni riga è costituita=
da
un carattere:
‘C’ s=
e la
stringa è cattiva
‘B’ s=
e 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 f=
ile
è 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, fou=
t: text;
var n, i, le=
ngth,
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:=3D1 to N do
begin
cres:=3D1;
cons:=3D1;
length:=3D1;
read(fin,cur);
tipo:=3D'B';
while ((tipo=3D'=
B')and
(length < 6)) do
begin
=
prec:=3Dcur;
=
read(fin,cur);
=
length:=3D length+1;
=
if cur=3Dprec then begin cons:=3Dcons+1; cres:=3D1 end
=
&nb=
sp;
else begin
=
&nb=
sp;
cons:=3D1;
=
&nb=
sp;
if prec<cur then cres:=3D cres+1
=
=
&nb=
sp; else
cres:=3D1;
=
&nb=
sp;
end;
=
if ((cres=3D3) or (cons=3D3)) then tipo:=3D'C';
end;
writeln(fout,tip=
o);
writeln('tipo
stringa', i, tipo, 'cres', cres, 'cons', cons);
re=
adln(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:
<=
span
style=3D'mso-list:Ignore'>1.&n=
bsp; scriviamo tanti zeri quante sono le cif=
re
necessarie per esprimere $n$, seguiti da ‘1’
<=
span
style=3D'mso-list:Ignore'>2.&n=
bsp; scriviamo $n$ (con la consueta
rappresentazione decimale)
<=
span
style=3D'mso-list:Ignore'>3.&n=
bsp; scriviamo $x$
Esempio:
$x$ =3D 42011
$n$ =3D 5
Rappresenta=
zione
di $x$ =3D 01542011
Usando
questa rappresentazione si possono concatenare più numeri senza biso=
gno
di separatori
Esempio
La
stringa 001121122334455660110 rappresenta&=
nbsp;
112233445566 e 0=
.
Infatti
$x$=3D 112233445566
$n$=3D12
001-12-112233445566
Mentre
x=3D0, n=3D1 à 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 contener=
e in
decimale il primo intero rappresentato nell’input, la seconda riga il
secondo e così via.
Esempio
input: &=
nbsp; 001121122334455660110
Esempio
output: 1122334455=
66
program CODICE(input,o=
utput);
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 =3D '1' then convert:=3D1
=
else if a=3D'2' then convert:=3D2
=
else if a =3D'3' then convert:=3D3
=
else if a=3D'4' then convert:=3D4
=
else=
if a
=3D'5' then convert:=3D5
=
&nb=
sp;
else if a=3D'6' then convert:=3D6
=
&nb=
sp; =
else if a =3D'7' then convert:=3D7
=
&nb=
sp; =
else if a=3D'8' then convert:=3D8
=
&nb=
sp;
=
else
if a =3D'9' then convert:=3D9
=
&nb=
sp; =
&nb=
sp;
else if a=3D'0' then convert :=3D0
=
&nb=
sp; =
&nb=
sp;
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:=3D0;
while temp <> '1' do
begin
zeri:=3Dzeri+1;
read(fin,temp);
writeln('ho
contato', zeri, 'zero');
numcifra:=3D0;
while zeri > 0 do
=
begin
=
read(fin,temp);
=
j:=3Dconvert(temp);
=
writeln('j',j);
=
readln;
=
numcifra:=3Dnumcifra*10+j;
=
zeri:=3Dzeri-1;
=
end;
writeln('il
numero ha ', numcifra, 'cifrè);
for j:=3D1 to numcifra do begin
read(fin,temp);
write(fout,temp);
end;
writeln(fout);
read(fin,temp);
if temp <> '*=
' then
writeln('attendi un nuovo numero')
=
&nb=
sp;
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 list=
a di
panini che verranno serviti nell’ordine in cui appiaiono nel menu ste=
sso.
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:
<=
span
style=3D'mso-list:Ignore'>1.&n=
bsp; il panino è il primo che mangia =
in
indeterminato pasto
<=
span
style=3D'mso-list:Ignore'>2.&n=
bsp; il panino ha un peso mino dell’ul=
timo
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 pan=
ini
proposti nel menu. Le successive $m$ righe rappresentano ciascuna il peso d=
i 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 intege=
r;
var sol: array [1..100] of integer;<= o:p>
begin
clrscr;
writeln('numero
panini=3D');
readln(num);
for
i:=3D1 to num do
begin
write('peso ', i ,'-es=
imo
panino ');
readln(temp);
panino[i]:=3Dtemp;
sol[i]:=3D1;
end;
for i:=3D(num-1) downto 1 do
for j:=3D(i+1) to num =
do
begin
if panino[j]<panino[i] then
=
begin
=
temp:=3D 1 + sol[j];
=
if temp> sol[i] then
sol[i]:=3D temp;
=
end
end;
max:=3D1;
for i:=3D1 to num do
begin
writeln('sol', i , '
', sol[i]);
if
max<sol[i] then max :=3D 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&nb=
sp;
a fianco due dei suoi amici, altrimenti si rifiuta di sedersi al tav=
olo.
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 tav=
ola
rotonda. Nella
i-esima riga, vi sono $N$ interi. =
span>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 f=
ra 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 =3D 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:=3Dfalse;
table[s]:=3D1;
for j:=3D1 to n do
begin
writeln(j);
if ((G[s,j]=3D1) and
(table[j]=3D0)) then begin
=
&nb=
sp; =
procedo :=3D true;
writeln('prec',s,'succ',j);
=
&nb=
sp; =
write(fout,’
‘, j,’ ‘);
=
&nb=
sp; =
DFSnode(G,j);
=
&nb=
sp; =
end;
end;
writeln('chiusura sorgentè, s=
);
i:=3D1;
while table[i]=3D1 do i:=3Di+1;
if (i > N)and (not procedo) and
(G[s,sorgente]=3D1) 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:=3D 1 to N do
for j:=3D1 to N do
read(fin,g[i,j]);
readln(fin);
close(fin);
assign(fout,'output.txt');
rewrite(fout);
readln;
sorgente:=3D5;
write(fout, sorgente);
for i:=3D 1 to n do table[i]:=3D 0;
writeln('ok2');
readln;
DFSnode(g,sorgente);
readln;
close(fout);
end<=
span
lang=3DEN-GB style=3D'font-family:"Courier New";mso-ansi-language:EN-GB'>.<=
span
style=3D'mso-spacerun:yes'>