Հիմնական նյութ
Համակարգչային գիտություն
Դասընթաց․ (Համակարգչային գիտություն) > Բաժին 1
Դաս 8: Միացման տեսակավորումԱրագ տեսակավորում. ակնարկ
Քանի որ տեսակավորելու համար օգտագործում ենք «Բաժանիր և տիրիր» ալգորիթմը, պետք է որոշենք, թե ինչպիսին պետք է լինեն մեր ենթախնդիրները։ Ամբողջական խնդիրը զանգվածը տեսակավորելն է։ Արի ասենք, որ ենթախնդիրը կլինի ենթազանգված տեսակավորելը։ Ընդհանուր առմամբ՝ ենթախնդիր է ենթազանգված տեսակավորելը, որը սկսում է ցուցչից մինչև ցուցիչը։ Լավ կլինի՝ ունենանք ենթազանգվածի նշագրում, հետևաբար արի ասենք, որ տարր ունեցող զանգվածի համար կարող ենք ասել, որ սկզբնական խնդիրն է տեսակավորել
array[p..r]
-ը ցույց է տալիս, որ սա array
-ի ենթազանգվածն է։ Հաշվի առ, որ երկկետ նշագրումը լեգալ չէ JavaScript-ում․ մենք դա օգտագործում ենք, որ բառացի նկարագրենք ալգորիթմը, ոչ թե այդպես գրենք կոդի մեջ։ Իսկ ինչ վերաբերում է նշագրմանը, array[0..n-1]
-ը։Ահա, թե ինչպես է միացման տեսակավորումն օգտագործում «Բաժանիր և տիրիր» ալգորիթմը․
- Բաժանիր՝ գտնելով
թիվը -ի և -ի միջնակետում։ Այս քայլն արա այնպես, ինչպես երկուական որոնման մեջ գտանք միջնակետը․ գումարիր -ն ու -ը, բաժանիր 2-ի և կլորացրու։ - Տիրիր՝ ռեկուրսիվորեն տեսակավորելով ենթազանգվածները բաժանումից առաջացած երկու ենթախնդիրներից յուրաքանչյուրում։ Այսինքն՝ ռեկուրսիայով տեսակավորիր
array[p..q]
-ն և ռեկուրսիայով տեսակավորիրarray[q+1..r]
-ը։ - Միավորիր՝ միացնելով տեսակավորված ենթազանգվածները
array[p..r]
-ի մեջ։
Մեզ պետք է առաջնային դեպք։ Առաջնային դեպքը ենթազանգված է, որն ունի երկուսից պակաս անդամ, այսինքն, երբ , քանի որ անդամ չունեցող կամ մեկ անդամ ունեցող ենթազանգվածն արդեն տեսակավորված է։ Հետևաբար, մենք կբաժանենք-կտիրենք-կմիավորենք միայն, եթե ։
Արի դիտարկենք մի օրինակ։ Սկսենք և )։ Այս ենթազանգվածն ունի առնվազն երկու տարր, հետևաբար այն առաջնային դեպքը չէ։
array
-ով, որտեղ [14, 7, 3, 12, 9, 11, 6, 2] թվերն են, հետևաբար դրա ենթազանգվածն իրականում ամբողջական զանգված է՝ array[0.,7]
(- Բաժանելու քայլում գտնում ենք՝
։ - Տիրելու քայլում պետք է տեսակավորենք ենթազանգվածները՝
array[0.,3]
, որը [14, 7, 3, 12]-ն է ևarray[4.,7]
, որը [9, 11, 6, 2]-ն է։ Երբ հետ ենք գալիս «տիրելու» քայլից, երկու ենթազանգվածներն արդեն տեսակավորված են լինում․array[0.,3]
-ը՝ [3, 7, 12, 14] ևarray[4.,7]
-ը՝ [2, 6, 9, 11], հետևաբար ամբողջական զանգվածը [3, 7, 12, 14, 2, 6, 9, 11] է։ - Վերջում միավորում ենք տեսակավորված ենթազանգվածները՝ ստանալով [2, 3, 6, 7, 9, 11, 12, 14]։
Ինչպե՞ս տեսակավորվեց և ՝ գտնում ենք , ռեկուրսիվորեն տեսակավորում
array[0.,3]
-ը։ Նույն կերպ։ Այն ունի երկուսից ավելի տարրեր, հետևաբար այն առաջնային դեպք չէ։ Ունենալով array[0.,1]
([14, 7])-ը և array[2.,3]
([3, 12])-ը՝ ստանալով array[0.,3]
՝ [7, 14, 3, 12], և առաջին ու երկրորդ հատվածներն իրար միավորելով ստանում [3, 7, 12, 14]։Ինչպե՞ս տեսակավորվեց և ՝ գտնում ենք , ռեկուրսիվորեն տեսակավորում
array[0.,1]
-ը։ Ունենալով array[0.,0]
([14])-ը և array[1.,1]
([7])-ը՝ ստանալով array[0.,1]
՝ [14, 7], և առաջին ու երկրորդ հատվածներն իրար միավորելով ստանում [7, 14]։array[0.,0]
և array[1.,1]
ենթազանգվածներն առաջնային դեպքեր են, քանի որ յուրաքանչյուրն ունի երկուսից պակաս տարր։ Ահա թե ինչպես է ամբողջ ալգորիթմն աշխատում․Միացման տեսակավորման շատ քայլեր պարզ են։ Հեշտությամբ կարող ես ստուգել առաջնային դեպքը։ Բաժանման քայլի ժամանակ -ն գտնելը նույնպես շատ հեշտ է։ Պետք է տիրելու քայլին կատարես ռեկուրենտ կանչեր։ Միացման քայլին պետք է միացնես երկու տեսակավորված ենթազանգված, որտեղ իսկական աշխատանքն է կատարվում։
Հաջորդ մարտահրավերում կկենտրոնանաս միացման տեսակավորում ալգորիթմն օգտագործելու վրա, որպեսզի ավելի լավ հասկանաս, թե ինչպես պետք է ռեկուրսիվորեն «Բաժանել և տիրել»։ Դա անելուց հետո մենք ավելի կխորանանք երկու տեսակավորված ենթազանգված արդյունավետ կերպով միավորելու վրա, և դու այն կօգտագործես հետագա մարտահրավերի մեջ։
Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։