Clasa a IX-a lecția 6

From Algopedia
Jump to navigationJump to search

Note de curs: prof. Isabela Coman

Prelucrarea cifrelor unui numar

Teorie

Prima cifra a unui numar

Se citește n. Să se afișeze prima cifra lui n. Pseudocod

  intreg n
  citeste n
  cat_timp ( n > 9 ) executa
    n = n div 10
  scrie n

C/C++

#include <stdio.h>

int main() {
  int n;

  scanf( "%d", &n );
  
  while ( n > 9 ) 
    n = n / 10;

  printf( "%d ", n );
  return 0;
}
#include <iostream>
using namespace std;
int main() {
  int n;

  cin >> n;
  
  while ( n > 9 ) 
    n = n / 10;

  cout << n;
  return 0;
}
#include <iostream>
using namespace std;
int main() {
  int n;
  int p = 1000000000;
  cin >> n;
  while ( p > n )
    p = p / 10;
  cout << n / p;
  return 0;
}
#include <iostream>
using namespace std;
int main() {
  int n;
    cin >> n;
  int p = 1;
  while ( p <= n )
    p = p * 10;
  p = p / 10;
  cout << n / p;
  return 0;
}

Afisare cifre in ordine inversa

Se citește n. Să se afișeze cifrele lui n în ordine inversă.

Afișare cifre număr în ordine inversă

Acest algoritm de PARCURGERE a cifrelor unui numar, se va aplica problemelor care prelucreaza intr-un fel sau altul cifrele numarului respectiv. Pentru a putea parcurge cifrele unui numar, accesam mai intai cifra care se poate extrage cel mai usor din numar, si anume ultima cifra (stim ca ultima cifra a oricarui numar este restul impartirii numarului respectiv la 10). Dupa ce am extras aceasta cifra si am afisat-o , eliminam aceasta cifra din numar, astfel incat, penultima cifra a numarul va deveni ultima cifra, si deci o vom putea extrage usor si pe aceasta, la pasul urmator.

Pseudocod

intreg n
Citeste n
Cat_timp ( n > 0 ) executa
  scrie n mod 10
  n = n div 10

C:

#include<stdio.h>
int main(){
  int n;
  printf( "Dati un numar: " );
  scanf( "%d", &n );
  printf( "Cifrele in ordine inversa: " );
  while(n > 0){         
    printf( "%d", n % 10 );
    n = n / 10;
  }
  return 0;
}

C++:

#include <iostream>
using namespace std;
int main(){
  int n;
  cin >> n;
  while( n > 0 ){
    cout << n % 10;
    n = n / 10;
  }
return 0;
}

Suma cifrelor unui numar

Schemă logică

Acest algoritm, se bazeaza pe algoritmul de parcurgere a cifrelor unui numar, descris anterior. Vom avea nevoie in plus, de o variabila ACUMULATOR (o vom denumi s, de la suma), variabila in care vom aduna pe rand valorile cifrelor accesate. Pe masura ce accesam o cifra a unui numar, adunam valoarea cifrei la valoarea anterioara a acumulatorului, care valoare, este initial 0. Daca am fi dorit sa calculam produsul cifrelor unui numar, cat ar fi trebuit sa fie initial variabila acumulator?

Pseudocod

intreg n, s
citeste n
s = 0;
cat_timp ( n > 0 ) executa
  s <- s + n mod 10
  n <- n div 10
scrie s

C

include<stdio.h>
int main(){
  int n, s;
  scanf( "%d", &n );
  s = 0;
  while( n > 0 ){
    s= s + n % 10;
    n = n / 10;
  }
  printf("%d",s);
  return 0;
}

C++:

#include <iostream>
using namespace std;
int main(){
  int n, s;
  cin >> n;
  s = 0;
  while( n > 0 ){
    s = s + n % 10;
    n = n / 10;
  }
  cout << s;
return 0;
}

Cate cifre are un numar

Acest algoritm, se bazeaza pe algoritmul de parcurgere a cifrelor unui numar, descris anterior. Vom avea nevoie in plus, de o variabila CONTOR , cu ajutorul caruia vom numara cifrele pe masura ce le vom parcurge. Vom parcurge cifrele numarului incepand cu ultima cifra , si pentru fiecare cifra accesata, vom mari valoarea contorului cu 1.

Pseudocod

intreg n, contor
citeste n
contor = 1
cat_timp ( n > 9 ) executa
  contor = contor + 1
  n = n div 10
scrie contor

C

#include<stdio.h>
int main(){
  int n, contor;
  scanf( "%d", &n );
  contor = 1;
  while( n > 9 ){
    contor = contor + 1; 
    n = n / 10;
  }
  printf( "%d", contor );
return 0;
}

C++

include <iostream>
using namespace std;
int main(){
  int n, contor;
  cin >> n;
  contor = 0;
  while( n > 0 ){
    contor = contor + 1; 
    n = n / 10;
  }
 cout << contor;
return 0;
}

Algoritmul de mai sus ne da raspunsul corect pentru n = 0?

include <iostream>
using namespace std;
int main(){
  int n, contor;
  cin >> n;
  contor = 1;
  while( n > 9 ){
    contor = contor + 1; 
    n = n / 10;
  }
 cout << contor;
return 0;
}

Cate cifre sunt egale cu o cifra k

Acest algoritm, se bazeaza pe algoritmul de parcurgere a cifrelor unui numar, descris anterior. De asemenea, vom avea nevoie sa numaram cifrele care indeplinesc conditia data, folosind o variabila contor. In plus, vom avea nevoie sa testam daca o anumita cifra indeplineste conditia ceruta, si numai daca conditia este adevarata sa marim valoarea contorului.

Pseudocod

contor <- 0;
cat_timp( n > 0 ) executa
  daca ( n mod 10 = k ) atunci
    contor <- contor + 1
  n <- n div 10
scrie contor

C

#include <stdio.h>

int main(){
  int n, k, contor;
  scanf("%d%d", &n, &k);  
  if ( n == 0 && k == 0 )
    contor = 1;
  else
    contor = 0;
  while( n > 0 ){
    if( n % 10 == k )
      contor ++;
    n = n / 10;
  }
  printf( "%d", contor );
}

C++

#include <iostream>
using namespace std;
int main(){
  int n, k, contor;
  cin >> n >> k;  
  if ( n == 0 && k == 0 )
    contor = 1;
  else
    contor = 0;
  while( n > 0 ){
    if( n % 10 == k )
      contor ++;
    n = n / 10;
  }
  cout << contor;
  return 0;
}

Sunt toate cifrele lui n pare?

Acest algoritm, se bazeaza pe algoritmul de parcurgere a cifrelor unui numar, descris anterior. Vom avea nevoie in plus, de o variabila STEAG (SEMN) , cu ajutorul caruia vom identifica daca numarul are o cifra care nu respecta conditia data. Vom parcurge toate cifrele numarului si de fiecare data cand vom gasi o cifra care nu respecta conditia( nu este para) vom seta valoarea steguletului pe 0 (codificare a raspunsului NU, nu este ok numarul). Initial valoarea steguletului va fi setata pe 1 (codificare a raspunsului DA; presupunem ca numarul are numai cifre pare, adica este ok) Variabila cu rol de steag este gasit.

Pseudocod

gasit = 1;
cat_timp( n > 0 ) executa
  daca( n mod 2 == 1 )
    gasit = 0
  n<-n div 10;
daca ( gasit == 0 )
  scrie “nu sunt toate pare”
altfel
  scrie “sunt toate pare”

C

  gasit = 0;             // pp ca numarul nu are cifre impare ( toate cifrele sunt pare )
  while( n > 0 && gasit == 0 ) {
    if( n % 2 == 1 )     // dc am gasit o cifra impara
      gasit = 1;         // numarul are cifre impare
    n = n / 10;
  }
  if( gasit == 1 )
    cout << “nu sunt toate pare”;
  else
    cout << “sunt toate pare”;

Varianta condensata:

   
  while( n > 0 && n % 2 == 0 )    // cat timp am cifre in n si ultima nu e impara
    n = n / 10;  
  if( n > 0 )
    printf("nu sunt toate pare");
  else
    printf("sunt toate pare");

Afisare cifre de la stanga la dreapta

using namespace std;

int main(){
  int n;
  cin >> n;
  int p = 1000000000;
  while ( p > n )
    p = p / 10;
  while ( p > 0 ){
    cout << n / p << " ";
    n = n % p;
    p = p / 10;
  }
  return 0;
}

Cifra maxima

Se citeste un numar n, natural. Sa se afiseze cifra cea mai mare care apare in numarul n.

#include <stdio.h>

int main() {
  int n, cmax, f, nc;
  ///citim numarul n ca numar intreg
  scanf( "%d", &n );
  ///calculam cea mai mare cifra a sa
  cmax = n % 10;
  n = n / 10;
  while( n > 0 ){
    if( n % 10 > cmax )
      cmax = n % 10;
    n = n / 10;
  }
 
  printf( "%d\n", cmax );
  return 0;
}

Cifra maxima si frecventa acestuia

  • 1. Se citeste un numar n. Afisati cifra maxima si specificati de cate ori apare aceasta in numar.


#include <stdio.h>

int main() {
  int n, cmax, f, nc;
  ///citim numarul n ca numar intreg
  scanf( "%d", &n );
  nc = n;
  ///calculam cea mai mare cifra a sa
  cmax = n % 10;
  n = n / 10;
  while( n > 0 ){
    if( n % 10 > cmax )
      cmax = n % 10;
    n = n / 10;
  }
  ///calculam de cate ori apare cifra cmax in n
  f = 0;
  while( nc > 0 ){
    if( nc % 10 == cmax )
      f = f + 1;
    nc = nc / 10;
  }
  printf( "%d %d\n", cmax, f );
  return 0;
}
#include <stdio.h>

int main() {
  int n, cmax, f, uc;

  ///citim numarul n ca numar intreg
  scanf( "%d", &n );

  ///calculam cea mai mare cifra a sa cmax, si de cate ori apare f
  cmax = n % 10;                // cifra maxima presupun a fi ultima cifra
  f = 1;                        // aceasta apare deocamdata odata
  n = n / 10;                   // scoatem din numar ultima cifra
  while ( n > 0 ){              // cata vreme am cifre in numar
    if ( n % 10 > cmax ){       // compar ultima cifra a numarului cu cifra maxima
      cmax = n % 10;            // daca e mai mare, modific valoarea din maxim
      f = 1;                    // noul maxim apare deocamdata o data
    }
    else if ( n % 10 == cmax )  // daca am gasit o val egala cu maximul
      f = f + 1;                // cresc frecventa maximului
    n = n / 10;                 // tai ultima cifra din n
  }
  printf( "%d %d\n", cmax, f );
  return 0;
}

Inversul unui numar

Schemă logică

Pseudocod

 intreg n, r;
 citeste n
 r = 0;
 cat_timp ( n > 0 ) executa
   r = r * 10 + n mod 10    
   n = n div 10
 scrie r

C

  int n, r;

  scanf( "%d", &n );
  r = 0;
  while ( n > 0 ) {
    r = r * 10 + n % 10;    
    n = n / 10;
  }
  printf( "Rasturnatul lui n este %d\n", r );
  return 0;
}

Palindrom

Definiție: un număr palindrom (sau simetric) este un număr care este identic cu răsturnatul lui. Cu alte cuvinte el arată la fel dacă îi scriem cifrele de la stînga la dreapta sau de la dreapta la stînga. Exemple de numere palindrom sînt 1221, 5229225, 27272, 44, 1. Problemă: să se determine dacă un număr n este palindrom. Rezolvare: vom calcula răsturnatul lui n în variabila r. Dacă cele două numere sînt egale înseamnă ca numărul este palindrom. Trebuie să acordăm atenție faptului că n va fi distrus în timpul calculului, drept pentru care îi vom face o copie în nc.

#include <stdio.h>

int main() {
  int n, nc, r;

  scanf( "%d", &n );
  nc = n;
  r = 0;
  while ( n > 0 ) {
    r = r * 10 + n % 10;
    n = n / 10;
  }
  if ( nc == r )
    printf( "%d este palindrom\n", nc );
  else
    printf( "%d nu este palindrom\n", nc );
  return 0;
}

Algoritmul clasic verifică dacă numărul este egal cu răsturnatul său: Avem şi o metodă mai apropiată de cea originală, în care răsturnăm numărul numai pînă la jumate:

#include<stdio.h>

int main(){
  long long n, r;
  scanf("%lld", &n );

  if ( n > 0 && n % 10 == 0 )
    printf("NU\n");
  else {
    r = 0;
    while( n > r ){
      r = r * 10 + n % 10;
      n = n / 10;
    }
    // cand numarul are un numar par de cifre testam daca p == r
    // cand numarul are un numar impar de cifre testam daca p == r / 10
    if( n == r || n ==(r /10))
      printf("DA\n");
    else
      printf("NU\n");
  }
  return 0;
}

Metoda: Rasturnam numarul pana la jumatate; Cum obtinem cele 2 jumatati? Vom muta in r cifre din n pana cand r devine mai mare ca n. Atentie la numerele cu zerouri la coada. Ex: 5500

Permutari circulare a cifrelor numarului catre dreapta

Sa se afiseze toate numerele obtinute prin permutarea cifrelor lui n. Ex: pentru n = 12345 vom afisa: 51234 45123 34512 23451

#include <iostream>
#include <iostream>
using namespace std;

int main(){
  long long n;
  cin >> n;

  long long p = 1e12;

  while ( p > n )
    p /= 10;

  long long p2 = 10;
  while ( p > 1 ){
    cout << n % p2 * p + n / p2 << " ";
    p /= 10;
    p2 *= 10;
  }
  return 0;
}

Permutari circulare a cifrelor numarului catre stanga

Sa se afiseze toate numerele obtinute prin permutarea cifrelor lui n. Ex: pentru n = 12345 vom afisa: 23451 34512 45123 51234

#include <iostream>
using namespace std;

int main(){
  long long n;
  cin >> n;

  long long p = 1e12;

  while ( p > n )
    p /= 10;

  long long p2 = 10;
  while ( p > 0 ){
    cout << n % p * p2 + n / p << " ";
    p /= 10;
    p2 *= 10;
  }
  return 0;
}

LABORATOR

Eliminarea primei cifre

Se citeste un numar n. Afisati numarul rezultat prin eliminarea primei cifre a lui n.

Varianta1

Vom construi un numar nou, adaugand la noul numar toate cifrele lui n, mai putin prima cifra.

Pseudocod C/C++
integer n, p, x;
read n;
p ← 1;
x ← 0;
while (n > 9) do
  x ← (n mod 10) * p + x;  
  p ← p * 10;
  n ← n div 10;
write x;
#include <iostream>
using namespace std;
int main(){
  int n, p, x;
  cout << "Dati un numar n:" << endl;
  cin >> n;
  p = 1;
  x = 0;
  while (n > 9){
    x = (n % 10) * p + x;
    p = p * 10;
    n = n / 10;
  }
  cout << "Numarul rezultat este: " << x;
  return 0;
}

Varianta2

Vom calcula puterea lui 10 la care trebuie sa impartim numarul astfel incat sa eliminam prima cifra.

Pseudocod C/C++
 integer n, p;
 read n;
 p = 1000000000;
 while(p>n)
   p = p / 10;
 write n % p;
#include <iostream>
using namespace std;
int main(){
  int n, p;
  cin >> n;
  p = 1000000000;
  while(p>n)
    p = p / 10;
  cout << n % p;
  return 0;
}

Numar corect scris in baza b

  • 3. Se citeste un numar n. Verificati daca este un numar scris corect in baza b, unde b <=10.
int n;
cin >> n;
cin>>b;      //citim b
ok = 1;      //presupunem ca e scris corect; folosim stegulet
while ( n > 0 ){    //si mai bine ar fi sa ne oprim cand gasim o cifra neok: while ( n > 0 && ok==1)
  pcif = n % 10;
  if ( pcif > = b )//daca am gasit o cifra >b 
    ok = 0;          //setam steguletul pe 0
  n = n % 10;      
}
if( ok == 1 )
  cout << " nr este corect in baza " << b;
else
  cout << " nr nu este corect in baza"<< b;

Putem de asemenea sa scriem algoritmul de mai sus fara a folosi o variabila stegulet;

while( n > 0 && n % 10 < b)  //cata vreme am cifre si ultima cifra e ok
     n = n / 10;
if( n == 0 )
  cout << "e ok";
else 
  cout << "nu e ok";

Extragere cifre pare din n

  • 2. Se citeste un numar n, de maxim 9 cifre. Afisati numarul care contine, in aceeasi ordine doar cifrele pare ale lui n. Ex: n = 12345, Se va afisa 24;

Varianta1

  intreg n, p, ucif, nr;  
  citeste n;             // citim numarul n ca numar intreg
  p = 1;
  nr = 0;                // nr pe care il construim adaugand doar cifrele pare
  cat_timp ( n > 0 ) executa
    ucif = n mod 10;                 // extragem ultima cifra a lui n
    daca ( ucif mod 2 == 0 )  atunci // daca cifra este para
      nr = ucif * p + nr;            // adaugam cifra para in fata numarului nr
      p = p * 10;                    // calc puterea cu care trebuie sa inmultim la pasul urmator
    n = n div 10;                    // taiem ultima cifra din n

  scrie nr;
#include <stdio.h>

int main() {
  int n, p, ucif, nr;

  ///citim numarul n ca numar intreg
  scanf( "%d", &n );

  p = 1;
  nr = 0;               /// nr pe care il construim adaugand doar cifrele pare
  while ( n > 0 ){
    ucif = n % 10;          /// extragem ultima cifra a lui n
    if ( ucif % 2 == 0){    /// daca cifra este para
      nr = ucif * p + nr;   /// adaugam cifra para in fata numarului nr
      p = p * 10;           /// calculam puterea cu care trebuie sa inmultim la pasul urmator
    }
    n = n / 10;             /// taiem ultima cifra din n
  }

  printf( "%d", nr );
  return 0;
}

Varianta2

Varianta cu citire/afisare date din/in fisier varianta C.

#include <stdio.h>
#include <stdlib.h>

int main(){
  int n, p10, nr, pcif;
  FILE *fin = fopen("date.in", "r");     /// r de la read
  FILE *fout = fopen ("date.out", "w");  /// w de la write
  /// cititm n din fisierul de intrare
  fscanf(fin,"%d", &n);

  ///calculeaza puterea lui 10 care aproximeaza pe n ( mai mica sau egala cu n)
  p10 = 100000000;
  while ( p10 > n )
    p10 = p10 /10;

  ///construiesc numarul cerut parcurgand cifrele incepand de la prima cifra a sa
  nr = 0;
  while ( p10 > 0 ){        /// ATENTIE! n>0 CA NU MERGE PT NUMERE CU ZEROURI LA COADA
    pcif = n / p10;         /// extrag prima cifra din n
    if ( pcif % 2 == 0)     /// daca cifra este para
      nr = nr * 10 + pcif;  /// adaug cifra la coada lui nr
    n = n % p10;            /// scot prima cifra din n
    p10 = p10 / 10;         /// ajustez puterea lui 10
  }
  
  ///afisam nr in fisierul; de iesire
  fprintf(fout, "%d", nr);
  fclose(fin);
  fclose(fout);
  return 0;
}

Numere palindrom apropiate de n

Varianta1: Se citeste un numar n. Sa se afiseze cel mai apropiat numar palindrom fata de n, diferit de n.
Ex1: n = 122 , afisam 121; nr 122 e cuprins intre 121 si 131, iar 121 este mai apropiat fata de 122
Ex2: n = 121 , afisam 111 131; 111, 131 sunt la aceeasi distanta fata de n
Ex3: n = 247 , afisam 242 252; 242, 252 sunt la aceeasi distanta fata de n

#include <iostream>
using namespace std;
int main(){
    int n, cn1, cn2, c1, c2, palin1, palin2, inv;
    cin>>n;               //citim n
    cn1=n-1;
    cn2=n+1;
    palin1 = palin2 = -1;                   //nu le-am gasit inca
    while (palin1 == -1 && palin2 == -1){   //inca nu le-am gasit
      //verific daca cn1 e palindrom
      c1=cn1;
      inv = 0;
      while (c1 > 0){
        inv = inv * 10 + c1 % 10;
        c1 = c1 /10; //div
      }
      if (cn1 == inv ){
        palin1 = cn1;
      }
      //verific daca cn2 e palindrom
      c2=cn2;
      inv = 0;
      while (c2 > 0){
        inv = inv * 10 + c2 % 10;
        c2 = c2 /10; //div
      }
      if (cn2 == inv ){
        palin2 =cn2;
      }
      cn1 = cn1-1;
      cn2 = cn2+1;
    }
    if (palin1!=-1 && palin2!=-1)   //cand am gasit 2 la aceeasi distanta
      cout<<palin1<<palin2;
    else if (palin1!=-1)            //daca am gasit doar pe palin1
      cout<<palin1;
    else
      cout<<palin2;

    return 0;
}

Varianta2: Se citeste un numar n. Sa se afiseze cel mai apropiat numar palindrom fata de n.
Ex1: n = 122 , afisam 121; nr 122 e cuprins intre 121 si 131, iar 121 este mai apropiat fata de 122
Ex2: n = 121 , afisam 121
Ex3: n = 247 , afisam 242 252; 242 si 252 sunt la aceeasi distanta fata de n

#include <iostream>
using namespace std;
int main(){
    int n, cn1, cn2, c1, c2, palin1, palin2, inv;
    cin>>n;               //citim n
    cn1=n;
    cn2=n;
    palin1 = palin2 = -1;                   //nu le-am gasit inca
    while (palin1 == -1 && palin2 == -1){   //inca nu le-am gasit
      //verific daca cn1 e palindrom
      c1=cn1;
      inv = 0;
      while (c1 > 0){
        inv = inv * 10 + c1 % 10;
        c1 = c1 /10; //div
      }
      if (cn1 == inv ){
        palin1 = cn1;
      }
      //verific daca cn2 e palindrom
      c2=cn2;
      inv = 0;
      while (c2 > 0){
        inv = inv * 10 + c2 % 10;
        c2 = c2 /10; //div
      }
      if (cn2 == inv ){
        palin2 =cn2;
      }
      cn1 = cn1-1;
      cn2 = cn2+1;
    }
    if (palin1!=-1 && palin2!=-1){   //cand am gasit 2 la aceeasi distanta
      if(palin1 == palin2)           //cand 
        cout<<palin1;
      else
      cout<<palin1<<" "<<palin2;
    }
      
    else if (palin1!=-1)            //daca am gasit doar pe palin1
      cout<<palin1;
    else
      cout<<palin2;

    return 0;
}

Tema

Teorie

Laborator

Probleme de concurs

Codeforces