Clasa a V-a lecția 40 - 2 iun 2015

From Algopedia
Revision as of 06:38, 11 June 2015 by Cristian (talk | contribs) (Cristian moved page Clasa a V-a lecția 40 - 2 iunie 2015 to Clasa a V-a lecția 40 - 2 iun 2015 without leaving a redirect)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Lecţie

Constante in C

Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc. Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:

#define D 1
...
if ( D )
  printf( "x=%d   y=%d   a=%d\n", x, y, a )
...

La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:

#define D 0

Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.

Instrucțiunea switch

Precum ştim instrucţiunea if implementează structura alternativă. Uneori avem nevoie de decizii multiple, de exemplu cînd vrem să ştim dacă o variabilă are valoarea 1, 2 sau 3. În aceste cazuri putem folosi o combinaţie de instrucţiuni if:

if ( n == 1 ) {
  cod pentru cazul 1;
} else if ( n == 2 ) {
  cod pentru cazul 2;
} else if ( n == 3 ) {
  cod pentru cazul 3;
}

Deoarece situaţiile cînd vrem să executăm diverse acţiuni în funcţie de valoarea unei variabile limbajul C se oferă instrucţiunea switch a cărei formă este:

switch ( n ) {
case constantă1:
  cod de executat dacă n este egal cu constantă1;
  break;
case constantă2:
  cod de executat dacă n este egal cu constantă2;
  break;
  .
  .
  . 
default:
   cod de executat dacă n nu este egal cu nici una din constante;
}

Exemplu: se citesc pe aceeaşi linie, în ordine, un caracter şi apoi două numere întregi, toate separate printr-un spaţiu. Dacă caracterul este una din operaţiile +, -, * sau / să se afişeze rezultatul acelei operaţii pe cele două numere. În caz contrar să se afişeze cuvîntul eroare.

Rezolvare:

#include <stdio.h>

int main() {
  int a, b;
  char ch;

  ch = fgetc( stdin );
  scanf( "%d%d", &a, &b );
  switch ( ch ) {
  case '+':
    printf( "%d\n", a + b );
    break;
  case '-':
    printf( "%d\n", a - b );
    break;
  case '*':
    printf( "%d\n", a * b );
    break;
  case '/':
    printf( "%d\n", a / b );
    break;
  default:
    printf( "eroare\n" );
  }
  return 0;
}

De menţionat că nu este obligatoriu să avem o variabilă testată în switch, putem avea o expresie, cu condiţia ca ea să aibă o valoare întreagă, nu reală.

Numere palindrom

Cum aflăm dacă un număr este palindrom (simetric)? Algoritmul clasic răstoarnă numărul şi testează dacă numărul este egal cu răsturnatul său:

#include <stdio.h>

int main() {
  long long p, c, r;
  scanf( "%lld", &p );
  c = p;
  r = 0;
  while ( p > 0 ) {
    r = r * 10 + p % 10;
    p = p / 10;
  }
  if ( c == r )
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

Acest algoritm poate depăși valoarea maximă reprezentabilă pe tipul long long.

Ce alt algoritm putem folosi? O idee ar putea fi să comparăm prima cifră cu ultima, apoi le eliminăm şi reluăm. Iată programul:

#include <stdio.h>

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

  scanf( "%d", &n );
  nc = n;
  p10 = 1;
  // Calculam 10 la puterea nr. cifre - 1
  while ( nc > 9 ) {
    p10 = p10 * 10;
    nc = nc / 10;
  }

  // cita vreme mai avem macar doua cifre si prima cifra este egala cu ultima
  while ( p10 > 1 && (n / p10 == n % 10) ) {
    n = n % p10;     // Taiem prima si ultima cifra din numar
    n = n / 10;
    p10 = p10 / 100; //Actualizam puterea
  }

  if ( p10 <= 1 ) // daca am ajuns la o cifra sau nici una este palindrom
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

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 p, r;
  scanf( "%lld", &p );
  r = 0;
  while ( p > r ) {
    r = r * 10 + p % 10;
    p = p / 10;
  }
  // cînd numărul are un număr par de cifre testăm dacă p == r
  // cînd numărul are un număr impar de cifre testăm dacă p == r / 10
  if ( p == r || p == (r / 10) )
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

Secvență crescătoare prin rotație

Verificare secvență crescătoare prin rotație. O secvență este crescătoare prin rotație dacă fie este crescătoare (nedescrescătoare, include mai mic sau egal), fie poate fi făcută crescătoare prin rotații succesive (permutări circulare). Am discutat despre rezolvarea liniară, care nu necesită vectori.

#include <stdio.h>

int main() {
  int n, i, a, b, primul, caderi;
  scanf( "%d%d", &n, &a );
  primul = a;

  caderi = 0; // de cite ori gasim un numar mai mic ca cel din-naintea lui
  i = 1;
  while ( i < n && caderi < 2 ) {
    scanf( "%d", &b );
    if ( a > b )
      ++caderi;
    a = b;
    ++i;
  }

  if ( caderi == 0 ) // daca e complet crescatoare, OK
    printf( "DA\n" );
  else if ( caderi > 1 )  // daca descreste de doua ori, nu este crescatoare
    printf( "NU\n" );
  else if ( primul >= b ) // daca descreste o data depinde de capete
    printf( "DA\n" );
  else
    printf( "NU\n" );

  return 0;
}

Discuţie probleme temă

Am discutat despre problemele pe care le aveţi ca temă.

Temă

Tema 40 clasa a 5a