Ագահ ալգորիթմ

[Վահե-91]

պիտի որ սենց լինի լուծումը՝

[armen9494]

պիտի որ սենց լինի լուծումը՝

լավն ա, իմ առաջարկածից ավելի արագ ա աշխատում
օրինակ եթե իմում հանդիպում էր 1x4 ուղղանկյան, ապա 4 անգամ ցիկլով անցնում էր՝ ամեն անգամ հանելով 1x1 չափսի քառակուսի, իսկ ստեղ միանգամից ա էդ 4 հատ քառակուսիները հանում

[soultaker]

Էտ խնդիրը կարծեմ NP-ա, այսինքն նորմալ լուծում չունի, իսկ վերը նշված էվկլիդեսի ալգորիթմով հաշված թիվը ցույցա տալիս ընդամենը պատասխանի վերևի սահմանը:

[Վահե-91]

Էտ խնդիրը կարծեմ NP-ա, այսինքն նորմալ լուծում չունի, իսկ վերը նշված էվկլիդեսի ալգորիթմով հաշված թիվը ցույցա տալիս ընդամենը պատասխանի վերևի սահմանը:

դուրսա գալիս, ես առանց իմանալու էվկլիդեսի ալգորիթմի մասին, բացահայտեցի այն

[armen9494]

Էտ խնդիրը կարծեմ NP-ա, այսինքն նորմալ լուծում չունի, իսկ վերը նշված էվկլիդեսի ալգորիթմով հաշված թիվը ցույցա տալիս ընդամենը պատասխանի վերևի սահմանը:

բայց ինչի՞ խնդիրը նորմալ լուծում չունի

[soultaker]

բայց ինչի՞ խնդիրը նորմալ լուծում չունի

Որովհետև նման տիպի խնդիրների համար օպտիմալ ալգորիթմը չի լինում բազմանդամային բարդության, օրինակ Օ(n), O(n^2) կամ O(n^2 + n^3), այլ էքսպոնենցիալ բարդության - այսինքն մուտքային տվյալներից կախված գործողությունների քանակի կարգը աճումա էքսպոնենցիալ, օրինակ O(2^n), O(3^n), O(n!), և այլն: Ես 100%-ով չեմ պնդում որ էս խնդիրը պատկանումա դրանց դասին, բայց ենթադրում եմ որ տենցա, որովհետև տարբեր հոդվածներ կան սրա մասին որ փորձում են ինչ-որ գնահատական տան օպտիմալ պատասխանին, թե ինչ միջակայքում պիտի գտնվի, կամ ասենք ամենաշատը ինչքան կարա լինի պատասխանը: Որոշ տեղեր կա նշված, որ որպես պատասխանի վերին սահման կարելիա ընդունել էվկլիդեսի ալգորիթմով ստացվող թիվը, իսկ եթե խնդիրը լուծելի լիներ, օպտիմալ լուծումն էլ պետքա որ նշված լիներ: Հիմա կոնկրետ լինկերը չունեմ, բայց կարաս փնտրես "Minimum tiling of a rectangle by squares":

[armen9494]

Ճիշտն ասած չհասկացա քո ասածը: Դու ուզում ես ասես, որ կարող ա լինի կոնկրետ ուղղանկյունու չափսեր որ Վահեի կամ իմ գրածը սխալ պատասխան տա՞:
Թե՞ ուզում ես ասես, որ խնդրի տվյալներից կախված կարա մի դեպքում իմ գրածը ավելի արդյունավետ աշխատի, մյուս դեպքում Վահեի (բայց միևնույնն է՝ արդյունքը լինի ճիշտ):

[soultaker]

Ճիշտն ասած չհասկացա քո ասածը: Դու ուզում ես ասես, որ կարող ա լինի կոնկրետ ուղղանկյունու չափսեր որ Վահեի կամ իմ գրածը սխալ պատասխան տա՞:

Ճիշտ է: Երկուսդ էլ կարծեմ նույն լուծումն էիք առաջարկում, ուղղակի ինքը մի քիչ ուրիշ ձև էր գրել, բայց էտ բան չի փոխում, որովհետև էվկլիդեսի ալգորիթմնա երկու դեպքում էլ:

[armen9494]

Ճիշտ է: Երկուսդ էլ կարծեմ նույն լուծումն էիք առաջարկում, ուղղակի ինքը մի քիչ ուրիշ ձև էր գրել, բայց էտ բան չի փոխում, որովհետև էվկլիդեսի ալգորիթմնա երկու դեպքում էլ:

Չէ, իր դեպքում ծրագիրն ավելի արագ էր աշխատում, չնայած ինձ թվում ա արդյունքը նույնը կլիներ:

Իսկ կասե՞ս մի տարբերակ, որի ժամանակ այդ ձևով լուծելով կստանանք սխալ պատասխան:
Ուղղակի չեմ պատկերացնում:

[soultaker]

ալգորիթմն էլ չես կարում կազմես ???? սրանից պրիմիտիվ խնդիր չի կարա գոյություն ունենա բնության մեջ

5x6 չափի ուղղանկյուն եմ քեզ տալիս, դե եթե լավ ալգորիթմ կա ու էտքան պրիմիտիվա, դրանով կտրտի քառակուսիներ ու ասա քանի հատ ես ստանում:

[soultaker]

Չէ, իր դեպքում ծրագիրն ավելի արագ էր աշխատում, չնայած ինձ թվում ա արդյունքը նույնը կլիներ:

Իսկ կասե՞ս մի տարբերակ, որի ժամանակ այդ ձևով լուծելով կստանանք սխալ պատասխան:
Ուղղակի չեմ պատկերացնում:

http://www.akumb.am/showthread.php/6...AB%D5%A9%D5%B4

Հեսա ստեղ գրել եմ:

[Վահե-91]

5x6 չափի ուղղանկյուն եմ քեզ տալիս, դե եթե լավ ալգորիթմ կա ու էտքան պրիմիտիվա, դրանով կտրտի քառակուսիներ ու ասա քանի հատ ես ստանում:

սկզբում ուրիշ ձև էի պատկերացրել խնդիրը: Իմ ասած ալգորիթմը կկտրի 6 հատ քառակուսի:

[Վահե-91]

http://www.akumb.am/showthread.php/6...AB%D5%A9%D5%B4

Հեսա ստեղ գրել եմ:

5 ու 6 չափերի դեպքում էլ կարամ լուծում առաջարկեմ մինիմալ քանակի քառակուսի ստանալու համար

[Varzor]

Էս ինչեր եք խոսքւմ, բան չեմ հասկանում
Եթե ուղղանկյան կողմերը բնական թվեր են` M և N, ապա ամենափոքր խառակուսին կլինի 1 կողմով քառակուսին, հետևաբար կունենանք M x N հատ այդպիսի քառակուսիներ:
Ու սկսվում է հակադարձ գործընթացը` փոքր քառակուսիների միավորման:
Իսկ ալգորիթմը կլինի մոտավորապես հետևյալը.
1. որոշում ենք որ թիվն է մեծ ` օրինակ M>N: Ըստ դրա կատարում ենք կողմերի վերադասավորում:
2. n` Առաջին քառակուսու կողմը: Տակը մնաց` M-N=>M1 և N=>N1 կողմերով ուղղանկյունը:

Այս երկու գործողությունները շարունակվում են այնքան, մինչև i-երորդ քայլում կողմերից որևէ մեկը չհավասարվի 1-ի: Արդյունքում տակը կմնա Ni x Mi չափերով ուղղանկյուն, որտեղ օր. Ni=1, հետևաբար տակը մնաց Mi հատ քառակուսի: քանակը ստացվեց ` i + Mi

Ծրագիրը C++-ով գրեմ տամ, թե արդեն հասկանալի է?

[armen9494]

5 ու 6 չափերի դեպքում էլ կարամ լուծում առաջարկեմ մինիմալ քանակի քառակուսի ստանալու համար

բայց կարա՞ս ընդհանուր մի լուծում առաջարկես, որ ցանկացած չափի համար լինի