ตัวเลขฟีโบนักชีในภาษาไพทอน

ตัวเลขฟีโบนักชีเป็นลำดับเฉพาะโดยที่ค่าแรกถูกประกาศล่วงหน้าเป็น 0 และค่าที่สองมีการประกาศล่วงหน้าเป็น 1 ตัวเลขที่เหลือสร้างจากสองตัวนี้โดยการเพิ่มตัวเลขสองตัวก่อนหน้า ตัวเลขฟีโบนักชีทั้งหมดเป็นจำนวนเต็มบวก โดยเริ่มจาก 0 ตัวเลขฟีโบนักชีสิบสองตัวแรกและวิธีการหามามีดังนี้

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

หากไม่มีนิพจน์ผลรวม ตัวเลขฟีโบนักชีเหล่านี้สามารถใส่ในตารางได้ดังนี้:

แถวแรกมีตัวเลขฟีโบนักชี แถวที่สองมีดัชนีแบบอิงศูนย์ สมมติว่าตัวเลขฟีโบนักชีอยู่ในอาร์เรย์

ตัวเลขฟีโบนักชีสามารถสร้างได้ในเวลา O(n) และในเวลา O(1) ในนิพจน์ความซับซ้อนของเวลาเหล่านี้ n หมายถึง n การดำเนินการหลัก และ 1 หมายถึง 1 การดำเนินการหลัก ด้วย O(n) ตัวเลขฟีโบนักชี n จะถูกสร้าง โดยเริ่มจาก 0 ด้วย O(1) ตัวเลขฟีโบนักชีหนึ่งหมายเลขจะถูกสร้างขึ้นจากดัชนีที่เกี่ยวข้อง นั่นคือเหตุผลที่ต้องใช้การดำเนินการหลักเพียงครั้งเดียวแทนการดำเนินการหลัก n รายการ

บทความนี้มีจุดมุ่งหมายเพื่ออธิบายวิธีสร้างตัวเลขฟีโบนักชีไม่ว่าจะด้วยวิธีใดโดยใช้ Python

สูตรสำหรับเลขฟีโบนักชี

คำจำกัดความอย่างเป็นทางการของตัวเลขฟีโบนักชีคือ:

ที่ไหน F _น คือตัวเลขฟีโบนักชีที่ดัชนี n

การสร้างตัวเลขฟีโบนักชีใน O(n) Time

ถ้า n เป็น 1 จะมีเพียง 0 เท่านั้นที่จะถูกพิมพ์เป็นเลขฟีโบนักชี ถ้า n คือ 2 ดังนั้น 0 และ 1 จะถูกพิมพ์เป็นตัวเลขฟีโบนักชีในลำดับนั้น ถ้า n คือ 3 ดังนั้น 0, 1 และ 1 จะถูกพิมพ์เป็นตัวเลขฟีโบนักชีในลำดับนั้น ถ้า n คือ 4 ดังนั้น 0, 1, 1 และ 2 จะถูกพิมพ์เป็นตัวเลขฟีโบนักชีในลำดับนั้น ถ้า n คือ 5 ดังนั้น 0, 1, 1, 2 และ 3 จะถูกพิมพ์เป็นตัวเลขฟีโบนักชี ตามลำดับนั้น ถ้า n คือ 6 ดังนั้น 0, 1, 1, 2, 3 และ 5 จะถูกพิมพ์เป็นตัวเลขฟีโบนักชี ตามลำดับ – และอื่นๆ

ฟังก์ชัน Python เพื่อสร้างตัวเลข n Fibonacci ตัวแรกคือ:

มันเริ่มต้นด้วยการสร้างอาร์เรย์ขององค์ประกอบ n ทั้งหมดเริ่มต้นเป็นศูนย์ อาร์เรย์นี้จะเก็บตัวเลขฟีโบนักชี เลขฟีโบนักชีแรก 0, มีอยู่แล้ว หมายเลขฟีโบนักชีที่สองคือ 1 ถูกกำหนดโดยคำสั่งถัดไป (ในฟังก์ชัน) จากนั้นมี for-loop ซึ่งเริ่มต้นจากดัชนี 2 ถึงก่อน n มีข้อความว่า

สิ่งนี้จะเพิ่มตัวเลขสองตัวก่อนหน้าในทันที

รหัสเพื่อเรียกใช้ฟังก์ชันและพิมพ์ตัวเลขฟีโบนักชีสิบสองตัวแรกสามารถ:

ยังไม่มีข้อความ = 12
A = ฟีโบนักชี(N)
สำหรับฉันอยู่ในช่วง (N):
พิมพ์ (A[i], end='')
พิมพ์()

ผลลัพธ์คือ:

การสร้างเลขฟีโบนักชีหนึ่งหมายเลขในเวลาคงที่

มีสูตรทางคณิตศาสตร์ที่เกี่ยวข้องกับดัชนีฐานศูนย์กับจำนวนฟีโบนักชีที่สอดคล้องกัน สูตรคือ:

สังเกตว่าทางด้านขวามือของสมการ ไม่ใช่รากที่สองของ 5 ที่ยกกำลัง n เป็นนิพจน์ในวงเล็บที่ยกกำลัง n มีสองนิพจน์ดังกล่าว

ถ้า n เป็น 0, Fibn จะเป็น 0 ถ้า n เป็น 1, Fib _น จะเป็น 1 ถ้า n เป็น 2, Fib _น จะเป็น 1 ถ้า n เป็น 3, Fib _น จะเป็น 2. ถ้า n เป็น 4, Fib _น จะเป็น 3 – และอื่นๆ ผู้อ่านสามารถตรวจสอบสูตรนี้ทางคณิตศาสตร์ได้โดยการแทนที่ค่าต่างๆ ของ n และการประเมิน n คือดัชนีแบบอิงศูนย์ในสูตรนี้

รหัส Python สำหรับสูตรนี้คือ:

นำเข้าคณิตศาสตร์

โมดูลคณิตศาสตร์ถูกนำเข้า มันมีฟังก์ชันสแควร์รูท โอเปอเรเตอร์ ** ใช้สำหรับจ่ายไฟ ฟังก์ชัน fibNo() ใช้สูตรโดยตรง การโทรและการพิมพ์ที่เหมาะสมสำหรับฟังก์ชัน fibNo() คือ:

ยังไม่มีข้อความ = 11
ขวา = fibNo(N)
พิมพ์ (ย้อนหลัง)

ผลลัพธ์คือ:

เป็นไปได้ที่จะลบตัวเลขทศนิยมที่ไม่จำเป็นออกจากคำตอบ อย่างไรก็ตาม นั่นคือการสนทนาในบางครั้ง

หากต้องใช้หมายเลข Fibonacci ที่แตกต่างกันสำหรับดัชนี n ที่แตกต่างกัน ฟังก์ชัน fibNo() จะต้องถูกเรียกหนึ่งครั้งสำหรับแต่ละดัชนี n เพื่อส่งคืนตัวเลข Fibonacci ที่ต่างกัน โปรแกรมต่อไปนี้ทำสิ่งนี้สำหรับดัชนีแบบศูนย์ 7 ถึง 9 (รวม) :

นำเข้าคณิตศาสตร์

ผลลัพธ์คือ:

สังเกตวิธีการเข้ารหัส for-loop ใน Python ดัชนีแรกคือ 7 ดัชนีถัดไปคือ 8 และดัชนีสุดท้ายคือ 9. 10 ในช่วงอาร์กิวเมนต์คือ 9 + 1 ค่าในตำแหน่ง 10 ต้องเป็นดัชนีฐานศูนย์สุดท้ายบวก 1 อันดับแรก อาร์กิวเมนต์ 7 เป็นดัชนีเริ่มต้นที่เป็นศูนย์

บทสรุป

ตัวเลขฟีโบนักชีเป็นลำดับเฉพาะของจำนวนเต็ม (จำนวนเต็มบวก) เริ่มต้นด้วย 0 ตามด้วย 1 โดยไม่มีเงื่อนไข ตัวเลขที่เหลือได้รับการพัฒนาจากที่นั่นโดยการเพิ่มตัวเลขสองตัวก่อนหน้าทันที

ในการรับตัวเลข n ฟีโบนักชี n แรก ให้ยอมรับ 0 และ 1 เป็นสองตัวแรก จากนั้นสำหรับส่วนที่เหลือ ให้ใช้ for-loop พร้อมคำสั่งเช่น:

ซึ่งบวกตัวเลขสองตัวก่อนหน้าในทันที

ในการรับเลขฟีโบนักชีเพียงตัวเดียวจากดัชนี n ที่เป็นศูนย์ ให้ใช้สูตร: