რეკურსიაა, როდესაც ქვეპროგრამა თავის თავს იძახებს. როდესაც პირველად შეხვდებით ასეთ ალგორითმულ კონსტრუქციას, ადამიანების უმეტესობა განიცდის გარკვეულ სირთულეებს, მაგრამ მცირე პრაქტიკით, რეკურსია გახდება გასაგები და ძალიან სასარგებლო ინსტრუმენტი თქვენს პროგრამირების არსენალში.
1. რეკურსიის არსი
პროცედურა ან ფუნქცია შეიძლება შეიცავდეს ზარებს სხვა პროცედურებზე ან ფუნქციებზე. მათ შორის პროცედურა შეიძლება ეწოდოს თავად. აქ პარადოქსი არ არის - კომპიუტერი მხოლოდ თანმიმდევრულად ასრულებს ბრძანებებს, რომლებსაც ხვდება პროგრამაში და, თუ პროცედურის გამოძახება შეხვდება, ის უბრალოდ იწყებს ამ პროცედურის შესრულებას. არ აქვს მნიშვნელობა რა პროცედურამ მისცა ბრძანება ამის გაკეთებას.
რეკურსიული პროცედურის მაგალითი:
პროცედურა Rec(a: მთელი რიცხვი); დაიწყება თუ a>
განვიხილოთ რა მოხდება, თუ მთავარ პროგრამაში ჩავსვამთ ზარს, მაგალითად, Rec(3) ფორმის. ქვემოთ მოცემულია დიაგრამა, რომელიც გვიჩვენებს თანმიმდევრობას, რომლითაც შესრულებულია განცხადებები.
ბრინჯი. 1. რეკურსიული პროცედურის ბლოკ-სქემა.
Rec პროცედურა გამოიძახება პარამეტრით a = 3. ის შეიცავს Rec პროცედურაზე გამოძახებას პარამეტრით a = 2. წინა ზარი ჯერ არ დასრულებულა, ასე რომ თქვენ წარმოიდგინეთ, რომ სხვა პროცედურა იქმნება და პირველი აკეთებს. არ დაასრულოს თავისი სამუშაო სამუშაოს დასრულებამდე. გამოძახების პროცესი სრულდება, როდესაც პარამეტრი a = 0. ამ მომენტში, პროცედურის 4 ინსტანცია ერთდროულად სრულდება. თანმხლები პროცედურების რაოდენობა ეწოდება რეკურსიის სიღრმე.
მეოთხე პროცედურა სახელწოდებით (Rec(0)) დაბეჭდავს რიცხვს 0 და გამოვა. ამის შემდეგ კონტროლი უბრუნდება პროცედურას, რომელიც მას ეძახდა (Rec(1)) და იბეჭდება ნომერი 1. და ასე შემდეგ სანამ ყველა პროცედურა არ დასრულდება. ორიგინალური ზარის შედეგი დაბეჭდავს ოთხ ნომერს: 0, 1, 2, 3.
კიდევ ერთი ვიზუალური სურათი იმისა, რაც ხდება, ნაჩვენებია ნახ. 2.
ბრინჯი. 2. Rec პროცედურის შესრულება მე-3 პარამეტრით მოიცავს Rec პროცედურის შესრულებას მე-2 პარამეტრით და 3 რიცხვის დაბეჭდვას. თავის მხრივ, Rec პროცედურის შესრულება მე-2 პარამეტრით მოიცავს Rec პროცედურის შესრულებას 1 პარამეტრით და 2 რიცხვის დაბეჭდვას. ასე შემდეგ.
როგორც დამოუკიდებლად სავარჯიშო, იფიქრეთ იმაზე, თუ რა ხდება Rec(4) დარეკვისას. ასევე გაითვალისწინეთ რა ხდება, როდესაც თქვენ გამოიძახებთ ქვემოთ აღწერილ Rec2(4) პროცედურას, სადაც ოპერატორები შებრუნებულია.
პროცედურა Rec2(a: მთელი რიცხვი); დაიწყე წერა (a); თუ a>0 მაშინ Rec2(a-1); დასასრული;
გაითვალისწინეთ, რომ ზემოხსენებულ მაგალითებში, რეკურსიული ზარი არის პირობითი განაცხადის შიგნით. ეს აუცილებელი პირობაა იმისთვის, რომ რეკურსი ოდესმე დასრულდეს. ასევე გაითვალისწინეთ, რომ პროცედურა თავის თავს იძახებს სხვა პარამეტრით, ვიდრე ის იყო დარეკილი. თუ პროცედურა არ იყენებს გლობალურ ცვლადებს, მაშინ ეს ასევე აუცილებელია, რათა რეკურსია განუსაზღვრელი ვადით არ გაგრძელდეს.
შესაძლებელია ოდნავ უფრო რთული სქემა: ფუნქცია A იძახებს B ფუნქციას, რომელიც თავის მხრივ იწვევს A. ამას ე.წ რთული რეკურსია. გამოდის, რომ აღწერილი პროცედურა ჯერ არ არის აღწერილი. იმისათვის, რომ ეს შესაძლებელი იყოს, თქვენ უნდა გამოიყენოთ.
პროცედურა A(n: მთელი რიცხვი); (პირველი პროცედურის წინსვლის აღწერა (სათაური)) პროცედურა B(n: მთელი რიცხვი); (მეორე პროცედურის წინსვლის აღწერა) პროცედურა A(n: მთელი რიცხვი); (პროცედურის სრული აღწერა A) start writeln(n); B(n-1); დასასრული; პროცედურა B(n: მთელი რიცხვი); (B პროცედურის სრული აღწერა) start writeln(n); თუნ
B პროცედურის წინა დეკლარაცია საშუალებას აძლევს მას გამოიძახონ A პროცედურიდან. A პროცედურის წინა დეკლარაცია არ არის საჭირო ამ მაგალითში და დამატებულია ესთეტიკური მიზეზების გამო.
თუ ჩვეულებრივი რეკურსია შეიძლება შევადაროთ ურობოროს (ნახ. 3), მაშინ რთული რეკურსიის გამოსახულება შეიძლება გამოვიტანოთ ცნობილი საბავშვო ლექსიდან, სადაც „მგლები შიშისგან შეჭამეს ერთმანეთს“. წარმოიდგინეთ, რომ ორი მგელი ჭამს ერთმანეთს და გესმით რთული რეკურსი.
ბრინჯი. 3. Ouroboros - გველი, რომელიც შთანთქავს საკუთარ კუდს. ნახატი თეოდორე პელეკანოსის ალქიმიური ტრაქტატიდან „სინოზიუსი“ (1478 წ.).
ბრინჯი. 4. კომპლექსური რეკურსია.
3. ციკლის მუშაობის სიმულაცია რეკურსიის გამოყენებით
თუ პროცედურა თავის თავს უწოდებს, მაშინ, ფაქტობრივად, ეს იწვევს მასში შემავალი ინსტრუქციების განმეორებით შესრულებას, რაც მსგავსია მარყუჟის მოქმედების. ზოგიერთი პროგრამირების ენა საერთოდ არ შეიცავს მარყუჟის კონსტრუქციებს, რაც პროგრამისტებს უტოვებს გამეორებების ორგანიზებას რეკურსიის გამოყენებით (მაგალითად, Prolog, სადაც რეკურსია არის პროგრამირების მთავარი ტექნიკა).
მაგალითად, მოვახდინოთ for loop-ის მუშაობის სიმულაცია. ამისათვის ჩვენ გვჭირდება ნაბიჯების მრიცხველი ცვლადი, რომელიც შეიძლება განხორციელდეს, მაგალითად, როგორც პროცედურის პარამეტრი.
მაგალითი 1
პროცედურა LoopImitation(i, n: მთელი რიცხვი); (პირველი პარამეტრი არის ნაბიჯების რაოდენობა, მეორე პარამეტრი არის ნაბიჯების საერთო რაოდენობა) start writeln("Hello N", i); //აქ არის ნებისმიერი განცხადება, რომელიც განმეორდება თუ ი LoopImitation(1, 10) მსგავსი ზარის შედეგი იქნება ინსტრუქციების ათჯერ შესრულება მრიცხველის ცვლილებით 1-დან 10-მდე. ამ შემთხვევაში, ის დაიბეჭდება: გამარჯობა N1 ზოგადად, ძნელი არ არის იმის დანახვა, რომ პროცედურის პარამეტრები არის მრიცხველის მნიშვნელობების ცვლილების საზღვრები. შეგიძლიათ შეცვალოთ რეკურსიული ზარი და ინსტრუქციები, რომლებიც უნდა განმეორდეს, როგორც შემდეგ მაგალითში. მაგალითი 2
პროცედურა LoopImitation2(i, n: მთელი რიცხვი); დაიწყოს თუ მე ამ შემთხვევაში პროცედურა გამოიძახება რეკურსიულად ინსტრუქციების შესრულებამდე. პროცედურის ახალი ინსტანცია ასევე, პირველ რიგში, გამოიძახებს სხვა ინსტანციას და ასე შემდეგ, სანამ არ მივაღწევთ მრიცხველის მაქსიმალურ მნიშვნელობას. მხოლოდ ამის შემდეგ გამოძახებული პროცედურებიდან ბოლო შეასრულებს თავის ინსტრუქციებს, შემდეგ წინაბოლო შეასრულებს ინსტრუქციებს და ა.შ. LoopImitation2(1, 10) გამოძახების შედეგი არის მისალმებების დაბეჭდვა საპირისპირო თანმიმდევრობით: გამარჯობა N 10 თუ წარმოვიდგენთ რეკურსიულად მოუწოდა პროცედურების ჯაჭვს, მაშინ 1-ელ მაგალითში ჩვენ გავდივართ მას უფრო ადრე წოდებული პროცედურებიდან მოგვიანებით. მაგალით 2-ში, პირიქით, მოგვიანებითიდან ადრე. საბოლოოდ, რეკურსიული ზარი შეიძლება განთავსდეს ინსტრუქციების ორ ბლოკს შორის. Მაგალითად: პროცედურა LoopImitation3(i, n: მთელი რიცხვი); დაიწყეთ წერა ("Hello N", i); (ეს შეიძლება იყოს განცხადებების პირველი ბლოკი) თუ ი აქ ჯერ პირველი ბლოკის ინსტრუქციები სრულდება თანმიმდევრობით, შემდეგ მეორე ბლოკის ინსტრუქციები შესრულებულია საპირისპირო თანმიმდევრობით. LoopImitation3(1, 10) გამოძახებისას ვიღებთ: გამარჯობა N1 საჭირო იქნება ორი მარყუჟი ერთდროულად, რომ იგივე გააკეთოს რეკურსიის გარეშე. თქვენ შეგიძლიათ ისარგებლოთ იმით, რომ ერთი და იგივე პროცედურის ნაწილების შესრულება დროშია დაშორებული. Მაგალითად: მაგალითი 3: რიცხვის ორობითად გადაქცევა.
ორობითი რიცხვის ციფრების მიღება, როგორც მოგეხსენებათ, ნაშთით გაყოფით ხდება რიცხვითი სისტემის 2-ის ფუძეზე. თუ არის რიცხვი, მაშინ მისი ბოლო ციფრი მის ორობით გამოსახულებაში უდრის. 2-ზე გაყოფის მთელი ნაწილის აღება: ვიღებთ რიცხვს, რომელსაც აქვს იგივე ორობითი წარმოდგენა, მაგრამ ბოლო ციფრის გარეშე. ამგვარად, საკმარისია ზემოაღნიშნული ორი მოქმედების გამეორება მანამ, სანამ მომდევნო გაყოფის ველს არ ექნება 0-ის ტოლი მთელი ნაწილი. რეკურსიის გარეშე ის ასე გამოიყურება: სანამ x>0 იწყება c:=x mod 2; x:=x div 2; ჩაწერე(გ); დასასრული; პრობლემა აქ არის ის, რომ ორობითი წარმოდგენის ციფრები გამოითვლება საპირისპირო თანმიმდევრობით (პირველი უახლესი). რიცხვის ნორმალური სახით დასაბეჭდად, თქვენ მოგიწევთ დაიმახსოვროთ მასივის ელემენტების ყველა რიცხვი და გამოიყვანოთ ისინი ცალკე ციკლში. რეკურსიით, ადვილია გამომავალი სწორი თანმიმდევრობით, მასივის და მეორე მარყუჟის გარეშე. კერძოდ: ორობითი წარმოდგენის პროცედურა (x: მთელი რიცხვი); var c, x: მთელი რიცხვი; დაწყება (პირველი ბლოკი. შესრულებულია პროცედურის გამოძახების წესით) c:= x mod 2; x:=x div 2; (რეკურსიული გამოძახება) თუ x>0 მაშინ BinaryRepresentation(x); (მეორე ბლოკი. მუშაობს საპირისპირო თანმიმდევრობით) write(c); დასასრული; საერთოდ, მოგება არ მიგვიღია. ორობითი წარმოდგენის ციფრები ინახება ლოკალურ ცვლადებში, რომლებიც განსხვავებულია რეკურსიული პროცედურის თითოეული გაშვებული ინსტანციისთვის. ანუ მეხსიერების შენახვა ვერ მოხერხდა. პირიქით, ჩვენ ვხარჯავთ დამატებით მეხსიერებას ბევრი ადგილობრივი ცვლადის x შესანახად. მიუხედავად ამისა, ასეთი გამოსავალი ლამაზად მეჩვენება. ვექტორების თანმიმდევრობა მოცემულია რეციდივის მიმართებით, თუ მოცემულია საწყისი ვექტორი და შემდეგი ვექტორის ფუნქციური დამოკიდებულება წინა ვექტორზე. განმეორებითი ურთიერთობების გამოყენებით გამოთვლილი რაოდენობის მარტივი მაგალითია ფაქტორიალი შემდეგი ფაქტორიალი შეიძლება გამოითვალოს წინადან შემდეგნაირად: აღნიშვნის შემოღებით ვიღებთ მიმართებას: ვექტორები ფორმულიდან (1) შეიძლება განიმარტოს, როგორც ცვლადი მნიშვნელობების სიმრავლე. შემდეგ მიმდევრობის საჭირო ელემენტის გაანგარიშება შედგება მათი მნიშვნელობების განმეორებით განახლებაში. კერძოდ ფაქტორიალისთვის: X:= 1; i:= 2-დან n-მდე გააკეთე x:= x * i; writeln(x); ყოველი ასეთი განახლება (x:= x * i) ეწოდება გამეორებადა გამეორებების პროცესი გამეორება. ამასთან, გაითვალისწინეთ, რომ მიმართება (1) არის მიმდევრობის წმინდა რეკურსიული განმარტება და n-ე ელემენტის გამოთვლა, ფაქტობრივად, არის f ფუნქციის განმეორებითი აღება თავისგან: კერძოდ, ფაქტორიალისთვის შეიძლება დაწეროთ: ფუნქცია Factorial(n: მთელი რიცხვი): მთელი რიცხვი; იწყება თუ n > 1, მაშინ ფაქტორული:= n * ფაქტორული(n-1) სხვა ფაქტორული:= 1; დასასრული; უნდა გვესმოდეს, რომ ფუნქციის გამოძახება იწვევს დამატებით ზედნადებს, ასე რომ, ფაქტორების გამოთვლის პირველი ვარიანტი გარკვეულწილად უფრო სწრაფი იქნება. ზოგადად, განმეორებითი გადაწყვეტილებები უფრო სწრაფად მუშაობს, ვიდრე რეკურსიული. სანამ ისეთ სიტუაციებზე გადავიდოდეთ, სადაც რეკურსია სასარგებლოა, მოდით შევხედოთ კიდევ ერთ მაგალითს, სადაც ის არ უნდა იქნას გამოყენებული. განვიხილოთ განმეორებითი ურთიერთობების განსაკუთრებული შემთხვევა, როდესაც თანმიმდევრობის შემდეგი მნიშვნელობა დამოკიდებულია არა ერთზე, არამედ რამდენიმე წინა მნიშვნელობაზე ერთდროულად. ამის მაგალითია კარგად ცნობილი ფიბონაჩის მიმდევრობა, რომელშიც ყოველი შემდეგი ელემენტი არის ორი წინა ელემენტის ჯამი: "ფრონტალური" მიდგომით შეგიძლიათ დაწეროთ: Fib(n: მთელი რიცხვი): მთელი რიცხვი; დაიწყება თუ n > 1 მაშინ Fib:= Fib(n-1) + Fib(n-2) სხვა Fib:= 1; დასასრული; თითოეული ზარი Fib-ზე ქმნის თავის ორ ასლს ერთდროულად, თითოეული ასლი ქმნის კიდევ ორს და ა.შ. ოპერაციების რაოდენობა იზრდება რაოდენობასთან ერთად ნექსპონენტურად, თუმცა განმეორებითი ამოხსნისთვის, წრფივი ნოპერაციების რაოდენობა. სინამდვილეში, ზემოთ მოყვანილი მაგალითი არ გვასწავლის ᲠᲝᲓᲔᲡᲐᲪრეკურსი არ უნდა იქნას გამოყენებული და ასის არ უნდა იქნას გამოყენებული. ყოველივე ამის შემდეგ, თუ არსებობს სწრაფი განმეორებითი (მარყუჟზე დაფუძნებული) გადაწყვეტა, მაშინ იგივე ციკლი შეიძლება განხორციელდეს რეკურსიული პროცედურის ან ფუნქციის გამოყენებით. Მაგალითად: // x1, x2 – საწყისი პირობები (1, 1) // n – საჭირო ფიბონაჩის რიცხვითი ფუნქციის რაოდენობა Fib(x1, x2, n: მთელი რიცხვი): მთელი რიცხვი; varx3: მთელი რიცხვი; იწყება თუ n > 1, შემდეგ იწყება x3:= x2 + x1; x1:=x2; x2:=x3; Fib:= Fib(x1, x2, n-1); ბოლოს სხვა Fib:= x2; დასასრული; მიუხედავად ამისა, სასურველია განმეორებითი გადაწყვეტილებები. საკითხავია, მაშინ როდის უნდა იქნას გამოყენებული რეკურსი? ნებისმიერი რეკურსიული პროცედურა და ფუნქცია, რომელიც შეიცავს მხოლოდ ერთ რეკურსიულ ზარს თავისთვის, ადვილად შეიცვლება განმეორებითი მარყუჟებით. იმისათვის, რომ მიიღოთ ისეთი რამ, რომელსაც არ აქვს მარტივი არარეკურსიული ანალოგი, უნდა მიმართოთ პროცედურებსა და ფუნქციებს, რომლებიც საკუთარ თავს ორ ან მეტჯერ უწოდებენ. ამ შემთხვევაში, მოწოდებული პროცედურების ნაკრები აღარ ქმნის ჯაჭვს, როგორც ნახ. 1, მაგრამ მთელი ხე. არსებობს პრობლემების ფართო კლასი, როდესაც გამოთვლითი პროცესი უნდა იყოს ორგანიზებული ამ გზით. მხოლოდ მათთვის რეკურსია გადაჭრის უმარტივესი და ბუნებრივი გზა იქნება. რეკურსიული ფუნქციების თეორიული საფუძველი, რომლებიც საკუთარ თავს არაერთხელ უწოდებენ, არის დისკრეტული მათემატიკის ფილიალი, რომელიც სწავლობს ხეებს. განმარტება:
ჩვენ დავარქმევთ სასრულ სიმრავლეს თ, რომელიც შედგება ერთი ან მეტი კვანძისგან, ისეთი, რომ: ეს განმარტება რეკურსიულია. მოკლედ, ხე არის ფესვი და მასზე მიმაგრებული ქვეხეების ნაკრები, რომლებიც ასევე ხეებია. ხე განისაზღვრება თავისით. თუმცა, ამ განმარტებას აქვს აზრი, რადგან რეკურსია სასრულია. თითოეული ქვეხე შეიცავს ნაკლებ კვანძს, ვიდრე შემცველი ხე. საბოლოო ჯამში, მივდივართ ქვეხეებთან, რომლებიც შეიცავს მხოლოდ ერთ კვანძს და ეს უკვე გასაგებია, რა არის ეს. ბრინჯი. 3. ხე. ნახ. 3 გვიჩვენებს ხეს შვიდი კვანძით. მიუხედავად იმისა, რომ ჩვეულებრივი ხეები იზრდება ქვემოდან ზევით, ჩვეულებრივია მათი დახატვა პირიქით. დიაგრამის ხელით შედგენისას ეს მეთოდი აშკარად უფრო მოსახერხებელია. ამ შეუსაბამობის გამო, დაბნეულობა ზოგჯერ წარმოიქმნება, როდესაც ამბობენ, რომ ერთი კვანძი მეორის ზემოთ ან ქვემოთაა. ამ მიზეზით, უფრო მოსახერხებელია გამოიყენოს ტერმინოლოგია, რომელიც გამოიყენება საგვარეულო ხეების აღწერილობაში, კვანძებს უფრო ახლოს ფესვის წინაპრებთან და უფრო შორეულ შთამომავლებთან. გრაფიკულად, ხე შეიძლება გამოსახული იყოს სხვა გზით. ზოგიერთი მათგანი ნაჩვენებია ნახ. 4. დეფინიციის მიხედვით, ხე არის წყობილი სიმრავლეთა სისტემა, სადაც ეს სიმრავლეები ან არ იკვეთება, ან მთლიანად შეიცავს ერთმანეთს. ასეთი კომპლექტები შეიძლება იყოს გამოსახული, როგორც რეგიონები სიბრტყეზე (ნახ. 4a). ნახ. 4b, წყობილი ნაკრები არ არის განლაგებული სიბრტყეზე, მაგრამ წაგრძელებულია ერთ ხაზზე. ბრინჯი. 4b ასევე შეიძლება ჩაითვალოს, როგორც ალგებრული ფორმულის დიაგრამა, რომელიც შეიცავს ჩადგმულ ფრჩხილებს. ბრინჯი. 4c გვაძლევს კიდევ ერთ პოპულარულ გზას ხის სტრუქტურის, როგორც ledger-ის სახით წარმოდგენის. ბრინჯი. 4. ხის სტრუქტურების წარმოდგენის სხვა გზები: (ა) წყობილი სიმრავლეები; (ბ) ჩასმული ფრჩხილები; (გ) გადაცემული სია. led სიას აშკარა მსგავსება აქვს კოდის ფორმატირების გზასთან. მართლაც, სტრუქტურირებული პროგრამირების პარადიგმის ფარგლებში დაწერილი პროგრამა შეიძლება წარმოდგენილი იყოს როგორც ხე, რომელიც შედგება ბუდობრივი სტრუქტურებისგან. თქვენ ასევე შეგიძლიათ დახაზოთ ანალოგია წიგნების სიასა და წიგნებში სარჩევის გამოჩენას შორის, სადაც სექციები შეიცავს ქვესექციას, რომელიც თავის მხრივ შეიცავს ქვესექციას და ა.შ. ასეთი სექციების ნუმერაციის ტრადიციულ ხერხს (ნაწილი 1, ქვესექცია 1.1 და 1.2, ქვეგანყოფილება 1.1.2 და ა.შ.) ეწოდება დიუის ათობითი სისტემა. როგორც გამოიყენება ხეზე ნახ. 3 და 4 ეს სისტემა მისცემს: 1.A; 1.1B; 1.2C; 1.2.1D; 1.2.2E; 1.2.3F; 1.2.3.1G; ხის სტრუქტურებთან დაკავშირებულ ყველა ალგორითმში უცვლელად ჩნდება ერთი და იგივე იდეა, კერძოდ, იდეა. გავლისან ხის გავლა. ეს არის ხის კვანძების მონახულების გზა, რომელშიც თითოეული კვანძი ზუსტად ერთხელ გადის. ეს იწვევს ხის კვანძების ხაზოვან მოწყობას. კერძოდ, არსებობს სამი გზა: შეგიძლიათ გადაკვეთოთ კვანძები წინსვლის, უკან და უკანა თანმიმდევრობით. წინ გადასვლის ალგორითმი: ეს ალგორითმი რეკურსიულია, რადგან ხეზე გადასასვლელი შეიცავს გადამკვეთ ქვეხეებს და ისინი, თავის მხრივ, იკვეთება იმავე ალგორითმის მიხედვით. კერძოდ, ნახ. 3 და 4 პირდაპირი გადაკვეთა იძლევა კვანძების თანმიმდევრობას: A, B, C, D, E, F, G. შედეგად მიღებული თანმიმდევრობა შეესაბამება კვანძების მარცხნიდან მარჯვნივ ჩამოთვლას ხის წარმოდგენისას წყობილი ფრჩხილების გამოყენებით და დიუის ათწილადში, ასევე ზემოდან ქვემოდან გადასვლისას, როდესაც წარმოდგენილია როგორც ledger-ის სია. როდესაც ეს ალგორითმი განხორციელებულია პროგრამირების ენაზე, root-ზე დარტყმა შეესაბამება გარკვეული მოქმედებების შესრულებას პროცედურის ან ფუნქციით, ხოლო ქვეხეებში გავლა შეესაბამება რეკურსიულ ზარებს თავისთვის. კერძოდ, ორობითი ხისთვის (სადაც არაუმეტეს ორი ქვეხე მოდის თითოეული კვანძიდან), შესაბამისი პროცედურა ასე გამოიყურება: // Preorder Traversal - პირდაპირი შეკვეთის პროცედურის ინგლისური სახელი PreorderTraversal((არგუმენტები)); დაწყება //ძირის გავლა DoSomething((არგუმენტები)); // მარცხენა ქვეხის გავლა if (There is a left subtree) then PreorderTransversal((არგუმენტები 2)); //მარჯვნივ ქვეხის გადაცემა if (Right subtree exists) მაშინ PreorderTransversal((არგუმენტები 3)); დასასრული; ანუ, ჯერ პროცედურა ასრულებს ყველა მოქმედებას და მხოლოდ ამის შემდეგ ხდება ყველა რეკურსიული ზარი. გვერდის ავლით ალგორითმი საპირისპირო თანმიმდევრობით: ანუ, ყველა ქვეხე იკვეთება მარცხნიდან მარჯვნივ და დაბრუნება ფესვში მდებარეობს ამ ტრავერსიებს შორის. ხისთვის ნახ. 3 და 4 ეს იძლევა კვანძების თანმიმდევრობას: B, A, D, C, E, G, F. შესაბამის რეკურსიულ პროცედურაში მოქმედებები განლაგდება რეკურსიულ ზარებს შორის არსებულ ხარვეზებში. კერძოდ ორობითი ხისთვის: // Inorder Traversal არის საპირისპირო რიგის პროცედურის ინგლისური სახელი InorderTraversal((არგუმენტები)); start // მარცხენა ქვეხის გავლა თუ (There is a left subtree) then InorderTraversal((არგუმენტები 2)); // DoSomething ((არგუმენტები)) ფესვის გავლა; // მარჯვენა ქვეხის გავლა თუ (There is a right subtree) მაშინ InorderTraversal((არგუმენტები 3)); დასასრული; გადაკვეთის ალგორითმი ტერმინალის თანმიმდევრობით: ხისთვის ნახ. 3 და 4 ეს მისცემს კვანძების თანმიმდევრობას: B, D, E, G, F, C, A. შესაბამის რეკურსიულ პროცედურაში მოქმედებები განლაგდება რეკურსიული ზარების შემდეგ. კერძოდ ორობითი ხისთვის: // Postorder Traversal არის ინგლისური სახელწოდება ბოლო შეკვეთის პროცედურისთვის PostorderTraversal((არგუმენტები)); start // მარცხენა ქვეხის გავლა თუ (There is a left subtree) then PostorderTraversal((არგუმენტები 2)); // მარჯვენა ქვეხის გავლა თუ (There is a right subtree) მაშინ PostorderTraversal((არგუმენტები 3)); // DoSomething ((არგუმენტები)) ფესვის გავლა; დასასრული; თუ გარკვეული ინფორმაცია მდებარეობს ხის კვანძებში, მაშინ შეიძლება გამოყენებულ იქნას შესაბამისი დინამიური მონაცემთა სტრუქტურა მის შესანახად. პასკალში ეს კეთდება ჩანაწერის ტიპის ცვლადით, რომელიც შეიცავს მითითებებს იმავე ტიპის ქვეხეებზე. მაგალითად, ორობითი ხე, სადაც თითოეული კვანძი შეიცავს მთელ რიცხვს, შეიძლება შეინახოს PTree ტიპის ცვლადის გამოყენებით, რომელიც აღწერილია ქვემოთ: ტიპი PTree = ^TTree; TTree = ჩანაწერი Inf: მთელი რიცხვი; LeftSubTree, RightSubTree: PTree; დასასრული; თითოეული კვანძი არის PTree ტიპის. ეს არის მაჩვენებელი, ანუ თითოეული კვანძი უნდა შეიქმნას მასზე ახალი პროცედურის გამოძახებით. თუ კვანძი არის ფოთლოვანი კვანძი, მაშინ მისი LeftSubTree და RightSubTree ველები დაყენებულია ნული. წინააღმდეგ შემთხვევაში, LeftSubTree და RightSubTree კვანძები ასევე იქმნება ახალი პროცედურის მიხედვით. სქემატურად, ერთი ასეთი ჩანაწერი ნაჩვენებია ნახ. 5. ბრინჯი. 5. TTree ჩანაწერის სქემატური წარმოდგენა. ჩანაწერს აქვს სამი ველი: Inf - ზოგიერთი ნომერი, LeftSubTree და RightSubTree - მითითებები იმავე TTree ტიპის ჩანაწერებზე. ასეთი ჩანაწერებისგან შემდგარი ხის მაგალითი ნაჩვენებია სურათზე 6. ბრინჯი. 6. ხე, რომელიც შედგება TTree ტიპის ჩანაწერებისგან. თითოეული ჩანაწერი ინახავს რიცხვს და ორ მაჩვენებელს, რომელიც შეიძლება შეიცავდეს ნული, ან იმავე ტიპის სხვა ჩანაწერების მისამართები. თუ ადრე არ გიმუშავიათ სტრუქტურებთან, რომლებიც შედგებოდა ჩანაწერებისგან, რომლებიც შეიცავს იმავე ტიპის ჩანაწერების ბმულებს, მაშინ გირჩევთ გაეცნოთ მასალებს. განვიხილოთ ხის დახატვის ალგორითმი, რომელიც ნაჩვენებია ნახ. 6. თუ თითოეული ხაზი განიხილება კვანძად, მაშინ ეს სურათი სრულად აკმაყოფილებს წინა ნაწილში მოცემულ ხის განმარტებას. ბრინჯი. 6. ხე. რეკურსიული რუტინა აშკარად დახაზავს ერთ ხაზს (ღერო პირველ ჩანგალამდე) და შემდეგ თავის თავს უწოდებს ორი ქვეხის დახატვას. ქვეხეები განსხვავდებიან მათი შემცველი ხისგან საწყისი წერტილის კოორდინატებით, ბრუნვის კუთხით, ღეროს სიგრძით და მათში შემავალი ტოტების რაოდენობით (ერთით ნაკლები). ყველა ეს განსხვავება უნდა იყოს რეკურსიული პროცედურის პარამეტრებში. ასეთი პროცედურის მაგალითი, რომელიც დაწერილია დელფში, ნაჩვენებია ქვემოთ: პროცედურის ხე (ტილო: TCanvas; //ტილო, რომელზეც ხე იქნება დახატული x,y: გაფართოებული; //ძირის კოორდინატები კუთხე: გაფართოებული; //კუთხე, რომელზეც ხე იზრდება. / /ფორკების რაოდენობა (რამდენი რეკურსიული ზარი ჯერ კიდევ არ არის განხორციელებული)); var x2, y2: გაფართოებული; // მაგისტრალის დასასრული (განშტოების წერტილი) დასაწყისი x2:= x + TrunkLength * cos(კუთხე); y2:= y - TrunkLength * sin(Angle); Canvas.MoveTo(round(x), round(y)); Canvas.LineTo(round(x2), round(y2)); თუ n > 1, მაშინ იწყება ხე (ტილო, x2, y2, კუთხე+Pi/4, 0.55*ტანის სიგრძე, n-1); ხე(ტილო, x2, y2, კუთხე-Pi/4, 0.55*ტანის სიგრძე, n-1); დასასრული; დასასრული; მისაღებად ნახ. 6 ეს პროცედურა გამოიძახეს შემდეგი პარამეტრებით: ხე (სურათი 1. ტილო, 175, 325, Pi/2, 120, 15); გაითვალისწინეთ, რომ ნახაზი შესრულებულია რეკურსიულ გამოძახებამდე, ანუ ხე დახატულია პირდაპირი თანმიმდევრობით. ლეგენდის თანახმად, ქალაქ ბენარასის დიდ ტაძარში, საკათედრო ტაძრის ქვეშ, რომელიც აღნიშნავს სამყაროს შუაგულს, არის ბრინჯაოს დისკი, რომელზედაც დამაგრებულია 3 ბრილიანტის ღერო, ერთი წყრთა სიმაღლით და ფუტკრის სისქით. დიდი ხნის წინ, ოდითგანვე, ამ მონასტრის ბერები იყვნენ დამნაშავენი ღმერთი ბრამას წინაშე. განრისხებულმა ბრაჰმამ აღმართა სამი მაღალი კვერთხი და ერთ მათგანზე დადო 64 სუფთა ოქროს დისკი და ისე, რომ ყოველი პატარა დისკი უფრო დიდზე დევს. როგორც კი 64-ვე დისკი გადაინაცვლებს ღეროდან, რომელზედაც ღმერთმა ბრაჰმამ დადო ისინი სამყაროს შექმნისას, სხვა ღეროზე, კოშკი ტაძართან ერთად გადაიქცევა მტვრად და სამყარო დაიღუპება ჭექა-ქუხილის ქვეშ. ბრამას მიუხედავად, ეს თავსატეხი შემოგვთავაზა მე-19 საუკუნის ბოლოს ფრანგმა მათემატიკოსმა ედუარდ ლუკამ. გაყიდულ ვერსიაში ჩვეულებრივ იყენებდნენ 7-8 დისკს (ნახ. 7). ბრინჯი. 7. თავსატეხი „ჰანოის კოშკები“. დავუშვათ, არსებობს გამოსავალი ნ- 1 დისკი. მერე თარგმნა ნდისკები უნდა გაკეთდეს შემდეგნაირად: 1) ჩვენ ვცვლით ნ- 1 დისკი. ვინაიდან საქმისთვის ნ= 1 გადანაცვლების ალგორითმი აშკარაა, შემდეგ ინდუქციით, (1) – (3) მოქმედებების შესრულებით, შეგვიძლია გადავიტანოთ დისკების თვითნებური რაოდენობა. მოდით შევქმნათ რეკურსიული პროცედურა, რომელიც ბეჭდავს ცვლის მთელ თანმიმდევრობას დისკების მოცემული რაოდენობისთვის. ასეთმა პროცედურამ უნდა დაბეჭდოს ინფორმაცია ერთი ცვლის შესახებ (ალგორითმის მე-2 საფეხურიდან) ყოველი გამოძახებით. (1) და (3) პუნქტებიდან გადაადგილებისთვის პროცედურა თავისთავად გამოიძახება დისკების რაოდენობის შემცირებით ერთით. //n – დისკების რაოდენობა //a, b, c – პინის ნომრები. გადართვა ხორციელდება pin a-დან, //b-ზე დამხმარე ქინძისთავზე. პროცედურა ჰანოი(n, a, b, c: მთელი რიცხვი); დასაწყისი, თუ n > 1, შემდეგ იწყება ჰანოი (n-1, a, c, b); writeln(a, " -> ", b); ჰანოი (n-1, c, b, a); end else writeln(a, " -> ", b); დასასრული; გაითვალისწინეთ, რომ რეკურსიულად მოწოდებული პროცედურების ნაკრები ამ შემთხვევაში ქმნის ხეს, რომელიც გადაკვეთს საპირისპირო თანმიმდევრობით. ანალიზის ამოცანაა გამოიყენოს არსებული სტრიქონი, რომელიც შეიცავს არითმეტიკულ გამოსახულებას და მასში შემავალი ცვლადების ცნობილი მნიშვნელობების გამოსათვლელად გამოხატვის მნიშვნელობის გამოსათვლელად. არითმეტიკული გამონათქვამების გამოთვლის პროცესი შეიძლება წარმოდგენილი იყოს ორობითი ხის სახით. მართლაც, თითოეული არითმეტიკული ოპერატორი (+, -, *, /) მოითხოვს ორ ოპერანდს, რომლებიც ასევე იქნება არითმეტიკული გამოსახულებები და, შესაბამისად, შეიძლება ჩაითვალოს ქვეხეებად. ბრინჯი. 8 გვიჩვენებს ხის მაგალითს, რომელიც შეესაბამება გამონათქვამს: ბრინჯი. 8. არითმეტიკული გამოხატვის შესაბამისი სინტაქსის ხე (6). ასეთ ხეში ფოთლის კვანძები ყოველთვის იქნება ცვლადები (აქ x) ან რიცხვითი მუდმივები და ყველა შიდა კვანძი შეიცავს არითმეტიკულ ოპერატორებს. ოპერატორის შესასრულებლად, ჯერ უნდა შეაფასოთ მისი ოპერანდები. ამრიგად, ფიგურაში ხე უნდა გაიაროს ბოლო თანმიმდევრობით. კვანძების შესაბამისი თანმიმდევრობა დაურეკა საპირისპირო პოლონური აღნიშვნაარითმეტიკული გამოხატულება. სინტაქსის ხის აგებისას ყურადღება უნდა მიაქციოთ შემდეგ მახასიათებელს. თუ არსებობს, მაგალითად, გამოხატულება და ჩვენ წავიკითხავთ შეკრებისა და გამოკლების მოქმედებებს მარცხნიდან მარჯვნივ, მაშინ სწორი სინტაქსური ხე პლუსის ნაცვლად შეიცავს მინუსს (ნახ. 9ა). ფაქტიურად ეს ხე შეესაბამება გამონათქვამს.ხის შედგენის გაადვილება შესაძლებელია, თუ გამონათქვამს (8) გავაანალიზებთ უკუსვლით, მარჯვნიდან მარცხნივ. ამ შემთხვევაში, ხე ნაჩვენებია ნახ. 9b, რომელიც უდრის 8a ხეს, მაგრამ არ საჭიროებს ნიშნის შეცვლას. ანალოგიურად, მარჯვნიდან მარცხნივ, თქვენ უნდა გაანალიზოთ გამონათქვამები, რომლებიც შეიცავს გამრავლებისა და გაყოფის ოპერატორებს. ბრინჯი. 9. სინტაქსის ხეები გამოხატვისთვის ა – ბ + გკითხვისას მარცხნიდან მარჯვნივ (ა) და მარჯვნიდან მარცხნივ (ბ). ეს მიდგომა სრულად არ გამორიცხავს რეკურსიას. თუმცა, ის საშუალებას გაძლევთ შემოიფარგლოთ მხოლოდ ერთი მოწოდებით რეკურსიულ პროცედურაზე, რაც შეიძლება საკმარისი იყოს, თუ მოტივი არის მაქსიმალური შესრულების ზრუნვა. ამ მიდგომის იდეაა რეკურსიული ზარების ჩანაცვლება მარტივი მარყუჟით, რომელიც შესრულდება იმდენჯერ, რამდენჯერაც არის რეკურსიული პროცედურებით წარმოქმნილი კვანძები ხეში. კონკრეტულად რა გაკეთდება თითოეულ საფეხურზე უნდა განისაზღვროს ნაბიჯის ნომრით. ნაბიჯის ნომრისა და აუცილებელი მოქმედებების შედარება არ არის ტრივიალური ამოცანა და თითოეულ შემთხვევაში ის ცალკე უნდა გადაწყდეს. მაგალითად, ვთქვათ, რომ გსურთ ამის გაკეთება კწყობილი მარყუჟები ნნაბიჯები თითოეულში: i1:= 0-დან n-1-მდე გააკეთეთ i2:= 0-დან n-1-მდე გააკეთეთ i3:= 0-დან n-1-მდე გააკეთეთ… Თუ კწინასწარ არ არის ცნობილი, მაშინ შეუძლებელია მათი ცალსახად დაწერა, როგორც ზემოთ არის ნაჩვენები. 6.5-ე ნაწილში ნაჩვენები ტექნიკის გამოყენებით, შეგიძლიათ მიიღოთ საჭირო რაოდენობის ჩადგმული მარყუჟები რეკურსიული პროცედურის გამოყენებით: პროცედურა NestedCycles(ინდექსები: მთელი რიცხვების მასივი; n, k, სიღრმე: მთელი რიცხვი); var i: მთელი რიცხვი; დაიწყოს თუ სიღრმე რეკურსიისგან თავის დასაღწევად და ყველაფერი ერთ ციკლზე დასაყვანად, გაითვალისწინეთ, რომ თუ რიცხვთა სისტემის საფეხურებს ფუძით დავთვლით ნ, შემდეგ თითოეულ საფეხურს აქვს რიცხვი, რომელიც შედგება ციფრებისგან i1, i2, i3, ... ან შესაბამისი მნიშვნელობები ინდექსების მასივიდან. ანუ, რიცხვები შეესაბამება ციკლის მრიცხველების მნიშვნელობებს. ნაბიჯის ნომერი ჩვეულებრივ ათობითი რიცხვების სისტემაში: სულ ნაბიჯები იქნება ნკ. ათწილადი რიცხვების სისტემაში მათი რიცხვების დახარისხების და თითოეული მათგანის ფუძის მქონე სისტემაში გადაყვანის შემდეგ ნ, ჩვენ ვიღებთ ინდექსის მნიშვნელობებს: M:= რაუნდი(IntPower(n, k)); i:= 0-დან M-1-მდე დაიწყეთ ნომერი:= i; p:= 0-დან k-1-მდე დაიწყეთ ინდექსები := ნომერი mod n; ნომერი:= რიცხვი div n; დასასრული; DoSomething (ინდექსები); დასასრული; კიდევ ერთხელ აღვნიშნავთ, რომ მეთოდი არ არის უნივერსალური და თითოეული ამოცანისთვის მოგიწევთ საკუთარი თავის მოფიქრება. 1. დაადგინეთ, რას გააკეთებს შემდეგი რეკურსიული პროცედურები და ფუნქციები. (ა) რა დაიბეჭდება შემდეგი პროცედურა Rec(4)-ის გამოძახებისას? პროცედურა Rec(a: მთელი რიცხვი); დაიწყე წერა (a); თუ a>0 მაშინ Rec(a-1); writeln(a); დასასრული; (ბ) რა იქნება Nod(78, 26) ფუნქციის მნიშვნელობა? ფუნქცია Nod(a, b: integer): მთელი რიცხვი; იწყება თუ a > b მაშინ Nod:= Nod(a – b, b) else if b > a მაშინ Nod:= Nod(a, b – a) else Nod:= a; დასასრული; (გ) რა დაიბეჭდება შემდეგი პროცედურებით A(1) გამოძახებისას? პროცედურა A(n: მთელი რიცხვი); პროცედურა B(n: მთელი რიცხვი); პროცედურა A(n: მთელი რიცხვი); დაიწყე წერა (n); B(n-1); დასასრული; პროცედურა B(n: მთელი რიცხვი); დაიწყე წერა (n); თუნ (დ) რას დაიბეჭდება შემდეგი პროცედურა, როდესაც BT(0, 1, 3) ეწოდება? პროცედურა BT(x: რეალური; D, MaxD: მთელი რიცხვი); დაიწყება, თუ D = MaxD, შემდეგ ჩაწერე (x) სხვაგან იწყება BT(x - 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); დასასრული; დასასრული; 2. Ouroboros - გველი, რომელიც შთანთქავს საკუთარ კუდს (სურ. 14) გაფართოებული სახით, აქვს სიგრძე. ლ, დიამეტრი თავის გარშემო დ, მუცლის კედლის სისქე დ. დაადგინეთ რამდენი კუდი ეტევა საკუთარ თავში და რამდენ ფენაში დაიდება კუდი ამის შემდეგ? ბრინჯი. 14. გაშლილი ორობორები. 3. ხისთვის ნახ. 10a, მიუთითეთ კვანძების ვიზიტების თანმიმდევრობა გადაკვეთის პირდაპირი, საპირისპირო და ბოლო თანმიმდევრობით. 4. გრაფიკულად წარმოადგინეთ წყობილი ფრჩხილებით მოცემული ხე: (A(B(C, D), E), F, G). 5. დახაზეთ სინტაქსის ხე შემდეგი არითმეტიკული გამოსახულებისთვის: დაწერეთ ეს გამოთქმა საპირისპირო პოლონური აღნიშვნით. 6. ქვემოთ მოყვანილი გრაფიკისთვის (სურათი 15) ჩაწერეთ მიმდებარეობის მატრიცა და ინციდენტის მატრიცა. 1. ფაქტორულის საკმარისად დიდი რაოდენობის (მილიონი ან მეტი) გაანგარიშების შემდეგ შეადარეთ რეკურსიული და იტერატიული ალგორითმების ეფექტურობა. რამდენჯერ განსხვავდება შესრულების დრო და როგორ იქნება ეს თანაფარდობა დამოკიდებული იმ რიცხვზე, რომლის ფაქტორიალიც არის გამოთვლილი? 2. დაწერეთ რეკურსიული ფუნქცია, რომელიც ამოწმებს ფრჩხილების სწორად განთავსებას სტრიქონში. სწორი მოწყობის შემთხვევაში, შემდეგი პირობები დაკმაყოფილებულია: (ა) გახსნისა და დახურვის ფრჩხილების რაოდენობა ტოლია. არასწორი განლაგების მაგალითები:)(, ())(, ())(()) და ა.შ. 3. ხაზი შეიძლება შეიცავდეს ფრჩხილებს, როგორც მრგვალ, ასევე კვადრატულ ფრჩხილებს. თითოეული გასახსნელი ფრჩხილი შეესაბამება იმავე ტიპის დახურვის ფრჩხილს (მრგვალი - მრგვალი, კვადრატი - კვადრატი). დაწერეთ რეკურსიული ფუნქცია, რათა შეამოწმოთ სწორია თუ არა ფრჩხილები ამ შემთხვევაში. არასწორი განლაგების მაგალითი: ([) ]. 4. 6 სიგრძის მოქმედი ფრჩხილების სტრუქტურების რაოდენობაა 5: ()()(), (())(), ()(()), ((())), (()()). მითითება: "()" მინიმალური სიგრძის ფრჩხილის სწორი სტრუქტურა. უფრო დიდი სიგრძის კონსტრუქციები მიიღება მცირე სიგრძის სტრუქტურებისგან, ორი გზით: (ა) თუ პატარა სტრუქტურა არის ფრჩხილებში, 5. შექმენით პროცედურა, რომელიც ბეჭდავს ყველა შესაძლო პერმუტაციას მთელი რიცხვებისთვის 1-დან N-მდე. 6. შექმენით პროცედურა, რომელიც ამობეჭდავს კომპლექტის ყველა ქვეჯგუფს (1, 2, ..., N). 7. შექმენით პროცედურა, რომელიც ბეჭდავს N ნატურალური რიცხვის ყველა შესაძლო წარმოდგენას სხვა ნატურალური რიცხვების ჯამის სახით. 8. შექმენით ფუნქცია, რომელიც გამოთვლის მასივის ელემენტების ჯამს შემდეგი ალგორითმის მიხედვით: მასივი იყოფა შუაზე, გამოითვლება და ემატება ელემენტების ჯამები თითოეულ ნახევარში. მასივის ნახევარში ელემენტების ჯამი გამოითვლება იმავე ალგორითმის მიხედვით, ანუ ისევ ნახევარზე გაყოფით. დაყოფა ხდება მანამ, სანამ მიღებული მასივი არ შეიცავს ერთ ელემენტს და ჯამის გამოთვლა, შესაბამისად, ტრივიალური გახდება. კომენტარი: ეს ალგორითმი არის ალტერნატივა . რეალური ღირებულების მასივების შემთხვევაში, ეს ჩვეულებრივ საშუალებას გაძლევთ მიიღოთ მცირე დამრგვალების შეცდომები. 10. შექმენით პროცედურა, რომელიც ხაზავს კოხის მრუდს (ნახ. 12). 11. გამრავლება ნახ. 16. ნახატზე ყოველი მომდევნო გამეორებისას წრე 2,5-ჯერ მცირეა (ეს კოეფიციენტი შეიძლება იყოს პარამეტრი). 1. დ.კნუტი. კომპიუტერული პროგრამირების ხელოვნება. ვ. 1. (ნაწილი 2.3. „ხეები“). პრეზენტაცია თემაზე „რეკურსიული ალგორითმები“ შეიქმნა იმისათვის, რომ მოემზადოს სტუდენტები გამოცდისთვის კომპიუტერულ მეცნიერებაში და ისტ-ში. ნაშრომში განხილულია რეკურსიის განმარტება, მოყვანილია რეკურსიულად განსაზღვრული გრაფიკული ობიექტების მაგალითები. პრეზენტაცია შეიცავს მე-11 ამოცანის ამოხსნის გზებს ერთიანი სახელმწიფო გამოცდის - 2015 წლის კომპიუტერულ მეცნიერებათა სახელმწიფო გამოცდის პროექტის დემო ვერსიიდან. პირველი მეთოდი მოიცავს გამოძახების ხის აგებას, მეორე მეთოდი წყვეტს პრობლემას ჩანაცვლების მეთოდის გამოყენებით. განხილულია ამოცანების ორივე მეთოდის ამოხსნის 4 მაგალითი. გარდა ამისა, პრეზენტაცია შეიცავს 25 დავალებას ვარჯიშისთვის, პასუხებით კონსტანტინე პოლიაკოვის საიტიდან. პრეზენტაციების წინასწარი გადახედვის გამოსაყენებლად შექმენით Google ანგარიში (ანგარიში) და შედით: https://accounts.google.com დავალება No11 გამოყენება (საბაზო დონე, დრო - 5 წუთი) რეკურსიული ალგორითმები. ავტორი - Korotun O.V., კომპიუტერული მეცნიერების მასწავლებელი, მემორანდუმის "71-ე საშუალო სკოლა" რა უნდა იცოდეთ: რეკურსია - ობიექტის ან პროცესის განმარტებაში, აღწერაში, გამოსახულებაში ამ ობიექტის ან თავად პროცესის ფარგლებში, ანუ სიტუაცია, როდესაც ობიექტი არის მისი ნაწილი. რუსეთის ფედერაციის გერბი არის რეკურსიულად განსაზღვრული გრაფიკული ობიექტი: მასზე გამოსახული ორთავიანი არწივის მარჯვენა თათზე დამაგრებულია კვერთხი, რომელიც დაგვირგვინებულია გერბის შემცირებული ასლით. ვინაიდან ამ გერბზე ასევე არის კვერთხი არწივის მარჯვენა თათში, მიიღება უსასრულო რეკურსი. რუსეთის რეკურსიული გერბი პროგრამირებაში რეკურსია არის ფუნქციის გამოძახება თავისთავად, პირდაპირ ან სხვა ფუნქციების მეშვეობით, მაგალითად, ფუნქცია A იძახებს ფუნქციას B, ხოლო B ფუნქცია იძახებს A ფუნქციას. ჩადგმული ფუნქციის ან პროცედურის ზარების რაოდენობას ეწოდება რეკურსიის სიღრმე. რეკურსიის მაგალითი: თუ კაბაზე ცხიმის ლაქა გაქვთ, არ ინერვიულოთ. ზეთის ლაქებს აშორებენ ბენზინით, ბენზინის ლაქებს ხსნიან ტუტე ხსნარით, ტუტეს აშორებენ ესენციით, ესენციის კვალს ზეთით შეიზილეთ, თქვენ უკვე იცით, როგორ მოიცილოთ ზეთის ლაქები! დავალების მაგალითი: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); თუნ დავალების მაგალითი: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n) ; თუნ დავალების მაგალითი: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); if n სლაიდი 9 დავალების მაგალითი: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); if n სლაიდი 10 დავალების მაგალითი: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); if n სლაიდი 11 15 მაგალითი #2: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); თუნ მაგალითი #2: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყე წერა (n); if n სლაიდი 13 მაგალითი #3: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); წერის დაწყება ("*"); თუ n > 0, მაშინ იწყება F(n-2); F(n div 2) ბოლოს დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? 7 5 3 2 3 1 1 1 1 ამ მაგალითში ნაჩვენებია არა n პარამეტრის მნიშვნელობები, არამედ სიმბოლო * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0 მაგალითი #3: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-2); F(n div 2) ბოლოს დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? * "ვარსკვლავების" რაოდენობის დათვლით, ვიღებთ 21-ს ამ მაგალითში, ეკრანზე არ არის ნაჩვენები n პარამეტრის მნიშვნელობები, არამედ სიმბოლო * * * * * * * * * * * * * * * * * * * * * * * მაგალითი #3: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-2); F(n div 2) ბოლოს დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? მოვაგვაროთ პრობლემა ხის გარეშე. მოდით S(n) იყოს "ვარსკვლავების" რიცხვი, რომელიც გამოჩნდება F(n)-ის გამოძახებისას. მაშინ 1+S(n-2)+ S(n div 2), n>0 1 , n უნდა ვიცოდეთ S(7). S(7)= 1 +S(5)+ S(3) S(5)= 1 +S(3)+S(2) S(3)= 1 +S(1)+S(1) S( 2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S(1)= 1+ S(-1)+S(0)=1+ 1+1=3 უკუ: S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+ 13+ 7= 21 S(n)= მაგალითი #4: პროცედურა F(n: მთელი რიცხვი); დაიწყება თუ n სლაიდი 18 მაგალითი #4: პროცედურა F(n: მთელი რიცხვი); დაიწყება თუ n სლაიდი 19 მაგალითი #4: პროცედურა F(n: მთელი რიცხვი); დაიწყება თუ ნ მაგალითი #4: პროცედურა F(n: მთელი რიცხვი); დაიწყება თუ ნ დავალებები ტრენინგისთვის ამოცანა 1: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-2); F(ndiv 2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(5) გამოძახებისას? პასუხი: 34 დავალება 2: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-2); F(n-2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(6) გამოძახებისას? პასუხი: 58 ამოცანა 3: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-3); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? პასუხი: 15 დავალება 4: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-3); F(n-2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? პასუხი: 55 ამოცანა 5: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, მაშინ იწყება F(n-3); F(n-2); F(ndiv 2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(6) გამოძახებისას? პასუხი: 97 ამოცანა 6: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, დაიწყეთ writeln("*"); F(n-2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? პასუხი: 31 ამოცანა 7: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, დაიწყეთ writeln("*"); F(n-2); F(ndiv 2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? პასუხი: 81 ამოცანა 8: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყეთ წერა ("*"); თუ n > 0, დაიწყეთ writeln("*"); F(n-2); F(n-2); F(ndiv 2); დასასრული დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(6) გამოძახებისას? პასუხი: 77 ამოცანა 9: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); იწყება თუ n > 0, შემდეგ იწყება F(n-2); F(n-1); F(n-1); დასასრული; writeln ("*"); დასასრული ; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(5) გამოძახებისას? პასუხი: 148 ამოცანა 10: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაწყება, თუ n > 0, შემდეგ დაიწყეთ writeln("*"); F(n-2); F(n-1); F(n-1); დასასრული; writeln ("*"); დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(5) გამოძახებისას? პასუხი: 197 ამოცანა 11: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დასაწყისი, თუ n > 1, შემდეგ იწყება F(n-2); F(n-1); F(ndiv 2); დასასრული; writeln ("*"); დასასრული ; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(7) გამოძახებისას? პასუხი: 88 ამოცანა 12: მოცემულია რეკურსიული ალგორითმი: პროცედურა F(n: მთელი რიცხვი); დაიწყოს თუ n > 2, შემდეგ დაიწყე writeln("*"); F(n-2); F(n-1); F(ndiv 2); დასასრული ; writeln ("*"); დასასრული; რამდენი ვარსკვლავი დაიბეჭდება ეკრანზე F(6) გამოძახებისას? პასუხი: 33 ამოცანა 13: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 14: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 15: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 16: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 17: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 18: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 19: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 20: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 21: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 22: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 23: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 24: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ ამოცანა 25: მოცემულია რეკურსიული ალგორითმი: პროცედურა F (n: მთელი რიცხვი); დაიწყე წერა (n); თუნ
გამარჯობა N2
…
გამარჯობა N 10
…
გამარჯობა N1
…
გამარჯობა N 10
გამარჯობა N 10
…
გამარჯობა N14. განმეორებითი ურთიერთობები. რეკურსია და გამეორება
5. ხეები
5.1. ძირითადი განმარტებები. ხეების გამოსახვის გზები
ა) არის ერთი სპეციალური კვანძი, რომელსაც ამ ხის ფესვი ჰქვია.
ბ) დარჩენილი კვანძები (ძირის გამოკლებით) მოთავსებულია წყვილ-წყვილად განცალკევებულ ქვეჯგუფებში, რომელთაგან თითოეული თავის მხრივ არის ხე. ხეებს ეძახიან ქვეხეებიამ ხის.
5.2. გამვლელი ხეები
5.3. ხის წარმოდგენა კომპიუტერის მეხსიერებაში
6. რეკურსიული ალგორითმების მაგალითები
6.1. ხის ნახატი
6.2. ჰანოის კოშკები
ამ პროცესში საჭიროა, რომ დიდი დისკი არასოდეს დადგეს პატარას თავზე. ბერებს უჭირთ, რა თანმიმდევრობით უნდა მოხდეს მორიგეობა? საჭიროა მათთვის პროგრამული უზრუნველყოფის მიწოდება ამ თანმიმდევრობის გამოსათვლელად.
2) ჩვენ ვცვლით ნდისკი დარჩენილ თავისუფალ პინზე.
3) გადაიტანეთ დასტა ნ-1 (1) პუნქტში მიღებული 1 დისკი ნე დისკი.6.3. არითმეტიკული გამონათქვამების გარჩევა
7.3. ხის კვანძის განსაზღვრა მისი რიცხვით
ტესტის კითხვები
Დავალებები
(ბ) ნებისმიერი წყვილი გახსნის შიგნით - შესაბამისი დახურვის ფრჩხილებში, ფრჩხილები სწორად არის განთავსებული.
დაწერეთ რეკურსიული პროგრამა 2 სიგრძის ყველა მოქმედი ფრჩხილის სტრუქტურის გენერირებისთვის ნ.
ბ) თუ ორი პატარა სტრუქტურა იწერება თანმიმდევრობით.
ლიტერატურა
2. ნ.ვირტი. ალგორითმები და მონაცემთა სტრუქტურები.ჩამოტვირთვა:
გადახედვა:
სლაიდების წარწერები:
