Tipul STRING. Tipul SET

Abordare in limbajul Pascal

Notiuni teoretice

A.     Tipul STRING (sir de caractere)

Un sir de caractere este o succesiune de caractere cuprinsa intre doua apostrofuri si poate sa contina orice caractere: litere mari si mici, caractere speciale ('#', '&', etc.) si delimitatori (virgula, punct, etc.).

Limbajul Pascal foloseste standardul ASCII, conform caruia fiecare caracter se caracterizeaza printr-un asa-numit cod ASCII, un intreg cuprins intre 0 si 255. Astfel, caracterele-litera mare 'A', 'B', . , Z' au codurile de la 65 la 90, in aceasta ordine, caracterele-litera mica 'a', 'b', . , 'z' au codurile de la 97 la 122, iar caracterele-cifra '0', '1', . , '9' au codurile intre 48 si 57. Cand compara doua caractere, calculatorul compara de fapt codurile lor ASCII.

Intre codurile ASCII ale celor doua litere-pereche exista relatia:

codul caracterului-litera mare + 32 = codul caracterului-litera mica

Proceduri si functii predefinite pentru siruri

1) Functia COPY copy(<sir>,<poz>,<nr>)

returneaza un subsir al sirului de caractere <sir>, care incepe din pozitia <poz> si are <nr> caractere.

2) Functia POS pos(<sir1>,<sir2>)

returneaza pozitia de inceput a lui <sir1> in cadrul sirului <sir2>, in cazul in care <sir2> este subsir al lui <sir1>. In caz contrar functia returneaza valoarea 0.

3) Procedura DELETE delete(<sir>,<poz>,<nr>)

sterge din sirul <sir>, un subsir de lungime <nr> caractere, subsir care incepe de la pozitia <poz>. Sirul rezultat dupa stergere este memorat tot in parametrul <sir>.

4) Procedura INSERT insert(<subsir>,<sir>,<poz>)

- insereaza subsirul <subsir> in cadrul sirului de caractere <sir>, incepand cu pozitia <poz>. Parametrul <sir> este o variabila care dupa executia procedurii va contine sirul rezultat prin inserare.

5) Procedura STR str(<nr>,<sir>)

- transforma numarul <nr> in sirul de caractere corespunzator, pe care il memoreaza in parametrul <sir>. La apel, parametrul <sir> va fi un identificator de variabila de tip string.

6) Procedura VAL val(<sir>,<nr>,<eroare>)

incearca sa converteasca sirul de caractere <sir> in numarul corespunzator. Tentativa va reusi daca sirul contine numai caractere permise pentru un numar, adica cifre, punctul zecimal si caracterul "-". La apel, parametrii <nr> si <eroare> vor fi identificatori de variabile, valorile acestora completandu-se in urma executiei procedurii, astfel: daca transformarea reuseste, atunci in parametrul <nr> se memoreaza numarul rezultat prin transformare, iar parametrul <eroare> va primi valoarea 0; daca transformarea esueaza, atunci parametrul <nr> va fi nedefinit, iar in parametrul <eroare> se memoreaza pozitia in sir a primului caracter din cauza caruia a esuat transformarea.

B) Tipul SET (multime)

Limbajul Pascal permite definirea multimilor in sensul cunoscut din matematica, cu ajutorul tipurilor de date anonime "set of". Elementele unei astfel de multimi, in numar de maxim 256, sunt valori distincte de acelasi tip, numit tip de baza.

Pentru a memora efectiv o multime trebuie sa declaram o variabila.

Sintaxa declararii unei variabile de tip multime este:

var <id>:set of <tip_elem>;

unde: - <id> = identificatorul (numele) variabilei de tipul multime

- <tip_elem> = tipul de baza al elementelor multimii.

Tipul de baza al elementelor trebuie sa fie un tip ordinal care poate cuprinde maxim 256 de valori.

Operatori aplicabili tipului multime

a)      operatori aritmetici

reuniune

intersectie

diferenta

b)      operatori relationali (cu ajutorul lor se pot forma expresii logice)

"IN" apartenenta: <element> IN A testeaza daca o valoare <element> apartine multimii A

"<=", ">=" incluziune

"<>" diferit

egalitate

Citirea unei multimi

Variabilele de tip multime nu pot fi citite in mod direct. Pentru a citi o multime M procedam astfel:

Initializam M cu multimea vida: . Apoi, intr-un ciclu, citim pe rand, in aceeasi variabila, de exemplu x, valorile care vor fi elemete ale multimii. Pentru fiecare valoare citita a lui x, adaugam prin reuniune multimea formata cu elementul x, la multimea M: . Prin reuniune, fecare nou x va fi adaugat la multimea M numai daca valoarea lui x nu exista deja in multime.

Afisarea unei multimi

Variabilele de tip multime nu pot fi afisate direct. Pentru a afisa o multime, vom parcurge intr-un ciclu toate valorile care fac parte din tipul elementelor multimii, adica toate valorile care teoretic ar putea fi elemente ele multimii. Pentru fiecare din aceste valori, testam daca valoarea respectiva apartine efectiv multimii, iar in caz afirmativ o afisam.

Iata cateva exemple de multimi pe care le putem utiliza in problemele de la tipul string si nu numai (ex.: sa verificam daca un caracter din sir este vocala / consoana / litera mare / litera mica / caracter-cifra). Vom declara aceste multimi ca niste constante, la sectiunea de declarare a constantelor din cadrul unui program Pascal, precedate de cuvantul-cheie "const", astfel:

const vocale=['A','E','I','O','U','a','e','i','o','u'];

litere_mari=['A'..'Z'];

litere_mici=['a'..'z'];

consoane=litere_mari + litere_mici - vocale;

cifre=['0'..'9'];

separatatori=[' ',',','.',';','?','!'];

Probleme propuse

Se citeste de la tastatura un cuvant de lungime cel mult 20 de caractere, format numai din litere mari. Sa se afiseze toate cuvintele distincte ce se pot forma prin eliminarea cate unui singur caracter din cuvantul dat.

Exemplu: pentru cuvantul BINE se vor afisa, nu neaparat in aceasta ordine, cuvintele:

INE BNE BIE BIN

Sa se scrie un program care inverseaza intr-un text toate cuvintele care incep cu litera 'a' sau 'A' prin oglindire. Cuvintele din text se considera separate prin spatii (unul sau mai multe).

Exemplu: Textul "Acesta este un exemplu aproape perfect asa ca am insistat sa-l vezi acum si tu." se va transforma in "atsecA este un exemplu epaorpa perfect asa ca ma insistat sa-l vezi muca si tu.".

Se dau n propozitii formate din caractere ale alfabetului englez (mari si mici). Ultimele caractere ale fiecarei propozitii sunt cifre care formeaza un numar intreg. Se cere sa se afiseze aceste propozitii in ordinea crescatoare a numerelor cu care se termina. La afisare, numerele respective vor fi eliminate.

Exemplu: pentru n=3 si propozitiile 'Elicopterul zboara jos 12', 'Alina citeste o carte 90', 'Bunica este batrana si bolnava 5' se va afisa

'Bunica este batrana si bolnava'

'Elicopterul zboara jos'

'Alina citeste o carte'

Se introduc de la tastatura doua numere naturale memorate in doua variabele de tip string.(numarul de cifre <=250). Se cere sa se afiseze suma si diferenta dintre cel mai mare si cel mai mic numar.

Exemplu:

Se citeste de la tastatura o propozitie terminata prin punct. Propozitia este alcatuita din cuvinte formate numai din litere mari. Cuvintele sunt separate prin unul sau mai multi separatori: spatiu, virgula, doua puncte.

Stiind ca propozitia are cel mult 30 de cuvinte, sa se afiseze grupurile de cuvinte din care fiecare membru reprezinta o anagrama a altui membru din grup (un cuvant are maximum 16 litere). Un grup va contine numarul maxim de membri; membrii dintr-un grup sunt distincti. Nu se considera gruparile cu un singur membru.

Fiind dat un careu rebusistic, sa se determine toate cuvintele care apar in careu si sa se verifice daca un cuvant apare de mai multe ori. Patratelele negre din careu sunt date utilizand caracterul "*". Se considera ca un cuvant are cel putin 2 caractere.

Exemplu: pentru n=12 si careul

cuvintele sunt: PRETUTINDENI, OMENIE, ORAS, UNITI, PASNIC, OS, CHEL, IVI, CAR, GS, AP, TROTINETA, BIET, BA, EURI, CLER, PLATAN, PUI, ASIA, UTA, REGIM, STRAT, CIFRE, SARITI, PRONOSTICURI, EMIS, RELIEF, OTET, COTE, GR, UNICAT, RAIE, STI, HRIB, SM, IEPE, NAPI, CN, ALGE, LASA, DOS, STEA, TR, IERNI, AUTURI, NAIVA, RATAT, DISCIPLINATI, iar cuvantul 'OS' este singurul care se repeta.

Scrieti programul de criptare a unui mesaj in care criptarea se bazeaza pe urmatoarele reguli:

mesajul sufera mai intai o transformare prin substitutie, fiecare al doilea caracter fiind inlocuit cu caracterul al carui numar de ordine in alfabet se obtine ca suma modulo 26 plus o unitate intre numarul sau de ordine si numarul de ordine al caracterului precedent din mesaj (caracterele A-Z sunt numerotate de la 1 la 26);

mesajul este impartit in grupuri de cate m = n caractere, n fiind numarl de ordine al primului caracter din mesaj (vzi observatia!), facandu-se eventual completarea mesajului pana la un numar de caractere multiplu de m, prin adaugarea repetata a caracterului ce urmeaza in alfabet ultimului caracter din mesaj;

fiecare grup de m caractere este transformat prin transpozitie, astfel: caracterele grupului sunt dispuse in ordine pe liniile unei matrice de n * n elemente, iar matricea este apoi parcursa incepand din linia 1 si coloana 1 in spirala, in sensul contrar acelor de ceasornic, obtinand mesajul cifrat.

Observatie: Primul caracter al mesajului nu are semnificatie pentru receptorul sau, el fiind ales convenabil pentru o cifrare corespunzatoare.

Se citesc de la tastatura informatii sub forma a n perechi de elevi (i, j) (date prin cate doua litere mici), avand semnificatia ca elevul i este in clasa cu elevul j. Se cere sa se precizeze care sunt toate clasele si ce elevi sunt in fiecare clasa.

Exemplu: pentru n=10 si perechile ('a','b'), ('a','d'), ('c','e'), ('f','u'), ('p','e'), ('a','p') ('i','t'), ('k','l'), ('t','u'), ('s','l') se obtin 3 clase cu urmatoarele componente: ('a','b','c','d','e','p'), ('f','i','t','u'), ('k','l','s').

Se considera o multime A. O relatie oarecare R intre elementele acestei multimi se numeste relatie de echivalenta, daca:

este reflexiva: avem x R x;

este simetrica: din x R y rezulta y R x;

este tranzitiva: din x R y si y R x rezulta x R z.

Partitia generata de relatiile de echivalenta definite pe multimea A, este un set de multimi A₁, A₂, . , A_p cu proprietatea:

A₁ È A₂ È ÈA_p = A;

pentru fiecare multime A_i, intre oricare elemente ale sale exista relatie de echivalenta;

oricare ar fi doua dintre aceste multimi A_i si A_j, nu exista nici o relatie de echivalenta intre un element din A_i si un element din A_j.

Se definesc n relatii de echivalenta de forma x R y pe multimea A = , unde m I [0,255]. Fiecare relatie se va introduce sub forma unei perechi (x,y). Sa se determine partitia generata de relatiile de echivalenta pe multimea data.

Exemplu: pentru perechile (1,2), (4,5), (2,3), (6,7), (7,1) se obtine partitia A₁, A₂ a multimii , unde A₁=, A₂=.

Se stie ca pentru caracterizarea structurii si a proprietatilor atomilor, un rol deosebit de important il are configuratia electronica a atomului respectiv. Reamintim ca exista mai multe straturi electronice (in prezent se cunosc 7 astfel de straturi), pe care sunt asezati electronii. Fiecare strat electronic este format din mai multe substraturi electronice. Exista 4 tipuri de substraturi electronice si anume s - cu 2 orbitali, p - cu 3 orbitali, d - cu 5 orbitali si f - cu 7 orbitali. Pe fiecare orbital se pot afla cel mult 2 electroni.

In scrierea configuratiei electronice se precizeaza, in ordine, substraturile ocupate de electroni, precum si numarul de electroni pe care il contine fiecare substrat. Numarul stratului din care face parte substratul respectiv precede literei ce reprezinta tipul substratului, iar numarul de electroni din substratul respectiv succede aceasta litera (2p6 => stratul este 2, numarul de electroni este 6).

1s

2s 2p

3s 3p 3d

4s 4p 4d 4f

5s 5p 5d 5f

6s 6p 6d

7s 7p

Conform principiului energetic, electronii ocupa orbitalii atomici in ordinea cresterii energiei, incepand cu orbitalul de cea mai joasa energie. Deci ordinea de completare a orbitalilor cu electroni este data de urmatoarea schema:1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p.

Se cere:

a)          Dandu-se numarul atomic al unui atom (este egal cu numarul de electroni ai atomului respectiv) sa se afiseze configuratia sa electronica.

Exemplu: Z=20 se obtine configuratia "1s2 2s2 2p6 3s2 3p6 4s2" (substraturile se vor desparti intre ele printr-un spatiu).

b)          Dandu-se configuratia electronica a unui atom sa se deduca numarul sau atomic precum si numarul de electroni de pe ultimul strat (care este egal cu valenta elementului respectiv).

Exemplu: elementul cu configuratia "1s2 2s2 2p6 3s2 3p3" are numarul atomic Z=15, iar valenta este 5.

Algoritmii Marcov sunt sisteme formale pentru manipularea sirurilor. Aceste scheme sunt des utilizate in proiectarea limbajelor de programare si a altor aplicatii cu un grad inalt de dificultate.

Strategia generala intr-un algoritm Marcov este de a lua sirul de intrare x si dintr-un numar de pasi, se transforma x intr-un sir de iesire y. Atat x cat si y sunt siruri continand caractere dintr-un alfabet (multime de caractere) V.

Pasii (productiile) sunt de forma u w, unde u si w sunt siruri de caractere din V. O astfel de productie este aplicabila unui sir z de caractere din V daca exista cel putin o aparitie a lui u in z, altfel productia este neaplicabila sirului z. Daca productia este aplicabila atunci prima aparitie a lui u in z este inlocuita cu w.

Exemplu: productia 'ba' 'c' aplicata sirului 'ababab' produce sirul 'acbab'. Productia 'baa' 'c' nu este aplicabila sirului 'ababab'.

Productiile se considera ordonate (prima este prioritara celorlaltor).

Un algoritm Marcov se termina atunci cand nu mai exista productii aplicabile.

Datele de intrare se citesc de la tastatura (sirul de intrare, numarul de productii, productiile). Sa se scrie un program care transforma sirul de intrare folosind procedeul descris mai sus. Se vor afisa toate fazele de transformare a sirului de intrare in sirul de iesire.

Exemplu: daca productiile sunt: 'ab' 'ef', 'ef' 'ad', 'ad' 'd', 'cd' 'ef', 'dg' 'd' atunci sirul initial 'abcdefg' se transforma succesiv astfel: 'abcdefg' 'efcdefg' 'adcdefg' 'adcdadg' 'dcdadg' 'dcddg' 'defdg' 'daddg' 'dddg' 'ddd'.

Pentru codificarea unui text format din litere mici se folosesc doua tablori bidimensionale 5*5, generate prin program.

a b c d e 1 2 3 4 5

f g h i j 6 7 8 9 10

k l m n p 11 12 13 14 15

o r s t u 16 17 18 19 20

v w x y z 21 22 23 24 25

Codificarea se realizeaza caracter dupa caracter astfel:

caracterul din linia i si coloana j se codifica prin elementul corespunzator din tabloul de numere intregi;

dupa efectuarea acestei codificari, linia i din tabloul de numere se permuta circular spre dreapta cu i pozitii, apoi coloana j din acelasi tabel se permuta circular in sus cu j pozitii.

Sa se scrie un program care, pentru orice text dat continand doar caractere mici ale alfabetului englez, sa afiseze succesiunea de numere obtinuta prin codificare. Textul poate sa contina si spatii care se vor ignora. Intre doua coduri succesive se va lasa exact un spatiu.

Exemplu: codificarea sirului 'exemplu' este 5 23 4 2 12 11 20.

O firma de hardware isi codifica produsele astfel: un cod este format dintr-o secventa de cifre urmata de o secventa de caractere (litere mici ale alfabetului englez). In momentul aparitiei unui nou produs, firma este interesata de codul urmatorului produs si de codul produsului anterior. Codurile produselor sunt generate astfel: se genereaza secventa urmatoare in ordine lexicografica formata din aceleasi caractere ale codului produsului anterior (fara a modifica secventa numerica a codului anterior), iar daca nu exista o secventa urmatoare se incrementeaza cu 1 secventa numerica si se genereaza primul cod in ordine lexicografica, format din aceleasi caractere.

Se cere ca pentru un anumit cod dat, sa se genereze codul anterior si codul urmator al unui produs. Daca unul din aceste coduri nu exista se va afisa '*' in locul sau.

Exemplu: pentru codul '000abc' se va afisa '*' si '000acb', pentru '2457z' se va afisa '2456z' si '2458z', pentru '153xabc' se va afisa '153cxba' si '153xacb'.

Se propune codificarea numerica a unui text de lungime n (n<=80) caractere, cu ajutorul a doua matrice de codificare de aceleasi dimensiuni p si k<=6, citite ca date initiale. Prima matrice contine caractere alfanumerice distincte, iar cea de-a doua contine numere intregi de cate doua cifre (>=10).

Codificarea se executa caracter cu caracter, dupa urmatoarea regula: fiecare caracter din text regasit in matricea de caractere se inlocuieste cu vecinul cu valoarea minima al elementului omolog (din aceeasi pozitie) din matricea de numere. In functie de pozitia sa, un element numeric poate avea 3, 5 sau 8 vecini.

Observatie: daca in text se detecteaza un caracter care nu apartine matricei alfanumerice, se semnaleaza EROARE si se intrerupe codificarea.

14) (Agenda) Vasile si-a cumparat o agenda noua si si-a notat in ea n numere de telefon ale cunostintelor sale intr-o ordine dorita de el. Chiar daca are agenda, Vasile ar vrea sa "invete" toate numerele de telefon notate. Deoarece el a observat ca cel mai usor se pot pastra in minte acele numere de telefon care au un numar minim de cifre distincte, isi propune sa le invete mai intai pe acestea. Apoi ar urma numerele de telefon din cele ramase care acum au numar minim de cifre distincte si asa mai departe.

Scrieti un program care stabileste care sunt numerele de telefon din cele existente in agenda lui Vasile, pe care le va "invata" in prima zi, apoi care sunt cele pe care le va retine in a doua zi, etc.

Date de intrare

Din fisierul de intrare AGENDA.IN se citesc numerele de telefon de pe linii distincte.

Date de iesire

In fisierul de iesire AGENDA.OUT se vor scie pe aceeasi linie, separate prin spatiu, numerele de telefon avand acelasi numar de cifre distincte, linia incheindu-se cu numarul de ordine al zilei in care se memoreaza acele numere.

Restrictii si precizari

un numar de telefon are cel mult 9 cifre

1<=n<=100

Exemplu

15) (Sistem AEL) Administratorul sistemului AEL cere elevilor primele 8 cifre din CNP pentru a le introduce ca parola pentru elevi. Administratorul isi da seama ca sunt foarte lungi parolele si elimina din parole cifrele de la stamga pana la cifra cea mai mare din parola. Prin eliminare, unele parole au devenit identice si le considera invalide. Parolele invalide le inlocuieste cu parola cea mai mare din sirul parolelor valide + pozitia parolei invalide in sirul parolelor invalide. Sa se afiseze noile parole. Numarul de elevi si primele 8 cifre din CNP-ul fiecarui elev se citesc din fisierul ELEV.TXT.

(Olimpiada locala de Informatica - Ploiesti, 2004)