{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "Courier" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 257 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 3 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Headi ng 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 6 6 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title " -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 } 3 1 0 0 12 12 1 0 1 0 2 2 19 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 22 "L'algoritmo di Euclide" } }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 4 " Note" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 6 "Autore" }}{PARA 0 "" 0 "" {TEXT -1 14 "Claudio Marsan" }}{PARA 0 "" 0 "" {TEXT -1 28 "Liceo Cant onale di Mendrisio" }}{PARA 0 "" 0 "" {TEXT -1 20 "Via Agostino Maspol i" }}{PARA 0 "" 0 "" {TEXT -1 31 "CH-6850 Mendrisio (Switzerland)" }} {PARA 0 "" 0 "" {TEXT -1 40 "e-mail: claudio.marsan@liceomendrisio.ch " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 8 "Versione" }}{PARA 0 "" 0 "" {TEXT -1 27 "Versione 2.0, 14 marzo 2003" }}{PARA 0 "" 0 "" {TEXT -1 37 "Maple V Release 6.02 for Windows 2000" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 389 "In questo foglio di lavo ro si mostra come lavora l'algoritmo di Euclide per il calcolo del mas simo comune divisore di due numeri interi positivi. Si fa inoltre nota re che il metodo appreso nelle scuole medie, consistente nello scompor re in fattori primi i due numeri interi positivi, \350 praticamente in utilizzabile (la fattorizzazione di un numero intero \350 un'operazion e molto complicata!)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{PARA 11 "" 1 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 87 "Implementazione della p rocedura \"euclide\" per il calcolo del MCD di due interi positivi" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 364 "euclide := proc(a::posint, b::posint)\n local x, y, q, r;\n if \+ a < b then\n x := a;\n y := b;\n else\n x := b;\n y := a; \n fi;\n q := iquo(x, y);\n r := irem(x, y);\n if r = 0 then\n \+ RETURN(y);\n fi;\n while r <> 0 do\n x := y;\n y := r;\n r \+ := irem(x, y);\n q := iquo(x, y);\n printf(`%d = %d * %d + %d\\n `, x, q, y, r);\n od;\n RETURN(y);\nend;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(euclideGR6$'%\"aG%'posintG'%\"bGF)6&%\"xG%\"yG%\"qG% \"rG6\"F1C(@%29$9%C$>8$F5>8%F6C$>F9F6>F;F5>8&-%%iquoG6$F9F;>8'-%%iremG FC@$/FE\"\"!-%'RETURNG6#F;?(F1\"\"\"FOF10FEFJC'>F9F;>F;FE>FEFF>F@FA-%' printfG6'%3%d~=~%d~*~%d~+~%d|+GF9F@F;FEFKF1F1F1" }}}}{SECT 0 {PARA 3 " " 0 "" {TEXT -1 22 "Calcolo di MCD(48, 30)" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 16 "euclide(48, 30);" }}{PARA 6 "" 1 "" {TEXT -1 16 "48 = 1 * 30 + 18" }}{PARA 6 "" 1 "" {TEXT -1 16 "30 = 1 * 18 + 12" }} {PARA 6 "" 1 "" {TEXT -1 15 "18 = 1 * 12 + 6" }}{PARA 6 "" 1 "" {TEXT -1 14 "12 = 2 * 6 + 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}} {SECT 0 {PARA 3 "" 0 "" {TEXT -1 25 "Calcolo di MCD(2826, 450)" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "euclide(2826, 450);" }} {PARA 6 "" 1 "" {TEXT -1 20 "2826 = 6 * 450 + 126" }}{PARA 6 "" 1 "" {TEXT -1 18 "450 = 3 * 126 + 72" }}{PARA 6 "" 1 "" {TEXT -1 17 "126 = \+ 1 * 72 + 54" }}{PARA 6 "" 1 "" {TEXT -1 16 "72 = 1 * 54 + 18" }}{PARA 6 "" 1 "" {TEXT -1 15 "54 = 3 * 18 + 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#=" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 27 "Un esempio pi\371 interessante" }}{PARA 0 "" 0 "" {TEXT -1 101 "Vogliamo calcolare il M CD(72291318168, 12538416). Applichiamo dapprima la nostra procedura \" euclide\":" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "euclide(722913 18168, 12538416);" }}{PARA 6 "" 1 "" {TEXT -1 39 "72291318168 = 5765 * 12538416 + 7349928" }}{PARA 6 "" 1 "" {TEXT -1 32 "12538416 = 1 * 734 9928 + 5188488" }}{PARA 6 "" 1 "" {TEXT -1 31 "7349928 = 1 * 5188488 + 2161440" }}{PARA 6 "" 1 "" {TEXT -1 30 "5188488 = 2 * 2161440 + 86560 8" }}{PARA 6 "" 1 "" {TEXT -1 29 "2161440 = 2 * 865608 + 430224" }} {PARA 6 "" 1 "" {TEXT -1 26 "865608 = 2 * 430224 + 5160" }}{PARA 6 "" 1 "" {TEXT -1 25 "430224 = 83 * 5160 + 1944" }}{PARA 6 "" 1 "" {TEXT -1 22 "5160 = 2 * 1944 + 1272" }}{PARA 6 "" 1 "" {TEXT -1 21 "1944 = 1 * 1272 + 672" }}{PARA 6 "" 1 "" {TEXT -1 20 "1272 = 1 * 672 + 600" }} {PARA 6 "" 1 "" {TEXT -1 18 "672 = 1 * 600 + 72" }}{PARA 6 "" 1 "" {TEXT -1 17 "600 = 8 * 72 + 24" }}{PARA 6 "" 1 "" {TEXT -1 15 "72 = 3 \+ * 24 + 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#C" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 54 "Applichiamo ora il metodo imparato alle scuole me die:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 65 "72291318168 = ifact or(72291318168); 12538416 = ifactor(12538416);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/\",o\"=8Hs*,)-%!G6#\"\"#\"\"$\"\"\"-F(6#F+F,-F(6#\"$\\ \"F,-F(6#\"$(eF,-F(6#\"&RW$F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/\"); %QD\"**)-%!G6#\"\"#\"\"%\"\"\"-F(6#\"\"$F,-F(6#\"#6F,-F(6#\"&ZP#F," }} }{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Moltiplicando i fattori comuni al le due scomposizioni si ottiene il MCD:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "2^3 * 3;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#C" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 281 "Si pu\362 osservare che l'algorit mo di Euclide permette di calcolare il MCD(72291318168, 12538416) con \+ un numero relativamente basso di operazioni. Il metodo imparato alle s cuole medie prevede la fattorizzazione di 72291318168 e di 12538416, c he sono tutt'altro che facili da trovare." }}}}{SECT 0 {PARA 3 "" 0 " " {TEXT -1 20 "Un esempio \"estremo\"" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "a := 4366564386584376587 433636523422340023420; \n`cifre di a` = length(a);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%\"aG\"I?M-SBUBljLuewVe'QklO%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+cifre~di~aG\"#S" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 62 "b := 8982410024132947543705730457345;\n`cifre di b`= \+ length(b);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"bG\"@XtXIdqVv%H8C+T# )*)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%+cifre~di~bG\"#J" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "euclide(a, b);" }}{PARA 6 "" 1 "" {TEXT -1 120 "4366564386584376587433636523422340023420 = 486123921 * 8 982410024132947543705730457345 + 5623163502200087963328665373675" }} {PARA 6 "" 1 "" {TEXT -1 103 "8982410024132947543705730457345 = 1 * 56 23163502200087963328665373675 + 3359246521932859580377065083670" }} {PARA 6 "" 1 "" {TEXT -1 103 "5623163502200087963328665373675 = 1 * 33 59246521932859580377065083670 + 2263916980267228382951600290005" }} {PARA 6 "" 1 "" {TEXT -1 103 "3359246521932859580377065083670 = 1 * 22 63916980267228382951600290005 + 1095329541665631197425464793665" }} {PARA 6 "" 1 "" {TEXT -1 101 "2263916980267228382951600290005 = 2 * 10 95329541665631197425464793665 + 73257896935965988100670702675" }} {PARA 6 "" 1 "" {TEXT -1 100 "1095329541665631197425464793665 = 14 * 7 3257896935965988100670702675 + 69718984562107364016074956215" }}{PARA 6 "" 1 "" {TEXT -1 96 "73257896935965988100670702675 = 1 * 69718984562 107364016074956215 + 3538912373858624084595746460" }}{PARA 6 "" 1 "" {TEXT -1 96 "69718984562107364016074956215 = 19 * 35389123738586240845 95746460 + 2479649458793506408755773475" }}{PARA 6 "" 1 "" {TEXT -1 94 "3538912373858624084595746460 = 1 * 2479649458793506408755773475 + \+ 1059262915065117675839972985" }}{PARA 6 "" 1 "" {TEXT -1 93 "247964945 8793506408755773475 = 2 * 1059262915065117675839972985 + 3611236286632 71057075827505" }}{PARA 6 "" 1 "" {TEXT -1 92 "10592629150651176758399 72985 = 2 * 361123628663271057075827505 + 337015657738575561688317975 " }}{PARA 6 "" 1 "" {TEXT -1 90 "361123628663271057075827505 = 1 * 337 015657738575561688317975 + 24107970924695495387509530" }}{PARA 6 "" 1 "" {TEXT -1 90 "337015657738575561688317975 = 13 * 2410797092469549538 7509530 + 23612035717534121650694085" }}{PARA 6 "" 1 "" {TEXT -1 86 "2 4107970924695495387509530 = 1 * 23612035717534121650694085 + 495935207 161373736815445" }}{PARA 6 "" 1 "" {TEXT -1 85 "2361203571753412165069 4085 = 47 * 495935207161373736815445 + 303080980949556020368170" }} {PARA 6 "" 1 "" {TEXT -1 82 "495935207161373736815445 = 1 * 3030809809 49556020368170 + 192854226211817716447275" }}{PARA 6 "" 1 "" {TEXT -1 82 "303080980949556020368170 = 1 * 192854226211817716447275 + 11022675 4737738303920895" }}{PARA 6 "" 1 "" {TEXT -1 81 "192854226211817716447 275 = 1 * 110226754737738303920895 + 82627471474079412526380" }}{PARA 6 "" 1 "" {TEXT -1 80 "110226754737738303920895 = 1 * 8262747147407941 2526380 + 27599283263658891394515" }}{PARA 6 "" 1 "" {TEXT -1 79 "8262 7471474079412526380 = 2 * 27599283263658891394515 + 274289049467616297 37350" }}{PARA 6 "" 1 "" {TEXT -1 77 "27599283263658891394515 = 1 * 27 428904946761629737350 + 170378316897261657165" }}{PARA 6 "" 1 "" {TEXT -1 77 "27428904946761629737350 = 160 * 170378316897261657165 + 1 68374243199764590950" }}{PARA 6 "" 1 "" {TEXT -1 71 "17037831689726165 7165 = 1 * 168374243199764590950 + 2004073697497066215" }}{PARA 6 "" 1 "" {TEXT -1 68 "168374243199764590950 = 84 * 2004073697497066215 + 3 2052610011028890" }}{PARA 6 "" 1 "" {TEXT -1 64 "2004073697497066215 = 62 * 32052610011028890 + 16811876813275035" }}{PARA 6 "" 1 "" {TEXT -1 61 "32052610011028890 = 1 * 16811876813275035 + 15240733197753855" }}{PARA 6 "" 1 "" {TEXT -1 60 "16811876813275035 = 1 * 152407331977538 55 + 1571143615521180" }}{PARA 6 "" 1 "" {TEXT -1 59 "1524073319775385 5 = 9 * 1571143615521180 + 1100440658063235" }}{PARA 6 "" 1 "" {TEXT -1 57 "1571143615521180 = 1 * 1100440658063235 + 470702957457945" }} {PARA 6 "" 1 "" {TEXT -1 56 "1100440658063235 = 2 * 470702957457945 + \+ 159034743147345" }}{PARA 6 "" 1 "" {TEXT -1 55 "470702957457945 = 2 * \+ 159034743147345 + 152633471163255" }}{PARA 6 "" 1 "" {TEXT -1 53 "1590 34743147345 = 1 * 152633471163255 + 6401271984090" }}{PARA 6 "" 1 "" {TEXT -1 52 "152633471163255 = 23 * 6401271984090 + 5404215529185" }} {PARA 6 "" 1 "" {TEXT -1 48 "6401271984090 = 1 * 5404215529185 + 99705 6454905" }}{PARA 6 "" 1 "" {TEXT -1 47 "5404215529185 = 5 * 9970564549 05 + 418933254660" }}{PARA 6 "" 1 "" {TEXT -1 46 "997056454905 = 2 * 4 18933254660 + 159189945585" }}{PARA 6 "" 1 "" {TEXT -1 46 "41893325466 0 = 2 * 159189945585 + 100553363490" }}{PARA 6 "" 1 "" {TEXT -1 45 "15 9189945585 = 1 * 100553363490 + 58636582095" }}{PARA 6 "" 1 "" {TEXT -1 44 "100553363490 = 1 * 58636582095 + 41916781395" }}{PARA 6 "" 1 " " {TEXT -1 43 "58636582095 = 1 * 41916781395 + 16719800700" }}{PARA 6 "" 1 "" {TEXT -1 42 "41916781395 = 2 * 16719800700 + 8477179995" }} {PARA 6 "" 1 "" {TEXT -1 41 "16719800700 = 1 * 8477179995 + 8242620705 " }}{PARA 6 "" 1 "" {TEXT -1 39 "8477179995 = 1 * 8242620705 + 2345592 90" }}{PARA 6 "" 1 "" {TEXT -1 38 "8242620705 = 35 * 234559290 + 33045 555" }}{PARA 6 "" 1 "" {TEXT -1 34 "234559290 = 7 * 33045555 + 3240405 " }}{PARA 6 "" 1 "" {TEXT -1 32 "33045555 = 10 * 3240405 + 641505" }} {PARA 6 "" 1 "" {TEXT -1 28 "3240405 = 5 * 641505 + 32880" }}{PARA 6 " " 1 "" {TEXT -1 27 "641505 = 19 * 32880 + 16785" }}{PARA 6 "" 1 "" {TEXT -1 25 "32880 = 1 * 16785 + 16095" }}{PARA 6 "" 1 "" {TEXT -1 23 "16785 = 1 * 16095 + 690" }}{PARA 6 "" 1 "" {TEXT -1 22 "16095 = 23 * \+ 690 + 225" }}{PARA 6 "" 1 "" {TEXT -1 18 "690 = 3 * 225 + 15" }}{PARA 6 "" 1 "" {TEXT -1 17 "225 = 15 * 15 + 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 21 "Grazie alla funzione " }{TEXT 256 6 "time()" }{TEXT -1 56 " possiamo vedere ora il tempo necessario a fattorizzare " }{TEXT 257 1 "a" }{TEXT -1 3 " e " }{TEXT 258 1 "b" }{TEXT -1 80 " (calcoli e seguiti su un PC con processore Pentium IV a 2.53GHz e 512MB di RAM): " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "time(ifactor(b));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# $\"$7$!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "time(ifactor( a));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"&`9&!\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{MARK "10 8 0 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }