წრის დაკავების ევკლიდეს ალგორითმის პრეზენტაცია. პრეზენტაცია თემაზე „ევკლიდეს ალგორითმი“. ევკლიდეს ალგორითმის იდეა

Კლასი: 6

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

• დააფიქსირეთ ალგორითმი უდიდესი საერთო გამყოფის მოსაძებნად ფაქტორიზაციის გამოყენებით;
• გაიმეორეთ დაკავშირებული განმარტებები და ცნებები;
• გააცნოს მოსწავლეებს ევკლიდეს ალგორითმი;
• მათემატიკური კულტურის უნარ-ჩვევების ჩამოყალიბება

აღჭურვილობა: კომპიუტერი, პროექტორი, ეკრანი.

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

1. საორგანიზაციო მომენტი (მოსწავლეთა მზადყოფნის შემოწმება გაკვეთილზე, არყოფნის აღნიშვნა) (1 წთ)

2. ზეპირი სამუშაო: (6 წთ)

1. შეცვალეთ პროდუქტი ხარისხით:

დ) ა * ა * ა * ა * ა

1. გამოთვალეთ: 2 3 ; 52; 3 3 ; 10 4 .
2. იპოვეთ გამოთქმის მნიშვნელობა: (3?3?5?11): (3?11). რა დასკვნის გაკეთება შეიძლება?
3. შეასრულეთ გაყოფა აზე ბთუ a=170, b=35. დაწერეთ ტოლობა, რისი ტოლია ა.

დაწერეთ ეს ტოლობა ზოგადი ფორმით: a იქნება იყოფა, ხოლო b გამყოფი. კოეფიციენტი იყოს q და ნაშთი r, მაშინ: a = bq + r და q შეიძლება იყოს ბუნებრივი რიცხვი ან ნული. შეიძლება r იყოს ნებისმიერი რიცხვი? [r არის ნატურალური რიცხვი და 0 < r < b .] რა შეიძლება ითქვას a და b რიცხვებზე, თუ r = 0? მთელი რიცხვის გაყოფა ნაშთით გაყოფის განსაკუთრებული შემთხვევაა.

4. გაარკვიეთ და ახსენით რიცხვი a იყოფა თუ არა ნაშთების გარეშე b რიცხვზე, თუ:

ა) a = 2 3 * 3 * 5 * 7;

ბ) a \u003d 2 4 * 3 * 5 7;

b = 2 7 * 3 * 5 4

გ) a \u003d 2 * 3 4 * 5 * 13;

b = 2 * 3 3 * 5 * 11.

3. საბაზისო ცოდნის განახლება(10 წუთი)

1) კითხვები:

რა არის რიცხვის გამყოფი ა ?

რა არის მარტივი რიცხვი?

რას ნიშნავს რიცხვის გამრავლება პირველ ფაქტორებად?

2, 3, 5, 9,10-ზე გაყოფის ნიშნების ჩამოყალიბება;

მოიყვანეთ ერთნიშნა კომპოზიციური რიცხვის მაგალითი;

მართალია, რომ რიცხვი 77 მარტივი რიცხვია?

რატომ, თუ ერთი რიცხვი შეიძლება დაიშალოს 2 მარტივ ფაქტორად, ხოლო მეორე 3 მარტივ ფაქტორად, მაშინ ეს რიცხვები არ არის ტოლი?

რომელი რიცხვი, მარტივი თუ შედგენილი, არის ორი მარტივი რიცხვის ნამრავლი?

რა არის ორი ან მეტი რიცხვის ყველაზე დიდი საერთო გამყოფი?

რომელ რიცხვებს ჰქვია თანაპრიმი?

გაიმეორეთ GCD-ის პოვნის გზები: არსებობს სხვადასხვა ალგორითმები ნატურალური რიცხვების GCD-ის საპოვნელად.

1 გზა:თუ მოცემულია ორი რიცხვი და ისინი შედარებით მცირეა, მაშინ საუკეთესო ალგორითმი არის უხეში ძალის ძიება. თუმცა, დიდი რიცხვებისთვის იპოვეთ gcd(a;b) რიცხვების ყველა გამყოფის ჩამოთვლით. ადა ბპროცესი შრომატევადი და არასანდოა.

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

2 გზა:რიცხვების ფაქტორინგით (ყველაზე გავრცელებული) (დანართი, სლაიდი 1)

2) გამოთვალეთ 24 და 16 რიცხვების GCD.

3) ფაქტორზე მოახდინე რიცხვები: 875 და 8000 და გამოთვალე ამ რიცხვების GCD.

(მაგალითად 8000 რიცხვის გამოყენებით, გაიმეორეთ ნულებით დამთავრებული რიცხვების ფაქტორინგის უფრო მარტივი გზა: ვინაიდან 10=2 *5, შემდეგ 8000=2 * 5 * 2 * 5 *2 * 5 * 2 * 2 * 2==2 6 *5 3)

4) შეიძლება თუ არა სამი რიცხვის GCD იყოს 15-ის ტოლი, თუ მათი ნამრავლი უდრის 3000-ს? [ არა, როგორც

15 \u003d 3 * 5, რაც ნიშნავს, რომ ნომერი 3 უნდა იყოს შეტანილი სამი ნომრიდან თითოეულის გაფართოებაში. მაგრამ, 3000 = 2 3 * 3 * 5 3 .]

5) პ მიირთვით დავალება„კლასში შემოიტანეს სახელმძღვანელოები: მათემატიკაში 24, ისტორიაში 36 და გეოგრაფიაში 48. რა არის ამ წიგნებიდან ყველაზე მეტი კომპლექტის დამზადება, რომ თითოეულში მათემატიკაში, ისტორიაში და გეოგრაფიაში წიგნების ერთნაირი რაოდენობა იყოს? რამდენი წიგნი იქნება თითოეულ კომპლექტში?"

4. გადამოწმების სამუშაო (დანართი, სლაიდი 2) (6 წთ)

5. ახალი მასალის შესწავლა (10 წთ)

მასწავლებელი: GCD(a, b)-ის პოვნის შესწავლილი მეთოდი მარტივი, გასაგები და მოსახერხებელია, მაგრამ მას აქვს მნიშვნელოვანი ნაკლი: თუ მოცემული რიცხვები დიდია და არც ისე ადვილად ფაქტორიზირებული, მაშინ ამოცანაა იპოვოთ GCD(a, b) საკმაოდ რთული ხდება. გარდა ამისა, შეიძლება აღმოჩნდეს, რომ დიდი შრომის შემდეგ, ჩვენ დავრწმუნდებით, რომ GCD(a, b) = 1 და როგორც ჩანს, ყველა სამუშაო უშედეგოდ შესრულდა.

ევკლიდემ იპოვა gcd(a, b)-ის პოვნის შესანიშნავი გზა რიცხვების წინასწარი დამუშავების გარეშე. (დანართი, სლაიდები 3 და 4)შემდგომში ეს ალგორითმი ცნობილი გახდა როგორც ევკლიდეს ალგორითმი)

გავეცნოთ ევკლიდეს ალგორითმს. დაე, საჭირო გახდეს gcd(102;84) პოვნა. გაყავით ერთი რიცხვი მეორეზე და იპოვეთ დარჩენილი.

ახლა გავაკეთოთ იგივე ოპერაცია 84 და 18 ნომრებზე:

შემდეგი ნაბიჯი არის 18 და 12:

ახლა - 12 და 6:

0-ნარჩენი. პროცესი დასრულდა.

ეს პროცესი არ შეიძლება იყოს უსასრულო, რადგან ნარჩენები მცირდება და რჩება არაუარყოფითი მთელი რიცხვები, რომელთა სიმრავლე, როგორც ცნობილია, შემოსაზღვრულია ქვემოდან:

84 >18 > 12> 6 >0

თუ ყურადღებით დააკვირდებით დაწერილ ტოლობებს, შეგიძლიათ დაადგინოთ, რომ რიცხვების ყველა წყვილის GCD ერთმანეთის ტოლია (მოიწვიეთ სტუდენტები დაფიქრდნენ - რატომ?),

ანუ gcd(102;84)=gcd(84;18)=gcd(18;12)=gcd(12;6)=6. მაგრამ რიცხვი 6 არის ბოლო არა-0 ნაშთი .

მართლაც, თუ c არის a და b რიცხვების თვითნებური საერთო გამყოფი, მაშინ r = a - bq იყოფა c-ზე; და პირიქით, თუ c არის b და r-ის თვითნებური საერთო გამყოფი, მაშინ a იყოფა c-ზე. ანუ (a; b) და (b; r) წყვილების ყველა საერთო გამყოფი ემთხვევა და შესაბამისად მათი უდიდესი საერთო გამყოფებიც ემთხვევა.

ევკლიდეს ალგორითმის მოხერხებულობა განსაკუთრებით შესამჩნევი ხდება, თუ აღნიშვნის ფორმას გამოვიყენებთ ცხრილის სახით:

ამ ტაბლეტში პირველად იწერება ორიგინალური ნომრები, იყოფა გონებაში, იწერება ნარჩენები მარჯვნივ, ხოლო პირადები ბოლოში პროცესის დასრულებამდე. ბოლო გამყოფი არის GCD.

ამგვარად, ორი რიცხვის ყველაზე დიდი საერთო გამყოფი არის უკანასკნელი, რომელიც არ უდრის 0-ს, ნაშთი დიდი რიცხვის უფრო მცირეზე გაყოფისას, ე.ი. თუ a = b*q + r, შემდეგ gcd(a; b) = gcd(b; r)

ოპერაციების ამ თანმიმდევრობას ე.წ ევკლიდეს ალგორითმი. ეს ალგორითმი საშუალებას გაძლევთ იპოვოთ რიცხვების GCD მათი ფაქტორინგის გარეშე (დანართი, სლაიდი 5)

6. ვარჯიშები (10 წთ)

1. მიზანშეწონილია განიხილოს მაგალითი. მოდით, საჭირო გახდეს 323 და 437 რიცხვების GCD-ის პოვნა. ამის გაკეთება ადვილი არ არის შერჩევით ან მარტივ ფაქტორებად დაშლით, რადგან არცერთი ეს რიცხვი არ არის 2, 3, 5, 7, 11-ის ჯერადი. გააგრძელეთ შემდეგნაირად (

თემა: ევკლიდეს ალგორითმი GCD-ს საპოვნელად.

მიზნები:გაიმეორეთ ადრე შესწავლილი თემები Greatest Common Divisor და Least Common Multiple, შემოიტანეთ ევკლიდეს ალგორითმი.

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

განვითარების ამოცანები - ლოგიკური აზროვნების, ყურადღების, მეტყველების მეხსიერების განვითარება, ახალი ცოდნის დამოუკიდებლად აღმოჩენის უნარი, მათემატიკური ცნობისმოყვარეობა, საგნის მიმართ შემეცნებითი ინტერესი.

განათლების ამოცანებია მათემატიკური აზროვნების კულტურის განვითარება, ურთიერთდახმარება, თვითშემოწმება და შეცდომების ანალიზი.

ბარათებზე მუშაობა

იპოვეთ GCD ან LCM ნომრები და გაშიფრეთ ფრაზა:

34

16

300

6

1

12

2

34

11

17

D: GCD (33.88)

H: NOC (9.40)

A: NOK (14.42)

E: GCD (48.18)

R: NOC (17.5)

C: GCD (48.24)

K: GCD (72.12)

L: GCD (20.14)

E: GCD (30.18)

M: NOC(25.12)

T: NOC(4,8,16)

H: NOC (12.40)

B: GCD (18.35)

A: GCD (17.34)

I: gcd (102.68)

E: GCD(18,12)

ბოლო ცხრილში ჩაწერეთ რიცხვების დარჩენილი წყვილი

პასუხები:

34

16

300

6

1

12

2

34

11

17

მაგრამ

ლ

გ

ო

რ

და

თ

მ

ე

AT

რომ

ლ

და

დ

მაგრამ

D: GCD(33.88)=11

G: LCM(9.40)=360

A: LCM(14.42)=42

E: GCD(48,18)=6

P: LCM (17.5) = 85

C: GCD(48,24)=24

K: GCD (72.12)=12

L: GCD(20,14)=2

E: GCD(30,18)=6

M: LCM(25,12)=300

T: LCM(4,8,16)=16

H: LCM(12.40)=120

B: gcd(18,35)=1

პასუხი: GCD(17.34)=17

და: GCD(102.68)=34

E: GCD(18,12)=6

გამოიცანით კიდევ 2 სიტყვა

რა შეიძლება ითქვას ბოლო ცხრილის ციფრებზე? ისინი კოპრაიმები არიან, ე.ი. თუ ამ რიცხვებს დავშლით მარტივ ფაქტორებად, მაშინ მათ არ ექნებათ იგივე ფაქტორები. როგორ მოვძებნოთ ასეთი რიცხვების GCD? ასეთი რიცხვების ქნევა =1. და როგორ მოვძებნოთ LCM, იმისათვის რომ იპოვოთ LCM, თქვენ უნდა გაამრავლოთ ეს რიცხვები ერთმანეთზე.

პირველ სვეტში არის რიცხვების წყვილი, რომლებშიც ერთი მათგანი მთლიანად არ იყოფა მეორეზე. იმათ. დარჩენილი არ არის 0.

როგორ იპოვნეთ ასეთი რიცხვების GCD და LCM? (ამ რიცხვების მარტივ ფაქტორებად დაშლით)

LCM(12,40)=2 3 *3*5=120

გაიხსენეთ GCD და LCM პოვნის წესი, იპოვეთ და შეამოწმეთ ფორმულა LCM (a, b) \u003d (a * b): GCD (a, b)

3 *3*11=264

LCM (a, b) \u003d (a * b): GCD (a, b)

264=(33*88):11=3*88=264

LCM(20,14)=2 2 *5*7=140

LCM (a, b) \u003d (a * b): GCD (a, b)

140=(20*14):2=10*14=140

GCD(12,40)=2 2 =4

LCM (a, b) \u003d (a * b): GCD (a, b)

120=(12*40):4=3*4=120

ახალი თემის შესწავლა:

რა წყვილი რიცხვების GCD არის 6?

6=gcd(48.18)=gcd(30.18)=gcd(12.18)

რა შეამჩნიე? როგორ მიიღეთ 30? 48-18

როგორ მიიღეთ 12? 30-18

როდესაც a> b \u003d GCD (a-b, c)

იმათ. GCD (a, c) როდესაც v> a = GCD (a, c-a)

ვის შეუძლია გააგრძელოს ეს თანასწორობა?

6=gcd(48.18)=gcd(30.18)=gcd(12.18) = gcd(12.6)=gcd(6.6)=6

ევკლიდეს ალგორითმი ამ წესს ეფუძნება.

ევკლიდეს ალგორითმი- ეფექტურია ორის საპოვნელად. ალგორითმი დასახელებულია, ვინც პირველად აღწერა VII და X წიგნებში "".

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

ძველი ბერძენი მათემატიკოსები ამ ალგორითმს „ურთიერთ გამოკლებას“ უწოდებდნენ.

ამ მეთოდის არსი მდგომარეობს შემდეგში: გამოაკლეთ პატარა რიცხვი უფრო დიდ რიცხვს, სანამ რიცხვები არ გათანაბრდება, დიდის ჩანაცვლება სხვაობით. როგორც კი ეს მოხდება, GCD იპოვება. (მაგალითი დაფაზე - ნომრები 48 და 18)

პირველი კითხვა არის, არის თუ არა ეს რიცხვები ტოლი? არა, ისინი არ არიან ტოლები, ამიტომ უფრო დიდს ვაკლებთ 48-18 = 30. 30 არ არის 18-ის ტოლი, რაც ნიშნავს 30-18= 12, 18-12=6, 12-6=6. ანუ ვასრულებთ ამ მოქმედებებს მანამ, სანამ რიცხვები არ გაუტოლდება. აქედან გამომდინარე, gcd(48,18)=6

იცოდეთ 48 და 18 ნომრების GCD, იპოვეთ NOC. LCM(48,18)=(48*18):6=48*3=144

ვიპოვოთ GCD(102;68) ევკლიდეს ალგორითმის გამოყენებით.

მოდი ვიპოვოთ NOD (357;273)

აქ ჩვენ გამოვაკლეთ რიცხვი 84 3-ჯერ და რიცხვი 21 სამჯერ.

როგორ გავარკვიოთ გამოკლების გარეშე რამდენი გამოკლება იქნება ერთ სერიაში და რა განსხვავება იქნება შედეგი? რა შემთხვევებია გასათვალისწინებელი? ( მითითება: დაიმახსოვრე გაყოფა.)

ზოგადი წესი შეიძლება ჩამოყალიბდეს შემდეგნაირად: თუ რიცხვი აარ იყოფა ბ, მაშინ ის შეიცვლება მისი ნაშთით გაყოფისას ბ(როდესაც ა< ბეს ნარჩენი არის ა); თუ აიყოფა ბ, შემდეგ შეცვალეთ იგი ნომრით ბ. ზუსტად იგივე წესი, პერმუტაციით ადა ბ, ასევე მოქმედებს ბ. უფრო დიდი რიცხვი გაყოფა მცირეზე, შემდეგ მცირეზე პირველ ნარჩენზე, შემდეგ პირველი ნაშთი მეორე ნაშთზე და ასე შემდეგ, სანამ არ მიიღებთ 0-ს. შემდეგბოლო ნაშთი, რომელიც არ უდრის 0-ს, არის GCD .

იპოვეთ GCD (357;273).

357 273 273 84 84 21 GCD (357; 273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

gcd(357.273)=gcd(273.84)=gcd(84.21)=21

ევკლიდეს ალგორითმის მოხერხებულობა განსაკუთრებით შესამჩნევი ხდება, თუ აღნიშვნის ფორმას გამოვიყენებთ ცხრილის სახით:

ამ ტაბლეტში პირველად იწერება ორიგინალური ნომრები, იყოფა გონებაში, იწერება ნარჩენები მარჯვნივ, ხოლო პირადები ბოლოში პროცესის დასრულებამდე. ბოლო გამყოფი არის GCD.

ამრიგად, ორი რიცხვის ყველაზე დიდი საერთო გამყოფი არის ბოლო არანულოვანი ნაშთი, როდესაც დიდი რიცხვი იყოფა პატარაზე., ე.ითუ a = b *q + r, შემდეგ gcd(a; b) = gcd(b; r)

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

1) ევკლიდის ალგორითმის გამოყენებით იპოვეთ რიცხვების GCD:

ა) 703, 481; ბ) 2112 და 1680; ბ) 5075 და 1450 წ

GCD(703;481)=37

GCD(2112;1680)=48

GCD(5075;1450)=

შეამოწმეთ შედეგები კომპიუტერზე.

კომპიუტერზე ბავშვების ამოცანაა იპოვონ GCD და LCM სამი ნომრისთვის GCD-ისა და LCM-ის პოვნის პროგრამის გამოყენებით.

gcd(150, ____) = ____

GCD(450,315,135)=____

GCD(135, ____) = ____

GCD(2160,1350,1080)=____

GCD (1080, ____) = ____

GCD(5300,3180,2120)=____

GCD (2120, ____) = ____

(სამი ან მეტი რიცხვის GCD-ის საპოვნელად ჯერ იპოვეთ ნებისმიერი ორი მათგანის GCD, შემდეგ ნაპოვნი გამყოფის GCD და მესამე მოცემული რიცხვი.

და მესამე მოცემული ნომერი.

7. შედეგების შემოწმება კომპიუტერზე. პრობლემის დამოუკიდებელი გადაჭრა.

1) იგივე საჩუქრები მომზადდა კლასის მოსწავლეებისთვის. ყველა საჩუქარი მოიცავდა 120 შოკოლადს, 280 ტკბილეულს და 320 თხილს. რამდენი მოსწავლეა პირველ კლასში, თუ ცნობილია, რომ 30-ზე მეტია?

პასუხი:_______________________

2) სადგურზე სამი სამგზავრო მატარებელია: პირველში - 418 ადგილიანი კუპე ვაგონებში, მეორეში - 494, ხოლო მესამეში - 456. რამდენი კუპე ვაგონია თითოეულ მატარებელში, თუ ადგილების რაოდენობა იგივეა. თითოეულ მანქანაში და მათი საერთო რაოდენობა 20-ზე მეტია? პასუხი ________________________

3) თაიგულები მზადდებოდა 156 ჩაის, 234 თეთრი და 390 წითელი ვარდისგან და ყველა ტიპის ვარდის თაიგულში იყო თანაბრად და ასეთი თაიგულების რაოდენობა იყო 50-ზე მეტი. რამდენი თაიგული დამზადდა ამ ვარდისგან და რამდენი. თითოეული ტიპის ვარდები ერთ თაიგულში იყო? პასუხი _________________

გაკვეთილის შეჯამება. GCD-ისა და LCM-ის პოვნის რა ხერხით შევხვდით გაკვეთილზე. ევკლიდეს ალგორითმი. რა არის ამ მეთოდის სხვა სახელი? (გამოკლების მეთოდი). როგორ გაუმჯობესდა ეს მეთოდი? გაყოფით უფრო დიდი რიცხვი იყოფა მცირე რიცხვზე, შემდეგ მცირე რიცხვი პირველ ნაშთზე, შემდეგ პირველი ნაშთი მეორე ნაშთზე და ასე შემდეგ, სანამ არ მიიღებთ 0-ს. ბოლო არანულოვანი ნაშთი არის 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)

პრობლემის ფორმულირება განიხილეთ შემდეგი ამოცანა: საჭიროა დაწეროთ პროგრამა ორი ნატურალური რიცხვის უდიდესი საერთო გამყოფის (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."> !}

სლაიდი 1

სლაიდი 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

STEP ოპერაცია M N მდგომარეობა 1 InputM 48 2 InputN 18 3 M N 48 18, დიახ 4 M>N 48>18, დიახ 5 M:=M-N 30 6 M N 30 18, დიახ 7 M>N 30>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

სლაიდი 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 წიგნი), რომელიც შეიცავს ანტიკური მათემატიკის საფუძვლებს, ელემენტარულ გეომეტრიას, რიცხვთა თეორიას, ურთიერთობების ზოგად თეორიას და ტერიტორიებისა და მოცულობების განსაზღვრის მეთოდს, რომელიც მოიცავდა ლიმიტების თეორიის ელემენტებს. მან დიდი გავლენა მოახდინა მათემატიკის განვითარებაზე. მუშაობს ასტრონომიაზე, ოპტიკაზე, მუსიკის თეორიაზე.