Clasa a VI-a lecția 7 - 1 nov 2018

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Submulțimi1

Problema submulțimi1 a fost explicată pe larg în clasă. Aveți în lecție și programul.

Baza ascunsă

Problema baza ascunsă.

Răspuns: aceasta este o problemă-exercițiu, destul de directă, care nu ar trebui să vă pună mari probleme. Vom citi mai întîi numărul n, apoi numărul în bază necunoscută, construind un vector cu valorile cifrelor lui. Apoi vom încerca pe rînd să-l convertim la baze din ce în ce mai mari, pînă ce găsim baza în care valoarea lui este mai mare ca a lui n. Atenție: trebuie să avem grijă la următoarele aspecte:

  • Deoarece numărul în baza ascunsă poate conține litere îl vom citi ca un șir de caractere.
  • În vector este bine să stocăm valorile cifrelor. Aceasta înseamnă că după citirea unui caracter al numărului el va trebui convertit la valoarea lui, scăzînd fie '0' dacă este cifră zecimală, fie 'A' dacă este literă, iar apoi îi adunăm zece, deoarece valorile cifrelor litere pornesc de la zece.
  • Baza de pornire, de la care începem căutarea, trebuie să fie egală cu valoarea celei mai mari cifre plus 1. Dacă baza ar fi mai mică acea cifră nu ar avea sens.
  • Deși cifrele numărului sînt între 0 și 35 ca valoare aceasta nu înseamnă că baza căutată nu depășește 36! Aici se pot păcăli cei neatenți. Putem avea numere în baza 100 scrise numai cu cifre între 0 și 35!
  • Deși numărul n este maxim două miliarde este posibil ca numărul în baza ascunsă să depășească două miliarde. De aceea va trebui să-l declarăm long long.

Iată programul bazat pe aceste idei:

#include <stdio.h>

char cifre[61];

int main() {
  FILE *fin, *fout;
  int n, i, nc, b;
  long long k;
  char ch;

  fin = fopen( "ascunsa.in", "r" );
  fscanf( fin, "%d ", &n ); // citim n si ignoram spatiile de dupa
  nc = b = 0;
  ch = fgetc( fin );
  while ( ch != '\n' ) {    // citim secventa de caractere
    if ( ch <= '9' )        // transformindu-le la valorile cifrelor
      cifre[nc] = ch - '0'; // valoarea este cifra minus caracterul zero
    else
      cifre[nc] = ch - 'A' + 10; // valoarea e cifra - 'A' dar incepe de la 10
    if ( cifre[nc] > b )
      b = cifre[nc];        // b va fi maximul dintre cifrele lui k
    nc++;
    ch = fgetc( fin );
  }
  fclose( fin );

  // deoarece cifra maxima este b stim ca baza minima posibila este b+1
  do {
    b++;
    k = 0;
    for ( i = 0; i < nc; i++ ) // calculam k in baza b
      k = k * b + cifre[i];
  } while ( k <= n );

  fout = fopen( "ascunsa.out", "w" );
  fprintf( fout, "%lld %d\n", k, b );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Citirea va fi O(log n). De ce? Deoarece știm că valoarea lui k nu va depăși 260, deci numărul maxim de cifre al lui este 61, adică log2 n. Bucla do ... while se va executa pîna la găsirea bazei. Care este baza maximă la care poate să se ajungă? Ea este n+1 dacă numărul la intrare, k, este '10'. Deci bucla se poate executa de O(n) ori! Mai mult, în interior avem o altă buclă în care calculăm valoarea lui k în baza b. Ea se va executa pentru fiecare cifră a lui k, deci de O(log n) ori. Rezultă complexitatea calculului ca fiind O(n log n) care vi fi și complexitatea finală a algoritmului.

Se poate mai bine?

Decbin

Problema decbin dată la concursul .campion 2005, grupa mică (nr01).

Răspuns: soluția forță brută este să parcurgem toate numerele de la 1 la n, să le convertim la baza b și să verificăm că au numai cifre zero și unu. Însă pentru baze diferite de baza doi vom avea multe numere care nu corespund. Această soluție este, așadar, ineficientă și poate pica teste, deoarece va testa maxim 100 000 000 de numere.

O soluție elegantă va genera direct numerele cerute: vom număra în baza doi, iar apoi, bazat pe cifrele numărului în baza doi vom genera numărul care are aceleași cifre în baza b. Ne vom opri atunci cînd numărul generat depășește n. În felul acesta vom trece doar prin numerele cerute. De ele depinde și complexitatea soluției. Cîte astfel de numere avem? Cît este cel mai mare număr. El va fi cel mai mare număr în baza doi, care interpretat în baza b este mai mic sau egal cu n. Cazul cel mai rău apare atunci cînd b este minim, adică 4. Cea mai mare putere a lui 4 care încape în n maxim (100 de milioane) este aproximativ 413 care este mai mic ca 227 care este aproximatic 100 de milioane. Cel mai mare număr pe 13 cifre binare este 213-1, deci vom avea maxim 10 000 000 000 000(2) = 8192(10) numere de afișat.

Ce complexitate are programul? Ea este O(2logbn). Deoarece știm că n este cel puțin patru, din calcule peste nivelul clasei a șasea rezultă o complexitate O({\sqrt  {n}}). În fapt complexitatea exactă este ceva mai bună, anume O({\sqrt[ {\log _{2}b}]{n}})

Iată programul:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, b, c, cc;
  long long cb, pb;

  fin = fopen( "decbin.in", "r" );
  fscanf( fin, "%d%d", &n, &b );
  fclose( fin );

  fout = fopen( "decbin.out", "w" );
  c = cb = 0;          // c este numarul in baza 2, cb numarul in baza b
  while ( cb <= n ) {  // numarul nu a depasit n
    fprintf( fout, "%lld\n", cb ); // deci il afisam
    c++;               // trecem la urmatorul numar in baza 2
    cc = c;            // si ii facem o copie
    pb = 1;            // pb=puterea in baza b
    cb = 0;            // cb=numarul de cifre 0 si 1 convertit la baza b
    while ( cc > 0 ) { // cita vreme mai avem cifre
      cb += pb * (cc % 2); // aduna puterea bazei (b^n) ori cifra in baza doi
      pb *= b;         // crestem puterea bazei
      cc /= 2;         // eliminam ultima cifra binara
    }
  }
  fclose( fout );

  return 0;
}

Rezolvări aici [1]

Lecție

Concursuri din materia predată în acest an școlar. Problemele necesită ciurul lui Eratostene și baza de numerație doi.

Grupa de dimineață

Grupa de după-amiază

Temă

Opțional (la arhivă):

  • Problema Submulţimi 2, problemă grea de baze de numerație
  • Problema Joc 2, dată la ONI 2010 clasa a 6a

Rezolvări aici [2]