PDA

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



Sonechka
11.11.2011, 22:51
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են NxMբնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը: Այս խնդիրը կարելիէ լուծել ագահ ալգորիթմի միջոցով՝ամեն քայլում կտրում ենք մաքսիմալ հնարավոր քառակուսին (ուղղանկյունիցNxM, N<M կտրում ենք NxN քառակուսին):
Պետք է ցույց տալ այս ագահ ալգորիթմի և Էվկլիդեսի ալգորիթմի կապը:

armen9494
12.11.2011, 09:44
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են NxMբնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը: Այս խնդիրը կարելիէ լուծել ագահ ալգորիթմի միջոցով՝ամեն քայլում կտրում ենք մաքսիմալ հնարավոր քառակուսին (ուղղանկյունիցNxM, N<M կտրում ենք NxN քառակուսին):
Պետք է ցույց տալ այս ագահ ալգորիթմի և Էվկլիդեսի ալգորիթմի կապը:

իսկ էվկլիդեսի ալգորիթմը ո՞րն է:8

soultaker
12.11.2011, 19:13
Տրված է ուղղանկյուն, որի կողմերը արտահայտված են NxMբնական թվերով: Այն պետք է բաժանել մինիմալ քանակությամբ քառակուսիների:Մեզանից պահանջվում է գտնել ստացված քառակուսիների քանակը: Այս խնդիրը կարելիէ լուծել ագահ ալգորիթմի միջոցով՝ամեն քայլում կտրում ենք մաքսիմալ հնարավոր քառակուսին (ուղղանկյունիցNxM, N<M կտրում ենք NxN քառակուսին):
Պետք է ցույց տալ այս ագահ ալգորիթմի և Էվկլիդեսի ալգորիթմի կապը:

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

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