Clasa a V-a lecția 18 - 22 ian 2013

Lecție

Atașamente în temă

Atunci cînd îmi trimiteți tema pe email vă rog să procedați în felul următor: trimiteți fișierul .c pe email, atașat ca atașament la mesaj. Nu-mi trimiteți copy/paste de pe vianuarena (conține numere de linie), și nu-mi trimiteți copy/paste direct în mesaj. În felul acesta voi putea să compilez și să testez programele voastre.

Indentare

Foarte mulți dintre voi nu își indentează programele C, sau le indentează greșit. Indentarea este foarte importantă, pentru a face codul citibil atît pentru voi, în timpul olimpiadei, sau peste cîteva luni cînd vă veți uita la el, cît și pentru alți oameni, inclusiv pentru mine. Dacă vreți să vă corectez programele C trebuie să le indentați corect. Iată mai jos exemple de indentare corectă, la două spații. Remarcați că acolada deschisă stă pe același rînd cu instrucțiunea de care aparține, în vreme ce acolada închisă este pe un rînd nou, singură, exact la nivelul instrucțiunii de care aparține și pe care o închide. Vă rog foarte mult să respectați aceste reguli, nu este opțional, este obligatoriu.

Primalitate

Cum testăm dacă un număr este prim? Iată mai multe variante, scrise de unii dintre voi.

Varianta 1

prim = 0;
for ( i = 2; i < n / 2; i++) {
  if ( n % i == 0) {
    i = n / 2;
    prim = 1;
  }
}
if ( prim == 0 )
  // ... este prim

Această variantă funcționează dar are următoarele probleme:

• folosește instrucțiunea for pentru un ciclu cu număr necunoscut de pași
• modifică variabila de ciclu, i, în interiorul instrucțiunii for.
• testează divizorii pînă la n / 2.

Din aceste motive nu o preferăm.

Varianta 2

num = 0;
div = 2;
while ( div < n ) {
  if ( n % div == 0 )
    num++;
  div++;
}
if ( num == 0 )
  // ... este prim

Această variantă funcționează dar are următoarele probleme:

• testează divizorii pînă la n.
• nu se oprește atunci cînd a găsit un divizor.

Din aceste motive nu o preferăm.

Varianta 3

prim = 0;
div = 2;
while ( div <= sqrt(a) && prim == 0 ) {
  if ( a % divizor == 0 )
    prim=1;
  div++;
}
if ( prim == 0 )
  // ... este prim

Această variantă funcționează și este cea mai bună de pînă acum, dar are și ea următoarele probleme:

• cheamă funcția sqrt pentru fiecare execuție a corpului buclei while.
• folosește un steguleț, cînd se poate și fără el.

Din aceste motive nu o preferăm.

Varianta optimă

Iată cea mai simplă variantă, care nu folosește stegulețe inutile, testează divizorii pînă la radical din n și se oprește la primul divizor găsit:

div = 2;
while ( div * div <= n && n % div > 0 )
  div++;
if ( div * div > n )
  // ... numarul este prim

Simulare olimpiadă

Rezolvați una din următoarele probleme, păstrînd regulile de la olimpiadă, respectiv:

• Nu discutați între voi
• Nu folosiți materiale externe, nu vă uitați pe web, etc.
• Dacă ați făcut problema în trecut rezolvați-o din nou, fără a vă uita la sursa trimisă mai demult. Nu uitați că acum sînteți contra timp, deci este o diferență.
• Voi considera că punctajul luat la o problemă este punctajul primei trimiteri la campion sau vianuarena.
• Aveți o problemă într-o oră jumate. Recomand ca după expirarea timpului să trimiteți sursa așa cum este ea la momentul respectiv, pentru a afla scorul la olimpiadă.

Mă bazez pe codul onoarei, adică pe faptul că veți respecta regulile. Alegeți una din următoarele probleme de rezolvat:

• problema numere1 la vianuarena (problemă ceva mai grea, dată la concursul Urmaşii lui Moisil - V-VIII 2012)
• problema cifre1 la vianuarena (problemă ceva mai ușoară, dată la OJI 2004 clasa a 5^a)

Tema

• terminați problemele de la test, ambele
• problema divizor la vianuarena, OJI 2009 clasa a 5^a
• opțional: problema inimioare la vianuarena, OJI 2009 clasa a 5^a

Rezolvări aici [1]