Clasa a V-a lecția 39 - 27 mai 2014

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Problema 2048

Problema 2048 a fost dată la ONI 2014 clasa a 5a.

Este o problemă de simulare (vom avea un capitol despre aceasta la anul). Sînt convins că puteți scrie o soluție directă, în care să efectuați întocmai operațiile cerute. Aici vom vorbi despre o soluție cît mai eficientă, care să nu copieze elemente în vector mai mult decît este necesar. În același timp vom încerca să nu scriem cod duplicat sau asemănător.

Pentru a nu copia elemente mai mult decît este necesar vom păstra doi indici care semnifică prima și ultima poziție între care se află elemente în vector. Pe măsură ce elementele fuzionează cei doi indici se vor apropia unul de altul.

Problema babilon

Problema babilon a fost dată la ONI 2014 clasa a 5a.

Pentru a rezolva corect această problemă trebuie să înțelegem conceptul de baze de numerație, care este un subiect de clasa a 6a. Nu știu motivul pentru care s-a dat la olimpiada de clasa a 5a. Poate că mottoul comisiei este "hai să depășim clasa a 6a la greutatea problemelor". Aceasta ar explica faptul că tot la clasa a 5a s-a dat problema iepurași, problemă NP-hard, de cercetare mondială, pentru care omenirea nu cunoaște o rezolvare bună.

Pe o notă mai serioasă, bănuiesc că problemele la clasa a 5a tind să fie de nivel mai mare pentru că comisia este îngrijorată că nivelul vostru este foarte ridicat. Ceea ce este de înțeles. Ce nu înțeleg este de ce, în loc să dea subiecte mai grele la nivel de clasa a 5a, comisia preferă să le facă artificial grele dînd subiecte de clasa a 6a. În acest ritm s-ar putea să trebuiască să învățăm grafuri orientate la clasa a 5a.

În concluzie, cei ce nu veți ști să rezolvați această problemă nu vă îngrijorați. După ce vom învăța baze de numerație veți vedea că problema este relativ banală.

Rezolvări aici [1]

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 39 clasa a 5a

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_V-a_lecția_39_-_27_mai_2014&oldid=10002"