If you're seeing this message, it means we're having trouble loading external resources on our website.

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა

კომპიუტერული მეცნიერება

თემა 1: გაკვეთილი 6

რეკურსიული ალგორითმები

მრავალჯერადი რეკურსია სერპინსკის სამკუთხედით

ჩვენ მიერ აქამდე გავლილ მაგალითებში ყოველ ჯერზე თითო რეკურსიული გამოძახება გვიწევდა. მაგრამ ზოგჯერ ბევრი რეკურსიული გამოძახებაა საჭირო. აი, კარგი მაგალითი. მათემატიკური კონსტრუქცია ფრაქტალი, რომელიც სერპინსკის სამკუთხედის სახელით არის ცნობილი:
სერპინსკის სრული სამკუთხედი
როგორც ხედავთ, ეს არის პატარა კვადრატების კოლექცია, რომელიც დახატულია კონკრეტული კანონზომიერების მიხედვით კვადრატულ არეში. აი, როგორ უნდა დახატოთ ის. დაიწყეთ სრული კვადრატული არით და დაყავით ის ოთხ სექციად შემდეგნაირად:
სერპინსკის სამკუთხედი 2 x 2
აიღეთ სამი კვადრატი, რომლებშიც გადის × — ზედა მარცხენა, ზედა მარჯვენა და ქვედა მარჯვენა — და დაყავით ისინი ოთხ სექციად იმავე გზით:
სერპინსკის სამკუთხედი 4 x 4
განაგრძეთ. დაყავით ყოველი ×-იანი კვადრატი ოთხ სექციად და შემდეგ დასვით × ზედა მარცხენა, ზედა მარჯვენა და ქვედა მარჯვენა კვადრატებში, მაგრამ არასდროს დასვათ ქვედა მარცხენაში.
სერპინსკის სამკუთხედი 8 x 8
სერპინსკის სამკუთხედი 16 x 16
სერპინსკის სამკუთხედი 32 x 32
სერპინსკის სამკუთხედი 64 x 64
როგორც კი კვადრატი საკმარისად დაპატარავდება, შეწყვიტეთ დაყოფა. თუ თითოეულ ×-იან კვადრატს შეავსებთ და დაივიწყებთ ყველა დანარჩენ კვადრატს, მიიღებთ სერპინსკის სამკუთხედს. აი, კიდევ ერთხელ:
სერპინსკის სრული სამკუთხედი
რომ შევაჯამოთ, აი, როგორ უნდა დახატოთ სერპინსკის სამკუთხედი კვადრატში:
  • გაარკვიეთ, რამდენად პატარაა კვადრატი. თუ ის საკმარისად პატარაა იმისთვის, რომ იყოს ბაზისი, მაშინ უბრალოდ შეავსეთ ეს კვადრატი. თქვენ ირჩევთ, რამდენად პატარა არის „საკმარისად პატარა“.
  • წინააღმდეგ შემთხვევაში, დაყავით კვადრატი ზედა მარცხენა, ზედა მარჯვენა, ქვედა მარცხენა და ქვედა მარჯვენა კვადრატებად. რეკურსიულად „ამოხსენით“ სამი ქვეამოცანა:
    1. დახატეთ სერპინსკის სამკუთხედი ზედა მარცხენა კვადრატში.
    2. დახატეთ სერპინსკის სამკუთხედი ზედა მარჯვენა კვადრატში.
    3. დახატეთ სერპინსკის სამკუთხედი ქვედა მარჯვენა კვადრატში.
შენიშნეთ, რომ გიწევთ არა ერთი, არამედ სამი რეკურსიული გამოძახება. აი, ამიტომ განვიხილავთ სერპინსკის სამკუთხედის დახატვას მრავალჯერადი რეკურსიის მაგალითად.
შეგიძლიათ, აირჩიოთ ოთხიდან ნებისმიერი სამი კვადრატი, რომლებშიც რეკურსიულად დახატავთ სერპინსკის სამკუთხედებს. უბრალოდ, შედეგები 90 გრადუსის რაიმე ჯერადით იქნება მობრუნებული ზედა ნახატიდან (თუ რეკურსიულად დახატავთ სერპინსკის სამკუთხედებს სხვა ნებისმიერი რაოდენობის კვადრატში, საინტერესო შედეგს ვერ მიიღებთ).
ქვემოთ მოცემული პროგრამა ხატავს სერპინსკის სამკუთხედს. სცადეთ ზოგიერთი რეკურსიული გამოძახების დაკომენტარება და განკომენტარება, რათა მიიღოთ მობრუნებული სამკუთხედები:

ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.