คำนำ
วันนี้ฉันเห็นคำถามที่ทำให้ดูเหมือนว่ามันไม่ยากที่จะระบุว่าตัวเลขเป็นตัวเลขที่สำคัญหรือไม่ ดังนั้นฉันจึงตัดสินใจใช้มัน
โครงสร้าง DOM
<! doctype html> <html lang = "en"> <head> <meta charset = "utf-8"> <title> คำนวณตัวเลขที่สำคัญภายใน 500 และเอาต์พุต </title> <meta name = "viewport" content = "width = ความกว้างของอุปกรณ์ src = "http://apps.bdimg.com/libs/jquery/2.1.4/jQuery.min.js"> </script> </head> <body> <div> <อินพุต type = "text" id = "num" value = " value = "ส่ง"> </div> </body> </html> <script> $ (function () {$ ("#ส่ง"). on ('คลิก', function () {var num = $ ("#num"). val (); ถ้า (isprimenum (num)) Composite ");}});}); </script>ดังที่แสดงไว้ข้างต้นเราใช้ฟังก์ชัน ISPrimenum (NUM) เพื่อตรวจสอบว่าเป็นหมายเลขเฉพาะหรือไม่ มาใช้ฟังก์ชั่นนี้ด้านล่าง
ใช้ FOR LOOP เพื่อตรวจสอบว่าเป็นจำนวนที่สำคัญ
ฟังก์ชั่น isprimenum (num) {สำหรับ (var i = 2; i <num; i ++) {ถ้า (num%i == 0) {return false;}}; return true;}หลักการค่อนข้างง่าย โดยการค้นหาส่วนที่เหลืออย่างต่อเนื่องด้วยหมายเลขเป้าหมายที่มี 2 หรือมากกว่าถ้าคุณได้รับ 0 นั่นหมายความว่านี่เป็นหมายเลขคอมโพสิตมากกว่าหมายเลขเฉพาะ
แต่การคำนวณนี้ดูเหมือนจะมีขนาดใหญ่เล็กน้อย
เพิ่มประสิทธิภาพวิธีแรก
มันง่ายมากมันถูกนำไปใช้ในระยะเวลาอันสั้น อย่างไรก็ตามดูเหมือนว่าเราสามารถปรับให้เหมาะสม เราไม่จำเป็นต้องไล่ล่าหมายเลขนี้และค้นหาส่วนที่เหลือ เราเพียงแค่ต้องวนซ้ำไปครึ่งหนึ่งของหมายเลขนี้เพื่อคำนวณว่าหมายเลขนี้เป็นจำนวนที่สำคัญหรือไม่
ฟังก์ชั่น isprimenum (num) {สำหรับ (var i = 2; i <num/2+1; i ++) {ถ้า (num%i == 0) {return false;}}; return true;}หลังจากการวัดจริงความเร็วได้รับการปรับปรุงอย่างมาก แต่ฉันรู้ว่า mantissa ของจำนวนนั้นเป็นหรือ 5 ดังนั้นจึงไม่ใช่จำนวนที่สำคัญดังนั้นจึงไม่จำเป็นต้องคำนวณ มาปรับให้เหมาะสมอีกครั้ง
ไม่มีการคำนวณตัวเลขที่มี Mantissa หรือ 5
ฟังก์ชั่น isprimenum (num) {ถ้า (! isdual (num)) {return false;} สำหรับ (var i = 2; i <num/2+1; i ++) {ถ้า (num%i == 0) {return false;}}; return true; num.substring (num.length-1, num.length); return lentnum%2 == 0 || LastNum%5 == 0? เท็จ: จริง;}ด้วยการเพิ่มประสิทธิภาพดังกล่าวเราสามารถลดปริมาณการคำนวณและอย่างน้อยครึ่งหนึ่งของจำนวน (แต่การวัดจริงช่วยปรับปรุงประสิทธิภาพเนื่องจากตัวเลขดังกล่าวสามารถตัดสินได้อย่างรวดเร็วว่าพวกเขาไม่ใช่ตัวเลขที่สำคัญ)
ที่นี่ฟังก์ชั่น substring () พบว่าไม่สามารถใช้กับตัวเลขได้ แต่สามารถใช้กับสตริงได้เท่านั้น น่าเศร้าดังนั้นตัวเลขจึงกลายเป็นสตริงก่อน
หากไม่ใช่ตัวเลขหรือการประมวลผลจำนวนเต็ม
ฉันควรทำอย่างไรถ้าผู้ใช้อินพุตไม่ใช่ตัวเลขหรือทศนิยม? ฉันเขียนสองวิธีในการประมวลผลอย่างรวดเร็ว ...
ฟังก์ชั่น isprimenum (num) {ถ้า (! isnum (num)) {return false;} ถ้า (! isinteger (num)) {return false;} ถ้า (! isdual (num)) {return false;} สำหรับ (var i = 2; isinteger (num) {return num == ~~ num? true: false;} function isnum (num) {var num = num.toString (); var lentnum = num.substring (num.length-1, num.length); return lentnum%2 == 0 || LastNum%5 == 0? เท็จ: จริง;}มีการใช้สองเคล็ดลับที่นี่หนึ่งคือการปัดเศษทศนิยม ~~ num และอื่น ๆ คือการแปลงสตริงเป็นตัวเลข +num
โปรดอ่านโพสต์บล็อกก่อนหน้าของฉัน "JS Skills Skills สำหรับ JavaScript Learning (I) โดย Fungleo"
สิ่งนี้ไม่ได้ปรับปรุงประสิทธิภาพใด ๆ แต่จะกำจัดการป้อนข้อมูลข้อผิดพลาดในการคำนวณเท่านั้น ลองคิดดูอีกครั้งมีวิธีใดที่จะตรวจสอบได้อย่างรวดเร็วว่าไม่ใช่ตัวเลขที่สำคัญหรือไม่?
ลบตัวเลขที่สามารถหารได้ 3 และไม่คำนวณ
ฟังก์ชั่น isprimenum (num) {ถ้า (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} ถ้า (num == 2 || num == 3 || num == 5) {return true;} if (! isdual (num) num/5+1; จริง: false;} ฟังก์ชั่น isnum (num) {return num == +num? true: false;} function isdual (num) {var num = num.toString (); var lentnum = num.substring (num.length-1, num.length); return lentnum%2 == 0 || LastNum%5 == 0? FALSE: true;} function ISTHREE (num) {var str = num.toString (); var sum = 0; สำหรับ (var i = 0; i <str.length; i ++) {sum+=+str.substring (i, i+1);}; return sum%3 == 0? เท็จ: จริง;}ที่นี่เราจะเปลี่ยนหมายเลขเป็นสตริงก่อนจากนั้นแยกแต่ละบิตของสตริงเพิ่มและผลรวมและใช้ผลลัพธ์และ 3 เพื่อค้นหาส่วนที่เหลือจากนั้นเราสามารถค้นหาว่าหมายเลขนี้สามารถคั่นด้วย 3 ได้หรือไม่
ฮ่าฮ่าฉันฉลาดมาก ... ประสิทธิภาพการทดสอบที่แท้จริงยังไม่ดีขึ้นมาก แต่มันก็ปรับปรุงเล็กน้อย มันหดหู่เล็กน้อย
อย่างไรก็ตามหากเรายกเว้นหมายเลข 3 ที่เราไม่จำเป็นต้องคำนวณครึ่งหนึ่ง เราไม่จำเป็นต้องคำนวณครึ่งหนึ่งของมันเราต้องคำนวณหนึ่งในสามเท่านั้น นอกจากนี้เรายังได้ยกเว้น 5 ดังนั้นเราเพียงแค่ต้องคำนวณหนึ่งในห้า ...
หลังจากปรับเปลี่ยนอย่างรวดเร็วประสิทธิภาพได้รับการปรับปรุงอย่างมาก !!! ฉันมีพลัง ...
อย่างไรก็ตามด้วยวิธีนี้รหัสจะกำหนดว่าเป็นหมายเลขคอมโพสิตใน 2/3/5 ดังนั้นจึงจำเป็นต้องเพิ่มประโยคอื่น
if (num == 2 || num == 3 || num == 5) {return true;}วิธีการของคนอื่น ๆ
จากนั้นฉันไม่สามารถนึกถึงวิธีการเพิ่มประสิทธิภาพ ... ดังนั้นฉันจึงค้นหาและพบวิธีแก้ปัญหาต่อไปนี้ ฉันตกใจ !!!
ฟังก์ชั่น isprimenum2 (num) {return!/^.? $ |^(..+?)/1+$/. ทดสอบ (อาร์เรย์ (num+1) .join ('1'))}วิธีการปกติใช้มันสั้นแน่นอน แต่ฉันสามารถเข้าใจได้แม้ว่าฉันจะอ่านมัน !!!
ฉันไม่เข้าใจจริงๆว่าหลักการคืออะไรดังนั้นฉันจึงทำการทดสอบเชิงปฏิบัติและพบว่าประสิทธิภาพของรหัสของฉันสูงกว่ารหัสนี้มาก จากนี้เราจะเห็นว่าวิธีการของฉันยังคงยอดเยี่ยมมาก !!
ต้องใช้เวลา 1600ms สำหรับรหัสของฉันในการพิมพ์หมายเลขเฉพาะทั้งหมดภายใน 100000 และรหัสนี้ใช้เวลา 160000ms กล่าวคือรหัสของฉันใช้เวลาเพียงหนึ่งเปอร์เซ็นต์ของเวลา
อย่างไรก็ตามหากใครสามารถเข้าใจรหัสนี้ได้โปรดอธิบายให้ฉันฟัง ...
เติมเต็ม
หลังจากอ่านข้อมูลที่เกี่ยวข้องบางอย่างดูเหมือนว่าวิธีที่ฉันใช้ NUM/5 ด้านบนไม่ดีมาก (ผลลัพธ์ไม่ผิด) มีวิธีที่ดีกว่าซึ่งก็คือการใช้ Math.SQRT (NUM) เพื่อค้นหาสแควร์รูท
ผลการทดสอบรหัสของฉันมีดังนี้
ดังที่แสดงในรูปด้านบนผลการคำนวณของรหัสของฉันถูกต้องอย่างสมบูรณ์ อย่างไรก็ตามต้องใช้เวลา 1638 มิลลิวินาที มันยังคงเป็นกรณีหลังจากการทดสอบหลายครั้ง
ผลการทดสอบของวิธีการสแควร์รูทมีดังนี้
ดังที่แสดงในรูปด้านบนวิธีนี้มีความสำคัญทางวิทยาศาสตร์และเร็วขึ้น ต้องใช้การทดสอบหลายครั้งและใช้เวลาระหว่าง 1150 มิลลิวินาทีถึง 1,250 มิลลิวินาที เมื่อเทียบกับประสิทธิภาพของรหัสของฉันมันอยู่ที่ประมาณ 25%
ฉันยังตัดสินด้วยว่าตัวเลขนั้นเป็นหรือ 5 และไม่ว่าผลรวมจะถูกแบ่งออกเป็น 3 ซึ่งเป็นเวลานาน ฉันหวังว่าจะลดจำนวนการดำเนินงานอย่างแน่นอน แต่รหัสเหล่านี้เองก็มีจำนวนการดำเนินงาน ฉันจะลบรหัสทั้งหมดของฉันแล้วดู
ประสิทธิภาพได้รับการปรับปรุงอีกครั้ง ดูเหมือนว่าการคำนวณทั้งหมดของฉันจะได้รับการปรับให้เหมาะสมในเชิงลบ!
ในที่สุดรหัสมีดังนี้:
ฟังก์ชั่น isprimenum (num) {if (! isnum (num)) {return false;} if (! isinteger (num)) {return false;} สำหรับ (var i = 2; i <= math.sqrt (num); i ++) {if (num%i == 0) {return; จริง: false;} ฟังก์ชั่น isnum (num) {return num == +num? จริง: เท็จ;}สรุป: มันเป็นเพราะเลขคณิตที่น่าสงสารของฉันที่ทำให้ฉันฉลาดในด้านหน้า อย่างไรก็ตามการฝึกเทคนิคขนาดเล็กก็ดีเช่นกัน -_- |||
สุดท้ายมาดูกันว่าต้องใช้เวลานานเท่าใดในการคำนวณจำนวนนายกทั้งหมดภายใน 1 ล้าน
ข้างต้นเป็นบทสรุปของวิธีการตัดสินว่าตัวเลขเป็นตัวเลขสำคัญที่แนะนำโดยบรรณาธิการหรือไม่ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน