Algoritmi elementari

Inainte de a rezolva probleme mai avansate sau chiar si cele de mijloc, trebuie sa stim bine acesti algoritmi elementari, foarte necesari in programare.

Acesti algoritmi elementari, de regula, sunt predati in clasa a 9-a. Teoretic. Voi prezenta azi doar algoritmii necesari pentru cei care abia pornesc la drum cu programarea. Astfel, vom incepe cu algoritmul de interschimbare.


Algoritmul de interschimbare

Unul, poate singurul, dintre cei mai usori algoritmi predati in liceu. Imi place aici sa folosesc metoda paharelor. Consider ca e mult mai logic sa intelegi acest algoritm cu metoda paharelor, decat sa-l inveti pe derost.

Interschimbarea presupune schimbarea valorilor intre 2 variabile. De exemplu, daca a=5 si b=3, dupa executarea algoritmului, a=3 si b=5. Daca stapanesti cat de cat C++, iti vei da cu usurinta seama ca pentru a face aceasta interschimbare, nu sunt de ajuns doar cele 2 variabile, ci ne va mai trebui inca una cu care ne vom ajuta.

Sa ne imaginam astfel:

  • Variabila a: Paharul cu vin rosu
  • Variabila b: Paharul cu vin alb

Este evident faptul ca, pentru a putea schimba vinul dintre cele doua pahare, mai avem nevoie de un pahar gol (auxiliar) de care ne putem folosi pentru schimbarea continutului celor 2 pahare (a si b).

Astfel, mai aducem un pahar aux, gol, iar continutul paharului a (vinul rosu), il turnam in acest pahar gol, aux. Acum paharul a va fi gol, iar paharul aux va contine vin rosu. Acum, paharul b (vin alb) il turnam in paharul a (care este acum gol), iar din paharul aux, turnan tot continutul in paharul b. Astfel, vom obtine vin rosu in paharul b si vin alb in paharul a.

Interschimbarea a doua valori in C++

Astfel, vom obtine urmatorul cod:


Algoritmul de minim si maxim

Pentru acest algoritm, ne vom folosi tot de variabile simple, insa lucrurile se mai schimba, deoarece vom citi pe rand n elemente, dupa care le vom compara pe fiecare, dupa fiecare citire, cu minimul sau maximul sirului.

Exemplu: Pentru n = 8, avem urmatoarele elemente: 2, 1, 4, 4, 5, 9, 0, 7. Astfel, dupa executarea algoritmului, vom obtine ca minim: 0 si ca maxim: 9.

Observatie: Primul numar citit va fi considerat si minimul si maximul, pentru a le putea compara ulterior cu celelalte elemente, pe rand.

Am citit pe rand numerele, iar dupa fiecare citire, am verificat daca numarul citit este mai mic decat minimul anterior sau mai mare decat maximul anterior.


Algoritmul de prelucrare a cifrelor unui numar

Tot ce trebuie sa stii la acest algoritm este faptul ca, pornirea se face de la dreapta catre stanga. Cu ajutorul acestui algoritm poti afla daca un numar este palindrom/cate cifre are numarul sau sa calculezi suma/produsul/etc. cu cifrele unui numar.

Prelucrarea unui numar in C++

In imaginea de mai sus am cuprins 2 informatii.

  1. Prelucrarea se face de la dreapta la stanga (de la „coada” numarului)
  2. Cum se extrage fiecare cifra dintr-un numar.

De exemplu, daca dorim sa facem suma cifrelor unui numar, vom avea urmatoarea secventa de cod:

Astfel, pentru n = 1234, vom obtine s = 4 + 3 + 2 + 1 = 10.


Algoritmul de formare al unui numar.

Se citesc mai multe cifre, pana cand ultima cifra citita este 0. Sa se afiseze numarul format din cifrele citite.

Exemplu: x = 7, 4, 3, 1, 0, s-ar obtine: 7431

Vom obtine urmatorul cod:

Observatii:

  • Primul numar citit: 7, iar nr = 0. Aplicam formula: nr*10+x si vom obtine 0*10+7 = 0+7 = 7.
  • Al doilea numar citit: 4, iar nr = 7. Aplicam formula si vom obtine 7*10+4 = 70+4 = 74.
  • etc.

Inversul unui numar

7431 -> 1347.

Ne vom folosi de algoritmul anterior. Vom extrage pe rand ultimele cifre, le memoram intr-o alta variabila (inv), dupa care cifra memorata o eliminam din numarul initial.

Daca luam exemplul 7431 si aplicam secventa de cod, vom obtine:

  • Cand inv = 0 => inv = 0*10 + 1 = 1 si eliminam 1: nr = nr/10.
  • Cand inv = 1 => inv = 1*10 + 3 = 13, nr=nr/10.
  • Cand inv = 13 => inv = 13*10 + 4 = 134, nr=nr/10.
  • etc.

Algoritmul pentru divizori

Daca n = 4, divizorii lui 4 sunt: 1, 2.

Ca sa verificam daca un numar este prim, aplicam acest algoritm si verificam daca are divizori (in afara de 1 si el insusi).

Am plecat de la 2, deoarece 1 este divizor al oricarui numar intreg si am mers pana la jumatatea numarului n pentru ca divizorii unui numar (fara 1 si el insusi) sunt cuprinsi intre [2, n/2].


Acestia au fost algoritmii fara de care nu putem crea un program eficient. Acesti algoritmi elementari sunt predati in clasa a 9-a, iar daca nu-i stapanesti bine, nu vei putea trece la lucruri mai avansate.

Vlad

Fac doar lucruri care-mi plac, care-mi aduc motivatie si fericire, nu material.

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *