{"id":7225,"date":"2009-07-06T08:00:00","date_gmt":"2009-07-06T08:00:00","guid":{"rendered":"http:\/\/xmau.com\/wp\/notiziole\/2009\/07\/06\/algoritmi_per_i\/"},"modified":"2009-07-06T08:00:00","modified_gmt":"2009-07-06T08:00:00","slug":"algoritmi_per_i","status":"publish","type":"post","link":"https:\/\/xmau.com\/notiziole\/2009\/07\/06\/algoritmi_per_i\/","title":{"rendered":"Algoritmi per il MCD"},"content":{"rendered":"<p>Abbiamo visto che il minimo comune multiplo (mcm) e il massimo comun divisore (MCD) di due numeri sono strettamente correlati; dati due numeri <i>r<\/i> e <i>s<\/i>, si ha che mcm(<i>r<\/i>,<i>s<\/i>) = <i>rs<\/i>\/MCD(<i>r<\/i>,<i>s<\/i>). Ne consegue che basta avere un algoritmo per calcolare uno dei due valori, e siamo anche in grado di trovare l&#8217;altro; visto che il mcm \u00e8 (di solito molto) maggiore del MCD, chiaramente \u00e8 meglio dedicarci a quest&#8217;ultimo.<br \/>\nL&#8217;algoritmo pi\u00f9 antico noto per calcolare il MCD di due numeri \u00e8 cos\u00ec antico che non sono non c&#8217;era ancora il nome &#8220;algoritmo&#8221;, ma non credo la gente avesse in mente addirittura il concetto idi algoritmo. Lo si trova infatti in Euclide, che nei suoi <em>Elementi<\/em> non ha trattato solo di geometria ma anche dei numeri. L&#8217;algoritmo euclideo per calcolare MCD(<i>r<\/i>,<i>s<\/i>) \u00e8 concettualmente molto semplice: se <i>r<\/i>=<i>s<\/i>, allora MCD(<i>r<\/i>,<i>r<\/i>)=<i>r<\/i>; altrimenti, supponendo che <i>r<\/i>&gt;<i>s<\/i>, MCD(<i>r<\/i>,<i>s<\/i>)=MCD(<i>r-s<\/i>,<i>s<\/i>). Tutto qua. Il lettore pi\u00f9 attento (occhei, il lettore meno attento ha gi\u00e0 semsso di leggere da un po&#8217;) si sar\u00e0 sicuramente accorto che il procedimento deve per forza terminare, visto che nel caso generale si passa da una coppia di numeri a una coppia la cui somma \u00e8 minore, e non si pu\u00f2 scendere all&#8217;infinito visto che la somma sar\u00e0 sempre positiva. Non \u00e8 nemmeno troppo difficile scoprire che in effetti l&#8217;algoritmo calcola correttamente il MCD di due numeri. Se i numeri sono uguali la cosa \u00e8 immediata; altrimenti, se m \u00e8 l&#8217;ancora incognito MCD(<i>r<\/i>,<i>s<\/i>), allora <i>r<\/i>=<i>mh<\/i> e <i>s<\/i>=<i>mk<\/i>; quindi <i>m<\/i> \u00e8 sicuramente un fattore comune di <i>r-s<\/i>=<i>m<\/i><i>(h-k)<\/i> e <i>s<\/i>=<i>mk<\/i>: e se ci fosse un fattore comune maggiore nella differenza, quel fattore ci sarebbe stato anche all&#8217;inizio.<br \/>\nLa cosa pi\u00f9 incredibile \u00e8 che l&#8217;algoritmo che si usa oggi per calcolare il MCD di due numeri \u00e8 ancora essenzialmente quello di Euclide! L&#8217;unica miglioria che c&#8217;\u00e8 stata \u00e8 che non si sottraggono pi\u00f9 i due numeri ma si prende il resto della loro divisione e lo si sostituisce al maggiore dei due; se il minore divide esattamente il maggiore, allora il MCD cercato \u00e8 il numero minore. E in effetti non \u00e8 che cambi molto, visto che come certo ricordate la divisione tra numeri interi non \u00e8 altro che una ripetuta serie di sottrazioni. L&#8217;algoritmo cos\u00ec modificato \u00e8 molto veloce, richiedendo una quantit\u00e0 di operazioni dell&#8217;ordine del logaritmo dei numeri; il caso peggiore si ha quando i due numeri dati sono in posizioni successive della successione di Fibonacci&#8230; ma questa \u00e8 un&#8217;altra storia, che forse prima o poi racconter\u00f2.<br \/>\nTermino con un simpatico problemino matematico (la parola &#8220;simpatico&#8221; sta ovviamente a indicare qualcosa che far\u00e0 arrabbiare chi cercher\u00e0 di risolverlo, e far\u00e0 arrabbiare ancora di pi\u00f9 chi legger\u00e0 la soluzione e scoprir\u00e0 la semplicit\u00e0). Ci sono due amiche, Thelma e Louise, che hanno preparato due pile di pancake e si accingono a mangiarle. Le amiche si alternano a prendere pancake dalla pila in quel momento pi\u00f9 alta, togliendone un multiplo a piacere del numero presente nella pila pi\u00f9 piccola. Visto che il pancake pi\u00f9 in basso \u00e8 sempre molliccio, la prima che \u00e8 costretta a prenderlo ha perso il gioco. Se Thelma e Louise scelgono la loro migliore strategia, chi vincer\u00e0, data una coppia di valori iniziali? La risposta alla prossima puntata!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dai tempi di Euclide non \u00e8 che si sia fatto chiss\u00e0 quale progresso!<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":3,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[214],"tags":[],"class_list":["post-7225","post","type-post","status-publish","format-standard","hentry","category-matematica_light"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/phh2yV-1Sx","jetpack-related-posts":[{"id":4991,"url":"https:\/\/xmau.com\/notiziole\/2007\/05\/18\/ah_la_romania\/","url_meta":{"origin":7225,"position":0},"title":"Ah, la Romania!","author":".mau.","date":"2007-05-18","format":false,"excerpt":"un tentativo di phishing cos\u00ec sgarrupato da diventare patetico.","rel":"","context":"In &quot;spam_phishing&quot;","block_context":{"text":"spam_phishing","link":"https:\/\/xmau.com\/notiziole\/category\/spam_phishing\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":27589,"url":"https:\/\/xmau.com\/notiziole\/2023\/11\/01\/quasi-senza-analisi-matematica\/","url_meta":{"origin":7225,"position":1},"title":"Quasi senza analisi matematica","author":".mau.","date":"2023-11-01","format":false,"excerpt":"Come dimostrare una propriet\u00e0 matematica senza barare troppo.","rel":"","context":"In &quot;matematica_light&quot;","block_context":{"text":"matematica_light","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/10\/231101-sfere-bucate.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/10\/231101-sfere-bucate.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/10\/231101-sfere-bucate.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":35799,"url":"https:\/\/xmau.com\/notiziole\/2026\/02\/04\/logaritmo-discreto-e-dimostrazioni-a-conoscenza-zero\/","url_meta":{"origin":7225,"position":2},"title":"Logaritmo discreto e dimostrazioni a conoscenza zero","author":".mau.","date":"2026-02-04","format":false,"excerpt":"Un protocollo per dimostrare che conosco qual \u00e8 il logaritmo discreto di un numero.","rel":"","context":"In &quot;mate-light 2026&quot;","block_context":{"text":"mate-light 2026","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2026\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":28498,"url":"https:\/\/xmau.com\/notiziole\/2024\/03\/13\/come-arrivare-a-pi-greco\/","url_meta":{"origin":7225,"position":3},"title":"Come arrivare a pi greco","author":".mau.","date":"2024-03-13","format":false,"excerpt":"Un metodo iterativo che sembra troppo bello per essere vero","rel":"","context":"In &quot;mate-light-2024&quot;","block_context":{"text":"mate-light-2024","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2024\/"},"img":{"alt_text":"Freccia verso pi greco","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2024\/03\/freccia-pi-158x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":33652,"url":"https:\/\/xmau.com\/notiziole\/2025\/09\/17\/come-generare-punti-casuali-dentro-un-triangolo\/","url_meta":{"origin":7225,"position":4},"title":"Come generare punti casuali dentro un triangolo","author":".mau.","date":"2025-09-17","format":false,"excerpt":"pensare matematicamente aiuta a trovare soluzioni migliori","rel":"","context":"In &quot;mate-light-2025&quot;","block_context":{"text":"mate-light-2025","link":"https:\/\/xmau.com\/notiziole\/category\/matematica_light\/matelight-2025\/"},"img":{"alt_text":"un triangolo generato casualmente con coordinate baricentriche.","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/triangle-bari.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/triangle-bari.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2025\/09\/triangle-bari.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":26493,"url":"https:\/\/xmau.com\/notiziole\/2023\/06\/04\/quizzino-della-domenica-rapporti\/","url_meta":{"origin":7225,"position":5},"title":"Quizzino della domenica: Rapporti","author":".mau.","date":"2023-06-04","format":false,"excerpt":"Nella figura qui sotto (non disegnata in scala) il quarto di cerchio di raggio R centrato nell'angolo a sinistra in basso del quadrato di sinistra occupa met\u00e0 del quadrato, esattamente come il cerchio di raggio r centrato nel quadrato di destra occupa met\u00e0 di quel quadrato. Quanto vale il rapporto\u2026","rel":"","context":"In &quot;giochi&quot;","block_context":{"text":"giochi","link":"https:\/\/xmau.com\/notiziole\/category\/giochi\/"},"img":{"alt_text":"la figura","src":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/06\/q646a-1.png?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/06\/q646a-1.png?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/xmau.com\/notiziole\/wp-content\/uploads\/sites\/6\/2023\/06\/q646a-1.png?resize=525%2C300&ssl=1 1.5x"},"classes":[]}],"jetpack_likes_enabled":true,"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7225","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/comments?post=7225"}],"version-history":[{"count":0,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/posts\/7225\/revisions"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/media?parent=7225"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/categories?post=7225"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/notiziole\/wp-json\/wp\/v2\/tags?post=7225"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}