Difference between revisions of "Clasa a V-a lecția 35 - 25 apr 2020"

From Algopedia
Jump to navigationJump to search
 
Line 1: Line 1:
= Tema - rezolvări =
 
== Problema siruri1 ==
 
Problema [http://varena.ro/problema/siruri1 siruri1] a fost dată la OJI 2004 clasa a 7<sup>a</sup>. Ea este deosebită. Nu am mai făcut așa ceva pînă acum. De aceea are un grad mai mare de dificultate. Deși rezolvarea, precum veți vedea, este simplă, ea depinde de înțelegerea unei idei.
 
 
'''Ipoteză''': dacă ordonăm numerele crescător, apoi fiecăruia din numere îi "atașăm" poziția pe care se află el, apoi readucem numerele la ordinea inițială, pozițiile atașate lor vor fi chiar vectorul soluție.
 
 
'''Exemplu''': fie numerele originale:
 
 
<pre>12 3 7 16 10 1 </pre>
 
 
După ordonare vom obține:
 
 
<pre>1 3 7 10 12 16</pre>
 
 
Apoi atașăm numerelor pozițiile lor, începînd cu <tt>1</tt>:
 
 
<pre>1 3 7 10 12 16
 
1 2 3  4  5  6</pre>
 
 
Apoi readucem numerele la ordinea inițială, păstrînd și numerele de ordine:
 
 
<pre>12 3 7 16 10 1
 
5 2 3  6  4 1</pre>
 
 
Observați că în al doilea vector am obținut exact ceea ce ni se cere.
 
 
'''Schiță de demonstrație''': deoarece relațiile de inegalitate între elemente se păstrează de la un vector la altul (vorbim de vectorii <tt>x</tt> și <tt>y</tt> din problemă), înseamnă că dacă ordonăm ambii vectori elementele își vor schimba poziția în mod identic. De aceea știm că vectorului ordonat <tt>x</tt> îi corespunde vectorul ordonat <tt>y</tt>, adică valorile de la <tt>1</tt> la <tt>n</tt>.
 
 
Cum rezolvăm problema bazat pe această idee? Știm să ordonăm un vector, conform problemei ''culori''. Dar cum facem să atașăm poziția fiecărui element? Ne putem folosi de următorul truc: știm că toate elementele vectorului <tt>x</tt> sînt distincte. Înseamnă că vectorul lor de frecvență va conține numai unu sau zero. Ce-ar fi ca în loc de <tt>1</tt> să păstram chiar poziția acelui element în vectorul sortat? De exemplu, pentru vectorul nostru, vom avea un vector de frecvență astfel:
 
 
<pre>0 1 0 2 0 0 0 3 0 0  4  0  5  0  0  0  6
 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16</pre>
 
 
Cum transformăm vectorul de frecvență? Pornind cu un contor <tt>k</tt> de la <tt>1</tt> și adunînd unu la <tt>k</tt> de fiecare dată cînd găsim un unu în vectorul de frecvență.
 
 
Ce facem cu acest vector nou de frecvență? El păstrează pentru fiecare număr din <tt>x</tt> poziția sa în vectorul ordonat <tt>x</tt>. De aceea este deajuns sa parcurgem vectorul original <tt>x</tt> și să afișăm valorile <tt><nowiki>f[x[i]]</nowiki></tt>. Iată o soluție bazată pe această idee:
 
 
<syntaxhighlight>#include <stdio.h>
 
 
int v[100], apare[32001];
 
 
int main() {
 
  FILE *fin, *fout;
 
  int n, i, k;
 
 
  fin = fopen( "siruri1.in", "r" );
 
  fscanf( fin, "%d", &n );
 
  for ( i = 0; i < n; i++ ) {
 
    fscanf( fin, "%d", &v[i] );
 
    apare[v[i]] = 1;
 
  }
 
  fclose( fin );
 
 
  // calculam pentru fiecare elemente din vectorul original al citelea
 
  // este in ordine crescatoare
 
  k = 1; // k ne va spune al citelea element este cel actual
 
  for ( i = 0; i <= 32000; i++ ) // parcurgem elementele in ordine crescatoare
 
    if ( apare[i] == 1 ) {
 
      apare[i] = k; // pentru fiecare element pastram al citelea este
 
      k++;          // pregatim urmatorul element
 
    }
 
 
  // in acest moment pentru fiecare element v[i] avem valoarea apare[v[i]]
 
  // care reprezinta al citelea este el in vectorul ordonat
 
  // vom afisa aceste valori in ordinea elementelor de la intrare
 
  fout = fopen( "siruri1.out", "w" );
 
  for ( i = 0; i < n; i++ )
 
    fprintf( fout, "%d ", apare[v[i]] );
 
  fprintf( fout, "\n" );
 
  fclose( fout );
 
 
  return 0;
 
}</syntaxhighlight>
 
 
== Problema case1 ==
 
Problema [http://varena.ro/problema/case1 case1] a fost dată la ONI 2009 clasa a 5<sup>a</sup>. Ea conține un element deosebit: vom folosi elemente ale unui vector ca poziții următoare în același vector. În afara acestei noutăți problema nu prezintă dificultăți deosebite. Iată o soluție cu comentarii:
 
 
<syntaxhighlight>#include <stdio.h>
 
 
int placa[10001];
 
 
int main() {
 
  FILE *fin, *fout;
 
  int n, i, c, vizitate, ok, intoarceri, minint, mini, maxviz;
 
 
  fin = fopen( "case1.in", "r" );
 
  fscanf( fin, "%d", &n );
 
  for ( i = 1; i <= n; i++ )
 
    fscanf( fin, "%d", &placa[i] );
 
  fclose( fin );
 
 
  ok = 0;
 
  minint = n + 1;
 
  maxviz = 0;
 
  mini = 0;
 
  for ( i = 1; i <=n; i++ ) {
 
    c = i;                // piticul i porneste la casuta sa, i
 
    vizitate = 1;        // a vizitat o casuta, pina acum
 
    intoarceri = 0;      // deocamdata nu a facut nici o intoarcere
 
    while ( i != placa[c] ) { // placuta sa e diferita?
 
      vizitate++;        // a mai vizitat o casuta
 
      if ( placa[c] < c ) // daca casuta noua e mai mica decit cea veche
 
        intoarceri++;    // inseamna ca s-a mai intors o data
 
      c = placa[c];      // mergem la casuta urmatoare
 
    }
 
    if ( vizitate == 1 )  // piticul i si-a gasit placuta chiar in casa sa
 
      ok++;
 
    // daca a vizitat mai multe case, sau a vizitat la fel de multe dar
 
    // a facut mai putine intoarceri, retinem piticul
 
    if ( vizitate > maxviz || (vizitate == maxviz && intoarceri < minint) ) {
 
      mini = i;            // retinem piticul i
 
      maxviz = vizitate;  // numarul lui de case vizitate
 
      minint = intoarceri; // si numarul lui de intoarceri
 
    }
 
  }
 
 
  fout = fopen( "case1.out", "w" );
 
  fprintf( fout, "%d\n%d\n%d\n", ok, maxviz, mini );
 
  fclose( fout );
 
 
  return 0;
 
}</syntaxhighlight>
 
 
== Problema arme ==
 
Problema [http://varena.ro/problema/arme arme] a fost dată la OJI 2012 clasa a 7<sup>a</sup>. Ea este o aplicație a sortării prin selecție. Enunțul este oarecum complicat. El ne povestește cum Vasile poate să țină arme la brîu sau să le înlocuiască cu altele din camera armelor. În fapt este destul de clar că pentru a avea cele mai puternice arme la brîu el va lua primele N arme din totalul armelor existente, la brîu sau în camera armelor.
 
 
Odată ce ne lămurim ce ni se cere, problema are o rezolvare directă: așezăm puterile armelor de la brîu și din cameră într-un vector, pe care îl ordonăm. Ultimele N arme vor fi cele de sumă maximă.
 
 
Iată o soluție posibilă:
 
 
<syntaxhighlight>#include <stdio.h>
 
 
int v[2000];
 
 
int main() {
 
  FILE *fin, *fout;
 
  int n, m, s, i, u, p, max;
 
 
  fin = fopen( "arme.in", "r" );
 
  fscanf( fin, "%d%d", &n, &m );
 
  for ( i = 0; i < n + m; i++ )
 
    fscanf( fin, "%d", &v[i] );
 
  fclose( fin );
 
 
  // sortare elemente: avem vectorul v de m + n elemente
 
  for ( u = m + n - 1; u > 0; u-- ) { // pozitia ultimului element din subvector
 
    max = v[0];
 
    p = 0;                        // p este poziția maximului
 
    for ( i = 1; i <= u; i++ )
 
      if ( v[i] > max ) {        // memoram noul maxim si pozitia lui
 
        max = v[i];
 
        p = i;
 
      }
 
    // interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia u
 
    v[p] = v[u];
 
    v[u] = max;
 
  }
 
 
  // calcul suma
 
  s = 0;
 
  for ( i = m + n - 1; i >= m; i-- )
 
    s += v[i];
 
 
  fout = fopen( "arme.out", "w" );
 
  fprintf( fout, "%d\n", s );
 
  fclose( fout );
 
 
  return 0;
 
}</syntaxhighlight>
 
 
 
= Lecţie =
 
= Lecţie =
 
Nu există video. Lecția este doar teoretică și disponibilă online.
 
Nu există video. Lecția este doar teoretică și disponibilă online.

Latest revision as of 17:06, 9 February 2021

Lecţie

Nu există video. Lecția este doar teoretică și disponibilă online.

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.

Exemplu: să se ordoneze n numere cu valori între 0 și 100.

Input Output
8

3 2 9 6 3 2 9 6

2 2 3 3 6 6 9 9

Rezolvare: vom folosi sortarea bazată pe vector de frecvență (counting sort). Construim vectorul de frecvență al numerelor de la intrare, apoi îl parcurgem afișînd pozițiile cu valori nenule de cîte ori arată acea valoare. Ca noutate vom folosi o constantă pentru valoarea maximă a unui element, adică 100. Iată programul:

// ordonare crescatoare a n numere cu valori intre 0 si 100
#include <stdio.h>

#define VAL_MAX 100

int v[VAL_MAX + 1];

int main() {
  int n, i, j;

  scanf( "%d", &n );
  for ( i = 0; i < n; i++ ) {
    scanf( "%d", &j );
    v[j]++;
  }

  for ( i = 0; i <= VAL_MAX; i++ )
    for ( j = 0; j < v[i]; j++ )
      printf( "%d ", i );
  printf( "\n" );

  return 0;
}

Avantajul folosirii constantei VAL_MAX este că, dacă ulterior enunțul problemei se schimbă, valoarea maximă devenind 200 sau alt număr, vom modifica doar VAL_MAX, într-un singur loc în program.

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.

Input Output
+ 12 191 203
* 12 11 132
% 20 8 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;
}

Temă

Tema 35: să se rezolve următoarele probleme (program C trimis la vianuarena):

Rezolvări aici [1]