|
1. Algoritmlerdi proektlestiriwge kirisiw
|
| bet | 5/11 | | Sana | 09.06.2024 | | Hajmi | 1,23 Mb. | | #261899 |
Bog'liq Algoritmlerdi proektlestiriw JB sorawlarx=24; y=64.
1 -shi qádem z=y-x=40 x=24; y=40
2 -shi qádem z=y-x=16 x=16; y=24
3 -shi qádem z=y-x=8 x=8; y=16
4-shi qádem z=y-x=8 bul jerde z=x=8 EUUB boladı. Sanlar dızbegin ósiw tártibinde tártiplew máselesin kórip shıǵamız. Bul máseleni sheshiw usıllarınan biri qońsılas elementlerdi ósiw tártibinde áste aqırın orın almastırılıwı. Bul algoritmdı blok -sxemasın keltiremiz. Bizge n dana elementten ibarat a1, a2,…,an sanlar massivi berilgen bolsın. Olardı ósiw tártibinde jaylastırıwımız kerek. Eger dáslepki jaǵdaydı saqlap qalıw zárúriyatı bolsa, ol jaǵdayda biz bi=ai bolǵan jumısshı massivi b1, b2,…,bn di qáliplestiriwimiz múmkin.
A lgoritmınıń blok - sxemasın dúzemiz:
1 0. 1-Súwret
awa
yaq
C= ; ; =c
50. Kommivoyajer haqqında másele.
Másele qoyılıwı. Djek -kompyuterler satıw boyınsha agent (kommivoyajer), onıń qarawında 20 tashahar bar. islep atirǵan kompaniya jol ǵárejetleriniń 50% ni tóliydi. Djek onıń qarawdaǵı janhar eki qala arasında jol ǵárejetin esaplab shıqqan. Másele jol ǵárejetlerin kemeytiwden ibarat. Dáslepki maǵlıwmatlar Djek ıqtıyarındaǵı qalalar ruyhati hám bahalar matrisasi kórinisinde berilgen. Bul jerde matrisa i qaladan j qalaǵa barıw bahasına teń bolǵan c (i, j) elementlerden shólkemleskenikki ólshemli massiv. Qalalar sanı 20 ta bolsa, matrisa -20 x20 boladı. Biz Djekga jol ǵárejetlerin kemeytiwge járdem beriwimiz kerek. Djekning marshruti óziyashagan qaladan baslanıp, qalǵan hámme qalalardı bir retten ótip, taǵı óz qalasına qaytıpkelishi kerek. Sonday eken, biz dúzip atırǵan ruyhatda hár bir qala tek bir ret dús keliwi kerek, Lekin Djekyashagan qala eki ret ushırasıp, ruyhatning birinshi hám aqırǵı elementleri boladı. Odan tısqarı, ruyhatdagi qalalar tártibi Djekning marshrutini belgileydi. Ruyhatdagi eki aqırǵı qalalar arasındaǵıyo'l bahası -bul pútkil marshrut bahası dep esaplanadı. Sonday eken, eger biz Djekga eń kishi bahadagiruyhatni tuzib bersak, máseleni sheshken bólemiz.
51. Xanoy minaraları máselesi
Rekursiya menen nátiyjeli sheshiletuǵın «Xanoy minarı» máselesin kóreylik.
Másele. Ush A, B, C qazıq hám n-ta hár túrlı o4 chamli sheńberler bar. Sheńberlami ólshemleri ósiw tártibinde 1 den n ge shekem tártiplengen. Boshda barlıq sheńberler A qazıqqa 5. 3 a -suwretdegi sıyaqlı jaylastırılǵan. A qazıqtaǵı barlıq sheńberlami B qazıqqa, járdemshi S qazıqtan paydalanǵan halda, tómendegi qaǵıydalarǵa ámel ete otırıp ótkeriw talap etiledi: sheńberlami birden kóshiriw kerek hám úlken ólshemli sheńberdi kishi olchamli sheńber ústine qoyıw múmkin emes.
Ámeller izbe-izligin baspadan shıǵaratuǵın («Sheńber q den r ga ótkerilsin» kórinisinde, bunda q hám r - 5. 3-suwretdegi A, v yamasa S sheńberler). Berilgen n ta sheńber ushın másele sheshilsin. Kórsetpe: sheńberlami A den B ga tuwrı o4 kazishda 5. 3 b-su'wretler degi jaǵday júzege keledi, yaǵnıy n sheńberdi A den B o4 kazish máselesi n-1 sheńberdi A den S ga o4 kazish, hám de bir sheńberdi A den B o4 kazish máselesine keledi. Odan keyin S qazıqtaǵı n-1 sheńberli A qazıq járdeminde B qazıqqa ótkeriw máselesi júzege keledi hám hakoza.
#include
void Hanoy(int n,char a='A',char b='B',char c='C')
{
if (n)
{ Hanoy(n-l,a,s,b) ;
cout<<"Xalqa " < < a « " dan " < < b « " ga o'tkazilsin\n";
Hanoy(n-l,c,b,a);
}
}
int m a i n ()
{unsigned int Xalqalar_Soni;
cout<<"Hanoy minorasi masalasi"<<<"Xalqalar sonini kiriting: ";
cin>>Xalqalar_Soni;
Hanoy(Xalqalar_Soni);
return 0;
}
Sheńberler sanı 3 bolǵanda (Sheńberlar_Sanı=3) programma ekranǵa sheńberlami kóshiriw boyınsha ámeller izbe-izligin baspadan shıǵaradı :
Sheńber A den B ga ótkerilsin
Sheńber A den C ga ótkerilsin
Sheńber B den C ga ótkerilsin
Sheńber A den B ga ótkerilsin
Sheńber C den A ga ótkerilsin
Sheńber C den B ga ótkerilsin
Sheńber A den B ga ótkerilsin
Rekursiya shıraylı, ıqsham kóringeni menen yadtı tejew hám esaplaw waqtın kemeytiw kóz qarasınan onı múmkinshiligi barınsha iterativ esaplaw menen almastırilgani maqul. Mısalı, x haqıyqıy sanınıń ndarajasini esaplawdıń tómendegi sheshim variantı salıstırǵanda kem resurs talap etedi (n- pútkil belgisiz san):
double Butun_Daraja(double x, int n)
{
double p = l ;
for(int i=l; i<=n; i++)p*=x;
return p ;
}
Ekinshi tárepden, sonday máseleler bar, ulami sheshiwde rekursiyajuda nátiyjeli, hátte birden-bir usıl bolıp tabıladı. Atap aytqanda, grammatik analiz máseleIarida rekursiyajuda da ońaylıq esaplandı.
52. Kruskal algoritmi.
Kruskal algoritmi yo'naltirilmagan shetleri salmaqlıqtaǵı grafning minimal orman daǵı ormanın tabadı Eger grafik baylanısqan bolsa, ol minimal terekti tabadı Bul ashkóz algoritm bolıp, hár bir basqıshda ormanǵa eń kem salmaqlıqtaǵı chetni qosadı, bul bolsa cikl payda etmeydi. Algoritmdiń tiykarǵı qádemleri - tártiplew hám cikllerdi anıqlaw ushın disjoint-set maǵlıwmatlar strukturasınan paydalanıw Onıń jumıs waqtı olardıń salmaǵı boyınsha barlıq graf shetlerin saralaw ushın waqıt tárepinen basqarıladı Baylanısqan vaznli grafning minimal úzilis tereki - bul cikllersiz baylanısqan subgraf bolıp, onıń subgrafdagi barlıq qırlar salmaqlarınıń jıyındısı minimal boladı Bir-birine baylanıspaǵan grafik ushın minimal oralǵan orman hár bir baylanısqan komponent ushın minimal oralǵan terekten ibarat Bul algoritm birinshi ret Jozef Kruskal tárepinen 1956 jılda baspa etilgen hám tez arada Loberman & Weinberger tárepinen qayta jańalıq ashılǵan (1957). Bul mashqala ushın basqa algoritmlerge Prim algoritmi, Barovka algoritmi hám teris óshiriw algoritmi kiredi.
Algoritm tómendegi qádemlerdi ámelge asıradı :
Ormandı (terekler kompleksin ) jaratıw, daslep kirisiw grafikındaǵı hár bir múyesh ushın bólek bir múyeshtegi terekten ibarat
Grafik shetlerin salmaǵı boyınsha saralaw
Grafikdıń shetleri boylap, olardıń salmaǵı boyınsha kóteriletuǵın tártipte aylantırıń Hár bir qirg ' aq ushın: qirg ' oqni házirgi o ' rmonga qosıw cikl jaratadimi yamasa joq ekenligin tekseriń Eger joq bolsa, eki terekti bir terekke birlestirib, ormanǵa shegara áskerg Algoritmdiń aqırında orman grafikdıń minimal ormanın payda etedi Eger graf baylanısqan bolsa, orman bir strukturalıq bólekke iye hám minimal terekti payda etedi.
Tómendegi kod disjoint-set maǵlıwmatlar dúzilisi menen ámelge asıriladı Bul F ormanın yo'naltirilmagan qırlar kompleksi retinde ańlatadı hám disjoint-set maǵlıwmatlar strukturasınan paydalanıp, eki shıń birdey terektiń bir bólegi ekenligin nátiyjeli anıqlaydı.
|
| |
