ความหมายของตัวเลขฟีโบนักชี
ตัวเลขฟีโบนักชีเป็นลำดับเฉพาะของจำนวนเต็มบวก โดยเริ่มจาก 0 ตัวเลขทั้งหมดเป็นจำนวนเต็มบวก ดังนั้น หมายเลขฟีโบนักชีคือลำดับเฉพาะของจำนวนเต็มหรือจำนวนธรรมชาติ โดยเริ่มจาก 0 ในลำดับนี้ ตัวเลขสองตัวแรกคือ 0 และ 1 ตามลำดับนั้น ตัวเลขที่เหลือได้รับการพัฒนาจากที่นั่นโดยการเพิ่มตัวเลขสองตัวก่อนหน้า ได้ตัวเลขฟีโบนักชีสิบสองตัวแรกดังนี้:
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
กล่าวอีกนัยหนึ่ง ตัวเลขฟีโบนักชีสิบสองตัวแรกคือ:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
แน่นอน ตัวเลขที่สิบสามจะเป็น: 144 = 55 + 89 ตัวเลขฟีโบนักชีอาจถูกจินตนาการว่าอยู่ในอาร์เรย์ เช่น:
0 | 1 | 1 | สอง | 3 | 5 | 8 | 13 | ยี่สิบเอ็ด | 3. 4 | 55 | 89 |
อาร์เรย์มีดัชนี ในตารางต่อไปนี้ แถวที่สองแสดงดัชนีฐานศูนย์ที่สอดคล้องกันสำหรับตัวเลขฟีโบนักชีในอาร์เรย์:
0 | 1 | 1 | สอง | 3 | 5 | 8 | 13 | ยี่สิบเอ็ด | 3. 4 | 55 | 89 |
0 | 1 | สอง | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด |
ด้วยดัชนีแบบอิงศูนย์ หากมีองค์ประกอบสิบสององค์ประกอบ ดัชนีสุดท้ายคือ 11
ตัวเลขฟีโบนักชีสามารถสร้างได้ในเวลา O(n) หรือเวลา O(1) ในนิพจน์ความซับซ้อนของเวลาเหล่านี้ n หมายถึง n การดำเนินการหลัก และ 1 หมายถึง 1 การดำเนินการหลัก ด้วย O(n) ตัวเลขฟีโบนักชี n จะถูกสร้าง โดยเริ่มจาก 0 ด้วย O(1) ตัวเลขฟีโบนักชีหนึ่งหมายเลขจะถูกสร้างจากดัชนีที่เกี่ยวข้อง นั่นคือเหตุผลที่ O(1) ใช้การดำเนินการหลักเพียงครั้งเดียวแทนการดำเนินการหลัก n รายการ
บทความนี้มีจุดมุ่งหมายเพื่ออธิบายวิธีสร้างตัวเลขฟีโบนักชีไม่ว่าจะด้วยวิธีใด โดยใช้ JavaScript ซึ่งจริงๆ แล้วเป็น ECMAScript ในปัจจุบัน
สภาพแวดล้อมการเข้ารหัส
สภาพแวดล้อม node.js จะไม่ถูกใช้ตามที่ผู้อ่านคาดไว้ เบราว์เซอร์จะใช้ในการตีความโค้ดและแสดงผลแทน สคริปต์ (โค้ด) ควรเขียนในไฟล์แก้ไขข้อความ ซึ่งควรบันทึกด้วยนามสกุล '.html' สคริปต์ควรมีรหัสขั้นต่ำ:
DOCTYPE HTML >< html >
< ศีรษะ >
< ชื่อ > ตัวเลขฟีโบนักชีด้วย JavaScript ชื่อ >
ศีรษะ >
< ร่างกาย >
< ประเภทสคริปต์ = 'ข้อความ/ecmascript' >
สคริปต์ >
ร่างกาย >
html >
นี่คือรหัสขั้นต่ำโดยประมาณที่หน้าเว็บต้องการ การเข้ารหัสทั้งหมดสำหรับบทความนี้อยู่ระหว่างแท็ก
หากต้องการเรียกใช้โค้ดที่เขียน (เพิ่มเติม) เพียงดับเบิลคลิกที่ไอคอนของชื่อไฟล์ แล้วเบราว์เซอร์ของคอมพิวเตอร์จะเปิดขึ้น
คำจำกัดความของตัวเลขฟีโบนักชี
มีคำจำกัดความทางคณิตศาสตร์สำหรับตัวเลขฟีโบนักชี กำหนดไว้ดังนี้
โดยที่ Fn คือหมายเลขฟีโบนักชีที่สอดคล้องกับดัชนีฐานศูนย์ n
ตัวเลขสองตัวแรก: 0 และ 1 ถูกประกาศไว้ล่วงหน้าในลำดับนั้น บรรทัดสุดท้ายของฟังก์ชันนี้แสดงให้เห็นว่าตัวเลขที่เหลือมาจากตัวเลขสองตัวแรกในลำดับอย่างไร
คำจำกัดความนี้เป็นหนึ่งในสูตรสำหรับเลขฟีโบนักชี
การสร้างตัวเลขฟีโบนักชีใน 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 จะแสดงเป็นตัวเลขฟีโบนักชี ตามลำดับ – และอื่นๆ
ฟังก์ชัน ECMAscript เพื่อสร้างจำนวนเต็ม n ฟีโบนักชี (ตัวเลข) แรกคือ:
< ประเภทสคริปต์ = 'ข้อความ/ecmascript' >การทำงาน ฟีโบนักชี ( อา ) {
น = ก. ความยาว ;
ถ้า ( น > 0 )
อา [ 0 ] = 0 ;
ถ้า ( น > 1 )
อา [ 1 ] = 1 ;
สำหรับ ( ผม = สอง ; ผม < น ; ผม ++ ) { //n=0 และ n=2 ได้รับการพิจารณาแล้ว
ปัจจุบันไม่มี = อา [ ผม - 1 ] + อา [ ผม - สอง ] ;
อา [ ผม ] = ปัจจุบันไม่มี ;
}
}
ไม่ได้แสดงแท็กสคริปต์ปิด ฟังก์ชันได้รับอาร์เรย์ ตัวเลขฟีโบนักชีสองตัวแรกถูกกำหนดไว้ที่ตำแหน่ง for-loop วนซ้ำจากดัชนีแบบ zero-based 2 ถึงต่ำกว่า n คำสั่งที่สำคัญที่สุดใน for-loop คือ:
currNo = A[i – 1] + A[i – 2];
สิ่งนี้จะเพิ่มตัวเลขสองตัวก่อนหน้าในอาร์เรย์เพื่อให้มีตัวเลขปัจจุบัน เมื่อฟังก์ชัน fibonacci() ทำงานเสร็จสิ้น องค์ประกอบทั้งหมดของอาร์เรย์จะเป็นตัวเลข n Fibonacci ตัวแรก รหัสที่เหมาะสมในการเรียกใช้ฟังก์ชัน fibonacci() และแสดงตัวเลขฟีโบนักชีคือ:
นู๋ = 12 ;arr = ใหม่ Array ( นู๋ ) ;
ฟีโบนักชี ( arr ) ;
สำหรับ ( ผม = 0 ; ผม < นู๋ ; ผม ++ )
เอกสาร. เขียน ( arr [ ผม ] + ' ' ) ;
เอกสาร. เขียน ( '
' ) ;
สคริปต์ >
รหัสนี้แสดงแท็กสคริปต์ปิด รหัสถูกพิมพ์ด้านล่างรหัสด้านบน ผลลัพธ์ที่แสดงบนหน้าเว็บคือ:
0 1 1 2 3 5 8 13 21 34 55 89
อย่างที่คาดไว้.
การผลิตเลขฟีโบนักชีหนึ่งหมายเลขใน O(1) Time
O(1) คือเวลาคงที่ หมายถึงการดำเนินการหลักอย่างหนึ่ง สูตรทางคณิตศาสตร์อีกสูตรหนึ่งในการสร้างตัวเลขฟีโบนักชีคือ:
สังเกตว่าทางด้านขวามือของสมการ ไม่ใช่รากที่สองของ 5 ที่ยกกำลัง n เป็นนิพจน์ในวงเล็บที่ยกกำลัง n มีสองนิพจน์ดังกล่าว
ถ้า n คือ 0, Fibn จะเป็น 0 ถ้า n คือ 1, Fibn จะเป็น 1 ถ้า n คือ 2, Fibn จะเป็น 1 ถ้า n คือ 3, Fibn จะเป็น 2 ถ้า n คือ 4, Fibn จะเป็น 3 – และอื่นๆ ผู้อ่านสามารถตรวจสอบสูตรนี้ทางคณิตศาสตร์ได้โดยการแทนที่ค่าต่างๆ ของ n และการประเมิน n คือดัชนีแบบอิงศูนย์ในสูตรนี้ ผลลัพธ์คือหมายเลขฟีโบนักชีที่สอดคล้องกัน
รหัส ECMAScript (JavaScript) สำหรับสูตรนี้คือ:
< ประเภทสคริปต์ = 'ข้อความ/ecmascript' >การทำงาน fibNo ( น ) {
FibN = ( คณิตศาสตร์ . pow ( ( 1 + คณิตศาสตร์ . sqrt ( 5 ) ) / สอง , น ) - คณิตศาสตร์ . pow ( ( 1 - คณิตศาสตร์ . sqrt ( 5 ) ) / สอง , น ) ) / คณิตศาสตร์ . sqrt ( 5 ) ;
กลับ FibN ;
}
ไม่ได้แสดงแท็กสคริปต์ปิด สังเกตว่าฟังก์ชันที่กำหนดไว้ล่วงหน้ากำลัง (pow) และรากที่สอง (sqrt) ได้ถูกนำมาใช้อย่างไร ใน ECMAScript (JavaScript) ไม่จำเป็นต้องนำเข้าโมดูลคณิตศาสตร์ ฟังก์ชัน fibNo() ใช้สูตรโดยตรง การโทรและการแสดงผลที่เหมาะสมสำหรับฟังก์ชัน fibNo() บนหน้าเว็บคือ:
นู๋ = สิบเอ็ด ;ขวา = fibNo ( นู๋ ) ;
เอกสาร. เขียน ( ขวา ) ;
สคริปต์ >
รหัสแสดงแท็กสคริปต์ปิด ผลลัพธ์คือ:
89.00000000000003
เป็นไปได้ที่จะลบตัวเลขทศนิยมที่ไม่จำเป็นออกจากคำตอบ อย่างไรก็ตาม นั่นคือการสนทนาในบางครั้ง
หากต้องการหมายเลขฟีโบนักชีมากกว่าหนึ่งหมายเลข โค้ดจะต้องเรียกสูตรนี้หนึ่งครั้งสำหรับดัชนี n ที่สอดคล้องกันตามศูนย์แต่ละตัว
บทสรุป
ตัวเลขฟีโบนักชีเป็นลำดับเฉพาะของจำนวนเต็มบวก โดยเริ่มจาก 0 ตัวเลขทั้งหมดเป็นจำนวนเต็มบวก ดังนั้น หมายเลขฟีโบนักชีคือลำดับเฉพาะของจำนวนเต็มหรือจำนวนธรรมชาติ โดยเริ่มจาก 0 ในลำดับนี้ ตัวเลขสองตัวแรกคือ 0 และ 1 ตามลำดับนั้น ตัวเลขสองตัวแรกนี้ถูกกำหนดไว้เช่นนั้น ตัวเลขที่เหลือได้รับการพัฒนาจากที่นั่นโดยการเพิ่มตัวเลขสองตัวก่อนหน้าทันที
หลังจากสร้างตัวเลข Fibonacci สองตัวแรกแล้ว เพื่อสร้างตัวเลข Fibonacci ที่เหลือ เพื่อให้ได้ตัวเลขทั้งหมด n จำนวน ต้องใช้ for-loop กับข้อความต่อไปนี้
currNo = A[i – 1] + A[i – 2];
สิ่งนี้จะเพิ่มตัวเลขฟีโบนักชีสองตัวสุดท้ายในทันทีเพื่อให้มีหมายเลขฟีโบนักชีปัจจุบัน
เมื่อกำหนดดัชนีเป็นศูนย์ หากต้องการได้เลขฟีโบนักชีที่สอดคล้องกัน ให้ใช้สูตร: