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

[soultaker]

հո ձեռքով չենք հաշվում պատասխանը ? թող քանի անգամ ուզումա համակարգիչը հաշվի տվյալ խնդրի դեպքում դժվար հզորության պակաս նկատվի: Կարելիա սկզբում չափերի ընդհանուր բազմապատիկը գտնել, հետո նոր մնացած գործողություններն անել: Բայց դա էլ ավելորդ գործողություն կլինի, եթե չափերը չունենան ընդհանուր բազմապատիկ:

Հարցը հենց նրանումա որ մինչև այժմ ֆորումում խնդիրը լուծող ալգորիթմ չի առաջարկվել (համենայն դեպս ես չեմ տեսել), ու ես կասկածում եմ որ գոյություն ունի այնպիսի ալգորիթմ որը արագ կաշխատի ու ճիշտ պատասխան կտա մեծ դեպքերի վրա թեկուզ ամենաարագ համակարգչով:

[Վահե-91]

Հարցը հենց նրանումա որ մինչև այժմ ֆորումում խնդիրը լուծող ալգորիթմ չի առաջարկվել (համենայն դեպս ես չեմ տեսել)

5 ու 6 չափերի դեպքում ասեցիր սխալ կաշխատի իմ առաջարկածը՝ ուղղեցի: Էլի սխալ աշխատելու տարբերակ կա , որ չես ասում ?

[soultaker]

5 ու 6 չափերի դեպքում ասեցիր սխալ կաշխատի իմ առաջարկածը՝ ուղղեցի: Էլի սխալ աշխատելու տարբերակ կա , որ չես ասում ?

Չեմ հիշում որ նոր բան առաջարկած լինես, որը ճիշտ կաշխատի 5x6-ի վրա: Ուղղակի ասեցիր որ հեշտա էտ ուղղելը, իսկ թե ոնց` երևի մենակ դու գիտես:
Ամեն դեպքում, մի՞թե քեզ թվումա որ 5x6-ը տենց հատուկ սատանայական չափա, որի վրա ամեն ինչ սխալա աշխատում, ու էտ դեպքը առանձին քննարկելով մնացած ամեն ինչ ճիշտ կաշխատի: Կամ կարաս արդյոք բացատրես թե ինչ պատճառովա քո առաջարկած մեթոդը ճիշտ:

[Վահե-91]

Չեմ հիշում որ նոր բան առաջարկած լինես, որը ճիշտ կաշխատի 5x6-ի վրա: Ուղղակի ասեցիր որ հեշտա էտ ուղղելը, իսկ թե ոնց` երևի մենակ դու գիտես:
Ամեն դեպքում, մի՞թե քեզ թվումա որ 5x6-ը տենց հատուկ սատանայական չափա, որի վրա ամեն ինչ սխալա աշխատում, ու էտ դեպքը առանձին քննարկելով մնացած ամեն ինչ ճիշտ կաշխատի: Կամ կարաս արդյոք բացատրես թե ինչ պատճառովա քո առաջարկած մեթոդը ճիշտ:

բա էս ինչա ?

[soultaker]

բա էս ինչա ?

Ճիշտն ասած բլոկսխեմայով չեմ հասկանում թե ինչա անում, բայց մեջը 5 ու 6 թվեր տեսա, նենց որ ինչ-որ բան խալտուրայա արած

[Վահե-91]

Ճիշտն ասած բլոկսխեմայով չեմ հասկանում թե ինչա անում, բայց մեջը 5 ու 6 թվեր տեսա, նենց որ ինչ-որ բան խալտուրայա արած

էտ դեպքում ինքդ ինչ-որ մի բան առաջարկի մենակ լսում ենք, որ ասում ես սխալա աշխատում

[Varzor]

5x6 = 30
Վերցնենք 5x5 + 2x2 + 1x1 = 30
Ստացանք 3 քառակուսի: Հիմա փորձիր բացատրել թե ինչպես ես 3 այսպիսի քառակուսիներ կտրելու 5x6 ուղղանկյունից:

Պայմանները թերի են: Ես արդեն նշել եմ

Քառակուսիների կողմերի երկարությունների գումարներիկ վրա էլ սահմանափակումներ են դրվում:

պիտի ավելացվեն ուղղանկյան կողմերի հետ կապված պայմանները` տվյալ պարագայում 5+2+1<=5 (6) պայմանը չի բավարարվում:
Պիտի լրացուցիչ լինեն առնվազն ևս 2 պայմաններ, օրինակ.
Sum(X(i) *i) <= 2*M
Sum(X(i) *i) <= 2*N
և դա բնական է, քանի որ իրար հարևան քառակուսիների կողմերի գումարը չի կարող գերազանցել ուղղանկյան կողմի երկարությունը:
Կրկնվում եմ, բայց էլի ասեմ, որ դասական գծային ամբողջաթիվ ծրագրավորման խնդիր է:
Դրանում պիտի լինի նպատակային ֆունկցիա` Sum(X(i) )->min
Ու պիտի լինեն սահմանափակումներ`
Sum(X(i) *i^2) = M*N
Sum(X(i) *i) <= 2*M
Sum(X(i) *i) <= 2*N
...
ավելի մանրամասն այստեղ

[soultaker]

Պայմանները թերի են: Ես արդեն նշել եմ

պիտի ավելացվեն ուղղանկյան կողմերի հետ կապված պայմանները` տվյալ պարագայում 5+2+1<=5 (6) պայմանը չի բավարարվում:
Պիտի լրացուցիչ լինեն առնվազն ևս 2 պայմաններ, օրինակ.
Sum(X(i) *i) <= 2*M
Sum(X(i) *i) <= 2*N
և դա բնական է, քանի որ իրար հարևան քառակուսիների կողմերի գումարը չի կարող գերազանցել ուղղանկյան կողմի երկարությունը:
Կրկնվում եմ, բայց էլի ասեմ, որ դասական գծային ամբողջաթիվ ծրագրավորման խնդիր է:
Դրանում պիտի լինի նպատակային ֆունկցիա` Sum(X(i) )->min
Ու պիտի լինեն սահմանափակումներ`
Sum(X(i) *i^2) = M*N
Sum(X(i) *i) <= 2*M
Sum(X(i) *i) <= 2*N
...
ավելի մանրամասն այստեղ

Ենթադրենք վերցնում ենք 3x3 չափի ու բաժանում միհատանոցների` 9 հատ 1x1:
Նոր ավելացրածդ մյուս երկու սահմանափակումներից ելնելով`
9 * 1 <= 2 * 3 պայմանը տեղի չունի, բայց այդպիսի տրոհումը հնարավոր է:

[soultaker]

էտ դեպքում ինքդ ինչ-որ մի բան առաջարկի մենակ լսում ենք, որ ասում ես սխալա աշխատում

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

[Varzor]

Դրա համար էլ ասում եմ - նորմալ լուծում, ոչ թե ուղղակի լուծում: Նորմալ լուծում ասելով նկատի ունեմ մուտքային տվյալներից բազմանդամային կախում ունեցող, այսինքն այնպիսին, որ մեծ թվերի համար հնարավոր լինի արագ լուծել:

Մեծ թվերի համար ծրագրեր են աշխատացնում
Հնարավոր չե տալ մի բանաձև, որի միջոցով ցանկացած թվերի համար հաշվարկը կկատարվի: Բայց ալգորիթմը արդեն վաղուց գոյություն ունի: Կահույքի արտադրամասերում օգտագործվող ծրագիրերը նմանատիպ ալգորիթմենորվ են աշխատում:

Հ.Գ.
Երբեք չէի մտացել, որ նորմալ ու արագ լուծումները իրար համարժեք են

[Varzor]

Հարցը հենց նրանումա որ մինչև այժմ ֆորումում խնդիրը լուծող ալգորիթմ չի առաջարկվել (համենայն դեպս ես չեմ տեսել), ու ես կասկածում եմ որ գոյություն ունի այնպիսի ալգորիթմ որը արագ կաշխատի ու ճիշտ պատասխան կտա մեծ դեպքերի վրա թեկուզ ամենաարագ համակարգչով:

Իզուր ես կասկածում, Նոյի թվի ալգորիթմը վաղուց կա, ներկայիս համակարգիչների վրա էլ բավականին արագ աշխատում է: Ստեղ են ասել, ամբիոնիս վարիչի ականջը կանչի

[Varzor]

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

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

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

[soultaker]

Մեծ թվերի համար ծրագրեր են աշխատացնում
Հնարավոր չե տալ մի բանաձև, որի միջոցով ցանկացած թվերի համար հաշվարկը կկատարվի:

Ես ամեն ինչ նշել եմ ծրագրով հաշվելու տեսանկյունից, մենք նախնադարում չենք ապրում:
Իսկ բանաձևի մասին խոսք չի գնացել ընդհանրապես:

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

[soultaker]

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

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

Միգուցե գծային ծրագրավորման, ոչ թե ուղղակի ծրագրավորման խնդիրները?
Եթե այո, ապա որտեղից ենթադրեցիր որ այս խնդիրը բերվում է գծային ծրագրավորման խնդրի(ու ինչպես)?

[Varzor]

Ենթադրենք վերցնում ենք 3x3 չափի ու բաժանում միհատանոցների` 9 հատ 1x1:
Նոր ավելացրածդ մյուս երկու սահմանափակումներից ելնելով`
9 * 1 <= 2 * 3 պայմանը տեղի չունի, բայց այդպիսի տրոհումը հնարավոր է:

Հնարավոր է, բայց սխալ է: 3x3-ը տրոհվում է 2x2+ 5x(1x1): Ոնց տեսնում ես պայմանը բավարարվում է
Ու դա ևս մեկ քայլն է դեպի ճիշտ լուծումը: Փաստացի 9 հատ 1 երկարության կողմով քառակուսիները չբավարարեցին պայմանին, հետևաբար չեն կարող հանդիսանալ օպտիմալ լուծում
Ու ասեմ, որ պայմանների քանակը մենակ այդ երկուսը չի, էլի կան