New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Problema de programare 1 #1

Open
dserban opened this Issue Jul 21, 2018 · 0 comments

Comments

Projects
None yet
1 participant
@dserban
Owner

dserban commented Jul 21, 2018

Operanzi

Rezolvă următoarea problemă în limbajul de programare ales de tine.

Se dau:

  • un număr natural numit target
  • o secvență de numere naturale distincte. Nu este specificat dinainte câte elemente conține această mulțime.

Folosind pe de o parte numerele din mulțimea de mai sus, și pe de altă parte doar operații de adunare și înmulțire, să se construiască (fără a apela la paranteze pentru grupare) expresia aritmetică al cărei rezultat se apropie cel mai mult de target.
Fiecare număr din secvența de numere naturale distincte poate fi folosit doar o singură dată în expresia-aritmetică-rezultat.

Exemple:

$ cat test_case_1.txt
3972
87 5 47
$
$ ./program < test_case_1.txt
4089
87*47
$
$ cat test_case_2.txt
119
3 5 17 37 61 87
$
$ ./program < test_case_2.txt
119
87+17+5*3
$
$ cat test_case_3.txt
424
17 19 23 29 31
$
$ ./program < test_case_3.txt
422
31+23*17
$
$ cat test_case_4.txt
1337
23 29 31 47 53
$
$ ./program < test_case_4.txt
1326
47+31+29+23*53
$
$ cat test_case_5.txt
4291
31 47 53 67 71 79 83
$
$ ./program < test_case_5.txt
4289
71+31+53*79
$
$ cat test_case_6.txt
256952
5 7 11 17 47 67 71
$
$ ./program < test_case_6.txt
256954
5+7*11*47*71
$
$ cat test_case_7.txt
947
17 19 23 29
$
$ ./program < test_case_7.txt
942
17*23+29*19
$
$ cat test_case_8.txt
5037
8 17 19 23 29 31 53
$
$ ./program < test_case_8.txt
5034
8*23*17+53*19+31*29
$

După cum se observă, programul comunică cu exteriorul prin STDIN și STDOUT.

De asemenea, nu contează ordinea operanzilor în expresia-aritmetică-rezultat. Luând ca exemplu testul 2 de mai sus, e OK dacă în loc de 87+17+5*3 programul tău scoate 87+5*3+17 sau 3*5+87+17 sau orice altă expresie echivalentă.

Enunțul nu cere explicit o anumită complexitate, dar te rugăm să atașezi la soluția ta, sub formă de comentariu, analiza complexității.

Este permisă folosirea oricărui "clever trick" și a oricărei biblioteci third-party pentru rezolvarea problemei.

IMPORTANT: Te rugăm să postezi soluția ta pe secțiunea Gist de pe GitHub ( https://gist.github.com/ ), folosind opțiunea "Create Secret Gist". În acest mod putem exclude posibilitatea plagiatului.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment