โปรแกรม Perfect Number ใน Python: จะตรวจสอบได้อย่างไรว่าตัวเลขสมบูรณ์แบบหรือไม่?

เผยแพร่แล้ว: 2021-01-29

บทนำ

ตัวเลขจะเป็นจำนวนเต็มถ้าผลรวมของตัวหารถูกต้อง (ไม่รวมตัวตัวเลขเอง) เท่ากับจำนวนนั้น

เพื่อให้ได้แนวคิดที่ดีขึ้น มาลองพิจารณาตัวอย่างกัน ตัวหารที่เหมาะสมของ 6 คือ 1, 2, 3 ทีนี้ผลรวมของตัวหารเหล่านี้เท่ากับ 6 (1+2+3=6) ดังนั้น 6 จึงเป็นจำนวนสมบูรณ์ . ในขณะที่เราพิจารณาจำนวนอื่น เช่น 12 ตัวหารแท้ของ 12 คือ 1, 2, 3, 4, 6 ตอนนี้ผลรวมของตัวหารเหล่านี้ไม่เท่ากับ 12 ดังนั้น 12 จึงไม่ใช่จำนวนสมบูรณ์

การเขียนโปรแกรมใน Python ค่อนข้างง่ายและสนุกกว่าเมื่อเปรียบเทียบกับภาษาอื่น เนื่องจากมีรูปแบบที่ง่ายกว่าและอ่านง่าย ตอนนี้เราเข้าใจแนวคิดเรื่องจำนวนสมบูรณ์แล้ว เรามาเขียนโปรแกรม python เพื่อตรวจสอบว่าตัวเลขนั้นเป็นจำนวนสมบูรณ์หรือไม่ มาสร้างโค้ด python เพื่อตรวจสอบว่าข้อมูลที่ผู้ใช้ป้อนนั้นเป็นตัวเลขที่สมบูรณ์แบบหรือไม่ และสำรวจความสนุกในการเขียนโค้ดด้วย python ดูโปรแกรมวิทยาศาสตร์ข้อมูลของเราหากคุณสนใจที่จะรับความเชี่ยวชาญ

อ่าน: โปรแกรมรูปแบบหลาม

สารบัญ

โปรแกรมหลาม

วิธีแก้ปัญหาพื้นฐานในการหาจำนวนสมบูรณ์คือการวนรอบ 2 ถึงจำนวน-1 รักษาผลรวมของตัวหารที่เหมาะสม และตรวจสอบว่าผลรวมเท่ากับตัวเลขหรือไม่

n=int(อินพุต("ป้อนหมายเลข"))
ผลรวม=1
สำหรับฉันอยู่ในช่วง (2,n):
ถ้า(n%i==0):
sum=sum+i
ถ้า(ผลรวม==n):
print(n”เป็นตัวเลขที่สมบูรณ์แบบ”)
อื่น:
print(n”ไม่ใช่จำนวนที่สมบูรณ์แบบ”)

มาดูโค้ดกันเลย

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

เรากำลังวนรอบ 2 ไปที่หมายเลข 1 และเพิ่มจำนวนเต็มเพื่อรวมหากเป็นตัวหารที่เหมาะสม และสุดท้าย เมื่อเราออกจากลูป เรากำลังตรวจสอบว่าผลรวมที่ได้รับนั้นเท่ากับตัวเลขหรือไม่ ชิ้นส่วนของเค้กใช่มั้ย?

เวอร์ชันที่ปรับให้เหมาะสมเล็กน้อย

หลังจากรันโปรแกรมข้างต้นจนหมด เราอาจมีคำถามว่าเราสามารถปรับให้เหมาะสมได้หรือไม่? แต่เราสามารถลดจำนวนการวนซ้ำเป็นตัวเลข/2 โดยไม่ต้องเปลี่ยนอัลกอริทึม เพราะเราได้แนวคิดที่ว่าตัวเลขไม่สามารถมีตัวหารที่เหมาะสมมากกว่าจำนวน/2

n=int(อินพุต("ป้อนหมายเลข"))
ผลรวม=1
สำหรับฉันอยู่ในช่วง (2,n//2+1):
ถ้า(n%i==0):
sum=sum+i
ถ้า(ผลรวม==n):
print(n”เป็นตัวเลขที่สมบูรณ์แบบ”)
อื่น:
print(n, “ไม่ใช่จำนวนที่สมบูรณ์แบบ”)

ตัวอย่างด้านบนเกือบจะคล้ายกับตัวอย่างก่อนหน้านี้ โดยมีความแตกต่างเพียงอย่างเดียวของการวนซ้ำจนถึงหมายเลข/2 โปรดทราบว่าเรากำลังทำการหารจำนวนเต็มเพื่อหลีกเลี่ยงการแปลงเป็นประเภททศนิยม และเรากำลังวนซ้ำจนถึง n//2+1 เนื่องจากจำนวนเต็มสุดท้ายในช่วงนี้ไม่ถือว่าอยู่ในลูปไพธอน

ข้อจำกัด

เมื่อเราถูกขอให้ค้นหาตัวเลขที่สมบูรณ์ในช่วงที่กำหนด วิธีแก้ปัญหาของเราจะต้องใช้เวลาเป็นสัดส่วนกับจำนวน^2 เช่น ความซับซ้อนของเวลา O(n²) เนื่องจากเราต้องวนซ้ำตัวเลขแต่ละตัวในช่วงที่กำหนด แล้วตรวจสอบตัวหารที่เหมาะสมสำหรับแต่ละตัวเลข และจำนวนน้อยตรงตามเงื่อนไขจำนวนสมบูรณ์ ตัวอย่างเช่น จำนวนของตัวเลขสมบูรณ์ในช่วง 0 ถึง 1,000 เป็นเพียง 3 (6, 28, 496)

มีทางออกที่ดีที่สุดสำหรับสิ่งนี้ โดยที่เราไม่จำเป็นต้องวนซ้ำองค์ประกอบทั้งหมดเพื่อค้นหาตัวหารที่เหมาะสม สูตรของยุคลิดระบุว่า 2 n -1(2 n − 1) เป็นจำนวนคู่ที่สมบูรณ์แบบโดยที่ทั้ง n, (2 n -1) คือ จำนวนเฉพาะ. ตัวอย่างเช่น 6 เป็นไปตามสมการข้างต้นโดยที่ n เป็น 2 และทั้ง 2, 2 2 − 1 (2 2 − 1 = 3) เป็นจำนวนเฉพาะ แต่เราไม่สามารถตอบได้หากเราถูกขอให้ค้นหาว่ามีเลขสมบูรณ์คี่หรือไม่

นอกจากนี้ เราทราบดีว่าทุกภาษามีการจำกัดช่วงของจำนวนเต็มที่สามารถจัดเก็บได้ ด้วยข้อจำกัดนี้ เราอาจไม่มีทางหาจำนวนสมบูรณ์ที่ใหญ่ที่สุดได้

ข้อจำกัดทั้งหมดเหล่านี้จะเกิดขึ้นหากจำนวนอินพุตของเรามีขนาดใหญ่ แต่ถ้าจำนวนอินพุตของเรามีค่าน้อย วิธีแก้ปัญหาเริ่มต้นของเราจะใช้เวลาน้อยลง

อ่านเพิ่มเติม: Python Framework สำหรับการพัฒนาเว็บ

บทสรุป

เราทราบคำจำกัดความและเข้าใจแนวคิดเบื้องหลังจำนวนที่สมบูรณ์แบบแล้ว เดินผ่านวิธีแก้ปัญหาเบื้องต้นในการหาตัวเลขที่เป็นตัวเลขที่สมบูรณ์หรือไม่ และหลังจากดูวิธีแก้ปัญหาเบื้องต้นแล้ว เราได้ปรับให้เหมาะสมขึ้นเล็กน้อยโดยลดจำนวนการวนซ้ำ เราได้ผ่านข้อจำกัดของอัลกอริธึมของเราแล้ว และกล่าวถึงสูตรของ Euclid ในการหาจำนวนคู่ที่สมบูรณ์แบบ

ตอนนี้คุณทราบโปรแกรม python แล้ว เพื่อตรวจสอบว่าตัวเลขนั้นเป็นตัวเลขที่สมบูรณ์หรือไม่ ลองเขียนโค้ดด้วยตัวเองและลองปรับให้เหมาะสมหากพบว่ามีการทำซ้ำที่ทับซ้อนกัน นอกจากนี้ ให้ลองสร้างรหัสเพื่อค้นหาตัวเลขที่สมบูรณ์ในช่วงตัวเลขที่กำหนด

หากคุณอยากเรียนรู้เกี่ยวกับ python, data science, ลองดู IIIT-B & upGrad's Executive PG Program in Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 แบบ, เวิร์กช็อปภาคปฏิบัติ, การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม แบบตัวต่อตัวกับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ

อธิบายความซับซ้อนของโปรแกรม Perfect Number ใน Python

กล่าวได้ว่าจำนวนนั้นเป็นจำนวนสมบูรณ์หากมันเท่ากับผลรวมของตัวหาร วิธีตรวจสอบว่าจำนวนนั้นสมบูรณ์หรือไม่ เรามีสองวิธี วิธีแรกเป็นวิธีที่ไร้เดียงสาซึ่งความซับซ้อนของเวลาคือ O (n2) เนื่องจากเรากำลังวนซ้ำ "j" สำหรับแต่ละ "i" และตรวจสอบตัวหาร
วิธีที่สองคือวิธีแก้ปัญหาที่เหมาะสมที่สุดโดยที่ความซับซ้อนของเวลาคือ O(√n) ที่นี่เราไม่จำเป็นต้องวนซ้ำทุกตัวเลข เราสามารถสรุปได้โดยตรงโดยใช้สูตรของ Euclid นั่นคือ:
2n-1(2n − 1) โดยที่ n และ 2n เป็นจำนวนเฉพาะ
อย่างไรก็ตาม สูตรนี้ใช้ไม่ได้กับจำนวนเต็มคี่ ดังนั้นเราจึงต้องหาแนวทางอื่นสำหรับจำนวนดังกล่าว

แนวทางของ Perfect Number Program มีข้อจำกัดอะไรบ้าง?

ทั้งสองแนวทางนี้ดีแต่ในระดับหนึ่งเท่านั้น ทั้งสองวิธีไม่สามารถถือเป็นแนวทางที่สมบูรณ์แบบได้เนื่องจากเทคนิคบางอย่าง ข้อจำกัดของแนวทางเหล่านี้มีดังนี้:

1. วิธีแรกและวิธีไร้เดียงสานั้นแย่กว่านั้นเพราะต้องใช้เวลาและความจำมาก และมีเวลาซับซ้อนเป็น O(n2) นี่เป็นเพราะว่าเราใช้การวนซ้ำซ้อนและวนซ้ำวงใน n ครั้งสำหรับทุกองค์ประกอบของวงรอบนอก วิธีการนี้ไร้เดียงสาและจะให้ TLE สำหรับค่า n ที่มากกว่า ดังนั้นจึงไม่แนะนำ
2. จากนั้นเราก็มีแนวทางที่เหมาะสมในการแก้ปัญหาใน O(√n) นี่เป็นแนวทางที่ดี เว้นแต่ว่าจะมีตัวเลขสมบูรณ์คี่เข้ามาเล่น เราไม่สามารถตรวจสอบจำนวนเต็มคี่ด้วยวิธีนี้ได้ เนื่องจากเป็นไปตาม “สูตรของยูคลิดสำหรับจำนวนสมบูรณ์คู่” ซึ่งใช้ได้กับจำนวนสมบูรณ์คู่เท่านั้น

Python เหมาะสมสำหรับการเขียนโปรแกรมเชิงแข่งขันหรือไม่?

Python พัฒนามาจาก C/C++ และแม้แต่ Java และถือเป็นภาษาที่เหมาะสมที่สุดสำหรับการวิจัยและพัฒนา แต่เมื่อพูดถึงการเขียนโปรแกรมเชิงแข่งขัน ชุมชนการเขียนโปรแกรมส่วนใหญ่หลีกเลี่ยง Python เหตุผลที่เป็น Python นั้นช้าที่สุดในบรรดาสามภาษานี้