ძირითადი მასალა
კომპიუტერული მეცნიერება
კურსი: კომპიუტერული მეცნიერება > თემა 1
გაკვეთილი 6: რეკურსიული ალგორითმები- რეკურსია
- ფაქტორიალის ფუნქცია
- გამოწვევა: განმეორებითი ფაქტორიალი
- რეკურსიული ფაქტორიალი
- გამოწვევა: რეკურსიული ფაქტორიალი
- რეკურსიული ალგორითმების თვისებები
- რეკურსიის დახმარებით განვსაზღვროთ სიტყვა პალინდრომია თუ არა
- გამოწვევა: არის თუ არა სტრიქონი პალინდრომი?
- რიცხვის ხარისხების გამოთვლა
- გამოწვევა: რეკურსიული ხარისხები
- მრავალჯერადი რეკურსია სერპინსკის სამკუთხედით
- რეკურსიული ფუნქციების ეფექტურობის გაუმჯობესება
- პროექტი: რეკურსიული ხელოვნება
© 2023 Khan Academyგამოყენების პირობებიკონფიდენციალურობის პოლიტიკაშენიშვნა ქუქი-ჩანაწერებზე
მრავალჯერადი რეკურსია სერპინსკის სამკუთხედით
ჩვენ მიერ აქამდე გავლილ მაგალითებში ყოველ ჯერზე თითო რეკურსიული გამოძახება გვიწევდა. მაგრამ ზოგჯერ ბევრი რეკურსიული გამოძახებაა საჭირო. აი, კარგი მაგალითი. მათემატიკური კონსტრუქცია ფრაქტალი, რომელიც სერპინსკის სამკუთხედის სახელით არის ცნობილი:
როგორც ხედავთ, ეს არის პატარა კვადრატების კოლექცია, რომელიც დახატულია კონკრეტული კანონზომიერების მიხედვით კვადრატულ არეში. აი, როგორ უნდა დახატოთ ის. დაიწყეთ სრული კვადრატული არით და დაყავით ის ოთხ სექციად შემდეგნაირად:
აიღეთ სამი კვადრატი, რომლებშიც გადის × — ზედა მარცხენა, ზედა მარჯვენა და ქვედა მარჯვენა — და დაყავით ისინი ოთხ სექციად იმავე გზით:
განაგრძეთ. დაყავით ყოველი ×-იანი კვადრატი ოთხ სექციად და შემდეგ დასვით × ზედა მარცხენა, ზედა მარჯვენა და ქვედა მარჯვენა კვადრატებში, მაგრამ არასდროს დასვათ ქვედა მარცხენაში.
როგორც კი კვადრატი საკმარისად დაპატარავდება, შეწყვიტეთ დაყოფა. თუ თითოეულ ×-იან კვადრატს შეავსებთ და დაივიწყებთ ყველა დანარჩენ კვადრატს, მიიღებთ სერპინსკის სამკუთხედს. აი, კიდევ ერთხელ:
რომ შევაჯამოთ, აი, როგორ უნდა დახატოთ სერპინსკის სამკუთხედი კვადრატში:
- გაარკვიეთ, რამდენად პატარაა კვადრატი. თუ ის საკმარისად პატარაა იმისთვის, რომ იყოს ბაზისი, მაშინ უბრალოდ შეავსეთ ეს კვადრატი. თქვენ ირჩევთ, რამდენად პატარა არის „საკმარისად პატარა“.
- წინააღმდეგ შემთხვევაში, დაყავით კვადრატი ზედა მარცხენა, ზედა მარჯვენა, ქვედა მარცხენა და ქვედა მარჯვენა კვადრატებად. რეკურსიულად „ამოხსენით“ სამი ქვეამოცანა:
- დახატეთ სერპინსკის სამკუთხედი ზედა მარცხენა კვადრატში.
- დახატეთ სერპინსკის სამკუთხედი ზედა მარჯვენა კვადრატში.
- დახატეთ სერპინსკის სამკუთხედი ქვედა მარჯვენა კვადრატში.
შენიშნეთ, რომ გიწევთ არა ერთი, არამედ სამი რეკურსიული გამოძახება. აი, ამიტომ განვიხილავთ სერპინსკის სამკუთხედის დახატვას მრავალჯერადი რეკურსიის მაგალითად.
შეგიძლიათ, აირჩიოთ ოთხიდან ნებისმიერი სამი კვადრატი, რომლებშიც რეკურსიულად დახატავთ სერპინსკის სამკუთხედებს. უბრალოდ, შედეგები 90 გრადუსის რაიმე ჯერადით იქნება მობრუნებული ზედა ნახატიდან (თუ რეკურსიულად დახატავთ სერპინსკის სამკუთხედებს სხვა ნებისმიერი რაოდენობის კვადრატში, საინტერესო შედეგს ვერ მიიღებთ).
ქვემოთ მოცემული პროგრამა ხატავს სერპინსკის სამკუთხედს. სცადეთ ზოგიერთი რეკურსიული გამოძახების დაკომენტარება და განკომენტარება, რათა მიიღოთ მობრუნებული სამკუთხედები:
ამ მასალის შინაარსი შექმნილია დარტმუთის კომპიუტერული მეცნიერების პროფესორების, თომას კორმენისა და დევინ ბალკომის, ასევე ხანის აკადემიის კომპიუტრეული ჯგუფის მიერ. მასალის ლიცენზიაა CC-BY-NC-SA.
გსურთ, შეუერთდეთ დისკუსიას?
პოსტები ჯერ არ არის.