Lekce matematického kroužku pro studenty 7. –9. ročníku na téma „Euklidův algoritmus“

Novoselova O. A. Lekce matematického kroužku pro studenty 7.–9. ročníku na téma „Euklidův algoritmus“ // Vědecký a metodologický elektronický časopis „Koncept“. – 2013. – č. 7 (červenec). – s. 76–80. – URL: http://e-koncept.ru/2013/13152.htm.

Anotace. Článek představuje vývoj lekce pro matematický kroužek na téma „Euklidův algoritmus“, určené pro žáky 7.–9. ročníku. Lekce je navržena na 2–3 hodiny. Je zvažován původ slova algoritmus. Podstata euklidovského algoritmu je prezentována ve formě dvou vzorců. Článek také uvádí příklady aplikace euklidovského algoritmu, včetně úloh na nalévání a skládání lineárních diofantových rovnic.

Komentáře
Žádné komentáře
Zanechat komentář
Chcete-li komentovat, přihlaste se nebo se zaregistrujte.
Text článku

Novoselova Olga Anatoljevna, učitelka matematiky, Střední škola MOAU s UIOP č. 60, [email protected]

Lekce pro matematický kroužek pro žáky 7.–9. ročníku na téma „Euklidův algoritmus“

Abstrakt. Článek představuje vývoj lekce pro matematický kroužek na téma „Euklidův algoritmus“ určené pro žáky 7.–9. ročníku. Lekce je navržena na 2–3 hodiny. Je zvažován původ slova algoritmus. Podstata euklidovského algoritmu je prezentována ve formě dvou vzorců. Článek také uvádí příklady aplikace euklidovského algoritmu, včetně úloh na transfuzi a na skládání lineárních diofantových rovnic. Klíčová slova: největší společný dělitel dvou přirozených čísel, rozklad čísla na prvočísla, algoritmus, euklidovský algoritmus, úlohy na transfuzi, úlohy na skládání lineárních diofantových rovnic.

V každé třídě se najdou studenti, kteří by si rádi získali více znalostí o tématu, s jehož obsahem se seznámili v hodinách matematiky. Některé děti se zajímají o aplikované zaměření studovaného tématu, jiné o historické informace týkající se určitých pojmů nebo vynikajících osobností, které přispěly k rozvoji vědy. Touha studovat, pracovat, zájem o proveditelnou výzkumnou práci studentů musí být neustále podporován. K tomu všemu mimoškolní práce poskytuje velké pole pro tvůrčí činnost. Mimoškolní práce na daném předmětu také zvyšuje kvalifikaci samotného učitele, povzbuzuje ho ke studiu různé literatury k danému tématu. Jednou ze specifických forem mimoškolní práce v matematice ve škole je matematický kroužek [1]. Problematika probíraná v klubových hodinách přesahuje základní úroveň požadovaných znalostí v matematice, ale zároveň úzce souvisí s problematikou programové látky. Tento článek navrhuje vytvoření klubové hodiny na téma „Euklidův algoritmus“. Úvod. Jedna z postav francouzského spisovatele Molièra, pan Jourdain, byl strašně překvapen, když zjistil, že v průběhu života provádíme obrovské množství nejrůznějších algoritmů. V každodenním životě musí člověk řešit velké množství různých problémů, které vyžadují použití určitých algoritmů. Když si děláme čaj, používáme určitý algoritmus (někdy specifikovaný pokyny vytištěnými na obalu). Když si bereme knihy z knihovny, dodržujeme určitá pravidla pro používání knihovních knih, tj. provádíme určitý algoritmus. Je možné vyjmenovat všechny problémy, při jejichž řešení používáme určité algoritmy? Slovo algoritmus se v poslední době hojně používá. Znamená popis souboru akcí, které tvoří určitý proces. Obvykle se tím myslí proces řešení problému, ale kulinářský recept, návod k použití pračky, popis postupu pro vzhled fotografického filmu a mnoho dalších pravidel, která nemají nic společného s matematikou, jsou algoritmy. Termín „algoritmus“ pochází ze jména vědce z XNUMX. až XNUMX. století Al-Chorezmiho. Jeho jméno naznačuje, že se narodil ve městě Chorezmi, které je dnes součástí Uzbekistánu. Al-Chvárizmí strávil většinu svého života na dvoře bagdádských chalífů. Z Al-Chvárizmího matematických děl se dochovaly pouze dvě: algebraické a aritmetické. Slovo „algebra“ vzniklo z názvu první knihy. První řádky druhé knihy byly přeloženy takto: „Algorithm řekl. Vzdejme chválu Bohu, našemu vůdci a ochránci.“ Jméno Al-Chvárizmí se tak změnilo na Algorithm, z něhož vzniklo slovo „algorithm“.

Prostudujme si „euklidovský algoritmus“ známý z matematiky. 1. Euklidovský algoritmus. Připomeňme si, jak najít největšího společného dělitele (NSD) dvou přirozených čísel: stačí zapsat rozklad těchto čísel na prvočísla a vzít jejich společnou část. U velkého počtu je však tento postup prakticky nemožný. Zkuste například tímto způsobem najít GCD čísel 1381955 a 690713. Naštěstí existuje další způsob, jak vypočítat největšího společného dělitele dvou čísel. Říká se tomu Euklidův algoritmus. Euklidův algoritmus je založen na následující jednoduché myšlence: jakýkoli společný dělitel čísel A a B (A B) také dělí číslo A–B; navíc jakýkoli společný dělitel čísel B a A–B dělí číslo A. Tedy NSD(A, B)  NSD(A–B, B)[2]. V podstatě jsme nastínili Euklidův algoritmus. Tuto rovnost lze doložit následovně: dokažte, že tyto dvojice čísel mají stejné množiny společných dělitelů, z čehož vyplývá, že i jejich největší společní dělitelé jsou stejní. Euklidův algoritmus funguje následovně: v každém kroku se od dvojice čísel A a B (A B) přesuneme k dvojici A–B a B, tj. odečteme menší číslo od většího. Pokračujeme v tomto procesu. Protože čísla nikdy nebudou záporná a vždy budou přirozená, proces nemůže pokračovat donekonečna. A kdy to přestane? A to pouze tehdy, když se čísla v páru shodují. Jakmile se to stane, nalezení jejich NSD již nebude obtížné [3]. Ukažme si na konkrétních příkladech, jak Euklidův algoritmus funguje. Příklad 1. Najděte NSD32, 12 pomocí Euklidova algoritmu. Řešení. NSD32, 12  NSD32–12, 12  NSD20, 12  NSD20 –12, 12) = =NSD8, 12  NSD8, 12–8  NSD8, 4  NSD8–4, 4  NSD4, 4 = 4. Příklad 2. Najděte NSD451, 287 pomocí Euklidova algoritmu. Řešení. NSD451, 287  NSD287, 164  NSD164, 123  NSD123, 41  NSD82, 41  NSD41, 41  41. Uvedená metoda výpočtu není optimální. Například k nalezení NSD = 100, 2 je třeba provést 50 odečítacích operací. B Následující úvaha urychlí proces hledání největšího společného dělitele: když několikrát odečítáme menší číslo od většího čísla (A–B, A–2B, A–3B), zastavíme se, když se číslo z většího čísla zmenší, například: A–4BB. Ale pak A = (A – 4B) + 4B, tj. A – 4B je zbytek z dělení A číslem B. Bylo tedy možné nevypisovat všechny A–B, A–2B atd., ale okamžitě nahradit Ana zbytkem z dělení Any B. To je často rychlejší než mnohonásobné odčítání [4]. Aby se tedy výpočet největšího společného dělitele urychlil, měla by být operace odčítání nahrazena operací odečtení zbytku z dělení. Nechť A  BQ + R, pak NSD(A, B)  NSD(B, R) [5]. Příklad 3. Najděte největšího společného dělitele čísel 7462 a 6279. Řešení. Pomocí Euklidova algoritmu máme: NSD(7462, 6279)  7462  6279 · 1 + 1183 NSD(6279, 1183)  6279  1183 · 5 + 364 NSD(1183, 364) = 1183  364 · 3 + 91 NSD364, 91  364  91 · 4 = 91. Všimněte si, že díky Euklidovu algoritmu jsme nemuseli rozkládat čísla 7462 a 6279 na prvočísla. V tomto případě není snadné je najít, protože původní čísla obsahují prvočísla jako 7, 13, 23, 41. Bohužel algoritmy pro rozklad čísel na prvočísla fungují poměrně dlouho, protože někdy musíte projít mnoha možnostmi, než najdete dalšího prvočísla. V tomto ohledu je Euklidův algoritmus mnohem rychlejší. Můžete studentům nabídnout i jiné způsoby formulace řešení. Příklad 4. Najděte GCD čísel 78 a 14. Řešení. NSD(78, 14)  NSD(78 mod14, 14)  NSD(8, 14)  NSD(8, 14 mod8) = = NSD(8, 6)  NSD(8 mod6, 6)  NSD(2, 6)  NSD(2, 6 mod2)  NSD(2, 0)  2. Příklad 5. Najděte NSD čísel 1381955 a 690713, uvažovaných na začátku článku. Řešení. NSD1381955, 690713  NSD690713, 529  NSD529, 368  =NSD368, 161  NSD161, 46  NSD46, 23  NSD23, 0  23. Uvažujme několik složitějších problémů s aplikací Euklidova algoritmu. Příklad 6. Najděte NSD čísel 2N + 13 a N + 7. Řešení. NSD (2N + 13, N + 7)  NSD (N + 7, N + 6)  NSD (N + 6, 1) = 1. Příklad 7. Dokažte, že zlomek (12N + 1) / (30N + 2) je neredukovatelný pro libovolné přirozené N. Řešení. NSD (30N + 2, 12N + 1)  NSD (12N + 1, 6N)  NSD (6N, 1) = 1.2. 2. Aplikace euklidovského algoritmu při řešení úloh. A. Úlohy s transfuzí. Nechť jsou XNUMX nádoby o objemu A a N litrů a neomezený zdroj vody. Zpočátku jsou obě nádoby prázdné. Úkolem je nabrat vodu do těchto nádob a přelít ji z jedné do druhé, aby se v jedné z nich dosáhlo požadovaného množství vody co nejmenším počtem nalití. V tomto případě je dovoleno nádoby vyprázdnit pouze úplně. Řešení tohoto problému si ukážeme na konkrétním příkladu. Příklad 8. Nechť nádoby mají objem 5 a 7 litrů a my potřebujeme získat 1 litr.

12345678A 7 l005570337V 5 l050533051

Všimněte si, že jsme potřebovali třikrát naplnit pětilitrovou nádobu a dvakrát vyprázdnit sedmilitrovou nádobu, což odpovídá rovnosti 3  2 × 1 – 5 × 3. Tento vzorec je v podstatě způsob, jak reprezentovat NSD dvou čísel (7 a 2) jako rozdíl čísel. Jak je známo z matematiky, takové znázornění vždy existuje pro největšího společného dělitele. Navíc, pokud požadovaný počet litrů není násobkem NSD původních objemů nádob, pak je takové znázornění v principu nemožné! Příklad 5. A Je možné změřit 7 litry pomocí nádob o objemu 9 a 3 litrů? B Je možné změřit 4 litry pomocí nádob o objemu 8 a 2 litrů? C Je možné změřit 4 litry pomocí nádob o objemu 8 a 3 litrů? D Je možné změřit 21 litr pomocí nádob o objemu 6 a 1 litrů? Ukazuje se, že je vždy možné odměřit počet litrů, který je násobkem NSD (A, B) a nepřesahuje objem větší nádoby. Příklad 15. Uvažujme případ, kdy A = 5 litrů, B = 10 litrů a je potřeba získat 7 litry. Výše uvedené schéma umožňuje získat výsledek v 5 nalití: 2 = 18 × 2 –5 × 6.

123456789101112131415161718A 7 l0055703370116670447V 5 l0505330511050544052

Ve skutečnosti se tento problém dal vyřešit pouhými dvěma transfuzemi: 2  7 × 1 – 5 × 1.

12A 5 l005V 7 l072

K tomu stačí prohodit nádoby! Pro identifikaci nejdynamičtější reprezentace je tedy nutné porovnat počet nalití v případě, kdy je větší nádoba naplněna pomocí menší nádoby, s počtem nalití v opačném případě a zvolit nejlepší řešení. B Úlohy na sestavování lineárních diofantových rovnic. Příklad 11. Dopravní organizace mají vozidla o nosnosti 3,5 tuny a 4,5 tuny. Musí být přepraven náklad o hmotnosti 53 tun. Kolik vozidel musí být přiděleno na jednu cestu? [6]. Nechť x vozidel má hmotnost 3,5 tuny, y vozidel má hmotnost 4,5 tuny. Sestavme a vyřešme rovnici 3,5x + 4,5y = 53. Přejděme k rovnici s celočíselnými koeficienty. Obě části rovnice vynásobíme 2. Dostaneme 7x + 9y 106. Protože NSD (7, 9)  1, má rovnice celočíselná řešení.

Protože t nabývá celočíselných hodnot, soustavu nerovnic splňují hodnoty t = –47 a t = –46. Získáváme řešení diofantovy rovnice v přirozených číslech.

řešení 11> řešení 4. Na jednu cestu si tedy můžete vzít: a. 1 auto s nosností 3,5 tuny a 11 aut s nosností 4,5 tuny; b. 10 aut s nosností 3,5 tuny a 4 auta s nosností 4,5 tuny. Je užitečné věnovat pozornost tomu, která z možných variant bude pro provoz podniku z ekonomického hlediska nejefektivnější úspora benzínu, peníze za placení řidičů atd.. 3. Úkoly k samostatnému řešení ve třídě nebo doma. 1. A. Najděte NSD (6069, 663). B. Najděte NSD (987654 321, 123456789). C. Najděte NSD (7777777777, 777777). 2. Najděte NSD . 3. Najděte NSD111…111, 11…11 – první číslo má 100 jednotek, druhé má 60.4. Vasja a Péťa našli na cestě každý balíček jedenáctirublových bankovek. V čajovně Vasja vypil 11 sklenice čaje, snědl 3 kalače a 4 bagelů. Péťa vypil 5 sklenic čaje, snědl 9 kalač a 1 bagely. Sklenice čaje, kalač a bagel stály celý počet rublů. Ukázalo se, že Vasja může platit jedenáctirublovými bankovkami bez drobného. Dokažte, že Péťa dokáže totéž.4.

Z obdélníku o rozměrech 324 cm × 141 cm se vyřízne několik čtverců o stranách 141 cm, dokud nezůstane obdélník s jednou stranou menší než 141 cm. Z výsledného obdélníku se vyříznou co nejdelší čtverce se stranami rovnými jeho kratší straně atd. Na jaké čtverce se obdélník rozřeže? (Uveďte jejich rozměry a počet). 6. Najděte největší číslo takové, že čísla a jsou celá čísla. Jinými slovy, určete délku úsečky, která je největší společnou mírou úseček o délce a . 7. Škola obdržela 1 milion rublů na nákup 100 kusů vzdělávacího vybavení (za celou částku beze změny). Vedení školy bylo nabídnuto vybavení v hodnotě 3000 8000, 12000 XNUMX a XNUMX XNUMX rublů za kus. Kolika způsoby může škola toto vybavení koupit? Uveďte jeden ze způsobů.

Odkazy na zdroje 1. Gorev P. M. Základní formy organizace dalšího matematického vzdělávání na střední škole // Koncept. –2013. –№05 květen. –ART13116. –0,3 s. –URL: http://ekoncept.ru/2013/13116.htm. 2. Matematický kroužek. První ročník, 5.–6. ročník. –M.: IztvoAPN SSSR, 1995.–85 s. 3. Tamtéž. 4. Voropaev A. S., Dergach P. S., Mamedova F. I., Tsimbalov Yu. A. Teorie čísel –3. Euklidův algoritmus. 9.–11. ročník // Malý MekhMatMSU.–URL: http://mmmf.msu.ru/archive/20112012/Voropaev/8.html. 5. Vaguten V. N. Euklidův algoritmus a základní věta aritmetiky//Quantum. –1972.–№ 6.–S. 30–35.6. 2009. Šatilova A. V., Šatilov D. S. Volitelný kurz „Příběhy Šeherezády a Diofantovy rovnice“. –Balashov: Nikolajev, 56. –XNUMX s.

Novoselova Olg, učitelka matematiky, Škola číslo 60, [email protected], Lekce matematického kroužku pro žáky 7.–9. ročníku na téma „Euklidův algoritmus“, Abstrakt. Článek představuje vývoj lekcí matematického kroužku na téma „Euklidův algoritmus“, určených pro žáky 7. až 9. ročníku. Časová délka hodiny je navržena na 2–3 hodiny. Zabýváme se původem slova algoritmus. Podstata euklidovského algoritmu je prezentována ve formě dvou vzorců. Článek také uvádí příklady použití euklidovského algoritmu, včetně jeho účelu pro transfuzi a zápisu lineárních diofantových rovnic. Klíčová slova: největší společný dělitel dvou celých čísel, rozvoj počtu prvočísel, algoritmus, euklidovský algoritmus, úlohy pro transfuzi, úlohy pro sestavení lineárních diofantových rovnic.

Doporučeno k publikaci: Gorev P. M., kandidát pedagogických věd, šéfredaktor časopisu „Koncept“; Utemov V. V., kandidát pedagogických věd