อัลกอริทึมแบบเรียกซ้ำและแบบเรียกซ้ำ อัลกอริธึมแบบเรียกซ้ำและแบบเรียกซ้ำ สองโพรซีเดอร์แบบเรียกซ้ำถูกเขียนไว้ด้านล่าง
การเรียกซ้ำคือเมื่อรูทีนย่อยเรียกตัวเอง เมื่อพบโครงสร้างอัลกอริธึมดังกล่าวเป็นครั้งแรก คนส่วนใหญ่ประสบปัญหาบางอย่าง แต่ด้วยการฝึกฝนเพียงเล็กน้อย การเรียกซ้ำจะกลายเป็นเครื่องมือที่เข้าใจได้และมีประโยชน์มากในคลังแสงการเขียนโปรแกรมของคุณ
1. สาระสำคัญของการเรียกซ้ำ
โพรซีเดอร์หรือฟังก์ชันอาจมีการเรียกโพรซีเดอร์หรือฟังก์ชันอื่น รวมทั้งขั้นตอนสามารถเรียกตัวเองได้ ไม่มีความขัดแย้งที่นี่ - คอมพิวเตอร์ดำเนินการตามลำดับที่พบในโปรแกรมเท่านั้นและหากพบการเรียกโปรซีเจอร์ก็จะเริ่มดำเนินการตามขั้นตอนนี้ ไม่สำคัญว่าขั้นตอนใดให้คำสั่งให้ทำ
ตัวอย่างของขั้นตอนแบบเรียกซ้ำ:
ขั้นตอน Rec(a: integer); เริ่มต้นถ้า 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: จำนวนเต็ม); เริ่ม writeln(a); ถ้า a>0 แล้ว Rec2(a-1); จบ;
โปรดทราบว่าในตัวอย่างข้างต้น การเรียกซ้ำจะอยู่ภายในคำสั่งแบบมีเงื่อนไข มัน เงื่อนไขที่จำเป็นสำหรับการเรียกซ้ำจะสิ้นสุด โปรดทราบด้วยว่าโพรซีเดอร์เรียกตัวเองด้วยพารามิเตอร์ที่ต่างไปจากที่เรียกด้วย หากโพรซีเดอร์ไม่ได้ใช้ตัวแปรโกลบอล ก็จำเป็นเช่นกัน เพื่อไม่ให้การเรียกซ้ำดำเนินต่อไปอย่างไม่มีกำหนด
อาจมีรูปแบบที่ซับซ้อนกว่านี้เล็กน้อย: ฟังก์ชัน A เรียกใช้ฟังก์ชัน B ซึ่งจะเรียก A ซึ่งเรียกว่า การเรียกซ้ำที่ซับซ้อน. ปรากฎว่าขั้นตอนที่อธิบายก่อนจะต้องเรียกขั้นตอนที่ยังไม่ได้อธิบาย เพื่อให้เป็นไปได้ คุณต้องใช้ .
ขั้นตอน A(n: จำนวนเต็ม); (คำอธิบายไปข้างหน้า (ส่วนหัว) ของขั้นตอนแรก) ขั้นตอน B(n: จำนวนเต็ม); (คำอธิบายไปข้างหน้าของขั้นตอนที่สอง) ขั้นตอน A(n: จำนวนเต็ม); (คำอธิบายขั้นตอนแบบเต็ม A) เริ่ม writeln(n); ข(n-1); จบ; ขั้นตอน B(n: จำนวนเต็ม); (คำอธิบายทั้งหมดของขั้นตอน B) เริ่ม writeln(n); ifn
การประกาศไปข้างหน้าของขั้นตอน B อนุญาตให้เรียกจากขั้นตอน A การประกาศไปข้างหน้าของขั้นตอน A ไม่จำเป็นในตัวอย่างนี้และถูกเพิ่มเพื่อเหตุผลด้านสุนทรียะ
หากการเรียกซ้ำแบบธรรมดาสามารถเปรียบได้กับ ouroboros (รูปที่ 3) จากนั้นภาพของการเรียกซ้ำที่ซับซ้อนสามารถดึงออกมาจากที่รู้จักกันดี กวีเด็กที่ "หมาป่ากลัวกินกันเอง" ลองนึกภาพหมาป่าสองตัวกินกันเอง และคุณเข้าใจการเรียกซ้ำที่ซับซ้อน
ข้าว. 3. Ouroboros - งูที่กินหางของมันเอง วาดจากบทความเล่นแร่แปรธาตุ "Synosius" โดย Theodore Pelecanos (1478)
ข้าว. 4. การเรียกซ้ำที่ซับซ้อน
3. จำลองการทำงานของวงจรโดยใช้การเรียกซ้ำ
หากโพรซีเดอร์เรียกตัวเอง อันที่จริง สิ่งนี้นำไปสู่การดำเนินการตามคำสั่งที่อยู่ในนั้นซ้ำๆ ซึ่งคล้ายกับการทำงานของลูป ภาษาโปรแกรมบางภาษาไม่มีโครงสร้างการวนซ้ำเลย ปล่อยให้โปรแกรมเมอร์จัดระเบียบการทำซ้ำโดยใช้การเรียกซ้ำ (เช่น Prolog โดยที่การเรียกซ้ำเป็นเทคนิคการเขียนโปรแกรมหลัก)
ตัวอย่างเช่น ลองจำลองการทำงานของ for loop ในการทำเช่นนี้ เราจำเป็นต้องมีตัวแปรตัวนับขั้นตอน ซึ่งสามารถนำไปใช้ได้ ตัวอย่างเช่น เป็นพารามิเตอร์ขั้นตอน
ตัวอย่าง 1
ขั้นตอน LoopImitation(i, n: integer); (พารามิเตอร์แรกคือการนับขั้นตอน พารามิเตอร์ที่สองคือจำนวนขั้นตอนทั้งหมด) start writeln("Hello N", i); //ต่อไปนี้คือข้อความใด ๆ ที่จะถูกทำซ้ำหาก i ผลลัพธ์ของการโทรเช่น LoopImitation(1, 10) จะเป็นการดำเนินการตามคำสั่งสิบครั้งโดยเปลี่ยนตัวนับจาก 1 เป็น 10 ในกรณีนี้จะถูกพิมพ์: สวัสดี N1 โดยทั่วไปไม่ยากที่จะเห็นว่าพารามิเตอร์ของขั้นตอนคือข้อ จำกัด ของการเปลี่ยนแปลงค่าของตัวนับ คุณสามารถสลับการโทรแบบเรียกซ้ำและคำแนะนำที่จะทำซ้ำได้ ดังตัวอย่างต่อไปนี้ ตัวอย่าง 2
ขั้นตอน LoopImitation2(i, n: integer); เริ่มถ้าฉัน ในกรณีนี้ โพรซีเดอร์จะถูกเรียกซ้ำก่อนที่จะดำเนินการตามคำสั่ง อินสแตนซ์ใหม่ของโพรซีเดอร์ อย่างแรกเลย เรียกใช้อินสแตนซ์อื่น เป็นต้น จนกว่าเราจะถึงค่าสูงสุดของตัวนับ หลังจากนั้นโพรซีเดอร์สุดท้ายที่เรียกจะรันคำสั่ง จากนั้นโพรซีเดอร์สุดท้ายจะรันคำสั่งของมัน และอื่นๆ ผลลัพธ์ของการเรียก LoopImitation2 (1, 10) คือการพิมพ์คำทักทายในลำดับที่กลับกัน: สวัสดี N 10 หากเราจินตนาการถึงโพรซีเดอร์ที่เรียกซ้ำกันเป็นลูกโซ่ ในตัวอย่างที่ 1 เราจะดำเนินการจากโพรซีเดอร์ที่เรียกก่อนหน้านี้ไปยังโพรซีเดอร์ในภายหลัง ในตัวอย่างที่ 2 ในทางกลับกัน จากภายหลังไปก่อนหน้า สุดท้าย สามารถเรียกซ้ำระหว่างสองกลุ่มคำสั่ง ตัวอย่างเช่น: ขั้นตอน LoopImitation3(i, n: integer); เริ่ม writeln("สวัสดี N", i); (นี่อาจเป็นช่วงแรกของประโยค) ถ้า i ในที่นี้ อันดับแรก คำสั่งจากบล็อกแรกจะดำเนินการตามลำดับ จากนั้นคำสั่งของบล็อกที่สองจะดำเนินการในลำดับที่กลับกัน เมื่อเรียก LoopImitation3 (1, 10) เราได้รับ: สวัสดี N1 ต้องใช้สองลูปพร้อมกันเพื่อทำสิ่งเดียวกันโดยไม่เรียกซ้ำ คุณสามารถใช้ประโยชน์จากความจริงที่ว่าการดำเนินการของส่วนต่าง ๆ ของขั้นตอนเดียวกันนั้นแยกจากกันในเวลา ตัวอย่างเช่น: ตัวอย่างที่ 3: การแปลงตัวเลขเป็นเลขฐานสอง
การรับตัวเลขของเลขฐานสองดังที่คุณทราบนั้นเกิดขึ้นจากการหารด้วยเศษเหลือด้วยฐานของระบบตัวเลข 2 หากมีตัวเลข หลักสุดท้ายในการแทนค่าไบนารีจะเท่ากับ นำส่วนจำนวนเต็มของการหารด้วย 2: เราได้รับตัวเลขที่มีการแสดงเลขฐานสองเหมือนกัน แต่ไม่มีหลักสุดท้าย ดังนั้นจึงเพียงพอที่จะทำซ้ำสองการดำเนินการข้างต้นจนกว่าฟิลด์การหารถัดไปมีส่วนจำนวนเต็มเท่ากับ 0 หากไม่มีการเรียกซ้ำ จะมีลักษณะดังนี้: ในขณะที่ x>0 เริ่ม c:=x mod 2; x:=x div 2; เขียน (c); จบ; ปัญหาที่นี่คือตัวเลขของการแทนค่าไบนารีจะคำนวณในลำดับที่กลับกัน (ล่าสุดก่อน) ในการพิมพ์ตัวเลขในรูปแบบปกติ คุณจะต้องจำตัวเลขทั้งหมดในองค์ประกอบอาร์เรย์และส่งออกเป็นวงแยก ด้วยการเรียกซ้ำ การรับเอาต์พุตในลำดับที่ถูกต้องเป็นเรื่องง่ายโดยไม่ต้องใช้อาร์เรย์และลูปที่สอง กล่าวคือ: ขั้นตอน BinaryRepresentation(x: integer); 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: integer): integer; เริ่มต้นถ้า n > 1 แล้วแฟกทอเรียล:= n * แฟกทอเรียล(n-1) อื่นแฟกทอเรียล:= 1; จบ; ควรเข้าใจว่าการเรียกใช้ฟังก์ชันทำให้เกิดโอเวอร์เฮดเพิ่มเติม ดังนั้นตัวเลือกแรกสำหรับการคำนวณแฟกทอเรียลจะเร็วขึ้นบ้าง โดยทั่วไป โซลูชันแบบวนซ้ำจะทำงานได้เร็วกว่าโซลูชันแบบเรียกซ้ำ ก่อนที่จะไปยังสถานการณ์ที่การเรียกซ้ำมีประโยชน์ ลองมาดูตัวอย่างเพิ่มเติมอีกตัวอย่างหนึ่งที่ไม่ควรใช้ พิจารณากรณีพิเศษของความสัมพันธ์ที่เกิดซ้ำเมื่อค่าถัดไปในลำดับไม่ได้ขึ้นอยู่กับค่าใดค่าหนึ่ง แต่ขึ้นอยู่กับค่าก่อนหน้าหลายค่าในคราวเดียว ตัวอย่างคือลำดับฟีโบนักชีที่รู้จักกันดี ซึ่งแต่ละองค์ประกอบถัดไปเป็นผลรวมของสององค์ประกอบก่อนหน้า: ด้วยวิธีการ "หน้าผาก" คุณสามารถเขียน: Fib(n: integer): จำนวนเต็ม; เริ่มต้นถ้า n > 1 แล้ว Fib:= Fib(n-1) + Fib(n-2) อื่น Fib:= 1; จบ; การเรียก Fib แต่ละครั้งจะสร้างสำเนาของตัวเองขึ้นสองชุดในคราวเดียว แต่ละสำเนาจะสร้างอีกสองชุด เป็นต้น จำนวนการดำเนินการเพิ่มขึ้นตามจำนวน นแบบทวีคูณ แม้ว่าสำหรับการแก้ปัญหาแบบวนซ้ำ เชิงเส้น in นจำนวนการดำเนินการ อันที่จริง ตัวอย่างข้างต้นไม่ได้สอนเรา เมื่อไรไม่ควรใช้การเรียกซ้ำและ อย่างไรไม่ควรใช้ ท้ายที่สุด หากมีวิธีแก้ปัญหาแบบวนซ้ำ (แบบวนซ้ำ) แบบวนซ้ำ ลูปเดียวกันสามารถนำไปใช้ได้โดยใช้ขั้นตอนหรือฟังก์ชันแบบเรียกซ้ำ ตัวอย่างเช่น: // 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 เป็นอีกวิธีที่นิยมในการแสดงโครงสร้างต้นไม้เป็นรายการบัญชีแยกประเภท ข้าว. 4. วิธีอื่นในการแสดงโครงสร้างต้นไม้: (a) ชุดที่ซ้อนกัน; (b) วงเล็บที่ซ้อนกัน; (ค) รายการที่ยกให้ รายการนำมีความคล้ายคลึงกับวิธีการจัดรูปแบบโค้ดอย่างชัดเจน อันที่จริง โปรแกรมที่เขียนในกรอบของกระบวนทัศน์การเขียนโปรแกรมแบบมีโครงสร้างสามารถแสดงเป็นแผนผังที่ประกอบด้วยโครงสร้างที่ซ้อนกัน คุณยังสามารถเปรียบเทียบระหว่างรายการบัญชีแยกประเภทกับ รูปร่างสารบัญในหนังสือ โดยที่ส่วนต่างๆ มีส่วนย่อย ส่วนย่อยเหล่านั้นเป็นส่วนย่อย ฯลฯ วิธีดั้งเดิมในการนับส่วนดังกล่าว (ส่วนที่ 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 ลำดับผลลัพธ์สอดคล้องกับการแจงนับโหนดจากซ้ายไปขวาเมื่อแสดงต้นไม้โดยใช้วงเล็บที่ซ้อนกันและในทศนิยม Dewey เช่นเดียวกับการไปจากบนลงล่างเมื่อแสดงเป็นรายการบัญชีแยกประเภท เมื่ออัลกอริธึมนี้ถูกนำมาใช้ในภาษาการเขียนโปรแกรม การกดที่รูทจะสอดคล้องกับการดำเนินการบางอย่างโดยโพรซีเดอร์หรือฟังก์ชัน และการส่งผ่านทรีย่อยจะสอดคล้องกับการเรียกซ้ำไปยังตัวเอง โดยเฉพาะอย่างยิ่ง สำหรับไบนารีทรี (โดยที่ทรีย่อยไม่เกินสองทรีมาจากแต่ละโหนด) ขั้นตอนที่เกี่ยวข้องจะมีลักษณะดังนี้: // Preorder Traversal - ชื่อภาษาอังกฤษสำหรับขั้นตอนการสั่งซื้อโดยตรง PreorderTraversal((อาร์กิวเมนต์)); เริ่มต้น //ส่งผ่านรูท DoSomething((อาร์กิวเมนต์)); // ผ่านทรีย่อยด้านซ้ายถ้า (มีทรีย่อยด้านซ้าย) จากนั้น PreorderTransversal((อาร์กิวเมนต์ 2)); //ส่งทรีย่อยทางขวาถ้า (มีทรีย่อยที่ถูกต้อง) จากนั้น PreorderTransversal((อาร์กิวเมนต์ 3)); จบ; กล่าวคือ ขั้นแรก โพรซีเดอร์จะดำเนินการทั้งหมด จากนั้นจึงเกิดการเรียกซ้ำทั้งหมด อัลกอริทึมบายพาสในลำดับย้อนกลับ: นั่นคือ ทรีย่อยทั้งหมดจะเคลื่อนที่จากซ้ายไปขวา และการกลับไปยังรูทจะอยู่ระหว่างการข้ามผ่านเหล่านี้ สำหรับต้นไม้ในรูป 3 และ 4 นี้จะให้ลำดับของโหนด: B, A, D, C, E, G, F. ในโพรซีเดอร์แบบเรียกซ้ำที่สอดคล้องกัน การดำเนินการจะอยู่ในช่องว่างระหว่างการเรียกซ้ำ โดยเฉพาะอย่างยิ่งสำหรับต้นไม้ไบนารี: // Inorder Traversal เป็นชื่อภาษาอังกฤษสำหรับขั้นตอนการสั่งย้อนกลับ InorderTraversal((อาร์กิวเมนต์)); เริ่มต้น // ข้ามทรีย่อยด้านซ้ายถ้า (มีทรีย่อยด้านซ้าย) แล้ว InorderTraversal((อาร์กิวเมนต์ 2)); // ข้ามราก DoSomething((อาร์กิวเมนต์)); // การข้ามผ่านของแผนผังย่อยที่ถูกต้อง หาก (มีแผนผังย่อยที่ถูกต้อง) แล้ว InorderTraversal((อาร์กิวเมนต์ 3)); จบ; อัลกอริทึมการข้ามผ่านในลำดับเทอร์มินัล: สำหรับต้นไม้ในรูป 3 และ 4 สิ่งนี้จะให้ลำดับของโหนด: B, D, E, G, F, C, A ในโพรซีเดอร์แบบเรียกซ้ำที่สอดคล้องกัน การดำเนินการจะอยู่หลังจากการเรียกซ้ำ โดยเฉพาะอย่างยิ่งสำหรับต้นไม้ไบนารี: // Postorder Traversal เป็นชื่อภาษาอังกฤษสำหรับขั้นตอนการสั่งต่อท้าย PostorderTraversal((อาร์กิวเมนต์)); เริ่มต้น // ข้ามทรีย่อยด้านซ้ายถ้า (มีทรีย่อยด้านซ้าย) จากนั้น PostorderTraversal((อาร์กิวเมนต์ 2)); // การข้ามผ่านของแผนผังย่อยที่ถูกต้อง หาก (มีแผนผังย่อยที่ถูกต้อง) จากนั้น PostorderTraversal((อาร์กิวเมนต์ 3)); // ข้ามราก DoSomething((อาร์กิวเมนต์)); จบ; หากข้อมูลบางอย่างอยู่ในโหนดของทรี ก็สามารถใช้โครงสร้างข้อมูลแบบไดนามิกที่เหมาะสมเพื่อจัดเก็บได้ ใน Pascal ทำได้ด้วยตัวแปรประเภทเร็กคอร์ดที่มีตัวชี้ไปยังทรีย่อยที่เป็นประเภทเดียวกัน ตัวอย่างเช่น ต้นไม้ไบนารีที่แต่ละโหนดมีเลขจำนวนเต็มสามารถจัดเก็บได้โดยใช้ตัวแปรประเภท 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: ขยาย; //พิกัดรากมุม: ขยาย; //มุมที่ต้นไม้เติบโต TrunkLength: ขยาย; //ความยาวลำต้น n: จำนวนเต็ม // จำนวนส้อม (จำนวนการโทรซ้ำที่ยังไม่ได้ทำ)); var x2, y2: ขยาย; //จุดสิ้นสุดของลำต้น (จุดสาขา) เริ่มต้น x2:= x + TrunkLength * cos(มุม); y2:= y - TrunkLength * บาป (มุม); Canvas.MoveTo(รอบ(x), รอบ(y)); Canvas.LineTo(รอบ(x2) รอบ(y2)); ถ้า n > 1 ให้เริ่ม Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1); ต้นไม้ (ผ้าใบ, x2, y2, มุม-Pi/4, 0.55*TrunkLength, n-1); จบ; จบ; เพื่อให้ได้รูป 6 โพรซีเดอร์นี้ถูกเรียกด้วยพารามิเตอร์ต่อไปนี้: ต้นไม้ (Image1.Canvas, 175, 325, Pi/2, 120, 15); โปรดทราบว่าการวาดภาพเสร็จสิ้นก่อนการเรียกซ้ำ กล่าวคือ ต้นไม้ถูกวาดในลำดับโดยตรง ตามตำนานเล่าว่า ในวิหารใหญ่แห่งเมืองเบนารัส ใต้วิหารซึ่งเป็นศูนย์กลางของโลก มีจานสีบรอนซ์ซึ่งตรึงแท่งเพชร 3 แท่ง สูงหนึ่งศอกและหนาเท่าผึ้ง กาลครั้งหนึ่งนานมาแล้วภิกษุของอารามนี้มีความผิดต่อหน้าพระเจ้าพรหม ด้วยความโกรธ พระพรหมจึงสร้างไม้คฑาสูงสามอัน และวางแผ่นทองคำบริสุทธิ์ 64 แผ่นบนอันหนึ่ง และในลักษณะที่ดิสก์ขนาดเล็กแต่ละอันจะวางบนอันที่ใหญ่กว่า ทันทีที่ดิสก์ทั้ง 64 แผ่นถูกย้ายจากไม้เท้าซึ่งพระเจ้าพรหมวางไว้เมื่อสร้างโลกไปยังอีกแท่งหนึ่ง หอคอยพร้อมกับวัดจะกลายเป็นฝุ่นและโลกจะพินาศภายใต้เสียงฟ้าร้อง โดยไม่คำนึงถึง Brama ปริศนานี้ถูกเสนอเมื่อปลายศตวรรษที่ 19 โดยนักคณิตศาสตร์ชาวฝรั่งเศส Edouard Luca ในเวอร์ชันที่จำหน่ายแล้ว มักใช้ 7-8 ดิสก์ (รูปที่ 7) ข้าว. 7. ปริศนา "หอคอยแห่งฮานอย" สมมติว่ามีวิธีแก้ปัญหาสำหรับ น-1 แผ่น แล้วแปล นดิสก์ควรทำดังนี้: 1) เราเปลี่ยน น-1 ดิสก์ สำหรับกรณี น= 1 อัลกอริธึมการขยับนั้นชัดเจน จากนั้นโดยการเหนี่ยวนำโดยการดำเนินการ (1) – (3) เราสามารถเปลี่ยนจำนวนดิสก์ได้ตามอำเภอใจ มาสร้างขั้นตอนแบบเรียกซ้ำซึ่งพิมพ์ลำดับการเลื่อนทั้งหมดสำหรับดิสก์ตามจำนวนที่กำหนด ขั้นตอนดังกล่าวควรพิมพ์ข้อมูลเกี่ยวกับกะหนึ่งกะ (จากขั้นตอนที่ 2 ของอัลกอริทึม) กับการโทรแต่ละครั้ง สำหรับการเลื่อนจากจุด (1) และ (3) โพรซีเดอร์จะเรียกตัวเองด้วยจำนวนดิสก์ที่ลดลงหนึ่ง //n – จำนวนดิสก์ //a, b, c – หมายเลขพิน ทำการขยับจากพิน a, // ไปยังพิน b ด้วยพินเสริม c ขั้นตอน ฮานอย(n, a, b, c: จำนวนเต็ม); เริ่มต้นถ้า n > 1 แล้วเริ่มฮานอย (n-1, a, c, b); writeln(a, " -> ", b); ฮานอย(n-1, c, b, a); จบอย่างอื่น writeln(a, " -> ", b); จบ; โปรดทราบว่าชุดของโพรซีเดอร์ที่เรียกซ้ำในกรณีนี้จะสร้างต้นไม้ที่สำรวจในลำดับที่กลับกัน งานของการแยกวิเคราะห์คือการใช้สตริงที่มีอยู่ซึ่งมีนิพจน์ทางคณิตศาสตร์และค่าที่รู้จักของตัวแปรที่รวมอยู่ในนั้นเพื่อคำนวณค่าของนิพจน์ กระบวนการคำนวณนิพจน์เลขคณิตสามารถแสดงเป็นทรีไบนารี อันที่จริง ตัวดำเนินการเลขคณิตแต่ละตัว (+, -, *, /) ต้องการตัวถูกดำเนินการสองตัว ซึ่งจะเป็นนิพจน์ทางคณิตศาสตร์ด้วย ดังนั้นจึงถือได้ว่าเป็นทรีย่อย ข้าว. 8 แสดงตัวอย่างของต้นไม้ที่สอดคล้องกับนิพจน์: ข้าว. 8. แผนผังไวยากรณ์ที่สอดคล้องกับนิพจน์เลขคณิต (6) ในต้นไม้ดังกล่าว โหนดของใบไม้จะเป็นตัวแปรเสมอ (ที่นี่ x) หรือค่าคงที่ตัวเลข และโหนดภายในทั้งหมดจะมีตัวดำเนินการเลขคณิต ในการรันโอเปอเรเตอร์ คุณต้องประเมินตัวถูกดำเนินการก่อน ดังนั้นต้นไม้ในรูปควรถูกสำรวจในลำดับสุดท้าย ลำดับที่สอดคล้องกันของโหนด เรียกว่า สัญกรณ์โปแลนด์ย้อนกลับนิพจน์ทางคณิตศาสตร์ เมื่อสร้างแผนผังไวยากรณ์ คุณควรใส่ใจ คุณสมบัติต่อไป. หากมี ตัวอย่างเช่น นิพจน์ และเราจะอ่านการบวกและการลบจากซ้ายไปขวา จากนั้นแผนผังไวยากรณ์ที่ถูกต้องจะมีเครื่องหมายลบแทนที่จะเป็นเครื่องหมายบวก (รูปที่ 9a) อันที่จริง ต้นไม้นี้สอดคล้องกับนิพจน์ เป็นไปได้ที่จะอำนวยความสะดวกในการรวบรวมต้นไม้หากเราวิเคราะห์นิพจน์ (8) ในทางกลับกัน จากขวาไปซ้าย ในกรณีนี้ ต้นไม้ที่แสดงในรูปที่ 9b ซึ่งเทียบเท่ากับต้นไม้ 8a แต่ไม่ต้องการการเปลี่ยนเครื่องหมาย ในทำนองเดียวกัน จากขวาไปซ้าย คุณต้องวิเคราะห์นิพจน์ที่มีตัวดำเนินการการคูณและการหาร ข้าว. 9. ต้นไม้ไวยากรณ์สำหรับนิพจน์ เอ – ข + คเมื่ออ่านจากซ้ายไปขวา (a) และจากขวาไปซ้าย (b) วิธีนี้ไม่ได้กำจัดการเรียกซ้ำอย่างสมบูรณ์ อย่างไรก็ตาม อนุญาตให้คุณจำกัดตัวเองให้โทรไปยังโพรซีเดอร์แบบเรียกซ้ำได้เพียงครั้งเดียว ซึ่งอาจเพียงพอหากแรงจูงใจนั้นเกี่ยวข้องกับประสิทธิภาพสูงสุด แนวคิดของวิธีนี้คือการแทนที่การเรียกแบบเรียกซ้ำด้วยการวนซ้ำแบบง่ายที่จะดำเนินการหลายครั้งเนื่องจากมีโหนดในทรีที่เกิดจากโพรซีเดอร์แบบเรียกซ้ำ สิ่งที่ต้องทำในแต่ละขั้นตอนควรกำหนดโดยหมายเลขขั้นตอน การเปรียบเทียบหมายเลขขั้นตอนและการดำเนินการที่จำเป็นนั้นไม่ใช่เรื่องง่าย และจะต้องแก้ไขแยกกันในแต่ละกรณี ตัวอย่างเช่น สมมติว่าคุณต้องการทำ kซ้อนลูปบน นขั้นตอนในแต่ละ: สำหรับ i1:= 0 ถึง n-1 ทำเพื่อ i2:= 0 ถึง n-1 ทำเพื่อ i3:= 0 ถึง n-1 ทำ … ถ้า kไม่ทราบล่วงหน้าจึงเป็นไปไม่ได้ที่จะเขียนให้ชัดเจนดังที่แสดงไว้ข้างต้น การใช้เทคนิคที่แสดงในหัวข้อ 6.5 คุณสามารถรับจำนวนลูปที่ซ้อนกันตามที่ต้องการโดยใช้ขั้นตอนแบบเรียกซ้ำ: ขั้นตอน NestedCycles (ดัชนี: อาร์เรย์ของจำนวนเต็ม; n, k, ความลึก: จำนวนเต็ม); var i: จำนวนเต็ม; เริ่มต้นถ้าความลึก เพื่อกำจัดการเรียกซ้ำและลดทุกอย่างให้เป็นหนึ่งรอบ โปรดทราบว่าถ้าเรานับขั้นตอนในระบบตัวเลขด้วยฐาน นจากนั้นแต่ละขั้นตอนจะมีตัวเลขซึ่งประกอบด้วยตัวเลข i1, i2, i3, ... หรือค่าที่เกี่ยวข้องจากอาร์เรย์ Indexes นั่นคือตัวเลขที่สอดคล้องกับค่าของตัวนับรอบ หมายเลขขั้นตอนในระบบเลขฐานสิบปกติ: ขั้นตอนทั้งหมดจะเป็น NK. หลังจากจัดเรียงตัวเลขในระบบเลขฐานสิบแล้วแปลแต่ละตัวให้เป็นระบบฐาน นเราได้รับค่าดัชนี: M:= รอบ (IntPower(n, k)); สำหรับ i:= 0 ถึง M-1 เริ่ม Number:= i; สำหรับ p:= 0 ถึง k-1 เริ่มต้น Indexes := Number mod n; จำนวน:= จำนวน div n; จบ; ทำอะไรบางอย่าง (ดัชนี); จบ; เราทราบอีกครั้งว่าวิธีการนี้ไม่เป็นสากล และสำหรับแต่ละงาน คุณจะต้องคิดหาวิธีของคุณเอง 1. กำหนดว่าขั้นตอนและฟังก์ชันแบบเรียกซ้ำต่อไปนี้จะทำอะไร (a) ขั้นตอนต่อไปนี้จะพิมพ์อะไรเมื่อเรียก Rec(4)? ขั้นตอน Rec(a: integer); เริ่ม writeln(a); ถ้า a>0 แล้ว Rec(a-1); writeln(ก); จบ; (ข) ค่าของฟังก์ชัน Nod(78, 26) จะเป็นอย่างไร? ฟังก์ชัน Nod(a, b: integer): integer; เริ่มถ้า a > b แล้วก็ Nod:= Nod(a – b, b) else if b > a แล้วก็ Nod:= Nod(a, b – a) อื่น Nod:= a; จบ; (c) สิ่งที่จะพิมพ์โดยขั้นตอนต่อไปนี้เมื่อเรียก A(1)? ขั้นตอน A(n: จำนวนเต็ม); ขั้นตอน B(n: จำนวนเต็ม); ขั้นตอน A(n: จำนวนเต็ม); เริ่ม writeln(n); ข(n-1); จบ; ขั้นตอน B(n: จำนวนเต็ม); เริ่ม writeln(n); ifn (d) ขั้นตอนต่อไปนี้จะพิมพ์อะไรเมื่อเรียก BT(0, 1, 3)? ขั้นตอน BT(x: จริง; D, MaxD: จำนวนเต็ม); เริ่มต้นถ้า D = MaxD แล้ว writeln(x) อื่นเริ่ม BT(x - 1, D + 1, MaxD); BT(x + 1, D + 1, MaxD); จบ; จบ; 2. Ouroboros - งูกินหางของตัวเอง (รูปที่ 14) ในรูปแบบขยายมีความยาว หลี่, เส้นผ่านศูนย์กลางรอบศีรษะ ดี, ความหนาของผนังช่องท้อง d. กำหนดจำนวนหางที่เขาสามารถใส่เข้าไปในตัวเองและหางจะวางกี่ชั้นหลังจากนั้น? ข้าว. 14. แฉ ouroboros 3. สำหรับต้นไม้ในรูป 10a ระบุลำดับของการเข้าชมโหนดในลำดับโดยตรง ย้อนกลับ และสิ้นสุดของการข้ามผ่าน 4. แทนกราฟิกต้นไม้ที่กำหนดโดยวงเล็บที่ซ้อนกัน: (A(B(C, D), E), F, G). 5. วาดแผนผังไวยากรณ์สำหรับนิพจน์เลขคณิตต่อไปนี้: เขียนนิพจน์นี้ในสัญกรณ์โปแลนด์ย้อนกลับ 6. สำหรับกราฟด้านล่าง (รูปที่ 15) ให้เขียนเมทริกซ์ adjacency และเมทริกซ์อุบัติการณ์ 1. คำนวณแฟคทอเรียลก็พอ จำนวนมากของครั้ง (ล้านหรือมากกว่า) เปรียบเทียบประสิทธิภาพของอัลกอริธึมแบบเรียกซ้ำและแบบวนซ้ำ เวลาดำเนินการจะแตกต่างกันกี่ครั้งและอัตราส่วนนี้จะขึ้นอยู่กับจำนวนที่คำนวณแฟคทอเรียลอย่างไร 2. เขียนฟังก์ชันแบบเรียกซ้ำที่ตรวจสอบตำแหน่งที่ถูกต้องของวงเล็บในสตริง ด้วยการจัดวางที่ถูกต้อง จะเป็นไปตามเงื่อนไขต่อไปนี้: (ก) จำนวนวงเล็บเปิดและวงเล็บปิดเท่ากัน ตัวอย่างการวางตำแหน่งที่ไม่ถูกต้อง:)(, ())(, ())(() เป็นต้น 3. เส้นสามารถมีวงเล็บทั้งวงเล็บกลมและเหลี่ยม วงเล็บเปิดแต่ละอันสอดคล้องกับวงเล็บปิดประเภทเดียวกัน (กลม - กลม, สี่เหลี่ยม - สี่เหลี่ยม) เขียนฟังก์ชันเรียกซ้ำเพื่อตรวจสอบว่าวงเล็บถูกต้องหรือไม่ในกรณีนี้ ตัวอย่างของตำแหน่งที่ไม่ถูกต้อง: ([) ] 4. จำนวนโครงสร้างวงเล็บที่ถูกต้องของความยาว 6 คือ 5: ()()(), (())(), ()(()), ((())), (()()) ข้อบ่งชี้: โครงสร้างวงเล็บที่ถูกต้องของความยาวขั้นต่ำ "()" โครงสร้างที่มีความยาวมากกว่านั้นได้มาจากโครงสร้างที่มีความยาวน้อยกว่า ในสองวิธี: (ก) ถ้าโครงสร้างที่เล็กกว่านั้นอยู่ในวงเล็บ 5. สร้างขั้นตอนที่พิมพ์พีชคณิตที่เป็นไปได้ทั้งหมดสำหรับจำนวนเต็มตั้งแต่ 1 ถึง N 6. สร้างขั้นตอนที่พิมพ์ชุดย่อยทั้งหมดของชุด (1, 2, ..., N) 7. สร้างขั้นตอนที่พิมพ์การแทนค่าที่เป็นไปได้ทั้งหมดของจำนวนธรรมชาติ N เป็นผลรวมของจำนวนธรรมชาติอื่นๆ 8. สร้างฟังก์ชันที่คำนวณผลรวมขององค์ประกอบอาร์เรย์ตามอัลกอริธึมต่อไปนี้: อาร์เรย์ถูกแบ่งครึ่ง ผลรวมขององค์ประกอบในแต่ละครึ่งจะถูกคำนวณและเพิ่ม ผลรวมขององค์ประกอบในอาร์เรย์ครึ่งหนึ่งคำนวณโดยใช้อัลกอริธึมเดียวกัน นั่นคือหารครึ่งอีกครั้ง การดิวิชั่นจะเกิดขึ้นจนกว่าชิ้นส่วนอาเรย์ที่เป็นผลลัพธ์จะมีองค์ประกอบอย่างละหนึ่งองค์ประกอบ และการคำนวณผลรวมจึงกลายเป็นเรื่องเล็กน้อย ความคิดเห็น: อัลกอริธึมนี้เป็นทางเลือกแทน ในกรณีของอาร์เรย์มูลค่าจริง มักจะช่วยให้คุณได้รับข้อผิดพลาดในการปัดเศษที่น้อยลง 10. สร้างขั้นตอนที่วาดเส้นโค้ง Koch (รูปที่ 12) 11. ทำซ้ำมะเดื่อ 16. ในรูป ในการวนซ้ำแต่ละครั้ง วงกลมจะเล็กกว่า 2.5 เท่า (ค่าสัมประสิทธิ์นี้สามารถสร้างเป็นพารามิเตอร์ได้) 1. ด. คนุต. ศิลปะการเขียนโปรแกรมคอมพิวเตอร์ v. 1. (ส่วนที่ 2.3. "ต้นไม้") การนำเสนอในหัวข้อ "อัลกอริทึมแบบเรียกซ้ำ" ถูกสร้างขึ้นเพื่อเตรียมนักเรียนสำหรับการสอบด้านวิทยาการคอมพิวเตอร์และไอซีที กระดาษพิจารณาคำจำกัดความของการเรียกซ้ำ โดยให้ตัวอย่างของวัตถุกราฟิกที่กำหนดแบบเรียกซ้ำ การนำเสนอประกอบด้วยวิธีแก้ไขงานหมายเลข 11 จากร่างเวอร์ชันสาธิตของ Unified State Examination - 2015 ในสาขาวิทยาการคอมพิวเตอร์ วิธีแรกเกี่ยวข้องกับการสร้างแผนผังการโทร วิธีที่สองแก้ปัญหาโดยใช้วิธีการทดแทน พิจารณา 4 ตัวอย่างการแก้ปัญหาโดยใช้ทั้งสองวิธี นอกจากนี้ การนำเสนอยังมี 25 งานสำหรับการฝึกอบรมพร้อมคำตอบจากไซต์ของ Konstantin Polyakov หากต้องการใช้ตัวอย่างการนำเสนอ ให้สร้างบัญชีสำหรับตัวคุณเอง ( บัญชีผู้ใช้) Google และลงชื่อเข้าใช้: https://accounts.google.com งานหมายเลข 11 USE (ระดับพื้นฐาน เวลา - 5 นาที) อัลกอริธึมแบบเรียกซ้ำ ผู้เขียน - Korotun O.V. อาจารย์วิทยาการคอมพิวเตอร์ MOU "มัธยมศึกษาปีที่ 71" สิ่งที่คุณต้องรู้: การเรียกซ้ำ - ในคำจำกัดความ คำอธิบาย ภาพของวัตถุหรือกระบวนการภายในวัตถุหรือกระบวนการนี้เอง นั่นคือสถานการณ์เมื่อวัตถุเป็นส่วนหนึ่งของตัวมันเอง ตราแผ่นดิน สหพันธรัฐรัสเซียเป็นวัตถุกราฟิกที่มีการกำหนดแบบเรียกซ้ำ: ในอุ้งเท้าขวาของนกอินทรีสองหัวที่แสดงอยู่บนนั้น คทาถูกยึดไว้ ซึ่งสวมมงกุฎด้วยสำเนาที่ลดลงของเสื้อคลุมแขน เนื่องจากบนแขนเสื้อนี้ยังมีคทาอยู่ที่อุ้งเท้าขวาของนกอินทรีจึงได้รับการเรียกซ้ำอย่างไม่สิ้นสุด แขนเสื้อแบบเรียกซ้ำของรัสเซีย ในการเขียนโปรแกรม การเรียกซ้ำคือการเรียกฟังก์ชันจากตัวเองโดยตรงหรือผ่านฟังก์ชันอื่นๆ เช่น ฟังก์ชัน A การเรียกใช้ฟังก์ชัน B และการเรียกใช้ฟังก์ชัน B การเรียกใช้ฟังก์ชัน A จำนวนฟังก์ชันที่ซ้อนกันหรือการเรียกโพรซีเดอร์เรียกว่าความลึกของการเรียกซ้ำ ตัวอย่างการเรียกซ้ำ: หากคุณมีคราบไขมันบนชุดของคุณ ไม่ต้องกังวล คราบน้ำมันจะถูกลบออกด้วยน้ำมันเบนซิน คราบน้ำมันเบนซินจะถูกลบออกด้วยสารละลายด่าง Alkali จะถูกลบออกด้วย Essence ถูร่องรอยของ Essence ด้วยน้ำมัน คุณรู้วิธีขจัดคราบน้ำมันแล้ว! ตัวอย่างงาน: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ifn ตัวอย่างงาน: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n) ; ifn ตัวอย่างงาน: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ถ้า n สไลด์ 9 ตัวอย่างงาน: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ถ้า n สไลด์ 10 ตัวอย่างงาน: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ถ้า n สไลด์ 11 15 ตัวอย่าง #2: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ifn ตัวอย่าง #2: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln(n); ถ้า n สไลด์ 13 ตัวอย่าง #3: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*") ; ถ้า n > 0 ให้เริ่ม F(n-2); F(n div 2) end end ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก 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: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-2); F(n div 2) end end ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? * การนับจำนวน "ดอกจัน" เราจะได้ 21 ในตัวอย่างนี้ ไม่ใช่ค่าของพารามิเตอร์ n ที่แสดงบนหน้าจอ แต่เป็นสัญลักษณ์ * * * * * * * * * * * * * * * * * * * * * * ตัวอย่าง #3: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-2); F(n div 2) end end ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก 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: จำนวนเต็ม); เริ่มถ้า n ตัวอย่าง #4: ขั้นตอน F(n: จำนวนเต็ม); เริ่มถ้า n งานสำหรับการฝึกอบรม ภารกิจที่ 1: ให้อัลกอริทึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-2); F(ndiv 2); F(ndiv 2); ปลาย ปลาย ; เมื่อเรียก F(5) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเท่าใด คำตอบ: 34 งาน 2: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-2); ฉ(n-2); F(ndiv 2); ปลาย ปลาย ; เมื่อเรียก F(6) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอกี่อัน? คำตอบ: 58 งาน 3: ให้อัลกอริทึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-3); F(ndiv 2); ปลาย ปลาย ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? คำตอบ: 15 ภารกิจที่ 4: ให้อัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-3); ฉ(n-2); F(ndiv 2); ปลาย ปลาย ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? คำตอบ: 55 ปัญหาที่ 5: ให้อัลกอริทึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม F(n-3); ฉ(n-2); F(ndiv 2); F(ndiv 2); ปลาย ปลาย ; เมื่อเรียก F(6) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอกี่อัน? คำตอบ: 97 ปัญหาที่ 6: ให้อัลกอริทึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม writeln("*"); ฉ(n-2); F(ndiv 2); ปลาย ปลาย ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? คำตอบ: 31 ปัญหาที่ 7: ให้อัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม writeln("*"); ฉ(n-2); F(ndiv 2); F(ndiv 2); ปลายปลาย; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? คำตอบ: 81 ปัญหาที่ 8: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่ม writeln("*"); ถ้า n > 0 ให้เริ่ม writeln("*"); ฉ(n-2); ฉ(n-2); F(ndiv 2); ปลายปลาย; เมื่อเรียก F(6) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอกี่อัน? คำตอบ: 77 ปัญหาที่ 9: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่มต้นถ้า n > 0 แล้วเริ่ม F(n-2); ฉ(n-1); ฉ(n-1); จบ; writeln("*"); จบ ; เมื่อเรียก F(5) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเท่าใด คำตอบ: 148 ปัญหาที่ 10: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่มต้นถ้า n > 0 แล้วเริ่ม writeln("*"); ฉ(n-2); ฉ(n-1); ฉ(n-1); จบ; writeln("*"); จบ; เมื่อเรียก F(5) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเท่าใด คำตอบ: 197 ปัญหาที่ 11: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่มต้นถ้า n > 1 แล้วเริ่ม F(n-2); ฉ(n-1); F(ndiv 2); จบ; writeln("*"); จบ ; จะพิมพ์เครื่องหมายดอกจันบนหน้าจอเมื่อเรียก F (7) กี่อัน? คำตอบ: 88 ปัญหาที่ 12: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F(n: จำนวนเต็ม); เริ่มต้นถ้า n > 2 แล้วเริ่ม writeln("*"); ฉ(n-2); ฉ(n-1); F(ndiv 2); จบ ; writeln("*"); จบ; เมื่อเรียก F(6) จะพิมพ์เครื่องหมายดอกจันบนหน้าจอกี่อัน? คำตอบ: 33 ปัญหาที่ 13: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 14: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 15: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 16: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 17: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 18: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 19: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 20: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 21: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 22: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหา 23: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 24: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn ปัญหาที่ 25: กำหนดอัลกอริธึมแบบเรียกซ้ำ: ขั้นตอน F (n: จำนวนเต็ม); เริ่ม writeln(n); ifn
สวัสดี N2
…
สวัสดี N 10
…
สวัสดี N1
…
สวัสดี N 10
สวัสดี N 10
…
สวัสดี N14. ความสัมพันธ์ที่เกิดซ้ำ การเรียกซ้ำและการวนซ้ำ
5. ต้นไม้
5.1. คำจำกัดความพื้นฐาน วิธีการพรรณนาต้นไม้
ก) มีโหนดพิเศษหนึ่งโหนดที่เรียกว่ารูทของต้นไม้นี้
b) โหนดที่เหลือ (ไม่รวมรูท) มีอยู่ในชุดย่อยที่ไม่ปะติดปะต่อแบบคู่ ซึ่งแต่ละโหนดจะเป็นทรี ต้นไม้เรียกว่า ทรีย่อยของต้นไม้ต้นนี้
5.2. ผ่านต้นไม้
5.3. การแสดงต้นไม้ในหน่วยความจำคอมพิวเตอร์
6. ตัวอย่างอัลกอริธึมแบบเรียกซ้ำ
6.1. ภาพวาดต้นไม้
6.2. หอคอยแห่งฮานอย
ในกระบวนการนี้ จะต้องไม่วางดิสก์ที่ใหญ่กว่าบนดิสก์ที่เล็กกว่า พระภิกษุมีความยากลำบาก ควรเลื่อนลำดับอย่างไร? จำเป็นต้องจัดเตรียมซอฟต์แวร์สำหรับการคำนวณลำดับนี้
2) เราเปลี่ยน นดิสก์ไปยังพินว่างที่เหลืออยู่
3) ย้ายกอง น-1 แผ่นที่ได้รับในวรรค (1) มากกว่า น th ดิสก์6.3. การแยกวิเคราะห์นิพจน์เลขคณิต
7.3. การกำหนดโหนดต้นไม้ด้วยจำนวน
คำถามทดสอบ
งาน
(b) ภายในคู่ของช่องเปิด - วงเล็บปิดที่สอดคล้องกัน วงเล็บถูกวางอย่างถูกต้อง
เขียนโปรแกรมแบบเรียกซ้ำเพื่อสร้างโครงสร้างวงเล็บที่ถูกต้องทั้งหมดที่มีความยาว2 น.
(b) ถ้าสองโครงสร้างที่เล็กกว่าถูกเขียนตามลำดับ
วรรณกรรม
2. น. เวิร์ธ. อัลกอริทึมและโครงสร้างข้อมูลดาวน์โหลด:
ดูตัวอย่าง:
คำบรรยายสไลด์:
