Enunțul problemei adunscad, de clasa a 8-a, dată în 2011 la OJI, se găsește pe PbInfo și .campion.

Rezumat adunscad

Se dă un număr întreg n și un șir de m cifre zecimale nenule. Trebuie să afișăm, dacă e posibil, o expresie aritmetică ce are valoarea n, și este formată doar din cifrele date drept termeni, precum și semne + și -. În cazul în care primul semn este +, acesta nu trebuie afișat. Dacă nu există o astfel de configurație, se afișează valoarea 0.

Soluție adunscad

Această problemă se poate rezolva foarte ușor cu backtracking, folosind o funcție recursivă pentru generarea tuturor configurațiilor. Pe vremea când am rezolvat-o eu, nu știam de backtracking, așa că am folosit o metodă ce se bazează pe numere mari. Este mai greu de implementat, și nu-i neapărat mai eficientă, dar este bună pentru cei din clasele mai mici, care nu știu recursivitate.

Am folosit un vector bin, de lungime m, ce reprezintă un număr mare scris în baza 2. Cifra de pe poziția i simbolizează semnul dinaintea celei de-a i-a cifră din șir. Am generat toate configurațiile pentru care primul semn este 0, iterând într-un for de la 0 la 2m - 1. La fiecare pas, am evaluat expresia atât considerând că 0 înseamnă minus și 1 plus (în s1), cât și în cazul opus (în s2). Astfel, am generat de două ori mai puține configurații. Dacă am obținut suma căutată, n, afișez expresia aritmetică, cu grijă la primul semn, și ies din main.

Adunarea în baza 2 pe numere mari se face exact cea obișnuită, în baza 10, doar că înlocuim % 10 cu % 2 și / 10 cu / 2. Ideea prezentată poate fi rafinată folosind operații pe biți: În loc să folosim un număr mare, putem să folosim un int, biții săi reprezentând semnele.

Sursă C++ adunscad

Dacă ai vreo nedumerire cu privire la problema adunscad, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!