momente şi schiţe de informatică şi matematică
anti point—and—click

Rangul elementului din mijloc

int
2008 nov

În cadrul capitolului referitor la metoda divide et impera (probabil în toate manualele), indicele elementului din mijlocul unui tablou este determinat astfel:

     int i_mijloc = (i_st + i_dr) / 2;     // toţi indicii fiind de tip "int"

Este adevărat că "abscisa mijlocului unui segment este media aritmetică a absciselor capetelor". Dar numerele vizate la matematică nu sunt totuna cu numerele vizate într-un limbaj de programare; ca urmare, transcrierea mot-à-mot de la formulă matematică la program atrage de obicei rezultate greşite pentru anumite cazuri.

Dacă suma i_st + i_dr depăşeşte sizeof(int), atunci rezultatul va fi trunchiat modulo INT_MAX + 1; se poate vedea ce se obţine de exemplu sub Borland C++ 3.1 (compilator pe 16 biţi), folosind main() { int a = 15000, b = 30000; cout << (a+b); }. Această greşeală de programare apare de altfel, în diverse alte locuri în manualele noastre (de exemplu, în programele de calcul a termenilor şirului lui Fibonacci).

Dacă atragi atenţia asupra acestei greşeli, fie eşti ignorat (greşeli în manual? eşti neserios), fie provoci replici didactice sofisticate, precum "A... algoritmul contează!", sau "A... nu lucrăm noi cu tablouri mai largi de 20 de numere". Dar corectura necesară este aşa de simplă, încât n-ar fi cazul să se recurgă la savantlâcuri:

     int i_mijloc = i_st + (i_dr — i_st) / 2;

Tocmai datorită obiceiului de a folosi pentru testare şi tablouri cu mai mult de 20 de elemente, am observat de mult şi am corectat fireşte greşeala respectivă "without any fanfare" (pe atunci nu aveam Internet; iar pe de altă parte… pur şi simplu am ignorat programele redate în manuale, constatând că în general sunt făcute cam de mântuială). Desigur că ea a fost semnalată şi de alţii - în orice caz deja s-a publicat asupra ei (cu referire la Java), de exemplu în 2006: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html.

Nu-i cazul să inventăm justificări pentru faptul că manualele noastre menţin de la an la an, asemenea greşeli de programare; în fond, greşelile sunt instructive. Iar pe de altă parte (iarăşi instructiv!), nu în toate limbajele ar fi vorba de o greşeală - de exemplu, în Javascript nu există un model nativ de "întreg", ceea ce elimină din start problemele de "depăşire" specifice operaţiilor cu numere întregi.

Dar într-un manual de C (şi încă într-unul în care nu prea se foloseşte altceva decât int şi "string") greşeala menţionată ar trebui totuşi corectată.

vezi Cărţile mele (de programare)

docerpro | Prev | Next