PDA

Դիտել ողջ տարբերակը : Ագահ ալգորիթմ



Sonechka
11.11.2011, 22:37
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են բնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը:Մշակել ալգորիթմ և C++ գրել ծրագիր:

Sonechka
11.11.2011, 22:54
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են բնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը:Մշակել ալգորիթմ և C++ գրել ծրագիր:

Լեո
11.11.2011, 23:11
Քառո՞րդ ենք փակում :))

Վահե-91
11.11.2011, 23:34
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են բնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը:Մշակել ալգորիթմ և C++ գրել ծրագիր:
ալգորիթմն էլ չես կարում կազմես ???? :o սրանից պրիմիտիվ խնդիր չի կարա գոյություն ունենա բնության մեջ :8

armen9494
11.11.2011, 23:55
Ես մի բան մտածեցի՝ չգիտեմ ինչքանով ա ռացիոնալ, բայց հիմա կգրեմ: Միայն ալգորիթմը ասեմ՝ հեսա պիտի դուրս գամ:

Սկզբում ուղղանկյան փոքր էջի չափով մեծ էջից քառակուսի ենք կտրում:
Հետո ստացվում ա մի նոր ուղղանկուն:
Հիմա նորից՝ փոքր էջի չափով մեծ էջից քառակուսի ենք կտրում:
.............
Ու դա անում ենք էնքան ժամանակ, քանի դեռ նոր ստացվող ուղղանկյունը քառակուսի չէ:
Մի հատ էլ նկար տեղադրեմ, որ ավելի պարզ լինի
http://i.imgur.com/5HGsH.jpg

Sonechka
12.11.2011, 00:38
Եթե m ≠ n, ապա հնարավոր են երկու դեպք m<n և m>n: Ուղղանկյունից կտրենք ամենամեծ մակարեսով քառակուսին,որի կողմերը բնական թվեր են: Քառակուսին կտրելուց հետո ուղղանկյան չափերը կլինեն հետևյալը. Մեծ կողմը կփոքրանա քառակուսու կողմի երկարությամբ, իսկ փոքրը չի փոխվի: Փնտրվող քառակուսիների քանակը կհաշվվի որպես այն քառակուսիների քանակ, որոնց վրա կկտրվի ստացված ուղղանկյունը և այդ ամենին գումարած մեկ( կտրած քայակուսին): Ստացված ուղղանկյանը կկիրառենք նույն դատողությունները:
Ուրիշ ինչ ալգորիթմ կառաչարկեք բացի սրանից

Sonechka
12.11.2011, 00:41
Շնորհակալություն...Սրանից բացի ուրիշ ինչ կառաչարկեք

Վահե-91
12.11.2011, 11:10
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են բնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը:Մշակել ալգորիթմ և C++ գրել ծրագիր:
1. Պետք է համամեատել մի կողմի երկարությունը մյուսի հետ
2. Որը մեծ եղավ բաժանել փոքրի վրա
3. Վերցնել ստացվածի ամբողջ մասը: Եթե ստացվելա 2,64, վերցնել 2-ը), էտ էլ կլինի պատասխանը:

Վահե-91
12.11.2011, 11:13
Ես մի բան մտածեցի՝ չգիտեմ ինչքանով ա ռացիոնալ, բայց հիմա կգրեմ: Միայն ալգորիթմը ասեմ՝ հեսա պիտի դուրս գամ:

Սկզբում ուղղանկյան փոքր էջի չափով մեծ էջից քառակուսի ենք կտրում:
Հետո ստացվում ա մի նոր ուղղանկուն:
Հիմա նորից՝ փոքր էջի չափով մեծ էջից քառակուսի ենք կտրում:
.............
Ու դա անում ենք էնքան ժամանակ, քանի դեռ նոր ստացվող ուղղանկյունը քառակուսի չէ:
Մի հատ էլ նկար տեղադրեմ, որ ավելի պարզ լինի

բայց էս մինիմալ չի կարելի համարել, դու ստացար մաքսիմում հնարավոր քառակուսիներ: Չնայած խնդիրն էլ ճիշտ չի ձևակերպված:

armen9494
12.11.2011, 11:20
բայց էս մինիմալ չի կարելի համարել, դու ստացար մաքսիմում հնարավոր քառակուսիներ: Չնայած խնդիրն էլ ճիշտ չի ձևակերպված:

Կամ դու խնդիրը ճիշտ չես հասկացել, կամ ես:
Ես այսպես եմ հասկացել.
Ուղղանկյունուց ստանալ քառակուսիներ՝ այնպես, որ էդ ստացված քառակուսիների մակերեսների գումարը լինի հավասար ուղղանկյան մակերեսին:
Եվ այնպես հաշվել, որ էդ քառակուսիների քանակը ինչքան հնարավոր է քիչ լինի:

Մի քիչ գեղավարի գրեցի, բայց դե գրեցի ընենց, ոնց ես եմ հասկացել :))

Վահե-91
12.11.2011, 11:29
Կամ դու խնդիրը ճիշտ չես հասկացել, կամ ես:
Ես այսպես եմ հասկացել.
Ուղղանկյունուց ստանալ քառակուսիներ՝ այնպես, որ էդ ստացված քառակուսիների մակերեսների գումարը լինի հավասար ուղղանկյան մակերեսին:
Եվ այնպես հաշվել, որ էդ քառակուսիների քանակը ինչքան հնարավոր է քիչ լինի:

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

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

Ես խնդիրը չեմ վերջացրել, գրեցի ոնց պիտի գնաս (ի՞նչ իմաստ ուներ մինչև վերջ գրելը, միևնույնն ա m և n թվերի համար ա) ու մի օրինակ էլ գրեցի, իսկ անվերջ քանակությամբ քառակուսի ստանալը չեմ պատկերացնում:think
Օրինակ ասեմ, թե ոնց եմ պատկերացնում իմ գրածով.
ենթադրենք իմ ուղղանկյան չափսերն են m=5, n=4 (t- մեջ կհաշվեմ ստացված քառակուսիների քանակը)
m>n , ուրեմն m=m-n և t=t+1 (ստացվեց m=1, n=4, t=1)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=3, t=2)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=2, t=3)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=1, t=4)
n=m, ուրեմն t=t+1 (ստացվեց m=1, n=1, t=5)

Այսինքն ստացանք, որ 5x4 չափերի ուղղանկյունին կարելի է բաժանել ամենաքիչը 5 քառակուսիների, այնպես, որ էդ քառակուսիների մակերեսների գումարը հավասար լինի ուղղանկյան մակերեսի գումարին:

Վահե-91
12.11.2011, 12:57
Ես խնդիրը չեմ վերջացրել, գրեցի ոնց պիտի գնաս (ի՞նչ իմաստ ուներ մինչև վերջ գրելը, միևնույնն ա m և n թվերի համար ա) ու մի օրինակ էլ գրեցի, իսկ անվերջ քանակությամբ քառակուսի ստանալը չեմ պատկերացնում:think
Օրինակ ասեմ, թե ոնց եմ պատկերացնում իմ գրածով.
ենթադրենք իմ ուղղանկյան չափսերն են m=5, n=4 (t- մեջ կհաշվեմ ստացված քառակուսիների քանակը)
m>n , ուրեմն m=m-n և t=t+1 (ստացվեց m=1, n=4, t=1)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=3, t=2)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=2, t=3)
n>m, ուրեմն n=n-m և t=t+1 (ստացվեց m=1, n=1, t=4)
n=m, ուրեմն t=t+1 (ստացվեց m=1, n=1, t=5)

Այսինքն ստացանք, որ 5x4 չափերի ուղղանկյունին կարելի է բաժանել ամենաքիչը 5 քառակուսիների, այնպես, որ էդ քառակուսիների մակերեսների գումարը հավասար լինի ուղղանկյան մակերեսի գումարին:
եթե մի չափը մյուսից 2 անգամ մեծ լինի, քո լուծումը սխալ կաշխատի: Ոնց որ էտքան էլ կարճ չի ստացվում լուծումը, բայց ստացվումա:

armen9494
12.11.2011, 13:10
եթե մի չափը մյուսից 2 անգամ մեծ լինի, քո լուծումը սխալ կաշխատի: Ոնց որ էտքան էլ կարճ չի ստացվում լուծումը, բայց ստացվումա:

ո՞նց սխալ կաշխատի:8

ընդեղ վերևում ես գրել եմ՝ քանի դեռ նոր ստացվող ուղղանկյունը քառակուսի չէ

Վահե-91
12.11.2011, 13:16
ո՞նց սխալ կաշխատի:8

որ ժամանակ լինի ամբողջ լուծումը կգրեմ (ալգորիթմը), կհասկանաս

Վահե-91
12.11.2011, 14:01
պիտի որ սենց լինի լուծումը՝
http://rghost.ru/private/29626711/1edde5e488c66a249d963d0de8261301/image.png

armen9494
12.11.2011, 14:17
պիտի որ սենց լինի լուծումը՝


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

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

Վահե-91
12.11.2011, 19:59
Էտ խնդիրը կարծեմ NP-ա, այսինքն նորմալ լուծում չունի, իսկ վերը նշված էվկլիդեսի ալգորիթմով հաշված թիվը ցույցա տալիս ընդամենը պատասխանի վերևի սահմանը:
դուրսա գալիս, ես առանց իմանալու էվկլիդեսի ալգորիթմի մասին, բացահայտեցի այն :D :8

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

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

soultaker
13.11.2011, 11:41
բայց ինչի՞ խնդիրը նորմալ լուծում չունի

Որովհետև նման տիպի խնդիրների համար օպտիմալ ալգորիթմը չի լինում բազմանդամային բարդության, օրինակ Օ(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
13.11.2011, 12:00
Ճիշտն ասած չհասկացա քո ասածը: Դու ուզում ես ասես, որ կարող ա լինի կոնկրետ ուղղանկյունու չափսեր որ Վահեի կամ իմ գրածը սխալ պատասխան տա՞:
Թե՞ ուզում ես ասես, որ խնդրի տվյալներից կախված կարա մի դեպքում իմ գրածը ավելի արդյունավետ աշխատի, մյուս դեպքում Վահեի (բայց միևնույնն է՝ արդյունքը լինի ճիշտ):

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

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

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

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

soultaker
14.11.2011, 00:32
ալգորիթմն էլ չես կարում կազմես ???? :o սրանից պրիմիտիվ խնդիր չի կարա գոյություն ունենա բնության մեջ :8

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

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

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

http://www.akumb.am/showthread.php/61975-%D4%B1%D5%A3%D5%A1%D5%B0-%D5%A1%D5%AC%D5%A3%D5%B8%D6%80%D5%AB%D5%A9%D5%B4?highlight=%D4%B1%D5%A3%D5%A1%D5%B0+%D5%A1%D5%AC%D5%A3%D5%B8%D6%80%D5%AB%D5%A9%D5%B4

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

Վահե-91
14.11.2011, 10:10
5x6 չափի ուղղանկյուն եմ քեզ տալիս, դե եթե լավ ալգորիթմ կա ու էտքան պրիմիտիվա, դրանով կտրտի քառակուսիներ ու ասա քանի հատ ես ստանում:
սկզբում ուրիշ ձև էի պատկերացրել խնդիրը: Իմ ասած ալգորիթմը կկտրի 6 հատ քառակուսի:

Վահե-91
14.11.2011, 10:20
http://www.akumb.am/showthread.php/61975-%D4%B1%D5%A3%D5%A1%D5%B0-%D5%A1%D5%AC%D5%A3%D5%B8%D6%80%D5%AB%D5%A9%D5%B4?highlight=%D4%B1%D5%A3%D5%A1%D5%B0+%D5%A1%D5%AC%D5%A3%D5%B8%D6%80%D5%AB%D5%A9%D5%B4

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

Varzor
14.11.2011, 14:53
Էս ինչեր եք խոսքւմ, բան չեմ հասկանում :))
Եթե ուղղանկյան կողմերը բնական թվեր են` 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
14.11.2011, 15:49
5 ու 6 չափերի դեպքում էլ կարամ լուծում առաջարկեմ մինիմալ քանակի քառակուսի ստանալու համար

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

armen9494
14.11.2011, 15:50
Էս ինչեր եք խոսքւմ, բան չեմ հասկանում :))
Եթե ուղղանկյան կողմերը բնական թվեր են` 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
14.11.2011, 16:08
էդքան էլ պարզ չէր, բայց մի բան ասա՝ ըստ քո ալգորիթմի քանի՞ քառակուսի կստացվի 5x6 -ի դեպքում
5 - 2 հատ 3x3, 3 հատ 2x2

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

armen9494
14.11.2011, 16:34
5 - 2 հատ 3x3, 3 հատ 2x2

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

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

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

Varzor
14.11.2011, 17:00
Էտ խնդիրը կարծեմ NP-ա, այսինքն նորմալ լուծում չունի, իսկ վերը նշված էվկլիդեսի ալգորիթմով հաշված թիվը ցույցա տալիս ընդամենը պատասխանի վերևի սահմանը:]
Միշտ էլ լուծում ունի, քանի որ կողմերը ամբողջ թվեր են, քառակուսիների քանակն էլ վերջավոր է:

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

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

Վահե-91
14.11.2011, 18:19
համ էլ բլոկ-սխեման սխալ է գծված (երեք վերջ չի կաորղ ունենալ),
իմ գծածը այսպես կոչված բետա վերսիա կարելի է համարել :D շատ հեշտությամբ կարելիա մի վերջ ստանալ


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

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



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

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

Varzor
14.11.2011, 19:00
իմ գծածը այսպես կոչված բետա վերսիա կարելի է համարել :D շատ հեշտությամբ կարելիա մի վերջ ստանալ
Դե բետա տարբերակի համար բավականին լավ է ստացվել :))

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

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

Վահե-91
14.11.2011, 19:29
Ագահ ալգորիթմ (կամ ինչպես էր ծուլանում sonechka-ն) Beta 2 :B

http://4put.ru/pictures/small/216/666407.jpg (http://4put.ru/pictures/max/216/666407.jpg)

Varzor
14.11.2011, 20:22
կամ ինչպես էր ծուլանում sonechka-ն

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

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

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

soultaker
14.11.2011, 20:29
Sum(X(i) *i^2) = M*N

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

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

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

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

Վահե-91
14.11.2011, 22:05
Հարցը հենց նրանումա որ մինչև այժմ ֆորումում խնդիրը լուծող ալգորիթմ չի առաջարկվել (համենայն դեպս ես չեմ տեսել)
5 ու 6 չափերի դեպքում ասեցիր սխալ կաշխատի իմ առաջարկածը՝ ուղղեցի: Էլի սխալ աշխատելու տարբերակ կա , որ չես ասում ? :think :8

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

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

Վահե-91
14.11.2011, 22:22
Չեմ հիշում որ նոր բան առաջարկած լինես, որը ճիշտ կաշխատի 5x6-ի վրա: Ուղղակի ասեցիր որ հեշտա էտ ուղղելը, իսկ թե ոնց` երևի մենակ դու գիտես:
Ամեն դեպքում, մի՞թե քեզ թվումա որ 5x6-ը տենց հատուկ սատանայական չափա, որի վրա ամեն ինչ սխալա աշխատում, ու էտ դեպքը առանձին քննարկելով մնացած ամեն ինչ ճիշտ կաշխատի: Կամ կարաս արդյոք բացատրես թե ինչ պատճառովա քո առաջարկած մեթոդը ճիշտ:
բա էս ինչա ?
http://4put.ru/pictures/max/216/666407.jpg

soultaker
15.11.2011, 00:44
բա էս ինչա ?
http://4put.ru/pictures/max/216/666407.jpg

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

Վահե-91
15.11.2011, 09:56
Ճիշտն ասած բլոկսխեմայով չեմ հասկանում թե ինչա անում, բայց մեջը 5 ու 6 թվեր տեսա, նենց որ ինչ-որ բան խալտուրայա արած :)
էտ դեպքում ինքդ ինչ-որ մի բան առաջարկի :angry մենակ լսում ենք, որ ասում ես սխալա աշխատում :goblin

Varzor
15.11.2011, 10:24
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
...
ավելի մանրամասն այստեղ (http://mat.gsia.cmu.edu/orclass/integer/integer.html)

soultaker
15.11.2011, 10:59
Պայմանները թերի են: Ես արդեն նշել եմ

պիտի ավելացվեն ուղղանկյան կողմերի հետ կապված պայմանները` տվյալ պարագայում 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
...
ավելի մանրամասն այստեղ (http://mat.gsia.cmu.edu/orclass/integer/integer.html)

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

soultaker
15.11.2011, 11:04
էտ դեպքում ինքդ ինչ-որ մի բան առաջարկի :angry մենակ լսում ենք, որ ասում ես սխալա աշխատում :goblin

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

Varzor
15.11.2011, 11:06
Դրա համար էլ ասում եմ - նորմալ լուծում, ոչ թե ուղղակի լուծում: Նորմալ լուծում ասելով նկատի ունեմ մուտքային տվյալներից բազմանդամային կախում ունեցող, այսինքն այնպիսին, որ մեծ թվերի համար հնարավոր լինի արագ լուծել:
Մեծ թվերի համար ծրագրեր են աշխատացնում ;)
Հնարավոր չե տալ մի բանաձև, որի միջոցով ցանկացած թվերի համար հաշվարկը կկատարվի: Բայց ալգորիթմը արդեն վաղուց գոյություն ունի: Կահույքի արտադրամասերում օգտագործվող ծրագիրերը նմանատիպ ալգորիթմենորվ են աշխատում:

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

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

Varzor
15.11.2011, 11:13
Եթե ուշադիր կարդայիր գրածներս, կտեսնեիր որ ըստ իմ տեսակետի խնդիրը նորմալ լուծում չունի, այսինքն միակ բանը որ կարամ առաջարկեմ լրիվ դեպքերի քննարկումնա, որը երևի արդեն 10x10-ից հետո էլ համակարգչի վրա մի քանի վայրկյանում չի տեղավորվի: Իսկ որ նորմալ աշխատող լուծում գրեյիր, չէի ասի սխալա:
Քո տեսակետը սխալ է: Լրիվ դեպքերի քննարկում պետք չի:
Վաղուց արդեն կան գրված համապատասխան ծրագրեր, որոնք ունիվերսալ կերպով լուծում են ամբողջաթվային ծրագրավորման խնդիրները: Մնում է միայն ճիշտ նկարագրել նպատակային ֆունկցիան ու սահմանափակումները:

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

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

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

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

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

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

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

Varzor
15.11.2011, 12:00
Ենթադրենք վերցնում ենք 3x3 չափի ու բաժանում միհատանոցների` 9 հատ 1x1:
Նոր ավելացրածդ մյուս երկու սահմանափակումներից ելնելով`
9 * 1 <= 2 * 3 պայմանը տեղի չունի, բայց այդպիսի տրոհումը հնարավոր է:
Հնարավոր է, բայց սխալ է: 3x3-ը տրոհվում է 2x2+ 5x(1x1): Ոնց տեսնում ես պայմանը բավարարվում է ;)
Ու դա ևս մեկ քայլն է դեպի ճիշտ լուծումը: Փաստացի 9 հատ 1 երկարության կողմով քառակուսիները չբավարարեցին պայմանին, հետևաբար չեն կարող հանդիսանալ օպտիմալ լուծում :)
Ու ասեմ, որ պայմանների քանակը մենակ այդ երկուսը չի, էլի կան ;)

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

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

Ոնց ինքդ ես տեսնում իմ առաջարկած մոդելի մեջ նպատակային ֆունկցիան գծային է: Իսկ եթե պայմանների մեջ կան ոչ գծային պայմաններ, ապա դրանք հեշտությամբ ձևափոխվում են գծային պայմանների:
Նույնպես ստանդարտ տարբերակներ կան: Քառակուսային ծրագրավորման խնդիրները վերածվում են գծայինի, օրնակ Վոլֆի մեթոդով:
Բայց անկեղծ ասած հեչ հավես ու ժամանակ չունեմ ուսանող ժամանակվաս անցածները քրքրելու, մանավանդ որ հիմա գործնականում այլ կարգի խնդիրների վրա եմ աշխատում:
Այդ ամենը շատ լավ նկարագրված է գրականությունում, ինչպես նաև ուսանողներին բավականին լավ դասախոսություններ են կարդում: համենայն դեպս մեր ամբիոնում շատ լավ էլ նկարագրում ու բացատրում էին:

soultaker
15.11.2011, 13:02
Բառեր ենք խաղում ?

Ոնց ինքդ ես տեսնում իմ առաջարկած մոդելի մեջ նպատակային ֆունկցիան գծային է: Իսկ եթե պայմանների մեջ կան ոչ գծային պայմաններ, ապա դրանք հեշտությամբ ձևափոխվում են գծային պայմանների:
Նույնպես ստանդարտ տարբերակներ կան: Քառակուսային ծրագրավորման խնդիրները վերածվում են գծայինի, օրնակ Վոլֆի մեթոդով:
Բայց անկեղծ ասած հեչ հավես ու ժամանակ չունեմ ուսանող ժամանակվաս անցածները քրքրելու, մանավանդ որ հիմա գործնականում այլ կարգի խնդիրների վրա եմ աշխատում:
Այդ ամենը շատ լավ նկարագրված է գրականությունում, ինչպես նաև ուսանողներին բավականին լավ դասախոսություններ են կարդում: համենայն դեպս մեր ամբիոնում շատ լավ էլ նկարագրում ու բացատրում էին:

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

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

Դու կոնկրետ չէիր նշել որ այդ պայմանները վերաբերվում են միայն օպտիմալ տրոհումներին(9 հատ 1x1 օպտիմալ տրոհում չի, բայց ամեն դեպքում տրոհում է): Եթե միայն դրանց են վերաբերվում, ապա կարող եմ օրինակ բերել 2x8-ը, որտեղ օպտիմալ տարբերակով ստացվում է 4 հատ 2x2: Ըստ քո առաջադրած պայմաններից մեկի` Sum(X(i) *i) <= 2*M և նաև < = 2*N, բայց Sum-ը այս դեպքում կլինի 4 * 2 = 8, որը այդ պայմաններից մեկին չի բավարարում:

MSGM
15.11.2011, 13:48
Դինամիկ ծրագրավորումով կարելի ա ավելի օպտիմալ լուծել, քան Էվկլիդեսի ալգորթիմն ա լուծում:
F(M, N) = 1, եթե M = N
հակառակ դեպքում.
F(M, N) = min(min_i{F(i, N) + F(M - i, N)}, i = 1...(M - 1); min_i{F(M, i) + F(M, N - i)}, i = 1...(N - 1))

Բայց բացարձակ օպտիմալ բազմանդամային բարդության լուծում պիտի որ չլինի: Ստեղ (http://arxiv.org/PS_cache/math/pdf/9411/9411215v1.pdf) էլ պատասխանի մի քանի սահմաններ ա ապացուցած մի քանի դեպքերի համար:

soultaker
15.11.2011, 14:11
Դինամիկ ծրագրավորումով կարելի ա ավելի օպտիմալ լուծել, քան Էվկլիդեսի ալգորթիմն ա լուծում:
F(M, N) = 1, եթե M = N
հակառակ դեպքում.
F(M, N) = min(min_i{F(i, N) + F(M - i, N)}, i = 1...(M - 1); min_i{F(M, i) + F(M, N - i)}, i = 1...(N - 1))

Բայց բացարձակ օպտիմալ բազմանդամային բարդության լուծում պիտի որ չլինի: Ստեղ (http://arxiv.org/PS_cache/math/pdf/9411/9411215v1.pdf) էլ պատասխանի մի քանի սահմաններ ա ապացուցած մի քանի դեպքերի համար:

Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?

MSGM
15.11.2011, 14:18
Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?
Իհարկե հնարավոր ա, դրա համար էլ էտ լուծումն էլ բացարձակ օպտիմալ չի, բայց Էվկլիդեսի ալգորիթմից ավելի օպտիմալ ա (վատագույն դեպքում նույն արդյունքը պիտի տա):

Varzor
15.11.2011, 14:26
Դու կոնկրետ չէիր նշել որ այդ պայմանները վերաբերվում են միայն օպտիմալ տրոհումներին(9 հատ 1x1 օպտիմալ տրոհում չի, բայց ամեն դեպքում տրոհում է): Եթե միայն դրանց են վերաբերվում, ապա կարող եմ օրինակ բերել 2x8-ը, որտեղ օպտիմալ տարբերակով ստացվում է 4 հատ 2x2: Ըստ քո առաջադրած պայմաններից մեկի` Sum(X(i) *i) <= 2*M և նաև < = 2*N, բայց Sum-ը այս դեպքում կլինի 4 * 2 = 8, որը այդ պայմաններից մեկին չի բավարարում:
Բայց ինչ կարիք կար կոնկրետ նշելու եթե խնդրի դրվածքն էր այդպիսին?` հաշվել հնարավոր մինիմալ քառակուսիների քանակը, որոնց հնարավոր է բաժանել MxN ուղղանկյունը:
Ինչ խնդիր լուծում էինք, դրա համար եմ գրել, հո ուրիշ խնդիր չեմ լուծում?
Ընդամենը քառակուսիների բաժանելու խնդիրը մի բանաձևով լուծվում է ` MxN հատ 1 երկարությամբ կողմով քառակուսիներ :)

Varzor
15.11.2011, 14:31
Հա, էտ հղումը ավելի համոզեց որ բազմանդամային բարդության լուծում չկա:
Դինամիկ ծրագրավորման բանաձևի հետ կապված դու վերցնում ես երկու մասի ես բաժանում ուղղանկյունը, բայց հնարավոր չի արդյոք որ տենց գիծ չլինի օպտիմալի ժամանակ?
Բայց էդ հղումը հստակ ասում է, թե որն է այդ քառակուսիների վերին սահմանը:
Ճիշտ է միարժեք լուծում չկա: Կախված ուղղանկյան չափերից այդ լուծումները կարող են լինել մի քանիսը` բաժանման տեսանկյունից, բայց քանակի տեսանկյունից` միշտ էլ մինիմալ քանակը մեկ թիվ է ստացվում:

Varzor
15.11.2011, 14:33
Իհարկե հնարավոր ա, դրա համար էլ էտ լուծումն էլ բացարձակ օպտիմալ չի, բայց Էվկլիդեսի ալգորիթմից ավելի օպտիմալ ա (վատագույն դեպքում նույն արդյունքը պիտի տա):
Այդ պարագայում կարելի է կիրառել կոմպլեքս ալգորիթմեր` կողմերի տարբեր հարաբերակցությունների համար:
Համենայն դեպս այդ մինիմալ քանակը միշտ էլ գոյություն ունի, ուղղակի կախված մուտքային տվյալներից կարող են տարբերվել լուծման քայլերն ու ալգորիթմերը:

Ստեղ հնչած խնդրի պարագայում ընդամենը պետք է հաշվել այդ քառակուսիների քանակը: Ու քո տված հղումից օգտվելով կարելի է դա կատարել:

soultaker
15.11.2011, 14:46
Բայց էդ հղումը հստակ ասում է, թե որն է այդ քառակուսիների վերին սահմանը:
Ճիշտ է միարժեք լուծում չկա: Կախված ուղղանկյան չափերից այդ լուծումները կարող են լինել մի քանիսը` բաժանման տեսանկյունից, բայց քանակի տեսանկյունից` միշտ էլ մինիմալ քանակը մեկ թիվ է ստացվում:
Այս դեպքում քո առաջարկած լուծումը որպես ինչ էիր ներկայացնում? ՈՐՈՇ դեպքերի համար լուծում?


Այդ պարագայում կարելի է կիրառել կոմպլեքս ալգորիթմեր` կողմերի տարբեր հարաբերակցությունների համար:
Հիմա գծային ծրագրավորումով լուծվումա թե չէ? :)


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

MSGM
15.11.2011, 14:53
Այդ պարագայում կարելի է կիրառել կոմպլեքս ալգորիթմեր` կողմերի տարբեր հարաբերակցությունների համար:
Համենայն դեպս այդ մինիմալ քանակը միշտ էլ գոյություն ունի, ուղղակի կախված մուտքային տվյալներից կարող են տարբերվել լուծման քայլերն ու ալգորիթմերը:

Ստեղ հնչած խնդրի պարագայում ընդամենը պետք է հաշվել այդ քառակուսիների քանակը: Ու քո տված հղումից օգտվելով կարելի է դա կատարել:

Խնդիրը հետևյալն ա.
մուտքային տվյալներ - M և N
ելքային թիվ - K, որը քառակուսիների մինիմալ քանակն ա, որով կարելի ա ծածկել M և N կողմերով ուղղանկյունը:
Ցանկացած M-ի և N-ի համար գոյություն ունի միակ ելքային թիվ:
Էս թեմայում նշված ալգորիթմներից ոչ մեկը խնդիրը չի լուծում: Ավելին, իմ ու soultaker-ի կարծիքով էտ խնդիրը էքսպոնենցիալից ավելի լավ բարդություն ունեցող լուծում չունի: Իհարկե կարելի ա էքսպոնենցիալ բարդությամբ լուծումը օպտիմիզացնել տարբեր սահմանների մասին ինֆորմացիայի, Էվկլիդեսի ու դինամիկ ծրագրավորման ալգորիթմերից ստացված ինֆորմացիայի միջոցով, բայց բարդությունը մեկ ա էքսպոնենցիալ ա մնում, ինչը նշանակում ա, որ էտ լուծումը պրակտիկ չի լինի ոչ փոքր մուտքային տվյալների համար (շատ ժամանակատար կլինի): Ուրիշ բան, եթե խնդիրը M-ի և N-ի համար ինչքան հնարավոր է քիչ (բայց ոչ բացարձակ մինիմալ) քառակուսիներով ծածկում գտնելն ա: Էտ դեպքում Էվկլիդեսի ալգորիթմն էլ կարա պետք գա, իմ նշածն ել:

Varzor
15.11.2011, 15:03
Խնդիրը հետևյալն ա.
մուտքային տվյալներ - M և N
ելքային թիվ - K, որը քառակուսիների մինիմալ քանակն ա, որով կարելի ա ծածկել M և N կողմերով ուղղանկյունը:
Ցանկացած M-ի և N-ի համար գոյություն ունի միակ ելքային թիվ:
Էս թեմայում նշված ալգորիթմներից ոչ մեկը խնդիրը չի լուծում: Ավելին, իմ ու soultaker-ի կարծիքով էտ խնդիրը էքսպոնենցիալից ավելի լավ բարդություն ունեցող լուծում չունի: Իհարկե կարելի ա էքսպոնենցիալ բարդությամբ լուծումը օպտիմիզացնել տարբեր սահմանների մասին ինֆորմացիայի, Էվկլիդեսի ու դինամիկ ծրագրավորման ալգորիթմերից ստացված ինֆորմացիայի միջոցով, բայց բարդությունը մեկ ա էքսպոնենցիալ ա մնում, ինչը նշանակում ա, որ էտ լուծումը պրակտիկ չի լինի ոչ փոքր մուտքային տվյալների համար (շատ ժամանակատար կլինի): Ուրիշ բան, եթե խնդիրը M-ի և N-ի համար ինչքան հնարավոր է քիչ (բայց ոչ բացարձակ մինիմալ) քառակուսիներով ծածկում գտնելն ա: Էտ դեպքում Էվկլիդեսի ալգորիթմն էլ կարա պետք գա, իմ նշածն ել:
Այ հիմա համամիտ եմ :)
Չկա այնպիսի "ռապիդ" ալգորիթմ, որը գծային, կամ գոներ պարզագույն քառակուսային բնույթի լինի: Ճշգրիտ լուծոը ստանալու համար, որքան մեծանում է ուղղանկյան չափսերը, այնքան մեծանում է իտերացիաների քանակը:
Ճիշտ է, մեծ կողմերի համար կարելի է մոտարկումների և ապրոքսիմացիաների միջոցով լոգարիթմական տեսը բերել գծայինի, բայց դա իրոք որ բավականին ռեսուրսատար է (համակարգչի համար) ու ժամանակի տեսանկյունից ոչ օպտիմալ:

Կենցաղային խնդիրների լուծման համար ուղղանկյան չափերը երբեք էլ այդքան մեծ չեն լինում, դրա համար էլ բազմաթիվ պատրաստի ծրագրեր կան ավելի խիստ մասնավորեցված խնդիրների լուծման համար (օրինակ` սալիկապատման հաշվարկ, սենյակների տեղաբաշխման հաշվարկ և այլն):

Հ.Գ.
Բայց չեմ հասկանում, թե ինչի համար պիտի այդպիսի "աբստրակտ" խնդիր տային` առանց ուղղանկյան չափերի սահմանափակման :think

Վահե-91
15.11.2011, 15:11
Բայց չեմ հասկանում, թե ինչի համար պիտի այդպիսի "աբստրակտ" խնդիր տային` առանց ուղղանկյան չափերի սահմանափակման :think
տարօրինակ մարդա sonechka-ն, էսքան խոսում ենք, իրա խնդիրն ենք լուծում կամ քննարկում, մի անգամ չարձագանքեց :o կարողա էլ պետք չի ՞ ինչի ենք հավայի տանջվում ՞ :) մի հատ պետքա հարցնել ինքը որերորդ կուրսա, կարողա դասախոսն էլ չգիտի ինչ բարդության խնդիրա տվել :D
1 կուրսում դասախոսներիցս մեկը կուրսային էր տվել, համարյա վերջացնում էի, պարզվեց տվյալներից մեկի սխալ լինելու պատճառով այլևս հնարավոր չէր շարունակել, նորից սկսեցի ուրիշ տվյալով :8

Varzor
15.11.2011, 15:30
տարօրինակ մարդա sonechka-ն, էսքան խոսում ենք, իրա խնդիրն ենք լուծում կամ քննարկում, մի անգամ չարձագանքեց :o կարողա էլ պետք չի ՞ ինչի ենք հավայի տանջվում ՞ :) մի հատ պետքա հարցնել ինքը որերորդ կուրսա, կարողա դասախոսն էլ չգիտի ինչ բարդության խնդիրա տվել :D
1 կուրսում դասախոսներիցս մեկը կուրսային էր տվել, համարյա վերջացնում էի, պարզվեց տվյալներից մեկի սխալ լինելու պատճառով այլևս հնարավոր չէր շարունակել, նորից սկսեցի ուրիշ տվյալով :8
Չի բացառվում :) Պոլիտեխնիկում ամեն ինչ հնարավոր է :))

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

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

Varzor
15.11.2011, 16:25
Այս դեպքում քո առաջարկած լուծումը որպես ինչ էիր ներկայացնում? ՈՐՈՇ դեպքերի համար լուծում?
Հիմա գծային ծրագրավորումով լուծվումա թե չէ? :)
Եթե լուծում է առաջարկվում, պիտի առաջարկվի կոնկրետ ալգորիթմ, ոչ թե նենց, որ դեպքերի մի մասի վրա ճիշտ աշխատի, մնացած մասի համար էլ ասեն լավ, սրանց համար էլ մի ուրիշ ձևով կանենք, կանցնի կգնա:
Իմ առաջարկած լուծումը կոնկրետ վերաբերվում էր 5x6-ի խնդրին: Այո, որոշ դեպքերի համար լուծում (ֆիքսված չափողականության համար):
Կոմպլեքս ալգորիթմերը նույն խնդրի լուծման համար կիրառվող մի քանի ալգորիթմեր են: Ասենք մի ալգորիթմով հաշվում ես մեկը, մյուսով մյուսը: Ու խնդրի լուծումը սկսելոց առաջ ընտրանքով ընտրում ես ալգորիթմը :)
Սենց ասեմ. Ամեն MxN-ի համար կարելի է կառուցել առանձին ալգորիթմ: Ու այն կարող է չգործել այլ արժեքների համար:
Ես խնդրի լուծմանը միջամտել եմ այս (http://www.akumb.am/showthread.php/61975-Ագահ-ալգորիթմ?p=2304377&viewfull=1#post2304377)գրառումից հետո, որպես տրամաբանական շարունակություն:
Ու այդ տարբերակի համար էլ հստակ լագորիթմ եմ առաջարկել:

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

soultaker
15.11.2011, 17:50
Իմ առաջարկած լուծումը կոնկրետ վերաբերվում էր 5x6-ի խնդրին: Այո, որոշ դեպքերի համար լուծում (ֆիքսված չափողականության համար):
Կոմպլեքս ալգորիթմերը նույն խնդրի լուծման համար կիրառվող մի քանի ալգորիթմեր են: Ասենք մի ալգորիթմով հաշվում ես մեկը, մյուսով մյուսը: Ու խնդրի լուծումը սկսելոց առաջ ընտրանքով ընտրում ես ալգորիթմը :)
Սենց ասեմ. Ամեն MxN-ի համար կարելի է կառուցել առանձին ալգորիթմ: Ու այն կարող է չգործել այլ արժեքների համար:
Ես խնդրի լուծմանը միջամտել եմ այս (http://www.akumb.am/showthread.php/61975-Ագահ-ալգորիթմ?p=2304377&viewfull=1#post2304377)գրառումից հետո, որպես տրամաբանական շարունակություն:
Ու այդ տարբերակի համար էլ հստակ լագորիթմ եմ առաջարկել:
Քո մոտեցումը հասկացա, բայց եթե այդպես նայենք, կամայական միարժեք պատասխան ունեցող խնդրի համար էլ կամայական կոնկրետ ֆիքսված մուտքային տվյալների համար գոյություն ունի մի ալգորիթմ, որը տալիս է ճիշտ պատասխան այդ դեպքում, և սխալ է աշխատում մյուս դեպքերում:

Varzor
15.11.2011, 18:16
Քո մոտեցումը հասկացա, բայց եթե այդպես նայենք, կամայական միարժեք պատասխան ունեցող խնդրի համար էլ կամայական կոնկրետ ֆիքսված մուտքային տվյալների համար գոյություն ունի մի ալգորիթմ, որը տալիս է ճիշտ պատասխան այդ դեպքում, և սխալ է աշխատում մյուս դեպքերում:
Ճիշտ է :)
Ես էլ հասկացել եմ քո մոտեցումը` միատեսակ տրամաբանությամբ ընդհանուր ունիվերսալ ալգորիթմ չկա, որի բարդության աստիճանը գծային լինի: Ու դա այդպես է որ կա, միանշանակ համամիտ եմ :)

Rafik
13.02.2013, 19:35
Երևի մաքսիմալ?