Şi "piticii" concurează

Groza Sorin

Pentru a veni în sprijinul celor care abia acum încep să pătrundă în tainele informaticii, vom prezenta câteva probleme împreună cu algoritmul de rezolvare şi programul sursă.

Am ales pentru început câteva din problemele propuse la ediţiile din 1996 şi 1997 ale concursului de informatică "INFO-STAR" organizat de Clubul Copiilor din Aiud. Problemele au fost compuse de domnul profesor Ovidiu Domşa de la Colegiul "Horea, Cloşca şi Crişan" din Alba Iulia, special pentru acest concurs. Organizatorii îi aduc mulţumiri şi pe această cale. Pentru fiecare problemă prezentăm un algoritm de rezolvare la nivelul copiilor cărora li se adresează.

Trepte

Un pitic vrea să urce o scară care are n trepte de înălţimi date, ordonate crescător. Înălţimile treptelor sunt date în cm şi sunt valori întregi. Acolo unde diferenţa între două trepte consecutive este de 1cm piticul urcă fără dificultăţi. Unde diferenţa este mai mare decât 1cm piticul trebuie să ia o pastilă care îi dă putere să sară pe treapta următoare. Cunoscând înălţimile treptelor, prima fiind obligatoriu 0, piticul vrea să afle care este numărul minim de pastile de care are nevoie pentru a urca scara şi de asemenea care este cea mai mare diferenţă dintre două trepte consecutive.

Date de intrare:

n=9

0,3,4,6,7,10,19,20,21

Date de ieşire:

numarul minim de pastile este 4

diferenta maxima este 9

Rezolvare

Pentru început se va calcula diferenţa de înălţime pentru fiecare două trepte consecutive. Când aceasta este mai mare decât 1 se va incrementa un contor care în final va reprezenta numărul de pastile necesare piticului. De asemenea, într-o variabilă se va păstra diferenţa; dacă diferenţa curentă este mai mare decât cea mai mare diferenţă găsită până atunci, evident, aceasta se actualizează. Practic, algoritmul determină maximul dintr-o mulţime de numere.

Robot

Membrii cercului de electronică de la Clubul Copiilor din Aiud au realizat un robot care ştie să se deplaseze la comandă. Astfel, comanda Nx deplasează robotul x metri spre nord, comanda Ey, Vz, St deplasează robotul y metri spre est, z metri spre vest, respectiv t metri spre sud (x, y, z, t sunt numere naturale). Un grup de copii "năzdrăvani" dau o serie de comenzi robotului pentru a-l rătăci. La comanda STAI robotul se opreşte. Ajutaţi membrii clubului de electronică ca prin maxim două comenzi să readucă robotul în punctul de plecare.

Date de intrare:

N3, V5, S3, E4, E5, N2, STAI

Date de ieşire:

Robotul revine prin comenzile:

V4

S2

Rezolvare

Pentru rezolvarea problemei vom folosi două variabile: x şi y care reprezintă poziţia robotului la un moment dat. Iniţial ele au valorile egale cu 0, acest lucru reprezentând faptul că robotul se află în originea unui sistem de coordonate. După citirea fiecărei comenzi, x şi y îşi măresc sau micşorează valoarea cu numărul de paşi, în funcţie de direcţia dată. În final (după citirea comenzii "STAI") x şi y vor reprezenta poziţia robotului. În funcţie de cadranul în care se află, se vor tipări direcţia de revenire şi numărul de paşi.

Cuvinte

Se consideră o listă de cuvinte, despărţite printr-un spaţiu, introduse de la tastatură. Cuvintele au în componenţă doar litere mici ale alfabetului latin.

Două cuvinte se oglindesc dacă literele unui cuvânt apar în celălalt cuvânt în ordine inversă ( car - rac se oglindesc).

Un cuvânt este simetric dacă citit de la stânga la dreapta şi de la dreapta la stânga obţinem acelaşi cuvânt (cojoc este simetric).

a) afişaţi perechile de cuvinte care se oglindesc;

b) afişaţi cuvintele simetrice din frază;

c) dacă fraza conţine numai cuvinte simetrice sau care se oglindesc să se formeze cea mai lungă frază simetrică (ca număr de cuvinte folosite), fiecare cuvânt fiind folosit o singură dată.

Date de intrare:

n=8

la mos era som al cojoc are caiac

Date de ieşire:

a)

are - era

mos - som

al - la

b)

cojoc

caiac

c)

la mos era cojoc are som al (o solutie !)

Fiecare cuvânt din text se inversează, apoi se caută un cuvânt identic cu inversul; când a fost găsit se tipăresc cele două cuvinte şi se depun fiecare în câte un şir. Aceste două şiruri, unul pentru cuvânt şi celălalt pentru invers, le vom folosi la punctul c) pentru formarea frazei.

Pentru determinarea cuvintelor simetrice inversăm fiecare cuvânt şi verificăm dacă este identic cu cuvântul însuşi. În caz afirmativ acesta va fi afişat şi depus într-un şir al cuvintelor simetrice, altfel va fi abandonat.

Pentru rezolvarea punctului c) verificăm dacă textul conţine doar cuvinte simetrice şi care se oglindesc. Acest lucru este adevărat doar dacă numărul cuvintelor depuse în cele trei şiruri este egal cu numărul total de cuvinte (s+2*k=n). În caz afirmativ vom adăuga cuvintele primului şir, urmat de un cuvânt din şirul celor simetrice, apoi cuvintele oglindă ale primului şir, dar de la sfârşit spre început pentru ca fraza să respecte condiţia de a fi simetrică.

Şeful

Un grup format din n copii, aşezaţi în linie la distanţe egale, participă la un joc. Fiecare trebuie să-şi aleagă pe rând o sumă de bani distinctă de cele alese de colegii săi. La un moment dat unul dintre copii devine şef, iar toţi cei din dreapta lui donează suma de bani celui aflat în stânga şefului la aceeaşi distanţă faţă de şef la care se află şi el.

Dacă un copil nu are corespondent, rămâne cu suma iniţială.

a) verificaţi dacă fiecare copil alege corect suma;

b) să se determine poziţia copilului care va deveni şef şi astfel va fi cel mai bogat posibil după donarea banilor de către cei din dreapta lui. Se va afişa poziţia şefului, şirul obţinut după donaţie, respectiv poziţia şi suma celui mai bogat copil.

Date de intrare:

n=7

45, 34, 23, 12, 57, 43, 24

Date de ieşire:

Sume corecte

Sef 3

dupa donatie 102, 46, 23, 0, 0, 43, 24

cel mai bogat 1 cu 102

Rezolvare

Problema este foarte interesantă şi face apel la procedeul numit "împăturarea unui şir". Primul punct este relativ simplu, el constând în a verifica dacă un element nou introdus nu se regăseşte printre elementele introduse până la el. Se vor păstra, apoi afişa poziţiile copiilor care nu verifică această proprietate.

Pentru aflarea şefului se procedează astfel: va fi considerat şef fiecare copil pe rând. Se va realiza împăturarea şirului, adică elementele din dreapta şefului se vor aduna la cele din stânga şefului (respectând simetria faţă de şef) după care devin nule. Se va determina cel mai bogat copil şi poziţia lui. Dacă se găseşte un copil mai bogat, după fiecare încercare se va reţine configuraţia. În final vom afişa rezultatele pentru situaţia optimă. Se observă că metoda nu este optimă, ea implementând algoritmul conform căruia se încearcă toate soluţiile şi se păstrează cea mai bună. Să nu uităm că problema se adresează "celor mici". Vă propunem să căutaţi soluţii mai performante.

Listing SEFUL.PAS

[cuprins]