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

[soultaker]

տարօրինակ մարդա sonechka-ն, էսքան խոսում ենք, իրա խնդիրն ենք լուծում կամ քննարկում, մի անգամ չարձագանքեց կարողա էլ պետք չի ՞ ինչի ենք հավայի տանջվում ՞ մի հատ պետքա հարցնել ինքը որերորդ կուրսա, կարողա դասախոսն էլ չգիտի ինչ բարդության խնդիրա տվել
1 կուրսում դասախոսներիցս մեկը կուրսային էր տվել, համարյա վերջացնում էի, պարզվեց տվյալներից մեկի սխալ լինելու պատճառով այլևս հնարավոր չէր շարունակել, նորից սկսեցի ուրիշ տվյալով

Ամենայն հավանականությամբ դասախոսը նկատիա ունեցել ուղղակի կիրառել էվկլիդեսի ալգորիթմը ու տեսնել թե ինչ թիվա ստացվում, ոչ թե գտնել օպտիմալ լուծումը:

[Varzor]

Այս դեպքում քո առաջարկած լուծումը որպես ինչ էիր ներկայացնում? ՈՐՈՇ դեպքերի համար լուծում?
Հիմա գծային ծրագրավորումով լուծվումա թե չէ?
Եթե լուծում է առաջարկվում, պիտի առաջարկվի կոնկրետ ալգորիթմ, ոչ թե նենց, որ դեպքերի մի մասի վրա ճիշտ աշխատի, մնացած մասի համար էլ ասեն լավ, սրանց համար էլ մի ուրիշ ձևով կանենք, կանցնի կգնա:

Իմ առաջարկած լուծումը կոնկրետ վերաբերվում էր 5x6-ի խնդրին: Այո, որոշ դեպքերի համար լուծում (ֆիքսված չափողականության համար):
Կոմպլեքս ալգորիթմերը նույն խնդրի լուծման համար կիրառվող մի քանի ալգորիթմեր են: Ասենք մի ալգորիթմով հաշվում ես մեկը, մյուսով մյուսը: Ու խնդրի լուծումը սկսելոց առաջ ընտրանքով ընտրում ես ալգորիթմը
Սենց ասեմ. Ամեն MxN-ի համար կարելի է կառուցել առանձին ալգորիթմ: Ու այն կարող է չգործել այլ արժեքների համար:
Ես խնդրի լուծմանը միջամտել եմ այս գրառումից հետո, որպես տրամաբանական շարունակություն:
Ու այդ տարբերակի համար էլ հստակ լագորիթմ եմ առաջարկել:

[Varzor]

Ամենայն հավանականությամբ դասախոսը նկատիա ունեցել ուղղակի կիրառել էվկլիդեսի ալգորիթմը ու տեսնել թե ինչ թիվա ստացվում, ոչ թե գտնել օպտիմալ լուծումը:

Կամ էլ սահմանափակվել է ուղղանկյան կողմերի երկարությունները, հակառակ դեպքում ուղանողից պահանջել այդպիսի խնդրի համար լիարժեք լուծում տալը, կոռեկտ չէր լինի:
Որքանով ես եմ հիշում, միշտ այդպիսի խնդիրների դեպքում վերևից սահմանափակում էին: Օրինակ` խնդիր էին դնում գրել ծրագիրը, որը MxM չափի մատրիցի հակադարձը հաշվի դասական եղանակով: Այն ժամանակվա P2-ների վրա 10x10-ի դեպքում կոմպը կախում էր: Բայց ոչ դասակն ալգորիթմերով հաշվելու դեպքում սահմանափակումը միայն տվյալ ծրագրային լեզվի փոփոխականների հասցեների տիրույթն է ու մեքենայի հիշողությունը, քանի որ կան ոչ ռեկուրսիվ մեթդոդներ:

[soultaker]

Իմ առաջարկած լուծումը կոնկրետ վերաբերվում էր 5x6-ի խնդրին: Այո, որոշ դեպքերի համար լուծում (ֆիքսված չափողականության համար):
Կոմպլեքս ալգորիթմերը նույն խնդրի լուծման համար կիրառվող մի քանի ալգորիթմեր են: Ասենք մի ալգորիթմով հաշվում ես մեկը, մյուսով մյուսը: Ու խնդրի լուծումը սկսելոց առաջ ընտրանքով ընտրում ես ալգորիթմը
Սենց ասեմ. Ամեն MxN-ի համար կարելի է կառուցել առանձին ալգորիթմ: Ու այն կարող է չգործել այլ արժեքների համար:
Ես խնդրի լուծմանը միջամտել եմ այս գրառումից հետո, որպես տրամաբանական շարունակություն:
Ու այդ տարբերակի համար էլ հստակ լագորիթմ եմ առաջարկել:

Քո մոտեցումը հասկացա, բայց եթե այդպես նայենք, կամայական միարժեք պատասխան ունեցող խնդրի համար էլ կամայական կոնկրետ ֆիքսված մուտքային տվյալների համար գոյություն ունի մի ալգորիթմ, որը տալիս է ճիշտ պատասխան այդ դեպքում, և սխալ է աշխատում մյուս դեպքերում:

[Varzor]

Քո մոտեցումը հասկացա, բայց եթե այդպես նայենք, կամայական միարժեք պատասխան ունեցող խնդրի համար էլ կամայական կոնկրետ ֆիքսված մուտքային տվյալների համար գոյություն ունի մի ալգորիթմ, որը տալիս է ճիշտ պատասխան այդ դեպքում, և սխալ է աշխատում մյուս դեպքերում:

Ճիշտ է
Ես էլ հասկացել եմ քո մոտեցումը` միատեսակ տրամաբանությամբ ընդհանուր ունիվերսալ ալգորիթմ չկա, որի բարդության աստիճանը գծային լինի: Ու դա այդպես է որ կա, միանշանակ համամիտ եմ

[Rafik]

Երևի մաքսիմալ?