Problema cere doar completarea recurenței date cu un caz de bază: diferența dintre domeniul de valori pentru care relația e dată și pentru care se cere completată e k = 0. Valoarea pentru cazul de bază o obținem din definiția în cuvinte a termenului: există un singur mod în care putem alege 0 elemente din n. Cu aceasta, funcția și programul devin:
#include <stdio.h>
unsigned A(unsigned n, unsigned k)
{
return k == 0 ? 1 : n * A(n-1, k-1);
}
int main(void)
{
printf("%u\n", A(5, 3));
return 0;
}
Problema 1b Definim cos x = 2 * cos2 x/2 - 1 iar pentru x < 0.01 (în radiani) aproximăm cos x cu 1 - x2/2. Scrieți o funcție care calculează cosinusul după relațiile de mai sus. Folosiți-o pentru a calcula cos π/3.
Folosim un alt nume pentru funcția cosinus, pentru a evita confuzia cu funcția standard de bibliotecă cos. Recursivitatea se transcrie direct din relația dată în enunț. S-ar putea scrie:
double cos2(double x)
{
return x < 0.01 ? 1 - x*x/2 : 2*cos2(x/2)*cos2(x/2) - 1;
}
Această variantă calculează de două ori cos2(x/2), ceea ce prin repetiție recursivă devine deosebit de ineficient. Folosim o variabilă pentru a reține această valoare. în plus, rescriem funcția cu cazul de bază pentru x < 0.01 în modul, ea funcționând astfel și pentru orice număr real:
#include <math.h>
#include <stdio.h>
double cos2(double x)
{
if (fabs(x) < 0.01) return 1 - x*x/2;
else {
double c = cos2(x/2);
return 2*c*c - 1;
}
}
int main(void)
{
printf("%f\n", cos2(3.1415926/3));
return 0;
}
Problema 2 Scrieți o funcție care calculează prin aproximări succesive expresia 1(x + 1/(x + 1(... + 1/x))) până când diferenta a două aproximări succesive e cel mult 10-6. Calculați și tipăriți o aproximație a expresiei pentru x = 4.
În problemă se dă un termen infinit (cu un număr infinit de apariții ale lui x), inspirat din problema cu fracții continue din laboratorul 3. Termenul are în mod clar o structură recursivă: el e de forma 1/(x + ...) unde în loc de ... apare termenul însuși. Mai riguros putem scrie: t1=1/x, tn=1/(x+tn-1), pentru n > 1, sau chiar pentru n > 0 dacă considerăm t0 = 0.
Deci, pentru a rezolva problema vom calcula succesiv termenul următor pornind de la termenul curent, ca aproximații pentru termenul infinit. Dacă diferența dintre cei doi nu depășește precizia cerută, procesul se oprește și returnăm aproximația curentă, altfel continuăm cu calculul încă unui termen. Dacă scriem soluția recursiv, avem nevoie de termenul (aproximația) curent(ă) ca parametru. Valoarea x nu se modifică, ea ar putea fi un parametru sau chiar o constantă în program.
double limrec(double x, double ultim) // ultimul termen calculat
{
double urm = 1 / (x + ultim); // termenul (aproximarea) următoare
return fabs(urm-ultim) <= 1e-6 ? urm : limrec(x, urm);
}
Funcția va fi apelată inițial cu t0 = 0 ca valoare pentru aproximația curentă ultim: limrec(4, 0).
double limit(double x)
{
double ultim, urm = 0;
do {
ultim = urm;
urm = 1/(x + ultim);
} while (fabs(urm-ultim) > 1e-6);
return urm;
}
Analizând matematic problema putem găsi ușor soluția exactă, înlocuind în recurență și termenul curent și cel următor cu limita: lim = 1/(x + lim), o ecuație de gradul II în lim.
Pentru x > 0 ne interesează soluția pozitivă (-x + sqrt(x2+4))/2. Putem remarca de asemenea că termenii șirului alternează în jurul limitei. Aceste observații nu sunt necesare pentru a rezolva problema prin program; putem să le folosim însă pentru o mai bună înțelegere și pentru a ne verifica.
Problema 3a Citiți un text până la sfârșitul intrării și afișați numai caracterele alfanumerice și de spațiu alb.
Problema e de tipul celor mai simple prelucrări de texte: caracterele se citesc independent și se prelucrează independent: ce facem cu un caracter depinde doar de tipul său, nu și de unde se află el în șirul de intrare, de caracterele dinaintea lui sau de după el.
Începem cu un ciclu simplu care citește toate caracterele până la sfârșit de fișier fără să facă nimic cu ele.
int c; while ((c = getchar()) != EOF);Acest tipar cu atribuire și test în condiție este util când înainte de fiecare iterație din ciclu (inclusiv prima) trebuie să citim un nou caracter pentru a putea să-l testăm.
Continuăm să construim soluția înlocuind corpul vid al ciclului cu o instrucțiune care tipărește caracterul citit, folosind funcția putchar:
int c;
while ((c = getchar()) != EOF)
putchar(c);
Avem astfel un ciclu care tipărește toate caracterele citite, până la sfârșitul intrării. Dorim însă tipărirea doar a anumitor caractere, deci plasăm tipărirea într-o instrucțiune if cu condiția dorită:
#include <stdio.h>
int main(void)
{
int c;
while ((c = getchar()) != EOF)
if (isalnum(c) || isspace(c)) putchar(c);
return 0;
}
Dacă preferăm să nu citim și testăm cu aceeași condiție
complexă, rescriem, în acest caz ciclul are două instrucțiuni,
a doua citește următorul caracter:
int c = getchar(); // primul caracter
while (c != EOF) {
if (isalnum(c) || isspace(c)) putchar(c);
c = getchar(); // urmatorul caracter
}
Problema 3b
Citiți un text până la sfârșitul intrării și afișați-l transformând literele mari în litere mici și reciproc.
Ca și în problema anterioară, fiecare caracter e prelucrat independent de celelalte. Pornim cu același tipar:
while ((c = getchar()) != EOF)
// aici vine prelucrarea caracterului
Ne folosim de funcțiile islower/isupper pentru test și de funcțiile tolower/toupper pentru transformare. Ne avantajează faptul că acestea din urmă nu modifică caracterele care nu sunt litere, respectiv sunt deja litere mici/mari. De aceea în prelucrare e suficient un singur test:
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int c;
while ((c = getchar()) != EOF)
if (islower(c)) putchar(toupper(c));
else putchar(tolower(c));
return 0;
}
ATENȚIE! tolower și toupper sunt funcții, deci nu își pot modifica argumentele, care sunt transmise prin valoare. Instrucțiunea toupper(c); nu are deci nici un efect! Funcția returnează valoarea transformată, dar ea nu e folosită niciunde (prin atribuire, în alt calcul, sau prin tipărire), și se pierde. Deci secvența incorectă
if (islower(c)) toupper(c); // INCORECT! nu are efect! else tolower(c); // INCORECT! nu are efect! putchar(c); // tipareste c nemodificat!va tipări caracterul c nemodificat!
Problema 3c Afișați un text citit până la sfârșitul intrării schimbând literele în succesori (A -> B, e ->f, etc.) iar Z -> A, z -> a.
și în această problemă, fiecare caracter e prelucrat independent de celelalte. Soluția va avea deci din nou structura:
while ((c = getchar()) != EOF)
putchar(transforma(c));
și rămâne să scriem funcția transformă, care va trebui definită (sau măcar declarată) înainte de codul de mai sus (care va apare în main).
Știm că un caracter e reprezentat prin valoarea codului său ASCII iar succesorul său are codul cu 1 mai mare (indiferent că e literă mare, mică sau altceva). Caracterul fiind un întreg, se folosește pur și simplu adunarea: + 1, iar literele Z și z sunt tratate ca și cazuri speciale:
int transforma(int c)
{
return c == 'Z' ? 'A' : c == 'z' ? 'a' : c + 1;
}
Problema 3d
Afișați un text citit până la sfârșitul intrării schimbând fiecare cifră în cea simetrică față de 4.5: 3 în 6, 7 în 2, etc.
Problema are structura identică cu cea anterioară. Nu trebuie să transformăm decât cifrele. Am putea să tratăm fiecare caz individual:
return c == '0' ? '9' : c == '1' ? '8' : c == 2 ? ... si asa mai departe ...dar soluția e foarte lungă, ineficientă, inestetică, și susceptibilă la erori de neatenție. Cum caracterul c și rezultatul transformării (să-l notăm cu r) sunt simetrice față de mijlocul intervalului ['0', '9'], putem scrie: c + r == '0' + '9'. Funcția de transformare e atunci:
int transforma(int c)
{
return isdigit(c) ? '0' + '9' - c : c;
}
Fiind atât de simplă, putem scrie și direct:
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int c;
while ((c = getchar()) != EOF)
putchar(isdigit(c) ? '0' + '9' - c : c);
return 0;
}
Problema 4a
Dintr-un text citit până la sfârșitul intrării, afișați toate secvențele de cifre, fiecare secvență pe câte o linie.
Dacă două secvențe de cifre sunt separate printr-un punct, afișați-le ca atare pe o singură linie.
Rezolvăm întâi problema mai simplă fără ultima cerință.
Trebuie să identificăm secvențe de cifre consecutive și să tipărim un caracter de linie nouă după fiecare.
Vom privi deci intrarea ca o alternanță de secvențe de cifre și secvențe de caractere care nu sunt cifre; oricare din cele două variante se poate afla la început și la sfârșit. Următoarea secvență consumă caractere atât timp cât nu sunt cifre:
while (!isdigit(c = getchar()) && c != EOF);La sfârșitul acestei secvențe, c e fie o cifră, fie EOF. În acest ultim caz, prelucrarea trebuie încheiată. Altfel trebuie tipărit caracterul curent (care e cifră) și citite și tipărite caractere în continuare, cât timp sunt cifre, iar apoi se trece la rândul următor. Dacă nu s-a ajuns la sfârșitul intrării, se reia alternanța de la secvența de mai sus, care consumă caractere cât timp nu sunt cifre. Secvența completă este:
do {
while (!isdigit(c = getchar()) && c != EOF); // cat timp nu e cifra
if (c == EOF) break; // iese din ciclul do ... exterior
do // aici sigur e cifra
putchar(c); // o tiparim
while (isdigit(c = getchar())); // citim, si continuam daca e cifra
putchar('\n'); // gata cifrele
} while (c != EOF); // daca nu, revenim la caractere ne-cifra
O variantă chiar mai simplă putem scrie dacă nu privim caracterele care nu sunt cifre ca formănd o secvență, ci le tratăm individual. Codul e structurat atunci după tiparul
while ((c = getchar()) != EOF)
if (isdigit(c))
// tratează secvența de cifre care începe aici
else
// tratează caracterul care nu e cifră
Cum în acest caz, caracterele care nu sunt cifre se ignoră, codul devine:
while ((c = getchar()) != EOF)
if (isdigit(c)) {
do
putchar(c);
while (isdigit(c = getchar()));
putchar('\n');
}
Completăm acum codul cu ultima cerință: de a afișa pe același
rând secvențele de forma cifre.cifre . Pentru aceasta, la sfârșitul secvenței de cifre (în loculul lui putchar('\n');) testăm dacă caracterul e punct, și dacă da, mai citim și afisăm o secvență de cifre:
if (c == '.') {
putchar(c);
while (isdigit(c = getchar())) putchar(c);
}
putchar('\n');
Am considerat că punctul se afișează și dacă ulterior secvența de cifre e vidă (altfel e necesar un test suplimentar). Dacă dorim să afișăm împreună mai multe secvențe de cifre separate prin punct: cifre.cifre.cifre, schimbăm ultimul if în while.
Problema 4b Citiți un text până la sfârșitul intrării și afișați-l înlocuind orice secvență de spații albe cu un singur spațiu. Excepție: când secvența conține cel puțin două caractere de linie nouă, e înlocuită cu două caractere de linie nouă.
Ca și în problema anterioară, intrarea e vazută ca o alternanță: spații albe și secvențe care nu conțin spații albe. Secvențele "interesante" sunt cele cu spații albe; începem prelucrând eventualele caractere care nu sunt spații albe:
while (!isspace(c = getchar()) && c != EOF)
putchar(c);
Dacă după acest ciclu c nu este EOF, cu el începe sigur o secvență de spații albe. Cât timp avem spații albe le consumăm fără a tipări, dar numărăm eventualele caractere de linie nouă dintre ele:
unsigned cnt = 0;
do
if (c == '\n') ++cnt;
while (isspace(c = getchar()));
În final, decidem ce tipărim (spațiu sau două linii noi); trebuie
tipărit și următorul caracter (deja citit), dacă nu e EOF.
Programul complet, în versiune ușor modificată:
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int c;
while (1) { // ciclu infinit, iesim cu break
while (!isspace(c = getchar())) {
if (c == EOF) return 0; // gata, iese din main/program
putchar(c);
} // aici sigur c e spatiu
unsigned cnt = 0;
do
if (c == '\n') ++cnt;
while (isspace(c = getchar()));
if (cnt < 2) putchar(' ');
else printf("\n\n");
if (c == EOF) break; else putchar(c); // caracter ne-spatiu deja citit
}
return 0;
}
Și aici putem da o soluție alternativă fără ciclul pentru caractere care nu sunt spații, după tiparul:
while ((c = getchar()) != EOF) {
if (isspace(c))
// tratează secvența de spații care începe aici
// pana se ajunge la un caracter diferit de spatiu
// tratează caracterul care nu e spațiu (provenind din if sau else)
Programul complet:
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int c;
while ((c = getchar()) != EOF) {
if (isspace(c)) {
unsigned cnt = 0;
do
if (c == '\n') ++cnt;
while (isspace(c = getchar()));
if (cnt < 2) putchar(' ');
else printf("\n\n");
if (c == EOF) break;
}
putchar(c); // caracter ne-spatiu, daca n-a intrat in if sau ultimul din if
}
return 0;
}
Problema 4c
Citiți un text până la sfârșitul intrării și afișați-l modificat astfel: după orice secvență de spații albe care conține cel puțin două caractere de linie nouă, următorul cuvânt începe cu literă mare; celelalte cuvinte se scriu integral cu litere mici.
Și aici, textul de intrare este o alternanță de spații albe și cuvinte (orice nu conține spațiu alb). Urmând strict enunțul, un eventual cuvânt inițial nu trebuie modificat:
while (!isspace(c = getchar()) && c != EOF)
putchar(c);
După această secvență inițială, parcurgem un ciclu: dacă nu s-a ajuns la sfârșitul intrării, caracterul e de tip spațiu alb, și acestea trebuie analizate, ca și în problema anterioară (dar afișate neschimbat). Apoi, trebuie transformat cuvântul ce urmează.
#include <ctype.h>
#include <stdio.h>
int main(void)
{
int c;
while (!isspace(c = getchar()) && c != EOF) // cuvantul initial
putchar(c);
while (c != EOF) {
unsigned cnt = 0; // caracterul sigur e spatiu
do {
if (c == '\n') ++cnt;
putchar(c);
} while (isspace(c = getchar()));
if (c == EOF) break; // daca nu, urmeaza un cuvant
if (cnt < 2)
do
putchar(tolower(c)); // toate literele devin mici
while (!isspace(c = getchar()) && c != EOF);
else {
putchar(toupper(c)); // litera initiala mare
while (!isspace(c = getchar()) && c != EOF)
putchar(c); // celelalte tiparite normal
}
}
return 0;
}