Էվկլիդեսյան ալգորիթմի ուսուցում դպրոցում. Էվկլիդեսի ալգորիթմ - Գտնել ամենամեծ ընդհանուր բաժանարարը
Լայնորեն տարածված է էլեկտրոնային առևտրում։ Նաև ալգորիթմն օգտագործվում է գծային Դիոֆանտին հավասարումների լուծման, շարունակական կոտորակների կառուցման ժամանակ Շտուրմի մեթոդով։ Էվկլիդեսի ալգորիթմը ժամանակակից թվերի տեսության թեորեմների ապացուցման հիմնական գործիքն է, ինչպիսիք են Լագրանժի թեորեմը չորս քառակուսիների գումարի մասին և թվաբանության հիմնարար թեորեմը։
Հանրագիտարան YouTube
1 / 5
✪ Մաթ. Բնական թվեր. Էվկլիդեսի ալգորիթմ. Ֆոքսֆորդի առցանց ուսուցման կենտրոն
✪ Էվկլիդեսի ալգորիթմը
✪ Էվկլիդեսի ալգորիթմը, արագ ճանապարհգտնել gcd
✪ Մաթեմատիկա 71. Մեծագույն ընդհանուր բաժանարար: Էվկլիդեսի ալգորիթմ - Ժամանցային գիտությունների ակադեմիա
✪ 20 while Loop Euclid Python ալգորիթմ
սուբտիտրեր
Պատմություն
Հին հույն մաթեմատիկոսներն այս ալգորիթմն են անվանել ἀνθυφαίρεσις կամ ἀνταναίρεσις - «փոխադարձ հանում». Այս ալգորիթմը չի հայտնաբերվել Էվկլիդեսի կողմից, քանի որ այն արդեն նշված է ՏոպեկաԱրիստոտել. Էվկլիդեսի «տարրերում» այն նկարագրված է երկու անգամ՝ VII գրքում երկու բնական թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու և X գրքում երկու միատարր մեծությունների ամենամեծ ընդհանուր չափումը գտնելու համար։ Երկու դեպքում էլ տրված է ալգորիթմի երկրաչափական նկարագրությունը երկու հատվածների «ընդհանուր չափումը» գտնելու համար։
Նկարագրություն
Էվկլիդեսի ալգորիթմը ամբողջ թվերի համար
Թող a (\displaystyle a)Եվ b (\displaystyle b)- միևնույն ժամանակ զրոյի չհավասար թվեր և թվերի հաջորդականություն
a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \կետեր \ >r_(n))որոշվում է նրանով, որ յուրաքանչյուրը r k (\displaystyle r_(k))- սա նախորդ թիվը նախորդի վրա բաժանելու մնացորդն է, իսկ նախավերջինը՝ վերջինի վրա, այսինքն.
a = b q 0 + r 1, (\displaystyle a=bq_(0)+r_(1),) b = r 1 q 1 + r 2 , (\displaystyle b=r_(1)q_(1)+r_(2),) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3),) ⋯ (\displaystyle \cdots) r k − 2 = r k − 1 q k − 1 + r k , (\ցուցադրման ոճ r_(k-2)=r_(k-1)q_(k-1)+r_(k),) ⋯ (\displaystyle \cdots) r n − 2 = r n − 1 q n − 1 + r n , (\ցուցադրման ոճ r_(n-2)=r_(n-1)q_(n-1)+r_(n),) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)Հետո gcd( ա, բ), ամենամեծ ընդհանուր բաժանարարը աԵվ բ, հավասար է r n , այս հաջորդականության վերջին ոչ զրոյական անդամը:
Գոյությունայդպիսին r 1 , r 2 , ..., r n , այսինքն՝ մնացորդով բաժանման հնարավորություն մվրա nցանկացած ամբողջության համար մև ամբողջ n≠ 0-ն ապացուցվում է ինդուկցիայի միջոցով մ.
Կոռեկտությունայս ալգորիթմը բխում է հետևյալ երկու հայտարարություններից.
- Թող ա = բ⋅ք + r, ապա gcd(a, b) = gcd(b, r):
Ապացույց
- GCD ( r, 0) = rցանկացած ոչ զրոյի համար r(քանի որ 0-ը բաժանվում է զրոյից բացի ցանկացած ամբողջ թվի վրա):
Էվկլիդեսի երկրաչափական ալգորիթմը
Թող տրվի երկարության երկու հատված աԵվ բ. Ավելի փոքր հատվածը հանեք մեծ հատվածից և ավելի մեծ հատվածը փոխարինեք ստացված տարբերությամբ: Կրկնեք այս գործողությունը, մինչև հատվածները հավասարվեն: Եթե դա տեղի ունենա, ապա սկզբնական հատվածները համադրելի են, և ստացված վերջին հատվածը նրանց ամենամեծ ընդհանուր չափումն է: Եթե չկա ընդհանուր չափում, ապա գործընթացը անսահման է։ Այս ձևով ալգորիթմը նկարագրված է Էվկլիդեսի կողմից և իրականացվում է կողմնացույցի և քանոնի միջոցով:
Օրինակ
Պատկերացնելու համար Էվկլիդես ալգորիթմը կօգտագործվի gcd-ը գտնելու համար ա= 1071 և բ= 462. Սկզբից հանեք 462-ի բազմապատիկը 1071-ից մինչև ստանանք 462-ից փոքր տարբերություն: Մենք պետք է երկու անգամ հանենք 462-ը, ( ք 0 = 2), մնալով 147 մնացորդով.
1071 = 2 × 462 + 147:
Այնուհետև մենք 462-ից հանում ենք 147-ի բազմապատիկ, մինչև ստացվի 147-ից փոքր տարբերություն: Մենք պետք է երեք անգամ հանենք 147-ը ( ք 1 = 3), մնալով 21 մնացորդով.
462 = 3 x 147 + 21:
Այնուհետև մենք 147-ից հանում ենք 21-ի բազմապատիկ, մինչև ստացվի 21-ից փոքր տարբերություն: Մենք պետք է յոթ անգամ հանենք 21-ը ( ք 2 = 7), մնալով առանց մնացորդի.
147 = 7 x 21 + 0:
Այսպիսով հաջորդականությունը a > b > r 1 > r 2 > r 3 > … > r n-ն այս կոնկրետ դեպքում կունենա հետևյալ տեսքը.
1071 > 462 > 147 > 21.
Քանի որ վերջին մնացորդը զրո է, ալգորիթմն ավարտվում է 21-ով և gcd(1071, 462) = 21:
Աղյուսակային ձևով քայլերը հետևյալն էին.
Դիմումներ
Ընդլայնված Էվկլիդեսի ալգորիթմը և Բեզութի հարաբերությունը
Բանաձևեր համար r i (\displaystyle r_(i))կարելի է վերաշարադրել այսպես.
r 1 = a + b (− q 0) (\ցուցադրման ոճ r_(1)=a+b(-q_(0))) r 2 = b − r 1 q 1 = a (− q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots) GCD (a , b) = r n = a s + b t (\displaystyle (a,b)=r_(n)=as+bt)Այստեղ սԵվ տամբողջ. Ամենամեծ ընդհանուր բաժանարարի այս ներկայացումը կոչվում է Բեզութի հարաբերություն, իսկ թվերը. սԵվ տ- գործակիցներ-Bezu . Բեզութի հարաբերությունը առանցքայինն է Էվկլիդեսի լեմայի և թվաբանության հիմնական թեորեմի ապացուցման մեջ։
Շարունակվող կոտորակներ
Էվկլիդեսի ալգորիթմը բավականին սերտորեն կապված է շարունակվող կոտորակների հետ։ Վերաբերմունք ա/բընդունում է կոտորակի շարունակական ներկայացում.
a b = [ q 0; q 1 , q 2 , ⋯ , q n ] (\ցուցադրման ոճ (\frac (a)(b))=).Այս դեպքում առանց վերջին անդամի շարունակվող կոտորակը հավասար է Բեզութի գործակիցների հարաբերությանը. տ/սվերցված մինուս նշանով.
[ q 0 ; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).Էվկլիդյան ալգորիթմը սահմանող հավասարումների հաջորդականությունը կարող է վերաշարադրվել հետևյալ ձևով.
a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N (\ցուցադրման ոճ (\սկիզբ(հավասարեցված)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\վերջ (հավասարեցված)))Հավասարման աջ կողմի վերջին անդամը միշտ հավասար է հետևյալ հավասարման ձախ կողմի փոխադարձին. Այսպիսով, առաջին երկու հավասարումները կարող են համակցվել հետևյալ ձևով.
a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1)) (r_(0))))))Երրորդ հավասարությունը կարող է օգտագործվել արտահայտության հայտարարի փոխարինման համար r 1 /r 0, մենք ստանում ենք.
a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))Վերջին մնացորդի հարաբերակցությունը r կ /r կ−1-ը միշտ կարելի է փոխարինել՝ օգտագործելով հաջորդականության հաջորդ հավասարությունը, և այդպես շարունակվում է մինչև վերջին հավասարումը: Արդյունքը շարունակական կոտորակն է.
a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1, q 2, …, q N ] (\ցուցադրման ոճ (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_ (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N))))))))))=)Ընդհանրացված Էվկլիդեսի ալգորիթմ բազմանդամների համար
Էվկլիդեսի Ալգորիթմը և Ընդլայնված Էվկլիդեսի Ալգորիթմը բնականաբարընդհանրացնում է բազմանդամների օղակին կ[x] մեկ փոփոխականից կամայական դաշտի վրա կ, քանի որ նման բազմանդամների համար սահմանված է մնացորդով բաժանման գործողությունը։ Բազմանդամների համար Էվկլիդեսի ալգորիթմն իրականացնելիս, ինչպես ամբողջ թվերի համար Էվկլիդեսի ալգորիթմը, ստացվում է բազմանդամ մնացորդների հաջորդականություն (PRS):
Մատանու օրինակ Զ[x]
Թող cont(f) ըստ սահմանման լինի f(x) բազմանդամի գործակիցների gcd-ն Z[x]-ից - բովանդակությունըբազմանդամ. f(x) cont(f)-ի բաժանելու գործակիցը կոչվում է պարզունակ մաս f(x) բազմանդամը և նշանակվում է primpart(f(x)): Այս սահմանումները անհրաժեշտ կլինեն երկու բազմանդամների gcd-ը գտնելու համար p 1 (x)Եվ p 2 (x)ռինգում Z[x]. Ամբողջ թվերի վրա բազմանդամների համար ճշմարիտ է հետևյալը.
C o n t ((\displaystyle cont()ՆՈԴՆՈԴ ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)), cont(p_(2)(x))\),)
P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\ցուցադրման ոճ \(p_(1)(x),p_(2)(x)\))=) GCD ( p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) ։ (\displaystyle \(primpart(p_(1)(x)),primpart(p_(2)(x))\):)
Այսպիսով, երկու կամայական բազմանդամների gcd-ն գտնելու խնդիրը կրճատվում է պարզունակ բազմանդամների gcd-ն գտնելու խնդրին։
Թող լինեն երկու պարզունակ բազմանդամ p 1 (x) և p 2 (x) Z[x]-ից, որոնց համար նրանց հզորությունների միջև կապը բավարարված է՝ deg(p 1 (x)) = m և deg(p 2 (x): )) = n, m > n. Բազմանդամների մնացորդով բաժանումը ենթադրում է դիվիդենտի ամենաբարձր գործակցի ճշգրիտ բաժանելիությունը բաժանարարի ամենաբարձր գործակցի վրա, ընդհանուր դեպքում մնացորդով բաժանումը չի կարող կատարվել։ Հետևաբար, ներդրվում է կեղծ բաժանման ալգորիթմ, որը, այնուամենայնիվ, թույլ է տալիս ստանալ կեղծ քանակություն և կեղծ մնացորդ (պրեմ), որոնք իրենք կպատկանեն ամբողջ թվերի բազմանդամների բազմությանը։
Կեղծբաժանում ասելով նկատի ունենք, որ բուն բաժանմանը նախորդում է բազմանդամի բազմապատկումը. p 1 (x) (\displaystyle p_(1)(x))վրա (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1)), այն է
L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg (r (x))< deg (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}
Որտեղ q (x) (\displaystyle q(x))Եվ r (x) (\displaystyle r(x))- համապատասխանաբար կեղծ մասնակի և կեղծ մնացորդ:
Այսպիսով, p 1 (x) , p 2 (x) ∈ Z [ x] (\ցուցադրման ոճ p_(1)(x),p_(2)(x)\in Z[x]), ընդ որում deg (p 1) = n 1 ≥ deg (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). Այնուհետև Էվկլիդեսի ալգորիթմը բաղկացած է հետևյալ քայլերից.
1. GCD պարունակության հաշվարկ.
C:= (\displaystyle c:=) GCD (c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)), cont(p_(2))\)).
2. Պարզունակ մասերի հաշվարկ.
P 1 ′ (x) := p r i m p a r t (p 1 (x)); (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)
P 2 ′ (x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)
3. Բազմանանդամների մնացորդների հաջորդականության կառուցում.
P 1 ′ (x) , (\displaystyle p_(1)"(x),)
P 2 ′ (x) , (\displaystyle p_(2)"(x),)
P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2 )"(x)))
P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (x)))
P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x ))))
. . . (\ցուցադրման ոճ...)
P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\ցուցադրման ոճ p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)):)
Մեծագույն ընդհանուր բաժանարար
Սահմանում 2
Եթե a բնական թիվը բաժանվում է $b$ բնական թվի վրա, ապա $b$-ը կոչվում է $a$-ի բաժանարար, իսկ $a$ թիվը՝ $b$-ի բազմապատիկ։
Թող $a$ և $b$ լինեն բնական թվեր։ $c$ թիվը կոչվում է ընդհանուր բաժանարար և $a$-ի և $b$-ի համար:
$a$ և $b$ թվերի ընդհանուր բաժանարարների բազմությունը վերջավոր է, քանի որ այս բաժանարարներից և ոչ մեկը չի կարող $a$-ից մեծ լինել։ Սա նշանակում է, որ այս բաժանարարներից կա ամենամեծը, որը կոչվում է $a$ և $b$ թվերի ամենամեծ ընդհանուր բաժանարար, և այն նշելու համար օգտագործվում է նշում.
$gcd \ (a;b) \ կամ \ D \ (a;b) $
Երկու թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու համար.
- Գտեք 2-րդ քայլում հայտնաբերված թվերի արտադրյալը: Ստացված թիվը կլինի ցանկալի ամենամեծ ընդհանուր բաժանարարը:
Օրինակ 1
Գտե՛ք $121$ և $132.$ թվերի gcd-ն
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Ընտրեք այն թվերը, որոնք ներառված են այս թվերի ընդլայնման մեջ
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
Գտեք 2-րդ քայլում հայտնաբերված թվերի արտադրյալը: Ստացված թիվը կլինի ցանկալի ամենամեծ ընդհանուր բաժանարարը:
$gcd=2\cdot 11=22$
Օրինակ 2
Գտեք $63$ և $81$ միանվագների GCD:
Մենք կգտնենք ըստ ներկայացված ալգորիթմի. Սրա համար:
Եկեք թվերը տարրալուծենք պարզ գործոնների
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Մենք ընտրում ենք այն թվերը, որոնք ներառված են այս թվերի ընդլայնման մեջ
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
Գտնենք 2-րդ քայլում հայտնաբերված թվերի արտադրյալը: Ստացված թիվը կլինի ցանկալի ամենամեծ ընդհանուր բաժանարարը:
$gcd=3\cdot 3=9$
Դուք կարող եք գտնել երկու թվերի GCD-ն այլ կերպ՝ օգտագործելով թվերի բաժանարարների բազմությունը:
Օրինակ 3
Գտեք $48$ և $60$ թվերի gcd-ն։
Լուծում:
Գտեք $48$-ի բաժանարարների բազմությունը՝ $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\աջ\)$
Հիմա եկեք գտնենք $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\աջ\)$ բաժանարարների բազմությունը
Գտնենք այս բազմությունների խաչմերուկը՝ $\left\((\rm 1,2,3,4,6,12)\right\)$ - այս բազմությունը կորոշի $48$ և $60 թվերի ընդհանուր բաժանարարների բազմությունը։ $. Այս հավաքածուի ամենամեծ տարրը կլինի $12$ թիվը: Այսպիսով, $48$-ի և $60$-ի ամենամեծ ընդհանուր բաժանարարը $12$ է:
ԱՕԿ-ի սահմանումը
Սահմանում 3
բնական թվերի ընդհանուր բազմապատիկ$a$-ը և $b$-ը բնական թիվ են, որը և $a$-ի և $b$-ի բազմապատիկն է:
Թվերի ընդհանուր բազմապատիկները այն թվերն են, որոնք առանց մնացորդի բաժանվում են բնագրի վրա։ Օրինակ՝ $25$ և $50$ թվերի համար ընդհանուր բազմապատիկները կլինեն $50,100,150,200$ և այլն։
Ամենափոքր ընդհանուր բազմապատիկը կկոչվի ամենափոքր ընդհանուր բազմապատիկը և կնշանակվի LCM$(a;b)$ կամ K$(a;b).$-ով:
Երկու թվերի LCM-ն գտնելու համար անհրաժեշտ է.
- Թվերը տարրալուծիր պարզ գործակիցների
- Դուրս գրի՛ր առաջին թվի մաս կազմող գործոնները և դրանց ավելացրո՛ւ այն գործոնները, որոնք երկրորդի մաս են կազմում և չեն գնում առաջինին.
Օրինակ 4
Գտեք $99$ և $77$ թվերի LCM:
Մենք կգտնենք ըստ ներկայացված ալգորիթմի. Սրա համար
Թվերը տարրալուծիր պարզ գործակիցների
$99=3\cdot 3\cdot 11$
Գրեք առաջինում ներառված գործոնները
դրանց ավելացրեք գործոններ, որոնք երկրորդի մաս են կազմում և չեն գնում առաջինին
Գտեք 2-րդ քայլում հայտնաբերված թվերի արտադրյալը: Ստացված թիվը կլինի ցանկալի նվազագույն ընդհանուր բազմապատիկը
$LCC=3\cdot 3\cdot 11\cdot 7=693$
Թվերի բաժանարարների ցուցակներ կազմելը հաճախ շատ ժամանակատար է։ GCD-ն գտնելու միջոց կա, որը կոչվում է Էվկլիդեսի ալգորիթմ:
Հայտարարություններ, որոնց վրա հիմնված է Էվկլիդեսի ալգորիթմը.
Եթե $a$ և $b$-ը բնական թվեր են, և $a\vdots b$, ապա $D(a;b)=b$
Եթե $a$-ը և $b$-ն այնպիսի բնական թվեր են, որ $b
Օգտագործելով $D(a;b)= D(a-b;b)$-ը, մենք կարող ենք հաջորդաբար կրճատել դիտարկվող թվերը, մինչև հասնենք այնպիսի թվերի, որ դրանցից մեկը բաժանվի մյուսի վրա: Այնուհետև այս թվերից փոքրը կլինի ցանկալի ամենամեծ ընդհանուր բաժանարարը $a$ և $b$ թվերի համար:
GCD-ի և LCM-ի հատկությունները
- $a$-ի և $b$-ի ցանկացած ընդհանուր բազմապատիկ բաժանվում է K$(a;b)$-ի
- Եթե $a\vdots b$, ապա K$(a;b)=a$
Եթե K$(a;b)=k$ և $m$-բնական թիվ, ապա K$(am;bm)=km$
Եթե $d$-ը $a$-ի և $b$-ի ընդհանուր բաժանարար է, ապա K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d): ) $
Եթե $a\vdots c$ և $b\vdots c$, ապա $\frac(ab)(c)$-ը $a$-ի և $b$-ի ընդհանուր բազմապատիկն է:
Ցանկացած բնական թվերի համար $a$ և $b$ հավասարությունը
$D(a;b)\cdot K(a;b)=ab$
$a$-ի և $b$-ի ցանկացած ընդհանուր բաժանարար $D(a;b)$-ի բաժանարարն է
Էվկլիդեսի ալգորիթմըերկու ամբողջ թվերի ամենամեծ ընդհանուր բաժանարարը (gcd) գտնելու միջոց է։ Ալգորիթմի սկզբնական տարբերակը, երբ GCD-ն հայտնաբերվում է հանման միջոցով, հայտնաբերել է Էվկլիդեսը (մ.թ.ա. 3-րդ դար): Ներկայումս բաժանումը ավելի հաճախ օգտագործվում է Էվկլիդյան ալգորիթմով GCD-ն հաշվարկելիս, քանի որ այս մեթոդն ավելի արդյունավետ է։
Gcd-ի հաշվարկը բաժանման միջոցով
Զույգ թվերի ամենամեծ ընդհանուր բաժանարարը ամենամեծ թիվն է, որը բաժանում է զույգի երկու թվերը։ Թող պահանջվի հաշվարկել GCD-ն 108 և 72 թվերի համար: Բաժանման հաշվարկի ալգորիթմը կլինի հետևյալը.
- Ավելի մեծ թիվը (դիվիդենտը) բաժանեք փոքրի (բաժանարարի) վրա՝ 108 / 72 = 1, մնացորդը՝ 36։
- Քանի որ մնացորդը հավասար չէր զրոյի, բաժանարարը կդարձնենք բաժանելի, իսկ մնացորդը՝ բաժանարար՝ 72 / 36 = 2, մնացորդը 0 է։
- Երբ մնացորդը զրո է, ապա բաժանարարը ցանկալի gcd է տրված թվերի զույգի համար։ Այսինքն, gcd(108, 72) = 36: Իրոք, 108/36 = 3 և 72/36 = 2:
Այս ալգորիթմում բաժանումը կրկնվում է մինչև մնացորդը զրոյի. Երբ նա դառնում է GCD-ն վերջին բաժանման բաժանարարն է. Օրինակ, դուք ցանկանում եք գտնել GCD(106, 16):
- 106 / 16 = 6, մնացորդը 10
- 16 / 10 = 1, մնացորդը 6
- 10 / 6 = 1, մնացորդը 4
- 6/4 = 1, մնացորդը 2
- 4/2 = 2, մնացորդը 0
- gcd (106, 16) = 2
GCD-ի հաշվարկը հանումով
GCD-ն հանումով գտնելիս պահանջվում է նաև հասնել զրոյի: Ալգորիթմը նման է բաժանման մեթոդին, միայն այստեղ՝ յուրաքանչյուր հաջորդ փուլում, հանվում և կրճատվում են ենթակառուցվածքը և նախորդ քայլի տարբերությունը։ Փոքր թիվը միշտ հանվում է ավելի մեծ թվից: Այս տեսակի ալգորիթմը հարմար է միայն դրական ամբողջ թվերի համար:
Թող պահանջվի գտնել GCD(108, 72):
- 108 - 72 = 36
- 72 - 36 = 36
- 36 - 36 = 0
- gcd (108, 72) = 36
Գտեք gcd(44, 60):
- 60 - 44 = 16
- 44 - 16 = 28
- 28 - 16 = 12
- 16 - 12 = 4
- 12 - 4 = 8
- 8 - 4 = 4
- 4 - 4 = 0
- gcd (44, 60) = 4
Այս ալգորիթմը երբեմն այլ կերպ է նկարագրվում: Հանացումն ավարտվում է ավելի վաղ, այն քայլով, երբ մի թիվը բաժանում է մյուսը: Այսինքն՝ միավորում են հանումը բաժանելիության թեստավորման հետ։ Այնուհետև 44-ի և 60-ի համար GCD-ն գտնելը այսպիսի տեսք կունենա.
- Արդյո՞ք 44-ը հավասարապես բաժանում է 60-ը: Ոչ 60 - 44 = 16:
- Արդյո՞ք 16-ը հավասարապես բաժանում է 44-ը: Ոչ 44 - 16 = 28:
- Արդյո՞ք 16-ը հավասարապես բաժանում է 28-ը: Ոչ 28 - 16 = 12:
- Արդյո՞ք 12-ը հավասարապես բաժանում է 16-ը: Ոչ 16 - 12 = 4:
- Արդյո՞ք 4-ը հավասարապես բաժանում է 12-ը: Այո՛։ Այսպիսով, gcd (44, 60) = 4:
Նշում, GCD-ն քանորդ չէ, այլ բաժանարար. Եթե օրինակում 12-ը բաժանենք 4-ի, կստանանք 3 գործակիցը։ Բայց սա GCD չէ։
Էվկլիդեսի ալգորիթմի ապացույց
Հաշվի առնենք այն հանգամանքը, որ եթե զույգից մի բնական թիվը բաժանի մյուսը, ապա նրանց gcd-ն հավասար կլինի նրանցից փոքրին։ Կարող եք գրել այսպես.
եթե a/b-ն ամբողջ թիվ է, ապա gcd(a, b) = b. Օրինակ, gcd(15, 5) = 5:
Այսպիսով, եթե մենք ավարտենք մի զույգ թվեր, որոնցից մեկը բաժանում է մյուսը, ապա փոքրը կլինի ամենամեծ ընդհանուր բաժանարարը երկուսի համար: Հենց այդպիսի զույգ թվեր են որոնվում Էվկլիդեսի ալգորիթմով՝ մի թիվն ամբողջությամբ բաժանում է մյուսը։
Երկրորդ փաստ. Պահանջվում է ապացուցել, որ եթե մի թիվ մյուսից մեծ է, ապա նրանց ամենամեծ ընդհանուր բաժանարարը հավասար է ամենամեծ ընդհանուր բաժանարարին զույգից փոքր թվի համար և մեծ և փոքր թվերի տարբերությանը։ Սա կարելի է գրել այսպես.
Եթե< b, то НОД(a, b) = НОД(a, b - a).
Մենք կարող ենք ապացուցել, որ gcd(a, b) = gcd(a, b - a) հետևյալ կերպ. Թող b - a = c. Եթե որևէ x թիվը բաժանում է a և b, ապա այն կբաժանի նաև c: Ի վերջո, եթե a-ն և b-ը տարբեր են, ապա բաժանարարը նրանց մեջ տեղավորվում է մի ամբողջ թիվ, բայց տարբեր անգամներ: Իսկ եթե մեկը մյուսից հանում ես, ապա բաժանարարը պետք է ստացված տարբերության մեջ նաև մի ամբողջ թիվ տեղավորի։
Եթե հաջորդաբար փոքրացնենք a-ն և b-ը, ապա վաղ թե ուշ կհասնենք դրանցից փոքրի այնպիսի արժեքի, որն ամբողջությամբ բաժանում է ավելի մեծը։ Նման զույգից փոքրը կլինի բնական թվերի սկզբնական զույգի ամենամեծ ընդհանուր բաժանարարը: Ահա թե ինչի մասին է Էվկլիդեսի ալգորիթմը:
Դիտարկենք GCD-ի հայտնաբերման երկու հիմնական եղանակ երկու հիմնական եղանակով՝ օգտագործելով Էվկլիդյան ալգորիթմը և ֆակտորինգը: Եկեք կիրառենք երկու մեթոդները երկու, երեք և ավելի թվերի համար:
Էվկլիդեսի ալգորիթմը GCD գտնելու համար
Էվկլիդեսի ալգորիթմը հեշտացնում է երկու դրական թվերի ամենամեծ ընդհանուր բաժանարարի հաշվարկը։ Մենք տվել ենք Էվկլիդեսի ալգորիթմի ձևակերպումները և ապացույցները Մեծագույն ընդհանուր բաժանարար՝ որոշիչ, օրինակներ բաժնում։
Ալգորիթմի էությունը մնացորդով հետևողականորեն բաժանումն է, որի ընթացքում ստացվում է ձևի մի շարք հավասարումներ.
a = b q 1 + r 1, 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
Մենք կարող ենք ավարտել բաժանումը, երբ rk + 1 = 0, որտեղ r k = gcd (a, b).
Օրինակ 1
64 Եվ 48 .
Լուծում
Ներկայացնենք նշումը՝ a = 64 , b = 48 :
Էվկլիդես ալգորիթմի հիման վրա մենք կիրականացնենք բաժանումը 64 վրա 48 .
Մենք ստանում ենք 1, իսկ մնացածը 16: Ստացվում է, որ q 1 = 1, r 1 = 16:
Երկրորդ քայլը բաժանելն է 48 16-ով ստանում ենք 3: Այն է q2 = 3, Ա r 2 = 0:Այսպիսով, 16 թիվը պայմանի թվերի ամենամեծ ընդհանուր բաժանարարն է։
Պատասխան. gcd (64, 48) = 16:
Օրինակ 2
Ո՞րն է թվերի GCD-ն 111 Եվ 432 ?
Լուծում
Բաժանել 432 վրա 111 . Էվկլիդեսի ալգորիթմի համաձայն՝ ստանում ենք 432 = 111 3 + 99 , 111 = 99 1 + 12 , 99 = 12 8 + 3, 12 = 3 4, հավասարությունների շղթան։
Այսպիսով, թվերի ամենամեծ ընդհանուր բաժանարարը 111 Եվ 432 3 է։
Պատասխան. gcd (111, 432) = 3:
Օրինակ 3
Գտե՛ք 661 և 113 թվերի ամենամեծ ընդհանուր բաժանարարը:
Լուծում
Մենք հաջորդաբար կբաժանենք թվերը և կստանանք GCD (661 , 113) = 1 . Սա նշանակում է, որ 661-ը և 113-ը համեմատաբար պարզ թվեր են։ Մենք կարող էինք դա պարզել նախքան հաշվարկները սկսելը, եթե նայեինք պարզ թվերի աղյուսակին:
Պատասխան. gcd (661, 113) = 1:
Գտեք GCD-ն՝ թվերը հիմնական գործոնների վերածելով
Ֆակտորինգով երկու թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու համար անհրաժեշտ է բազմապատկել բոլոր պարզ գործակիցները, որոնք ստացվում են այս երկու թվերի տարրալուծմամբ և ընդհանուր են նրանց համար։
Օրինակ 4
Եթե 220 և 600 թվերը տարրալուծենք պարզ գործակիցների, ապա կստանանք երկու արտադրյալ. 220 = 2 2 5 11Եվ 600 = 2 2 2 3 5 5. Այս երկու ապրանքների ընդհանուր գործոնները կլինեն 2-ը, 2-ը և 5-ը: Սա նշանակում է, որ NOD (220, 600) = 2 2 5 = 20.
Օրինակ 5
Գտե՛ք թվերի ամենամեծ ընդհանուր բաժանարարը 72 Եվ 96 .
Լուծում
Գտեք թվերի բոլոր պարզ գործակիցները 72 Եվ 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
Ընդհանուր պարզ գործակիցներ երկու թվերի համար՝ 2, 2, 2 և 3: Սա նշանակում է, որ NOD (72, 96) = 2 2 2 3 = 24.
Պատասխան. gcd (72, 96) = 24:
Երկու թվերի ամենամեծ ընդհանուր բաժանարարը գտնելու կանոնը հիմնված է ամենամեծ ընդհանուր բաժանարարի հատկությունների վրա, ըստ որի gcd (m a 1 , m b 1) = m gcd (a 1 , b 1), որտեղ m ցանկացած դրական ամբողջ թիվ է։ .
Գտնելով երեք և ավելի թվերի GCD
Անկախ այն թվերից, որոնց համար մենք պետք է գտնենք GCD-ն, մենք կհետևենք նույն ալգորիթմին, որը բաղկացած է հաջորդաբար երկու թվերի GCD-ն գտնելուց: Այս ալգորիթմը հիմնված է հետևյալ թեորեմի կիրառման վրա՝ GCD մի քանի թվերի a 1, a 2, …, a kհավասար է թվին դ կ, որը հանդիպում է gcd-ի հաջորդական հաշվարկում (a 1, a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .
Օրինակ 6
Գտե՛ք 78, 294, 570 և չորս թվերի ամենամեծ ընդհանուր բաժանարարը. 36 .
Լուծում
Ներկայացնենք նշումը՝ a 1 = 78, a 2 = 294, a 3 = 570, a 4 = 36:
Սկսենք գտնելով 78 և 294 թվերի GCD-ն. d2= GCD (78 , 294) = 6 .
Այժմ եկեք սկսենք գտնել d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) . Էվկլիդես ալգորիթմի համաձայն 570 = 6 95 .Դա նշանակում է որ դ 3 = GCD (6 , 570) = 6 .
Գտեք d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) . 36 առանց մնացորդի բաժանվում է 6-ի։ Սա թույլ է տալիս մեզ ստանալ d4= GCD (6 , 36) = 6 .
d4 = 6, այսինքն՝ GCD (78 , 294 , 570 , 36) = 6 .
Պատասխան.
Եվ հիմա եկեք դիտարկենք այս և ավելի շատ թվերի համար GCD-ն հաշվարկելու մեկ այլ եղանակ: Մենք կարող ենք գտնել gcd-ը՝ բազմապատկելով թվերի բոլոր ընդհանուր պարզ գործակիցները:
Օրինակ 7
Հաշվի՛ր 78 , 294 , 570 և թվերի gcd-ն 36 .
Լուծում
Եկեք այս թվերը տարրալուծենք պարզ գործակիցների՝ 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 :
Բոլոր չորս թվերի համար ընդհանուր պարզ գործակիցները կլինեն 2 և 3 թվերը:
Պարզվում է, որ NOD (78, 294, 570, 36) = 2 3 = 6.
Պատասխան. gcd(78, 294, 570, 36) = 6:
Բացասական թվերի gcd-ի հայտնաբերում
Եթե մենք պետք է գործ ունենանք բացասական թվերի հետ, ապա մենք կարող ենք օգտագործել այս թվերի մոդուլները՝ գտնելու ամենամեծ ընդհանուր բաժանարարը։ Մենք կարող ենք դա անել՝ իմանալով հակադիր նշաններով թվերի հատկությունը՝ թվեր nԵվ -nունեն նույն բաժանարարները.
Օրինակ 8
Գտեք բացասական ամբողջ թվերի gcd-ն − 231 Եվ − 140 .
Լուծում
Հաշվարկներ կատարելու համար վերցնենք պայմանում տրված թվերի մոդուլներ։ Դրանք կլինեն 231 և 140 թվերը։ Համառոտ ասենք՝ GCD (− 231 , − 140) = GCD (231, 140) . Այժմ կիրառենք Էվկլիդեսի ալգորիթմը՝ գտնելու երկու թվերի պարզ գործակիցներ՝ 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 և 42 = 7 6. Մենք ստանում ենք, որ gcd (231, 140) = 7 .
Եվ քանի որ NOD (− 231 , − 140) = GCD (231 , 140) , ապա թվերի gcd-ն − 231 Եվ − 140 հավասար է 7 .
Պատասխան. gcd (− 231, − 140) = 7։
Օրինակ 9
Որոշե՛ք երեք թվերի gcd-ն՝ 585, 81 և − 189 .
Լուծում
Վերոնշյալ ցուցակի բացասական թվերը փոխարինենք դրանց բացարձակ արժեքներով, ստանում ենք GCD (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . Այնուհետև մենք տրված բոլոր թվերը տարրալուծում ենք պարզ գործոնների. 585 = 3 3 5 13, 81 = 3 3 3 3 և 189 = 3 3 3 7. 3 և 3 պարզ գործակիցները ընդհանուր են երեք թվերի համար: Ստացվում է, որ gcd (585 , 81 , 189) = gcd (- 585 , 81 , - 189) = 9 ։
Պատասխան. GCD (− 585, 81, − 189) = 9։
Եթե տեքստում սխալ եք նկատել, ընդգծեք այն և սեղմեք Ctrl+Enter
Էվկլիդեսի ալգորիթմը
Մեծագույն ընդհանուր բաժանարար
Դիտարկենք հետևյալ խնդիրը. պահանջվում է երկու բնական թվերի ամենամեծ ընդհանուր բաժանարարը (GCD) որոշելու ծրագիր:
Հիշենք մաթեմատիկան. Երկու բնական թվերի ամենամեծ ընդհանուր բաժանարարը ամենամեծ բնական թիվն է, որով նրանք հավասարապես բաժանվում են։ Օրինակ՝ 12 և 18 թվերն ունեն ընդհանուր բաժանարարներ՝ 2, 3, 6։ Ամենամեծ ընդհանուր բաժանարարը 6-ն է։ Սա գրված է այսպես.
gcd (12, 18) = 6:
Նախնական տվյալները նշեք M u N-ով: Խնդրի հայտարարությունը հետևյալն է.
Տրված է.Մ, Ն
Գտնել. GCD (M, N):
Այս դեպքում լրացուցիչ մաթեմատիկական ֆորմալացում չի պահանջվում: Խնդրի շարադրումն ինքնին կրում է ֆորմալ մաթեմատիկական բնույթ։ GCD(M, N) M-ի և N-ի արժեքներից հաշվարկելու բանաձև չկա: Բայց մյուս կողմից, շատ վաղուց, համակարգիչների հայտնվելուց շատ առաջ, հայտնի էր այս խնդրի լուծման ալգորիթմական մեթոդը: . Դա կոչվում է Էվկլիդեսի ալգորիթմը .
Էվկլիդեսի ալգորիթմի գաղափարը
Այս ալգորիթմի գաղափարը հիմնված է այն հատկության վրա, որ եթե M>N, ապա
GCD (M, N) = GCD (M - N, N):
Այլ կերպ ասած, երկու բնական թվերի gcd-ն հավասար է նրանց դրական տարբերության gcd-ին (դրանց տարբերության մոդուլին) և փոքր թվին։
Հեշտ է ապացուցել այս հատկությունը: Թող K լինի M u N ընդհանուր բաժանարար (M > N): Սա նշանակում է, որ M \u003d mK, N \u003d nK, որտեղ m, n բնական թվեր են, իսկ m > n: Այնուհետև M - N \u003d K (m - n), ինչը ենթադրում է, որ K-ն M - N թվի բաժանարարն է: Հետևաբար, M և N թվերի բոլոր ընդհանուր բաժանարարները իրենց M - N տարբերության բաժանարարներ են, ներառյալ ամենամեծը: ընդհանուր բաժանարար.
Երկրորդ ակնհայտ հատկությունը.
GCD (M, M) = M.
«Ձեռքով» հաշվելու համար Էվկլիդեսի ալգորիթմն ունի հետևյալ տեսքը.
1) եթե թվերը հավասար են, ապա որպես պատասխան վերցրեք դրանցից որևէ մեկը, հակառակ դեպքում շարունակեք ալգորիթմը.
2) ավելի մեծ թիվը փոխարինել թվերից մեծի և փոքրի տարբերությամբ.
3) վերադառնալ 1-ին կետի կատարմանը.
Դիտարկենք այս ալգորիթմը M=32, N=24 օրինակով:
Ալգորիթմի կառուցվածքը իրենից ներկայացնում է while-loop՝ բնադրված ճյուղավորմամբ։ Ցիկլը կրկնվում է այնքան ժամանակ, մինչև M և N արժեքները հավասարվեն միմյանց: Ճյուղավորման ժամանակ երկու արժեքներից ավելի մեծը փոխարինվում է դրանց տարբերությամբ:
Այժմ նայեք ալգորիթմի հետքի աղյուսակին M = 32, N = 24 սկզբնական արժեքների համար:
| Քայլ | Գործողություն | Մ | Ն | Վիճակ |
| 1 | մուտքագրում Մ | 32 | ||
| 2 | մուտքագրում Ն | 24 | ||
| 3 | M ¹ N | 32 ¹ 24, այո | ||
| 4 | Մ>Ն | 32>24, այո | ||
| 5 | M:=M-N | 8 | ||
| 6 | M ¹ N | 8 ¹ 24, այո | ||
| 7 | Մ>Ն | 8>24, ոչ | ||
| 8 | N:=N-M | 16 | ||
| 9 | M ¹ N | 8 ¹ 16, այո | ||
| 10 | Մ>Ն | 8>16, ոչ | ||
| 11 | N:=N-M | 8 | ||
| 12 | M ¹ N | 8 ¹ 8, No | ||
| 13 | տերմինալ Մ | 8 | ||
| 14 | վերջ |
Վերջնական արդյունքը ճիշտն է:
Ծրագիր AZ և Pascal լեզուներով
Ալգորիթմը գրում ենք AI-ով, իսկ ծրագիրը՝ Պասկալով։
Հարցեր և առաջադրանքներ
1. Գործարկեք Evklid ծրագիրը ձեր համակարգչում: Փորձարկել այն M=32, N=24; M = 696, N = 234:
2. Գրի՛ր ծրագիր, որով կարելի է գտնել երեք թվերի ամենամեծ ընդհանուր բաժանարարը՝ օգտագործելով հետևյալ բանաձևը.
gcd (A, B, C) = gcd (gcd (A, B), C):
3. Գրեք ծրագիր երկու թվերի ամենափոքր ընդհանուր բազմապատիկը (LCM) գտնելու համար՝ օգտագործելով բանաձևը.
A × B = GCD (A, B) × LCM (A, B):
Բեռնվում է...
