Clasa a V-a lecția 30 - 8 mar 2018

From Algopedia
Jump to navigationJump to search

Comentarii rezultate faza pe sector

  1. Felicitări tuturor! Ați ajuns pînă aici cu foarte multă muncă.
  2. Felicitări celor ce au luat 100p la prima problemă, șir, o problemă ce necesita atenție și concentrare: Armin Asgari și Alex Nicu!
  3. Felicitări negative celor ce nu au luat 100p la a doua problemă, cifre. Era o problemă ușoară, de lecția 10. Poate nu v-ați dat suficiente teste?
  4. Cei ce nu ați dat surse la prima problemă, șir: ar fi fost bine să dați o sursă care afișa un număr, la inspirație. De exemplu 2 (primul număr prim), sau 1 (primul număr prim minu unu), sau poate suma primelor două numere prime minus 1 (adică 4). 10p puncte cîștigate la concurs vă puteau avansa 10-15 locuri în clasament!
  5. Pentru cei ce ați luat 100p la a doua problemă, cifre, și care ați lucrat la prima problemă, șir, dar ați luat 0p sau 10p: nu vă demoralizați! Este o problemă grea, la care este mai greu să iei punctaje parțiale. Uitați-vă la rezultate și veți vedea că avem doar patru scoruri nenule: 10p, 80p și 90p. O mică corectură în programul vostru putea să vă transforme sursa în una de 90p. La municipiu puteți foarte bine să luați 190p.
  6. Nu uitați, important: la IQ Academy nu facem pregătire pentru olimpiadă, ci ne formăm ca informaticieni. Aceasta înseamnă că nu facem dopaj și învățăm să codăm corect. Obiceiurile proaste cu care veniți de la pregătitorii de olimpici nu se acceptă. Printre acestea se numără folosirea lui break, a stegulețelor inutile, a freopen, vectori declarați cu cîteva elemente în plus în caz că vine drăcușorul indicilor și ne încurcă, for pe post de while și invers, if-uri exclusive între ele care nu se înlănțuie unul pe else-ul celuilalt.

Comentarii tema 29

  1. Felicitări pentru comentarii (cei care mă ajută comentînd programele): Nicola, Petcu
  2. Topul pescarilor la speciale: Aizic 14 surse, Togan 8 surse, Dumitrescu 7 surse, Ipate 7 surse, Iordache 6 surse, Tatomir 6 surse, Badea 5 surse, Nicu 5 surse
  3. Speciale: v-a cam dat gata! mulți nu ați luat 100p.
  4. Speciale: mulți dintre voi nu au folosit vectori preinițializați, sau i-au folosit parțial, acolo unde era cel mai puțin nevoie de ei. Nu e de mirare că v-a dat gata problema. Acesta era scopul problemei, să exersăm vectori preinițializați, nu doar să luăm 100p.

Tema - rezolvări

Rezolvări aici [1]

Lecţie

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-03-08-lectie-info-30-720p.mp4</html5media>

Problemele de la olimpiada pe sector

Dragilor, cred că sînteți de acord cu mine că problemele de anul acesta au fost drăguțe și abordabile, nici prea grele, nici prea ușoare. Nu cred că puteați primi probleme mai bune de olimpiada pe sector.

Să le discutăm.

Problema șir6

Problema șir6 a fost dată la faza pe sector 2018, clasa a 5a. O voi introduce pe varena.ro imediat ce obțin testele. Ea este o problemă standard ce se poate rezolva conform manualului de informatică (unul care predă informatică, nu Scratch :-). Ea conține doar elemente învățate, pe care voi trebuie să le combinați pentru a calcula rezultatul. Algoritmul este clar, fiind aproape explicat de enunț.

Pentru rezolvare vom citi cifrele de la intrare, păstrînd mereu penultima cifră, pentru testul de paritate. La fiecare citire de cifră va trebui să calculăm și următorul număr prim. Pentru aceasta vom porni de la numărul prim anterior, să-i spunem prim, și vom parcurge toate numerele prim+1, prim+2, prim+3, ..., testînd primalitatea lor. Ne vom opri atunci cînd găsim primul număr prim, pe care îl vom aduna la suma cerută. Dacă ultimele două cifre din secvență au parități diferite va trebui să scădem unu din sumă.

Unde trebuie să avem grijă?

Testul de găsire număr prim

Algoritmul va avea două bucle. Cea interioară testează dacă un număr este prim. Cea exterioară va executa bucla interioară în mod repetat, pînă ce va găsi un număr prim. Pentru testul buclei exterioare veți fi tentați să folosiți stegulețe și veți scrie cod încîlcit. Pentru a nu ajunge acolo, gîndim astfel:

  • Scriem mai întîi bucla interioară, care testează dacă un număr este prim. Ea este, sper banală și bine cunoscută:
      d = 2;
      while ( d * d <= prim && prim % d > 0 )
        d++;
  • Apoi scriem bucla interioară, fără să ne preocupăm de condiția ei de oprire:
    while ( <condiție necunoscută de oprire> ) {
      prim++; // numarul anterior nu este prim, deci avansam                    
      d = 2;
      while ( d * d <= prim && prim % d > 0 )
        d++;
    }
  • Acum:
    • Care este condiția să ieșim din while? Răspuns: să găsim un număr prim.
    • Care este condiția ce ne spune că am găsit un număr prim? Răspuns: clasică, if ( d * d > prim )
    • În concluzie, deoarece condiția din while este cea de a nu fi găsit un număr prim, va trebui să o punem pe dos: while ( d * d <= prim )

Rezultă codul: 

    while ( d * d <= prim ) {
      prim++; // numarul anterior nu este prim, deci avansam                    
      d = 2;
      while ( d * d <= prim && prim % d > 0 )
        d++;
    }
  • Ce mai rămîne de rezolvat? Pornirea: cu ce trebuie să inițializăm prim și d pentru a ne asigura că intrăm cu bine în buclă. Să vedem:
    • Ce semnificație exactă are prim? El este ultimul număr prim "folosit". La intrarea în buclă vom avea grijă să îl incrementăm. Deoarece primul număr prim este 2, el fiind și primul ce se va aduna la sumă, trebuie să pornim cu prim cu unu mai puțin, adică 1. Acest lucru se va întîmpla chiar la începutul algoritmului.
    • Dar d? Unde și cu cît îl inițializăm? Observăm că imediat ce intrăm în prima buclă d va fi setat la 2. Deci nu contează ce valoare va avea înainte de intrarea în buclă, cîtă vreme condiția din while este adevărată. Deoarece cea mai mică valoare a lui prim este 1, hai să-i dăm lui d valoarea 1.

Rezultă codul: 

    // cautam urmatorul numar prim, pentru a il insuma                          
    d = 1;    // valore introdusa astfel incit sa intram in bucla               
    while ( d * d <= prim ) {
      prim++; // numarul anterior nu este prim, deci avansam                    
      d = 2;
      while ( d * d <= prim && prim % d > 0 )
        d++;
    }

Citirea cifrelor

Enunțul problemei nu vă spune cîte cifre aveți la intrare, doar că avem minim două cifre, maxim 3000. Deci, pentru a citi aceste cifre, va trebui să le citim caracter cu caracter, pînă la '\n'. Unii din voi încă au probleme cu astfel de citiri. Să lămurim puțin lucrurile:

  • Șirul de la intrare e de forma: cf1 cf2 cf3 ...cfn\n
  • Remarcați că putem descompune elegant șirul în perechi de forma (cf, ch), unde cf este o cifră, iar ch este fie caracterul spațiu, fie caracterul \n. El va fi \n o singură dată, la final.
  • De aceea vom avea grijă ca la fiecare iterație a buclei să citim perechi de caractere, cifră și imediat după aceea caracterul următor. Ne oprim cînd acel caracter următor este '\n'.
  • O ultimă precauție: trebuie să memorăm valoarea penultimei cifre, pentru calculul parității perechilor de cifre.

Testul de paritate al perechilor de cifre

Sînt convins că vă veți descurca să scădeți unu din sumă în cazul cînd paritățile cifrelor sînt diferite, folosind trei instrucțiuni if. Hai să vedem cum facem fără nici un if. Pentru aceasta să facem tabelul celor patru cazuri posibile, pentru a vedea cînd scădem unu. În acest tabel vom calcula și paritatea sumei cifrelor.

Penultima cifră Ultima cifră Suma Scădem unu?
pară pară pară NU
pară impară impară DA
impară pară impară DA
impară impară pară NU

Ce observăm, imediat? Că vom scădea unu numai atunci cînd suma ultimelor două cifre este impară. Drept care putem rezolva adunarea numărului prim la sumă elegant, într-o singură linie, astfel: 

suma = suma + prim - (ucf + cf) % 2;

Iată un program foarte scurt care ține cont de cele discutate mai sus: 

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int suma, prim, ucf, cf, d;
  char ch;

  fin = fopen( "sir6.in", "r" );
  suma = 0; // suma de afisat la final, initial zero                            
  prim = 1; // pornim cu numarul din-naintea primului numar prim                
  ucf = fgetc( fin ) - '0';  // citim prima cifra la intrare                    
  ch = fgetc( fin );         // citim spatiul de dupa                           
  while ( ch != '\n' ) {     // mai avem cifre?                                 
    cf = fgetc( fin ) - '0'; // citim inca o cifra                              
    ch = fgetc( fin );       // si caracterul de dupa ea                        

    // cautam urmatorul numar prim, pentru a il insuma                          
    d = 1;    // valore introdusa astfel incit sa intram in bucla               
    while ( d * d <= prim ) {
      prim++; // numarul anterior nu este prim, deci avansam                    
      d = 2;
      while ( d * d <= prim && prim % d > 0 )
        d++;
    }

    // la iesirea din while stim ca prim este urmatorul numar prim              
    suma = suma + prim - (ucf + cf) % 2; // il adunam la suma conform paritatii
    ucf = cf; // pastram ultima cifra                                           
  }
  fclose( fin );

  fout = fopen( "sir6.out", "w" );
  fprintf( fout, "%d\n", suma );
  fclose( fout );

  return 0;
}

Problema cifre9

Problema cifre9 a fost dată la faza pe sector 2018, clasa a 5a. O voi introduce pe varena.ro imediat ce obțin testele. Ca și problema șir6, ea este o problemă standard, de manual, ea conținînd doar elemente învățate, simple, de lucrul cu cifre.

Există mai multe moduri de a aborda această problemă. Un mod este să extragem pe rînd cifrele lui N, de la coadă, numărînd aparițiile lui k și formînd în același timp numărul de afișat. Dacă cifra extrasă este diferită de k o vom adăuga la numărul nou format, dacă este k o vom număra și o vom adăuga la un număr ce va conține toate cifrele k.

Iată o variantă de program: 

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, k, nrk, kkk, nmod, p10, cf;

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

  nrk = 0;  // de cite ori apare cifra k in n                                   
  kkk = 0;  // numarul format din nrk cifre k                                   
  nmod = 0; // n modificat astfel incit toate cifrele k sa fie la inceput       
  p10 = 1;  // puterea lui 10 cu care vom adauga cifrele in nmod                
  while ( n > 0 ) {
    cf = n % 10; // ultima cifra a lui n                                        
    n /= 10;     // eliminam ultima cifra din n                                 
    if ( cf == k ) {      // n avea pe ultima pozitie cifra k?                  
      nrk++;              // adunam unu la numarul de cifre k din n             
      kkk = kkk * 10 + k; // adaugam cifra la kkk                               
    } else { // daca cifra este diferita de k                                   
      nmod = nmod + p10 * cf; // o adaugam la n modificat                       
      p10 *= 10;              // pregatim urmatoarea putere a lui 10            
    }
  }
  nmod += p10 * kkk; // adaugam kkk in fata numarului modificat                 

  fout = fopen( "cifre9.out", "w" );
  fprintf( fout, "%d\n%d\n", nrk, nmod ); // afisam numerele cerute             
  fclose( fout );

  return 0;
}

Manipularea orelor și minutelor pe ceas

Deși orele și minutele sînt doar numere, anumite exerciții pot pune probleme.

Problemă: se dau doi timpi, t1 și t2, specificați ca ore și minute. Astfel, vom avea la intrare o1, m1 și o2, m2. Cîte ore și minute se află între acești doi timpi? Atenție! Dacă t2 este înaintea lui t1 se consideră că am trecut într-o nouă zi. Exemplu: dacă t1 este 10:35 și t2 este 18:20 atunci vom afișa 07:45. Dacă t1 este 22:25 și t2 este 20:05 vom afișa 21:40.

La prima vedere acest exercițiu pare încîlcit. Va trebui să comparăm cei doi timpi. Dacă t1 este înaintea lui t2 atunci va trebui să comparăm cîte ore avem între o1 și o2. Dar și aceasta va depinde de relația dintre m1 și m2. Dacă t1 este după t2 lucrurile se complică și mai mult: trebuie să aflăm cîte ore și minute avem pîna la finalul zilei, apoi să aflăm cîte ore și minute avem de la începutul zilei pînă la t2, iar în final trebuie să le adunăm. Multe cazuri particulare. Cum facem să simplificăm lucrurile?

Regulă: pentru a nu ne încurca, întotdeauna vom face conversia orelor la cea mai mică unitate de măsură, fie ea minut sau secundă. În final vom face conversia inversă, de la minute, la ore și minute.

În cazul problemei noastre, vom converti t1 și t2 la minute. Algoritmul este următorul: 

1. calculează t1 = o1 * 60 + m1
2. calculează t2 = o2 * 60 + m2
3. calculează d = t2 - t1
4. dacă d < 0 atunci
     4.1 calculează d = 24 * 60 - d
5. calculează o3 și t3 pe baza lui d, astfel:
     5.1 o3 = d / 60
     5.2 m3 = d % 60
6. afișează o3 și m3

Concluzie: în problemele în care avem nevoie să lucrăm cu ore, minute și secunde, este foarte important să transformăm timpul într-un singur număr exprimat în cea mai mică unitate de timp implicată. În exemplul de mai sus această unitate este minutul. Uneori s-ar putea să fie secunda. După transformare vom face calculele cerute de problemă. În final vom transforma înapoi în ore, minute, posibil secunde, dacă problema necesită acest lucru.

Temă

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

  • chibrituri dată la OJI 2013 clasa a 5a
  • ore dată la concursul .campion 2011
  • consiliu dată la OMI Iași 2012

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_V-a_lecția_30_-_8_mar_2018&oldid=18062"