Informatyka. Konkursy i algorytmy
Algorytm zachłanny
Doczego służy?
Algorytm zachłanny służy do rozwiązywania problemów, w których jeśli będziemy brać najlepszą (jak szukamy największej to największą a jak najmniejszej to najmniejszą) to otrzymamy prawidłowy wynik. Poniżej omówię prosty przykładowy algorytm zachłanny.
Algorytm
Mamy obliczyć największą liczbę o długości dokładnie m i sumie cyfr dokładnie s. jeżeli
takiej liczby nie ma, to trzeba zwrócić -1. Liczba nie może mieć zer wiodących.
Kiedy liczba jest największa? Kiedy na początku ma największe możliwe cyfry. Algorytm dla
tego problemu przedstawia się zastępująco:
m razy dodajemy na koniec naszej liczby największą liczbę, jaką możemy jeszcze dołożyć.
Czyli tak naprawdę dodajemy 9 dopóki się mieści, potem tę liczbę co została do sumy i na
koniec dokładamy tyle zer ile trzeba, żeby liczba była długości m. Jeżeli już wykorzystamy
wszystkie miejsca na cyfry, a suma co nam pozostała do dostawienia jest większa od zera, to
znaczy że nie da się stworzyć liczby o długości m i sumie cyfr s. UWAGA na początku trzeba
jeszcze dołożyć warunek:
Jeśli m > 1 i s == 0, to zwróć -1
Czemu? Liczba nie może się składać tylko z kilku zer,
bo nie może mieć zer wiodących, a taką liczbę musiałby zwrócić nasz algorytm.
Przykład
Zasymulujmy nasz algorytm dla przykładowych danych: m = 2 s = 15; wynik oznaczmy jako maxi
1. maxi = 9, s = 15 - 9 = 6
2. maxi = 96, s = 0
Tu kończymy nasz algorytm(powinniśmy dołożyć tylko 2 cyfry). Wynikiem będzie 96.
Implementacja i złożoność
implementacja w c++:int cyfra;
string maxi;
if(m == 1 && s == 0){
return "0";
}
if(m * 9 < s || s==0 ){
return "-1";
}
cyfra = 9;
int s1 = s;
for(int i = 1; i <=m ; i++){
if(s1 < 9){
maxi += char(s1 + 48);
s1 = 9;
cyfra = 0;
continue;
}
maxi += char(cyfra + 48);
s1 -= cyfra;
}
return maxi;
}
implementacja w python:
maxi = ""
cyfra = 9
if(m == 1 and s == 0):
return "0"
if(m * 9 < s or s==0 ):
return "-1"
for i in range(m - 1):
if(s < 9):
maxi += chr(s + 48)
s = 9
cyfra = 0
else:
maxi += chr(cyfra + 48)
s -= cyfra
return maxi
złożoność: