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

[armen9494]

Էս ինչեր եք խոսքւմ, բան չեմ հասկանում
Եթե ուղղանկյան կողմերը բնական թվեր են` 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++-ով գրեմ տամ, թե արդեն հասկանալի է?

էդքան էլ պարզ չէր, բայց մի բան ասա՝ ըստ քո ալգորիթմի քանի՞ քառակուսի կստացվի 5x6 -ի դեպքում

[Varzor]

էդքան էլ պարզ չէր, բայց մի բան ասա՝ ըստ քո ալգորիթմի քանի՞ քառակուսի կստացվի 5x6 -ի դեպքում

5 - 2 հատ 3x3, 3 հատ 2x2

[Varzor]

էտ դեպքում դու ստացել ես 3 հատ քառակուսի ու մի հատ ուղղանկյուն: Եվ ընդհանրապես կարող է նենց ստացվել, որ անվերջ քանակությամբ քառակուսիներ ստացվեն

]
Անվերջ քանակով չեն ստացվի, որովհետև կողմերը բնական թվեր են: Սա ամբողջաթվային ծրագրավորման խնդիրը է` օպտիմիզացիայի խնդիրներից է: Նույն կերպ ասենք ԴՍՊ-ի լիստից մաքսիմալ հնարավոր քառակուսիներն են ստանում, կամ հակառակը մինիմալ հնարավոր քառակուսիները:

[armen9494]

5 - 2 հատ 3x3, 3 հատ 2x2

իսկ հիմա փորձեմ հասկանալ ալգորիթմը

Որ խնդրեմ կգրես, թե օրինակ կոնկրետ էս պայմանի դեպքում ի՞նչ քայլերով ա առաջ գնում, ճիշտը որ ասեմ՝ չեմ հասկանում

[Varzor]

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

Ավելի արագ է միայն այն պատճառովմ, որ դու 1 երկարությամբ կողմով ուղղանկյունները դեռ շարունակում ես կտրտելը: Դրանք այլևս կտրտել պետք չի` միանգամից բաժանելով ստացվում է:
Իսկ ընդհանուր առումով ալգորիթմը արհեստական է սխալ արդյունք է տալիս, համ էլ բլոկ-սխեման սխալ է գծված (երեք վերջ չի կաորղ ունենալ, վերագրման և բազմապատկման գործողությունը Պասկալ լեզվով է գրված, սլաքները բացակայում են )
Ըստ գրված ալգորիթմի հաշվեք արդեն որպես օրինակ բերված տարբերակը` 5x6 ուղղանկյունը:

[Varzor]

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

]
Միշտ էլ լուծում ունի, քանի որ կողմերը ամբողջ թվեր են, քառակուսիների քանակն էլ վերջավոր է:

[Varzor]

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

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

Իրականում քո ու իրա գրածների մեջ քայլային տրամաբանություն չկա: Ու չի էլ կարող ավելի արագ աշխատել

[Վահե-91]

համ էլ բլոկ-սխեման սխալ է գծված (երեք վերջ չի կաորղ ունենալ),

իմ գծածը այսպես կոչված բետա վերսիա կարելի է համարել շատ հեշտությամբ կարելիա մի վերջ ստանալ

համ էլ բլոկ-սխեման սխալ է գծված (վերագրման և բազմապատկման գործողությունը Պասկալ լեզվով է գրված, սլաքները բացակայում են )

կներեք, հեսա կգնամ c++ կսովորեմ, հատուկ sonechka-ի համար

Ըստ գրված ալգորիթմի հաշվեք արդեն որպես օրինակ բերված տարբերակը` 5x6 ուղղանկյունը:

կստացվի մի հատ քառակուսով ավել, քան ուրիշ ձևով բաժանելուց: Էս սխալն էլ կարելի է հեշտությամբ ուղղել: Բայց արդյոք ուրիշ բացառութոյւններ չկան ՞ ոնց որ 5x6 չափերի դեպքում ՞

[Varzor]

իսկ հիմա փորձեմ հասկանալ ալգորիթմը
Որ խնդրեմ կգրես, թե օրինակ կոնկրետ էս պայմանի դեպքում ի՞նչ քայլերով ա առաջ գնում, ճիշտը որ ասեմ՝ չեմ հասկանում

Ճիշտը որ ասեմ, ես էլ իմ գրածը կողքից մուշտարու աջքով կարդացի ու հասկացա ու հասկանալի չի
Ուրեմն, ոնց արդեն ասեցի` խնդիրը ամբողջաթիվ գծային ծրագրավորման խնդիր է:
Որպես մուտքային տվյալներ են ծառայում ուղղանկյան կողմերը, իսկ նպատակային ֆունկցիան քառակուսիների մակերեսների գումարն է:
Որպես սահմանափակումներ ընդունվում են ուղղանկյան կողմերի երկարությունները:
Մոտավորապես սենց
Sum(X(i) *i^2) = M*N, որտեղ i-ն քառակուսու կողմի երկարությունն է, իսկ X(i)-ն i կողմով քառակուսիների քանակն է:
Քառակոսիների կողմերի երկարությունների գումարներիկ վրա էլ սահմանափակումներ են դրվում:
Սկսում ես 1 երկարության քառակուսիներից, հետո հատ-հատ աճացնում ես:
Դասական խնդիր է: АСУ-ի ամբիոնում հաստատ անցնում են:

[Varzor]

իմ գծածը այսպես կոչված բետա վերսիա կարելի է համարել շատ հեշտությամբ կարելիա մի վերջ ստանալ

Դե բետա տարբերակի համար բավականին լավ է ստացվել

կներեք, հեսա կգնամ c++ կսովորեմ, հատուկ sonechka-ի համար

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

կստացվի մի հատ քառակուսով ավել, քան ուրիշ ձևով բաժանելուց: Էս սխալն էլ կարելի է հեշտությամբ ուղղել: Բայց արդյոք ուրիշ բացառութոյւններ չկան ՞ ոնց որ 5x6 չափերի դեպքում ՞

Դրանք բացառություններ չեն: Տվյալ ալգորիթմն է բացառությունների համար

[Վահե-91]

Ագահ ալգորիթմ (կամ ինչպես էր ծուլանում sonechka-ն) Beta 2

[Varzor]

կամ ինչպես էր ծուլանում sonechka-ն

Միթե դա ծուլանալ է?

[soultaker]

]
Միշտ էլ լուծում ունի, քանի որ կողմերը ամբողջ թվեր են, քառակուսիների քանակն էլ վերջավոր է:

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

[soultaker]

Sum(X(i) *i^2) = M*N

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

[Վահե-91]

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

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