Analiza si complexitatea algoritmilor - ACA

Extras din document

ALGORITMIC˘A. Seminar 1: Rezolvarea algoritmic˘a a problemelor. Identificarea algoritmilor si a propriet˘at¸ilor lor. Descrierea algoritmilor in pseudocod. Problema 1 (Inmult¸irea `a la russe.)(S 1) Se consider˘a urm˘atoarea metod˘a de ˆınmult¸ire (numit˘a ˆınmult¸irea ”`a la russe”) a dou˘a numere naturale nenule x ¸si y: ”Se scrie x al˘aturi de y (pe aceea¸si linie). Se ˆımparte x la 2 ¸si cˆatul imp˘art¸irii se scrie sub x (restul se ignor˘a deocamdat˘a). Se ˆınmult¸e¸ste y cu 2 iar produsul se scrie sub y. Procedeul continu˘a construindu-se astfel dou˘a coloane de numere. Calculele se opresc ˆın momentul ˆın care pe prima coloan˘a se obt¸ine valoarea 1. Se adun˘a toate valorile de pe coloana a doua care corespund unor valori impare aflate pe prima coloan˘a.” Exemplu. Fie x = 13 ¸si y = 25. Succesiunea de rezultate obt¸inute prin aplicarea operat¸iilor de mai sus este: x y rest factor multiplicare y 13 25 1 20 6 50 0 21 3 100 1 22 1 200 1 23 325