გაკვეთილის შეჯამება და პრეზენტაცია ევკლიდური ალგორითმი კვანძების საპოვნელად. პრეზენტაცია თემაზე „ევკლიდეს ალგორითმი“ თემა: ევკლიდესის ალგორითმი GCD-ს საპოვნელად

პრეზენტაციების წინასწარი გადახედვის გამოსაყენებლად შექმენით Google ანგარიში (ანგარიში) და შედით: https://accounts.google.com

სლაიდების წარწერები:

ევკლიდეს ალგორითმი ევკლიდე, ძველი ბერძენი მათემატიკოსი. III საუკუნეში მოღვაწეობდა ალექსანდრიაში. ძვ.წ ე. მთავარი ნაშრომი "დასაწყისები" (15 წიგნი), რომელიც შეიცავს ანტიკური მათემატიკის საფუძვლებს, ელემენტარულ გეომეტრიას, რიცხვთა თეორიას, ურთიერთობების ზოგად თეორიას და ტერიტორიებისა და მოცულობების განსაზღვრის მეთოდს, რომელიც მოიცავდა ლიმიტების თეორიის ელემენტებს. მან დიდი გავლენა მოახდინა მათემატიკის განვითარებაზე. მუშაობს ასტრონომიაზე, ოპტიკაზე, მუსიკის თეორიაზე. ევკლიდე (ძვ.წ. 365-300)

ეუკლიდის ალგორითმი ევკლიდის ალგორითმი არის ალგორითმი ორი არაუარყოფითი მთელი რიცხვის უდიდესი საერთო გამყოფის (GCD) საპოვნელად. ევკლიდე (ძვ. წ. 365-300 წწ.) ძველი ბერძენი მათემატიკოსები ამ ალგორითმს ἀνθυφαίρεσις ან ἀνταναίρεσις - „ურთიერთ გამოკლებას“ უწოდებდნენ.

გამოთვლა GCD GCD = ორი ნატურალური რიცხვის უდიდესი საერთო გამყოფი არის უდიდესი რიცხვი, რომლითაც ორივე საწყისი რიცხვი იყოფა ნაშთების გარეშე. gcd(a , b)= gcd(a-b, b)= gcd(a, b-a) შეცვალეთ ორი რიცხვიდან უფრო დიდი სხვაობით უფრო დიდსა და პატარას შორის, სანამ ისინი არ იქნებიან ტოლი. ეს არის NOD. gcd(18, 45) = gcd(18, 45-18) = gcd(18, 27) = gcd(18, 9) = =gcd(9,9)=9 მაგალითი:

STEP ოპერაცია M N მდგომარეობა 1 შეყვანა M 48 2 შეყვანა N 18 3 M  N 48 18, დიახ 4 M>N 48>18, დიახ 5 M:=M-N 30 6 M  N 30  18, დიახ 7 M>N >18, დიახ 8 M:=M-N 12 9 M  N 12 18, დიახ 10 M>N 12 >18, არა 11 N:=N-M 6 12 M  N 12  6, დიახ 13 M>N 12 >6 , დიახ 14 M:=M-N 6 15 M  N 6  6, არა 16 გამომავალი M

პროგრამა ევკლიდი ; var m, n: მთელი რიცხვი; დაიწყეთ წერა ("vved 2 chisla"); readln(m,n); ხოლო mn იწყება თუ m>n მაშინ m:=m-n სხვა n:= n-m ; დასასრული; write("nod=",m); წაკითხული ბოლომდე.

0.გაუშვით Evklid პროგრამა კომპიუტერზე. გამოცადეთ M=32, N=24; M=696, N=234. ერთი . შეამოწმეთ, არის თუ არა ორი მოცემული რიცხვი თანაპრომიტი. Შენიშვნა. ამბობენ, რომ ორი რიცხვი თანაპირდაპირია, თუ მათი უდიდესი საერთო გამყოფი არის 1. 2. იპოვეთ n და m რიცხვების უმცირესი საერთო ჯერადი (LCM), თუ LCM(n, m) = n * m / gcd(n, m). 3 . მოცემულია m და n ნატურალური რიცხვები. იპოვეთ p და q ნატურალური რიცხვები, რომლებსაც არ აქვთ ისეთი საერთო გამყოფები, რომ p/q = m/n. 4. იპოვეთ სამი რიცხვის GCD. Შენიშვნა. GCD(a, b, c)= GCD(gcd(a, b), c) ამოცანები

გადახედვა:

თემა: "ევკლიდეს ალგორითმი"

გაკვეთილის მიზნები:

1. საგანმანათლებლო:

1. ისწავლეთ ევკლიდეს ალგორითმის გამოყენება ორი და სამი რიცხვის gcd-ის საპოვნელად
2. ალგორითმული სტრუქტურების "განშტოება" და "ციკლი" გამოყენების უნარების კონსოლიდაცია.
3. მიიღეთ გამოცდილება პასკალის პროგრამირების ენაზე პროგრამების დაწერისა და გამართვის სფეროში

1. საგანმანათლებლო:

1. ახალი მასალის შესწავლისას დამოუკიდებლობისა და პასუხისმგებლობის ჩამოყალიბება

1. განვითარება:

1. ყურადღებისა და ანალიტიკური აზროვნების განვითარება

Გაკვეთილის გეგმა:

1. ორგანიზების დრო
2. ცოდნის განახლება
3. ახალი თემის ახსნა
4. პრაქტიკული ნაწილი
5. გაკვეთილის შეჯამება
6. Საშინაო დავალება.

ორგანიზების დრო

სალამი. ვინც არ არის. ნომერი. გაკვეთილის თემა. კითხვები საშინაო დავალების შესახებ.

ცოდნის განახლება.

კითხვები:

რა ტიპის ალგორითმული სტრუქტურები იცით?

რა არის ხაზოვანი სტრუქტურა? (Bl-sh)

რა არის განშტოება სტრუქტურა? (Bl-sh)

რა არის ციკლური სტრუქტურა? (Bl-sh)

რა ტიპის ციკლები იცით?

როგორ ხორციელდება ციკლი ცნობილი რაოდენობის გამეორებით პასკალის პროგრამირების ენაში?

როგორ ხორციელდება პასკალის პროგრამირების ენაში გამეორებების უცნობი რაოდენობის მარყუჟი?

ახალი თემის ახსნა (პრეზენტაცია)

ევკლიდეს შესახებ;

ევკლიდეს ალგორითმის იდეა

ამ ალგორითმის იდეა ეფუძნება:

1. თვისება, რომ თუ M>N, მაშინ GCD(M, N) = GCD(M - N, N).

სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd ტოლია მათი დადებითი სხვაობის gcd (მათი განსხვავების მოდული) და მცირე რიცხვის.

მტკიცებულება: მოდით K იყოს M და 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 გამყოფი, მათ შორის უდიდესი. საერთო გამყოფი.

2. მეორე აშკარა თვისება:

GCD(M, M) = M.

"ხელით" დათვლისთვის ევკლიდეს ალგორითმი ასე გამოიყურება:

1) თუ რიცხვები ტოლია, მაშინ პასუხად მიიღეთ რომელიმე მათგანი, წინააღმდეგ შემთხვევაში გააგრძელეთ ალგორითმი;

2) ჩაანაცვლეთ უფრო დიდი რიცხვი რიცხვთა უფრო დიდსა და პატარას შორის სხვაობით;

3) დაუბრუნდეთ 1-ლი პუნქტის შესრულებას.

ევკლიდეს ალგორითმის ბლოკ-სქემა

პროგრამა JS Pascal-ში

პროგრამა ევკლიდი;

var m, n: მთელი რიცხვი;

დაიწყოს

writeln ("vved 2 ნომერი");

readln(m,n);

მიუხედავად იმისა, რომ mn აკეთებს

დაწყება

თუ m>n

მაშინ m:=m-n

სხვა n:=n-m;

დასასრული;

Write("nod=",m);

წაკითხული

დასასრული.

პრაქტიკული ნაწილი

კითხვები და დავალებები:

1. გაუშვით Evklid პროგრამა თქვენს კომპიუტერში. გამოცადეთ M=32, N=24; M = 696, N = 234.
2. შეამოწმეთ, არის თუ არა ორი მოცემული რიცხვი თანაპრომიტი. Შენიშვნა. ითვლება, რომ ორი რიცხვი თანაპირდაპირია, თუ მათი უდიდესი საერთო გამყოფი არის 1.

გაკვეთილის შეჯამება

დღეს გაკვეთილზე გავეცანით ევკლიდის ალგორითმს, რომელიც საშუალებას გვაძლევს ვიპოვოთ ორი არაუარყოფითი მთელი რიცხვის GCD, დავწერეთ პროგრამა პასკალის პროგრამირების ენაზე, რომელიც ახორციელებს ამ ალგორითმს. სახლში მიიღებთ დავალებას, რომელშიც გამოიყენებთ ამ ალგორითმს სამი რიცხვის GCD და ორი რიცხვის LCM-ის მოსაძებნად.

Საშინაო დავალება.

1. დაწერეთ პროგრამა, რომ იპოვოთ სამი რიცხვის უდიდესი საერთო გამყოფი შემდეგი ფორმულის გამოყენებით:

gcd(A, B, C) = gcd(gcd(A, B), C)

2. დაწერეთ პროგრამა ორი რიცხვის უმცირესი საერთო ჯერადი (LCM) საპოვნელად ფორმულის გამოყენებით:

A  B \u003d GCD (A, B)  LCM (A, B)

სლაიდი 1

სლაიდი 2

სლაიდი 3

სლაიდი 4

სლაიდი 5

სლაიდი 6

სლაიდი 7

სლაიდი 2

ევკლიდეს ალგორითმი არის ალგორითმი ორი არაუარყოფითი მთელი რიცხვის უდიდესი საერთო გამყოფის (gcd) საპოვნელად. ევკლიდე (ძვ. წ. 365-300 წწ.) ძველი ბერძენი მათემატიკოსები ამ ალგორითმს ἀνθυφαίρεσις ან ἀνταναίρεσις - „ურთიერთ გამოკლებას“ უწოდებდნენ.

სლაიდი 3

GCD გაანგარიშება

GCD = ორი ნატურალური რიცხვის უდიდესი საერთო გამყოფი არის უდიდესი რიცხვი, რომლითაც ორივე საწყისი რიცხვი იყოფა ნაშთის გარეშე. GCD(a,b)= GCD(a-b, b)= GCD(a, b-a) შეცვალეთ ორი რიცხვიდან უფრო დიდი სხვაობით უფრო დიდ და პატარა რიცხვებს შორის, სანამ ისინი არ იქნებიან ტოლი. ეს არის NOD. GCD (18, 45)= GCD (18, 45-18)= GCD (18, 27)= GCD (18, 9)= = GCD(9,9)=9 მაგალითი:

სლაიდი 4

სლაიდი 5

პროგრამა ევკლიდი; var m, n: მთელი რიცხვი; დაიწყე წერა ("ვდ 2 ნომერი"); readln(m,n); ხოლო mn იწყება თუ m>n მაშინ m:=m-n სხვა n:=n-m; დასასრული; write("nod=",m); წაკითხული ბოლომდე.

სლაიდი 6

0.გაუშვით Evklid პროგრამა კომპიუტერზე. გამოცადეთ M=32, N=24; M=696, N=234. 1. შეამოწმეთ არის თუ არა ორი მოცემული რიცხვი თანაპრომიტი. Შენიშვნა. ორ რიცხვს უწოდებენ თანაპირს, თუ მათი უდიდესი საერთო გამყოფი არის 1. 2. იპოვეთ n და m რიცხვების უმცირესი საერთო ჯერადი (LCM), თუ LCM(n, m) = n * m / gcd(n, m). 3. მოცემულია m და n ნატურალური რიცხვები. იპოვეთ p და q ნატურალური რიცხვები საერთო გამყოფების გარეშე, რომ p / q = m / n. 4. იპოვეთ სამი რიცხვის GCD. Შენიშვნა. gcd(a, b, c)= gcd(gcd(a, b), c) ამოცანები

სლაიდი 7

ევკლიდე, ძველი ბერძენი მათემატიკოსი. III საუკუნეში მოღვაწეობდა ალექსანდრიაში. ძვ.წ ე. მთავარი ნაშრომი "დასაწყისები" (15 წიგნი), რომელიც შეიცავს ანტიკური მათემატიკის საფუძვლებს, ელემენტარულ გეომეტრიას, რიცხვთა თეორიას, ურთიერთობების ზოგად თეორიას და ტერიტორიებისა და მოცულობების განსაზღვრის მეთოდს, რომელიც მოიცავდა ლიმიტების თეორიის ელემენტებს. მან დიდი გავლენა მოახდინა მათემატიკის განვითარებაზე. მუშაობს ასტრონომიაზე, ოპტიკაზე, მუსიკის თეორიაზე.

ყველა სლაიდის ნახვა

პრობლემის ფორმულირება განიხილეთ შემდეგი ამოცანა: საჭიროა დაწეროთ პროგრამა ორი ნატურალური რიცხვის უდიდესი საერთო გამყოფის (GCD) დასადგენად. გავიხსენოთ მათემატიკა. ორი ნატურალური რიცხვის უდიდესი საერთო გამყოფი არის უდიდესი ნატურალური რიცხვი, რომლითაც ისინი თანაბრად იყოფა. მაგალითად, 12 და 18 რიცხვებს აქვთ საერთო გამყოფები: 2, 3, 6. ყველაზე დიდი საერთო გამყოფი არის რიცხვი 6. ეს იწერება შემდეგნაირად: gcd(12,18) = 6. აღნიშნეთ საწყისი მონაცემები M და N. პრობლემის ფორმულირება ასეთია: მოცემულია: M, N იპოვეთ: GCD(M, N).

N, შემდეგ GCD(M,N) = GCD(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd-ს და პატარა რიცხვს." title="(!LANG:ალგორითმის იდეა ამ ალგორითმის იდეა ეფუძნება თვისება, რომ თუ M>N, მაშინ gcd(M,N) = gcd( M - N, N) სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd და უფრო მცირე რიცხვს." class="link_thumb"> 4 !}ალგორითმის იდეა ამ ალგორითმის იდეა ემყარება იმ თვისებას, რომ თუ M>N, მაშინ GCD(M,N) = GCD(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd და პატარა რიცხვს. N, შემდეგ GCD(M,N) = GCD(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd და უფრო მცირე რიცხვს."> N, შემდეგ gcd(M,N) = gcd(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობისა და უფრო მცირე რიცხვის gcd-ს."> N, შემდეგ GCD(M,N) = GCD(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd-ს და პატარა რიცხვს." title="(!LANG:ალგორითმის იდეა ამ ალგორითმის იდეა ეფუძნება თვისება, რომ თუ M>N, მაშინ gcd(M,N) = gcd( M - N, N) სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd და უფრო მცირე რიცხვს."> title="ალგორითმის იდეა ამ ალგორითმის იდეა ემყარება იმ თვისებას, რომ თუ M>N, მაშინ GCD(M,N) = GCD(M - N,N). სხვა სიტყვებით რომ ვთქვათ, ორი ნატურალური რიცხვის gcd უდრის მათი დადებითი სხვაობის gcd და პატარა რიცხვს."> !}

ნ). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები და m>n. მაშინ M - N = K(m - n), რაც გულისხმობს, რომ K არის M - N-ის გამყოფი. აქედან გამომდინარე, M და N-ის ყველა საერთო გამყოფი გამყოფია" title="(!LANG:Proof მოდით K იყოს საერთო გამყოფი M და N (M > N). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები, და m> n. შემდეგ M - N = K(m - n), საიდანაც ის მოჰყვება რომ K არის M - N რიცხვის გამყოფი. აქედან გამომდინარე, M და N რიცხვების ყველა საერთო გამყოფი გამყოფია." class="link_thumb"> 5 !}დადასტურება მოდით K იყოს M და-ს საერთო გამყოფი. N (M>N). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები და m>n. მაშინ M - N = K(m - n), აქედან გამომდინარეობს, რომ K არის M - N რიცხვის გამყოფი. აქედან გამომდინარე, M და N რიცხვების ყველა საერთო გამყოფი არის მათი სხვაობის M - N გამყოფი, მათ შორის უდიდესი. საერთო გამყოფი. აქედან გამომდინარე: GCD(M,N) = GCD(M - N,N). მეორე აშკარა თვისება: GCD(M,M) = M. ნ). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები და m>n. შემდეგ M - N \u003d K (m - n), აქედან გამომდინარეობს, რომ K არის M - N რიცხვის გამყოფი. აქედან გამომდინარე, M და N რიცხვების ყველა საერთო გამყოფი არის გამყოფი "\u003e N). ეს ნიშნავს, რომ M \u003d mK, N \u003d pK , სადაც m, n არის ნატურალური რიცხვები და m > n. შემდეგ M - N = K(m - n), აქედან გამომდინარეობს, რომ K არის M - N რიცხვის გამყოფი. მაშასადამე, M და N რიცხვების ყველა საერთო გამყოფი არის მათი სხვაობის M-N გამყოფი, მათ შორის უდიდესი საერთო გამყოფი.აქედან გამომდინარე: GCD(M, N) = GCD(M - N, N). მეორე აშკარა თვისება: GCD(M , M) = M."> N). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები და m>n. მაშინ M - N = K(m - n), რაც გულისხმობს, რომ K არის M - N-ის გამყოფი. აქედან გამომდინარე, M და N-ის ყველა საერთო გამყოფი გამყოფია" title="(!LANG:Proof მოდით K იყოს საერთო გამყოფი M და N (M > N). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები, და m> n. შემდეგ M - N = K(m - n), საიდანაც ის მოჰყვება რომ K არის M - N რიცხვის გამყოფი. აქედან გამომდინარე, M და N რიცხვების ყველა საერთო გამყოფი გამყოფია."> title="დადასტურება მოდით K იყოს M და-ს საერთო გამყოფი. N (M>N). ეს ნიშნავს, რომ M = mK, N = pK, სადაც m, n არის ნატურალური რიცხვები და m>n. შემდეგ M - N \u003d K (m - n), რაც გულისხმობს, რომ K არის M - N რიცხვის გამყოფი. აქედან გამომდინარე, M და N რიცხვების ყველა საერთო გამყოფი გამყოფია."> !}

პროგრამა პასკალის პროგრამაში Evklid; var M, N: მთელი რიცხვი; დაიწყეთ წერა ("შეიყვანეთ M და N"); readln(M,N); ხოლო MN იწყება თუ M>N მაშინ M:=M-N სხვა N:=N-M დასასრული; write("HOD=",M) დასასრული. N შემდეგ M:=M-N სხვა N:=N-M დასასრული; write("HOD=",M) დასასრული."> N შემდეგ M:=M-N სხვა N:=N-M დასასრული; write("HOD=",M) დასასრული."> N შემდეგ M:=M-N სხვა N:=N-M დასასრული; write("HOD=",M) end." title="(!LANG:Pascal პროგრამის პროგრამა Evklid; var M, N: integer; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N შემდეგ M:=M-N სხვა N:=N-M დასასრული; write("HOD=",M) end." title="(!LANG:Pascal პროგრამის პროგრამა Evklid; var M, N: integer; start writeln("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}