Алчен, greedy алгоритъм - задача за плащане с най-малък брой монети

Съществуват няколко названия един особен подклас алгоритми на евристичните: жадни, алчни от англ. greedy.

Характерни особености на алчен алгоритъм:
а) за всеки конкретен етап от решението на задачата се взема най-доброто за момента решение като се "надява", че по този начин ще се стигне до глобалния максимум, т.е. реално намира локалния екстремум;
б) не дава възможност за преразглеждане на вече взети решения - главното му отличие от динамичното оптимиране, където решението се взима на базата на всички възможни решения взети до момента;
в) един алчен алгоритъм извежда отговор много близък до оптималния и в повечето случаи е доста ефективен;
г) в общия случай всеки алчен алгоритъм е по-лесен за реализация (за разлика от динамично оптимиране).

Нека разгледаме следната задача илюстрираща работата на алчен алгоритъм:
В България стотинките са с номинална стойност 1, 2, 5, 10, 20 и 50
Да се състави програма, която по въведена сума [10..999] извежда, чрез функция, възможно най-малък брой монети/стотинки, с които може да се плати.
Входни данни: естествено число от интервала [10 .. 999].
Пример: 88 Изход:
50 стотинки - 1 бр.
20 стотинки - 1 бр.
10 стотинки - 1 бр.
5 стотинки - 1 бр.
2 стотинки - 1 бр.
1 стотинкa - 1 бр.
В този случай описваният алчен алгоритъм ще се стреми да ползва най-малък брой монети. Крайният резултат е стремеж за плащане с монети имащи възможно най-голяма номинална стойност.

Следващата примерна програма дава решена задача за алчен, greedy алгоритъм:
#include<iostream>
using namespace std;

void stotinki (int suma)//predawane po parametyr
   {const int br=6;//6 wid moneti, ako ne smqtame monetata ot 1 lew
   int i,j,moneti [br]={50,20,10,5,2,1};//za da se plasha s naj-malyk broj
//  tyrsqt se moneti s naj-golqm nominal za poluchawane na naj-malyk broj moneti 
   j=suma;
   for (i=0;i<br;i++)//obhovda wsichki stajnosti zapochwajki ot naj-wisokata
    {if (j>= moneti [i])//ako ostawa]ata suma e => ot nominala
  {cout<<"Broj moneti po "<<moneti [i]<<" st. = "<<j/ moneti [i]<<endl;
   j=j % moneti [i];}//if ostawashata suma e celochislen ostayk ot nominala
  }//for
}//  alchen, greedy 

int main() 
 { int sum; //deklarirane na promenliwata
   cout<<"W Bylgariq vyltite stotinki sa s nominal 1, 2, 5, 10, 20 i 50. \n";
   cout<<"Da se systawi programa, koqto chrez funkciq po wywedena suma\n";
   cout<<"izwevda wyzmovno naj-malkiq broj moneti, s koito move da se plati.\n";
   cout<<"Whodni danni: estestweno chislo ot interwala [10-999].\n";
   cout<<"Primer pri suma 88 se izevdat wsichki moneti po 1 broj.\n";
   cout<<endl;//prazen red
   cout<<"Wywedete chislo: "; cin>>sum;
   stotinki (sum);//funkciqta ne wrusha stojnost
system("pause");
return 0;
}//kraj na programa alchen, greedy 

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: