Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (10)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)

Greedy

#816. [2016-11-20 - 18:23:58]
Colorarea hartii folosind metoda Greedy.
Fiind data o harta cu n tari, se cere o solutie de colorare a hartii, utilizand cel mult patru culori, astfel incat doua tari ce au frontiera comuna sa fie colorate diferit. Este demonstrat faptul ca sunt suficiente numai patru culori pentru ca orice harta sa poata fi colorata.
Exemplu:
colorare.in
6
alb verde galben rosu
1 2
1 3
1 4
1 5
1 6
2 3
2 5
2 6
3 4
3 5
4 5
5 6
colorare.out
1 alb
2 verde
3 galben
4 verde
5 rosu
6 galben

Rezolvare

#592. [2014-05-15 - 09:33:48]
Se citesc 3 numere naturale S, n si e cu urmatoarele semnificatii: S este o suma de bani care trebuie platita folosind bancnote care au valori puterile lui e de la 1 la e la n. Se se afiseze modalitatea de plata folosind un numar minim de bancnote de tipurile precizate. Sa se afiseze la final numarul de bancnote folosite. Datele se vor citi din fisierul eur.in, iar rezultatele se vor afisa in fisierul eur.out.
Exemplu:
eur.in
444 5 2
eur.out
13 bancnote de valoarea 32
1 bancnote de valoarea 16
1 bancnote de valoarea 8
1 bancnote de valoarea 4
16
Explicatie: n=5, e=2 rezulta ca bancotele au valorile 1, 2, 4, 8, 16 si 32.
Rezolvare


#395. [2012-11-22 - 09:34:32]
Problema comis-voiajorului (varianta 1)
Rezolvare

#394. [2012-11-22 - 08:28:07]
Fiind data o tabla de sah de dimensiunea nxn si un cal n coltul stnga sus al acesteia, se cere sa se deplaseze calul pe tabla astfel nct sa treaca o singura data prin fiecare patrat al tablei.
Solutia va fi afisata ca o matrice nxn n care sunt numerotate sariturile calului.
Exemplu, pentru n=11
1 26 85 30 23 28 99 120 21 104 101
84 31 24 27 86 119 22 103 100 121 20
25 2 83 80 29 98 107 118 115 102 105
32 81 34 87 108 79 116 97 106 19 114
3 36 69 82 75 88 109 112 117 96 93
64 33 76 35 70 111 78 95 92 113 18
37 4 63 68 77 74 89 110 57 94 91
40 65 38 71 62 67 56 73 90 17 54
5 44 41 66 49 72 61 58 55 14 11
42 39 46 7 60 51 48 9 12 53 16
45 6 43 50 47 8 59 52 15 10 13
Rezolvare

#393. [2012-11-21 - 10:07:15]
Problema rucsacului (cazul continuu)
O persoana are un rucsac cu care poate transporta o greutate maxima g. Persoana are la dispozitie n obiecte pentru care stie greutatea si castigul obtinut daca transporta obiectul.
Fiecare obiect poate fi transportat integral sau taiat.
Sa se precizeze ce obiecte alege persoana si in ce proportie le ia astfel incat castigul total sa fie maxim si sa nu se depaseasca greutatea maxima a rucsacului.
Exemplu:
g=3 n=3
obiectele(greutate,castig):
2 2
1 4
3 6
Solutie(greutate, castig, raport taiere):
1,4,1
3,6,0.6667 (al doilea obiect se ia in raport de 2/3)
castig maxim=8

Rezolvare

#392. [2012-11-21 - 08:38:04]
Problema programarii spectacolelor
Intr-o sala de spectacol trebuie planificate n spectacole intr-o zi. Pentru fiecare spectacol se cunosc ora de inceput si ora de terminare (numere intregi).
Sa se planifice un numar maxim de spectacole astfel inct sa nu fie doua spectacole care sa se suprapuna.
Exemplu:
date.in
7
2 4
8 11
5 6
5 8
3 7
7 8
9 12
date.out:
2,4 5,6 7,8 9,12
Rezolvare


19 oct 2018
Site-ul conține 867 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian