อันที่จริง ตัวเลขฟีโบนักชีสองตัวแรกถูกกำหนดไว้ล่วงหน้าแล้ว หมายเลข Fibonacci แรกคือ 0 และหมายเลข Fibonacci ที่สองคือ 1 ด้วยการจัดทำดัชนีแบบอิงศูนย์และสมมติว่าตัวเลข Fibonacci อยู่ในอาร์เรย์ ดังนั้น:
ที่ดัชนี 0 , เลขฟีโบนักชีคือ 0 , ( ที่กำหนดไว้ล่วงหน้า ) ;ที่ดัชนี 1 , เลขฟีโบนักชีคือ 1 , ( ที่กำหนดไว้ล่วงหน้า ) ;
ที่ดัชนี สอง , เลขฟีโบนักชีคือ 1 = 1 + 0 , ( ตามคำนิยาม ) ;
ที่ดัชนี 3 , เลขฟีโบนักชีคือ สอง = 1 + 1 , ( ตามคำนิยาม ) ;
ที่ดัชนี 4 , เลขฟีโบนักชีคือ 3 = สอง + 1 , ( ตามคำนิยาม ) ;
ที่ดัชนี 5 , เลขฟีโบนักชีคือ 5 = 3 + สอง , ( ตามคำนิยาม ) ;
ที่ดัชนี 6 , เลขฟีโบนักชีคือ 8 = 5 + 3 , ( ตามคำนิยาม ) ;
ที่ดัชนี 7 , เลขฟีโบนักชีคือ 13 = 8 + 5 , ( ตามคำนิยาม ) ;
ที่ดัชนี 8 , เลขฟีโบนักชีคือ ยี่สิบเอ็ด = 13 + 8 , ( ตามคำนิยาม ) ;
ที่ดัชนี 9 , เลขฟีโบนักชีคือ 3. 4 = ยี่สิบเอ็ด + 13 , ( ตามคำนิยาม ) ;
และอื่นๆ
ในการเขียนโปรแกรม ตัวแปร n และไม่ใช่ i ใช้สำหรับดัชนีฐานศูนย์สำหรับตัวเลขฟีโบนักชีเหล่านี้ และด้วยเหตุนี้ ตัวเลขฟีโบนักชีสิบสองตัวแรกคือ:
| 0 | 1 | 1 | สอง | 3 | 5 | 8 | 13 | ยี่สิบเอ็ด | 3. 4 | 55 | 89 |
| 0 | 1 | สอง | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด |
แถวที่สองในตารางแสดงดัชนีแบบศูนย์ ซึ่งแต่ละแถวจะมีตัวแปร n ในการเขียนโปรแกรม แถวแรกให้ตัวเลขฟีโบนักชีที่สอดคล้องกัน ดังนั้น ตัวเลขฟีโบนักชีจึงไม่ใช่แค่ตัวเลขใดๆ คำจำกัดความหลักเริ่มต้นด้วย 0 สำหรับหมายเลข Fibonacci แรก และ 1 สำหรับหมายเลข Fibonacci ที่สอง ตัวเลขที่เหลือผลิตจากที่นั่น
ตัวเลขฟีโบนักชีสามารถสร้างได้ในเวลา O(n) และในเวลา O(1) สำหรับเวลา O(n) ตัวอย่างเช่น ถ้า n คือ 12 เลขฟีโบนักชีสิบสองตัวแรกจะถูกสร้าง สำหรับเวลา O(1) จะมีการสร้างเลขฟีโบนักชีเพียงตัวเดียว ตัวอย่างเช่น ถ้า n คือ 6 ก็จะเกิดเลขฟีโบนักชีหมายเลข 8
บทความนี้จะอธิบายสองวิธีในการสร้างตัวเลขฟีโบนักชีใน Java
สูตรสำหรับเลขฟีโบนักชี
มีสูตรทางคณิตศาสตร์สำหรับตัวเลขฟีโบนักชี สูตรนี้สามารถเขียนได้สามบรรทัดหรือหนึ่งบรรทัด ในสามบรรทัดเขียนว่า:
ที่ไหน F น คือเลขฟีโบนักชีที่ศูนย์ n ไทย ดัชนี. นี่คือวิธีการกำหนดหมายเลขฟีโบนักชี
การสร้างตัวเลขฟีโบนักชีใน O(n) Time
ถ้าจะให้สร้างตัวเลขฟีโบนักชีใน O(3) คูณ ตัวเลข 0, 1, 1 จะถูกผลิตออกมา นั่นคือตัวเลขฟีโบนักชีสามตัวแรก n . ที่เป็นศูนย์ตัวสุดท้าย ไทย ดัชนีที่นี่ คือ 2 ถ้าจะให้สร้างตัวเลขฟีโบนักชีใน O(7) คูณ จะสร้างตัวเลข 0, 1, 1, 2, 3, 5, 8 นั่นคือตัวเลขฟีโบนักชีเจ็ดตัวแรก n . ที่เป็นศูนย์ตัวสุดท้าย ไทย ดัชนีที่นี่ คือ 6 ถ้าจะให้สร้างตัวเลขฟีโบนักชีใน O(n) คูณ ตัวเลข 0, 1, 1, 2, 3, 5, 8 – – - จะถูกสร้างขึ้น นั่นคือตัวเลขฟีโบนักชี n ตัวแรก n . ที่เป็นศูนย์ตัวสุดท้าย ไทย ดัชนีที่นี่คือ n-1
วิธี Java ในคลาสเพื่อสร้างตัวเลข n ฟีโบนักชีแรกคือ:
ระดับ ฟีโบนักชี {โมฆะ ฟีโบนักชี ( int [ ] พี ) {
int น = ป. ความยาว ;
ถ้า ( น > 0 )
พี [ 0 ] = 0 ;
ถ้า ( น > 1 )
พี [ 1 ] = 1 ;
สำหรับ ( int ผม = สอง ; ผม < น ; ผม ++ ) { //n=0 และ n=2 ได้รับการพิจารณาแล้ว
int ปัจจุบันไม่มี = พี [ ผม - 1 ] + พี [ ผม - สอง ] ;
พี [ ผม ] = ปัจจุบันไม่มี ;
}
}
}
คลาส ฟีโบนักชีเป็นแบบส่วนตัว ดิ ฟีโบนักชี() วิธีรับอาร์เรย์ P และส่งคืนเป็นโมฆะ วิธีการเริ่มต้นด้วยการกำหนดความยาวของอาร์เรย์ ความยาวของ n คือจำนวนเลขฟีโบนักชีที่ต้องการ ตัวเลขฟีโบนักชีตัวแรกและตัวที่สองถูกกำหนดไว้อย่างชัดเจนและใส่ไว้ในตำแหน่งที่หนึ่งและที่สองในอาร์เรย์
ตัวเลขฟีโบนักชีที่เหลือเริ่มต้นจากตัวเลขที่สาม (ดัชนี n = 2) ถูกกำหนดใน for-loop และใส่ในตำแหน่งในอาร์เรย์ ดังนั้นฟังก์ชันจะต้องคืนค่าเป็นโมฆะ คำสั่งหลักใน for-loop จะเพิ่มตัวเลขสองตัวก่อนหน้า
ตัวแปรดัชนี i ถูกใช้แทน n เพื่อความชัดเจน
คลาส Java Main ที่เหมาะสม (ด้วยวิธีการหลักของ Java) คือ:
สาธารณะ ระดับ หลัก {สาธารณะ คงที่ โมฆะ หลัก ( สตริง args [ ] ) {
int ม = 12 ;
int [ ] arr = ใหม่ int [ ม ] ;
ฟีโบนักชี obj = ใหม่ ฟีโบนักชี ( ) ;
วัตถุ ฟีโบนักชี ( arr ) ;
สำหรับ ( int ผม = 0 ; ผม < ม ; ผม ++ )
ระบบ . ออก . พิมพ์ ( arr [ ผม ] + ' ' ) ;
ระบบ . ออก . println ( ) ;
}
}
หลังจากที่สร้างตัวเลขโดยวิธี fibonacci() แล้ว เมธอดหลักของ Java จะอ่านออกมา
การสร้างเลขฟีโบนักชีหนึ่งหมายเลขในเวลาคงที่
มีสูตรทางคณิตศาสตร์ที่สามารถใช้สร้างตัวเลขฟีโบนักชีได้ เมื่อกำหนดดัชนีฐานศูนย์ที่สอดคล้องกัน n สูตรคือ:
โดยที่ n คือดัชนีตามศูนย์และ Fib น คือเลขฟีโบนักชีที่สอดคล้องกัน สังเกตว่าทางด้านขวามือของสมการ ไม่ใช่รากที่สองของ 5 ที่ยกกำลัง n เป็นนิพจน์ในวงเล็บที่ยกกำลัง n มีสองนิพจน์ดังกล่าว
ถ้า n เป็น 0, Fib น จะเป็น 0 ถ้า n คือ 1 Fib น จะเป็น 1 ถ้า n เป็น 2, Fib น จะเป็น 1 ถ้า n เป็น 3, Fib น จะเป็น 2. ถ้า n เป็น 4, Fib น จะเป็น 3 – และอื่นๆ ผู้อ่านสามารถตรวจสอบสูตรนี้ทางคณิตศาสตร์ โดยการแทนที่ค่าที่แตกต่างกันสำหรับ n และการประเมิน
เมื่อเข้ารหัส สูตรนี้จะให้เลขฟีโบนักชีเพียงตัวเดียวสำหรับ n หากต้องการตัวเลขฟีโบนักชีมากกว่าหนึ่งหมายเลข ต้องเรียกรหัสสำหรับสูตรหนึ่งครั้งสำหรับแต่ละดัชนีที่เกี่ยวข้องกัน
ใน Java วิธีสร้างหมายเลขฟีโบนักชีเพียงหมายเลขเดียวคือ:
นำเข้า java.lang.* ;ระดับ ฟีบ {
สองเท่า fibNo ( int น ) {
สองเท่า FibN = ( คณิตศาสตร์ . pow ( ( 1 + คณิตศาสตร์ . sqrt ( 5 ) ) / สอง , น ) – คณิตศาสตร์ . pow ( ( 1 - คณิตศาสตร์ . sqrt ( 5 ) ) / สอง , น ) ) / คณิตศาสตร์ . sqrt ( 5 ) ;
กลับ FibN ;
}
}
ต้องนำเข้าแพ็คเกจ java.lang.* ที่จุดเริ่มต้นของโปรแกรม เนื่องจากแพ็คเกจมีคลาส Math ซึ่งมีเมธอด power (pow) และสแควร์รูท (sqrt) วิธี Java แบบกำหนดเองที่นี่ใช้สูตรคณิตศาสตร์โดยตรง
ความซับซ้อนของเวลาสำหรับฟังก์ชันนี้คือ O(1) ค่าคงที่ของการดำเนินการหลักเดียว คลาส Java Main ที่เหมาะสม โดยมีวิธีหลักของ Java สำหรับวิธีการข้างต้นคือ:
สาธารณะ ระดับ หลัก {สาธารณะ คงที่ โมฆะ หลัก ( สตริง args [ ] ) {
int นู๋ = สิบเอ็ด ;
Fib obj = ใหม่ ฟีบ ( ) ;
สองเท่า ขวา = วัตถุ fibNo ( นู๋ ) ;
ระบบ . ออก . println ( ขวา ) ;
}
}
ดัชนี n = 11 ถูกส่งและหมายเลขฟีโบนักชี 89 ถูกส่งกลับ ผลลัพธ์คือ:
89.00000000000003ตัวเลขทศนิยมที่ไม่จำเป็นสามารถลบออกได้ แต่นั่นเป็นการสนทนาในบางครั้ง
บทสรุป
ตัวเลขฟีโบนักชีเป็นลำดับเฉพาะของจำนวนเต็ม เพื่อให้ได้ตัวเลขปัจจุบัน ให้เพิ่มตัวเลขที่เกี่ยวข้องสองตัวก่อนหน้าทันที ตัวเลขฟีโบนักชีสองตัวแรก 0 ตามด้วย 1 ได้รับการประกาศไว้ล่วงหน้าสำหรับลำดับทั้งหมด ตัวเลขฟีโบนักชีที่เหลือมาจากที่นั่น
ในการสร้างตัวเลขฟีโบนักชีจากดัชนี 2 ที่สอดคล้องกับดัชนี n-1 ให้ใช้ for-loop กับข้อความสั่งหลัก:
int ปัจจุบันไม่มี = พี [ ผม - 1 ] + พี [ ผม - สอง ] ;โดยที่ currNo คือหมายเลขฟีโบนักชีปัจจุบันและ P คืออาร์เรย์ที่ใช้เก็บตัวเลข n
ในการสร้างเลขฟีโบนักชีเพียงตัวเดียวจากดัชนีที่เป็นศูนย์ n ให้ใช้สูตรทางคณิตศาสตร์:
