Broken Ways (ปัญหาลอจิก)

ปัญหานี้เผยแพร่บนเว็บไซต์โรงเรียนนิวตัน “คำถามประจำวันที่ 9/ม.ค./2023”

คำชี้แจงปัญหา:

นิวตันต้องการขึ้นไปถึงยอดบันไดที่มีขั้นบันไดหัก (เขาไม่สามารถขึ้นไปถึงขั้นบันไดเหล่านั้นได้) เขาสามารถปีนขึ้นไปได้ครั้งละ 1 หรือ 2 ขั้น

ตัวอย่างบันได 15 ขั้น ขั้นที่ 3 และ 9 หัก ขั้นตอนที่ถูกต้องในการเข้าชมคือ: 1,2, 4,5,6,7,8, 10,11,12,13,14,15

วิธีหนึ่งที่เป็นไปได้ในการขึ้นสู่จุดสูงสุดของบันไดนี้คือไปที่ขั้นบันได: 2,4,5,7,8,10,12,14,15 (บางครั้งนิวตันก็ขึ้น 1 ขั้น และบางขั้นก็ขึ้น 2 ขั้น)

เป้าหมายของโจทย์คือการหาจำนวนวิธีต่างๆ ที่นิวตันสามารถขึ้นไปถึงยอดบันไดได้

ที่นี่ฉันแสดงวิธีแก้ปัญหาหนึ่งข้อ:

ปัญหานี้จำ "ลำดับฟีโบนัชชี" แต่ทำไม? เพราะเนื่องจากคุณสามารถไปถึงขั้นที่ 1 หรือขั้นที่ 2 ได้เท่านั้น จำนวนวิธีที่คุณไปถึงขั้นหนึ่งจึงเป็นผลรวมของ "วิธีที่คุณไปถึงขั้นที่ 1" + "วิธีที่คุณไปถึงขั้นที่ 2 ได้" ".

ดังนั้น ในการไปถึงขั้นที่ 1 คุณมีเพียง1 ทาง เท่านั้น (ปีนขึ้นจากพื้นดินไปยังขั้นที่ 1) เพื่อไปยังขั้นที่ 2 คุณมี2 วิธี (ปีนจากพื้นดินไปยังขั้นที่ 2 โดยตรงหรือปีนจากขั้นที่ 1) เพื่อไปยังขั้นที่ 3 คุณมี3 วิธี (1 ทางจากขั้นที่ 1 + 2 ทางจากขั้นที่ 2) เพื่อไปยังขั้นที่ 4 คุณ มี5 วิธี (2 วิธีจากขั้นตอนที่ 2 + 3 วิธีจากขั้นตอนที่ 3) เพื่อไปยังขั้นตอนที่ 5 คุณมี8 วิธี (3 วิธีจากขั้นตอนที่ 3 + 5 วิธีจากขั้นตอนที่ 4) ไปเรื่อยๆ จนถึงขั้นตอนสุดท้าย

แต่นี่คือ Fibonacci Sequence! ใช่ แต่ปัญหานี้มีจุดหักเห มีการเพิ่ม"ขั้นตอนที่ไม่ถูกต้อง" โอเค ไม่มีปัญหา เนื่องจากนิวตันไม่สามารถไปที่ขั้นตอนที่เสียหายได้ เพียงแค่ตั้งค่า 0 วิธีในการไปถึงขั้นตอนเหล่านั้น

กลับมาที่ตัวอย่างของเรา เมื่อหักขั้นตอนที่ 3 และ 9 เรามี"ลำดับฟีโบนักชีหัก" : 1, 2, 0, 2, 2, 4, 6, 10, 0, 10, 10, 20, 30, 50, 80.

ที่บันไดนี้ นิวตันมี 80 วิธีในการปีนขึ้นไป

ตอนนี้ คุณสามารถใช้ Fibonacci Broken Sequence Algorithm ในภาษาการเขียนโปรแกรมที่คุณชื่นชอบ และอัปโหลดไปยัง เว็บไซต์ Newton Schoolซึ่งมีปัญหาเจ๋งๆ มากมายให้แก้ไขในเซสชันคำถามประจำวัน

ขอให้มีความสุข!