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