Clasa a IX-a lecția 5

From Algopedia
Jump to navigationJump to search

Note de curs: prof. Isabela Coman

Lectie

Structura repetitiva while do

Structura repetitivă de tip WHILE-DO (cîtă timp - execută) reprezinta structura de control cu ajutorul careia executam un set de instructiuni, de mai multe ori, in functie de o conditie. Conditia se testeaza imediat la intrarea in structura repetitiva, de aceea, “while-do” se numeste structura repetitiva conditionata anterior.

Structura repetitivă de tip WHILE-DO

Pseudocod

Cat_timp(cond)executa
  Prel

C/C++

while(cond){
  Prel;
}

Mecanism:

  • Pas1. Se testeaza conditia. Daca conditia este adevarata atunci trecem la pasul 2. Daca conditia este falsa se trece la pasul 3
  • Pasul 2: Se executa pachetul de instructiuni “Prel” si se revine la pasul 1.
  • Pasul 3. Stop

Aplicatii

AfisareNumere

Se dă un număr natural n. Afișați în ordine crescătoare primele n numere naturale nenule. Pseudocod

    intreg n, i;
    citeste n;
    i <- 1; 
    cat_timp( i <= n )      
      scrie i, " ";
      i <- i + 1;

C++

#include <iostream>
using namespace std;

int main(){
    int n, i;
    cin >> n;
    i = 1; 
    while( i <= n ){       
      cout << i << " ";
      i++;                    // i = i + 1;
    }
    return 0;
}

Cifra de control

#include <iostream>

using namespace std;

int main(){
  int n;
  cin >> n;
  cout << ( n - 1 ) % 9 + 1;
  return 0;
}
  intreg n, s;
  citeste n;
  cat timp ( n > 9 ) executa       // cata vreme numarul are mai mult de o cifra
    s = 0;
    cat_timp ( n > 0 ) executa
      s = s + n mod 10;
      n = n div 10;
    n = s;
  scrie n;
#include <iostream>

using namespace std;

int main(){
  int n, s;
  cin >> n;
  while ( n > 9 ){
    s = 0;
    while ( n > 0 ){
      s += n % 10;
      n = n / 10;
    }
    n = s;
  }
  cout << n;
  return 0;
}
 intreg n, i, c;
 citeste n, c;
 i <- c;
 while ( i <= n )
   scrie i, " ";
   i <- i + 9;
#include <fstream>

using namespace std;
ifstream fin( "cifra.in" );
ofstream fout( "cifra.out" );
int main(){
  int n, i, c;
  fin >> n >> c;
  i = c;
  while ( i <= n ){
    fout << i << " ";
    i += 9;
  }
  return 0;
}

LABORATOR

2 la n

Sa se calculeze 2 la puterea n.

 intreg n, contor;
 citeste n;
 contor = 0; 
 p = 1;
 while ( contor < n ) 
   p = p * 2;
   contor <- contor + 1;
 scrie  p;
#include <stdio.h>

int main() {
  int n, contor;
  scanf( "%d", &n );
  contor = 0; 
  p = 1;
  while (  contor < n ) {
    p = p * 2;
    contor ++;
  }
  printf( "%d ", p );
  return 0;
}

Ridicarea la putere se poate face si in timp logaritmic astfel:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat. Complexitatea acestei soluţii va fi logaritmică, O(log n). Ce înseamnă acest lucru? Că timpul necesar calculului este proporţional cu un număr k, unde k este exponentul lui 2 astfel încît 2k=n.

Iată soluția bazată pe această idee:

#include <stdio.h>

int main() {
  int a, n, p;

  scanf( "%d%d", &a, &n );
  p = 1;
  while ( n > 0 ) {
    if (n % 2 == 1)
      p = p * a;
    a = a * a;
    n = n / 2;
  }
  printf( "%d", p );

  return 0;
}

Citire/ scriere in C/c++

Instalare codeblocks

Reguli minime de editare cod

  • acolada care deschide un bloc de intructiuni va fi pe aceeasi linie cu structura care il contine:
  • identarea la 2 spatii,

Ex:

int main() {
  if ( conditie ) {
    instructiune1;
  } 
  else if ( conditie ) {
    instructiune2;
  } 
  else {
    instructiune3;
  }
}

Tema

TEMA Teorie

Se dă un număr natural n. Afișați în ordine crescătoare primele n numere naturale pare nenule.

Se dă un număr natural n. Afișați în ordine descrescătoare primele n numere naturale nenule.

Se dă un număr natural n. Afișați în ordine descrescătoare primele n numere naturale impare. Se dă un număr natural n. Afișați în ordine crescătoare primele n numere naturale pare nenule.

  • Scrieti in pseudocod algoritmii de rezolvare pentru problema “palindrom”.

Tema 5 Laborator

  • Cangur
  • Economii
  • Minute
  • (usoara) Se citeste un numar n. Afisati numarul rezultat prin eliminarea primei cifre a lui n.
  • (medie) Se citeste un numar n. Afisati cifra de control a numarul n. Cifra de control se obtine prin adunarea repetata a cifrelor numarului pana cand se obtine o singura cifra.

Ex: n=193 s=1+9+3=13 s=1+3=4

  • (dificila)Se citeste un numar n. Sa se afiseze cel mai apropiat fata de n numar palindrom.

Ex1: 122 , afisam 121; nr 122 e cuprins intre 121 si 131, iar 121 este mai apropiat fata de 122 Ex2: 452 , afisam 454; nr 452 este cuprins intre 444 si 454

Suplimentar:

Ca aplicatie la ridicarea la putere:

Probleme OJI :