ევკლიდეს ალგორითმი
ალგორითმი არის მოქმედებათა ისეთი მიმდევრობა, რომელთა შესრულების შედეგად დასახული მიზნის მიღწევა, დასმული ამოცანის ამოხსნა ხდება. სიტყვა ალგორითმი წარმოიშვა ლათინური Algorithmi-დან, IX საუკუნის უდიდესი მათემატიკოსის ალ–ხვარაზმის სახელიდან, რომელმაც ჩამოაყალიბა არითმეტიკული მოქმედებების შესრულების წესები. თავდაპირველად ალგორითმში იგულისამებოდა მხოლოლ ოთხი არითმეტიკული მოქმედების შესრულების წესები მრავალნიშნა რიცხვებზე, შემდგომში კი ეს ცნება უკვე იხმარება იმ მოქმედებათა თანამიმდევრობის აღსანიშნავად, რომლებსაც დასმული ამოცანის ამოხსნამდე მივყავართ.
ვიპოვოთ ორი m და n ნატურალური რიცხვის უდიდესი საერთო გამყოფი.
ამოცანის ამოხსნის ალგორითმში ვიყენებთ შემდეგს: თუ m>n, მაშინ ამ რიცხვების უდიდესი საერთო გამყოფი იგივეა, რაც m-n და n_ის უდიდესი საერთო გამყოფი.
ალგორითმი არის ასეთი:
1). თუ რიცხვები ტოლია, მაშინ ნებისმიერი მათგანი ჩავთვალოთ პასუხად, წინააღმდეგ შემთხვევაში გავაგრძელოთ ალგორითმის შესრულება;
2). დავადგინოთ მოცემული რიცხვებიდან უდიდესი;
3). შევცვალოთ უდიდესი რიცხვი უდიდესისა და უმცირესის სხვაობით;
4). დავუბრუნდეთ ალგორითმის შესრულების პირველ ეტაპს.
მოცემული ალგორითმი არის "ევკლიდეს ალგორითმი"-ს სახელწოლებით ცნობილი. ეს ალგორითმი შედგება ცალკეული პუნქტებისაგან, სადაც გარკვეული მარტივი მოქმედების შესრულებაა საჭირო. ალგორითმის თავისებურებას წარმოადგენს ის, რომ ალგორითმში მოყვანილი მოქმედებები შეიძლება მრავალჯერ განმეორდეს. საზოგადოდ, ალგორითმის დასაწყისში დაბრუნების აუცილებლობამ შეიძლება მისი პუნქტების უსასრულო განმეორებამდე მიგვიყვანოს. ამ შემთახვევაში ეს არ მოხდება, რადგან ყოველი ახალი გამოკლების შემდეგ უდიდესი და უმცირესი რიცხვების სხვაობა მცირდება, რის გამოც გამეორებათა გარკვეული რაოდენობის შემდეგ შესადარებელი რიცხვები აუცილებლად ტოლი გახდება. ეს ალგორითმი გამოიყენება ნებისმიერი ნატურალური რიცხვებისათვის და ყოველთვის მიიღება უსგ (უდიდესი საერთო გამყოფი).
ვთქვათ m=56 და n=35, მაშინ ალგორითმი, მათი უდიდესი საერთო გამყოფის საპოვნელად, სრულდება ასე:
1). 56 არ უდრის 35-ს, ამიტომ ვაგრძელებთ ალგორითმის შემდეგ ნაბიჯს;
2). დავადგინოთ მოცემული რიცხვებიდან უდიდესი, ეს რიცხვია 56;
3). შევცვალოთ უდიდესი რიცხვი უდიდესისა და უმცირესის სხვაობით, 56 შევცვალოთ 56-35=21_ით;
4). დავუბრუნდეთ ალგორითმის შესრულების პირველ ეტაპს, 21 არ უდრის 35-ს, ამიტომ ვაგრძელებთ ალგორითმის შემდეგ ნაბიჯს, მე-2-ს.
უსგ(56; 35)=უსგ(56-35; 35)=უსგ(21; 35)=უსგ(21; 35-21)=უსგ(21; 14)=უსგ(21-14; 14)=უსგ(7; 14)=უსგ(7; 14-7)=უსგ(7; 7)=7
როგორ ვიპოვოთ ორი m და n ნატურალური რიცხვის უმცირესი საერთო ჯერადი?!
როგორია ალგორითმი და ვის სახელს ატარებს ის?
ავტორი: www.edumeter.ge - მამუკა კვინიკაძე
იყავი ინფორმირებული!
