Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:ars83-ի խոսքերից
Չե ոչ մի ցրագրից չեմ օգտվել: Ալգորիթմ էլ առանձնապես չեի մտածել: Ուղղակի մի քանի բան փորձեցի, հասկացա, որ անկյունագծերով դասավորելը ամենա հարմարն է: Իսկ քայլերս արդեն գրել եմ: Բայց կուզենաի քո ալգորիթմին ծանոթանալ:
Երևի ավելի ճիշտ կլիներ ասել դատողություններ, քան ալգորիթմ...
1. Տախտակի բոլոր հնարավոր ներկումները (նշանակություն չունի, թե ներկման որ քայլին են դրանք ստացվել) բաժանենք դասերի ըստ նրանցում դեղին վանդակների քանակի՝ Y[0], Y[1], ..., Y[21], որտեղ Y[N] ներկումների այն դասն է, որոնցում կա ճիշտ i հատ դեղին վանդակ։ Պարզ է, որ N–ը չի գերազանցում 21–ը, քանի որ անկյունների վանդակները հնարավոր չէ դեղին գույնով ներկել (մի քիչ ավելի ուշադիր ուսումնասիրությունը ցույց է տալիս, որ N-ը չի կարող գերազանցել նաև 18-ը բայց դա էական չի)։
2. Սկզբում ունենք որևէ ներկում Y[0] դասից։ Պարզ է, որ Y[i] դասի որևէ ներկում ունենալիս այդ պահին մեկ վանդակ ներկելով կարող է տեղի ունենալ հետևյալ դեպքերից միայն մեկը և այլ դեպք տեղի ունենալ չի կարող.
ա. ստանանք Y[i+1] դասի ներկում (որևէ կանաչ, կարմիր, կապույտ կամ չներկված վանդակ ներկել ենք դեղինով)
բ. ստանանք Y[i-1] դասի ներկում (դեղին վանդակներից մեկը ներկել ենք կանաչ, կարմիր կամ կապույտ գույնով)
գ. ստանանք Y[i] դասի ներկում (դեղինից բացի այլ գույնով ներկել ենք որևէ վանդակ, որը ներկված չէր կամ ներկված էր ոչ դեղին գույնով)։
Մեզ համար էական է միայն ա. դեպքը։
3. Կառուցենք ծառ, որի հանգույցներից յուրաքանչյուրը պարունակում է <a[1], a[2], ..., a[N]> տեսքի բուլյան վեկտոր՝ a[i]=1, եթե i-րդ վանդակը ներկված է դեղին, a[i]=0՝ հակառակ դեպքում։ Ծառը կառուցում ենք այսպես. գագաթում տեղադրում ենք <0, 0, ..., 0> վեկտորը, որպես նրա դուստր հանգույցվեր վերցնում ենք <1, 0, ..., 0>, <0, 1, 0, ..., 0>, ...., <0, 0, ..., 0, 1> վեկտորները։ Յուրաքանչյուր A=<a[1], a[2], ..., a[N]> վեկտորը պարունակող հանգույցի դուստր հանգույցները որոշում ենք հետևյալ կերպ.
B=<b[1], b[2], ..., b[N]>–ը A–ի դուստր հանգույցն է, եթե բավարարում է հետևյալ պայմաններին.
ա. Եթե k–ն ամենամեծ թիվն է, որի համար A վեկտորում a[k]=1 (այսինքն՝ a[k+1]=a[k+2]=...=a[N]=0), ապա B–ն պարունակում է ճիշտ մեկ հատ 1 a[k+1], a[k+2], ..., a[N] դիրքերից որևէ մեկում,
բ. Առաջին k բաղադրիչները A և B վեկտորների մոտ նույնն են՝ a[1]=b[1], a[2]=b[2], ..., a[k]=b[k]։
Այսպիսով, ծառի i-րդ շերտում գտնվում են Y[i] դասի ներկումները։ Ծառը կառուցելուց հետո բավական է գտնել նրա բարձրությունը՝ այսինքն ամենամեք P թիվը, որի համար ճանապարհ կա ծառի գագաթից մինչև այդ շերտի որևէ հանգույց (այսինքն, ենթադրաբար, կա ներկումների հաջորդականություն, որը կբերի P հատ դեղին վանդակ ունեցող ներկման)։
Մնացածը ծրագրավորման գործ է. կառուցում ես ծառը և գտնում նրա բարձրությունը։ Նոր հանգույցն ավելացնելիս ստուգվում է՝ արդյոք կարելի է այն ծնող–հանգույցից ստանալ առանց խնդրի պայմանները խախտելու, այսինքն, ներկվող դեղին վանդակի շուրջը կա՞ արդյոք առնվազն 3 ոչ դեղին վանդակ։
Ծրագիրը տալիս է ծառի խորությունը 12։ Դա նշանակում է, որ կարող է գոյություն ունենալ 12 դեղին վանդակից ոչ ավել դեղին վանդակ պարունակող ներկում. քո ներկումը ցույց է տալիս, որ այդ առավելագույն թւվը հասանելի է։
Հ.Գ. Իդեպ, ժողովուրդ, եթե որևէ մեկը առավելագույն դեղին վանդակների քանակը պարզող ծրագիր գրեր C կամ C++ –ով կամ Java–ով, հետաքրքիր կլիներ պարզել ծրագրերի աշխատանքի ժամանակները։ Իմը կազմում է 7.36վ, բայց ինձ թվում է այս արդյունքը կարելի է լավացնել...
Շնորհակալություն այս մեծ պատասխանիդ համարՓաստորեն մենք 2 ով տվեցինք թեմայի հարցի պատասխանը. դու գտար մաքսիմալ հնարավոր քանակը, ես ել ցույց տվեցի նրա գոյությունը
Հ.Գ. Որ մի քիչ ազատ ժամանակ գտնեմ, կաշխատեմ քո մեթոդով ծրագիր գրել C++-ով:
Այս պահին թեմայում են 1 հոգի. (0 անդամ և 1 հյուր)
Ձեր իրավունքները բաժնում
Մեջբերել
Էջանիշներ