ฉันควรจะเขียนฟังก์ชันที่คูณตัวเลขสองตัวใหญ่ซึ่งอยู่ในสองรายการที่เชื่อมโยงกัน ฉันต้องการความช่วยเหลือในการหาอัลกอริทึมที่ทำแบบเดียวกับที่คุณแก้ไขด้วยปากกาและกระดาษ นี่คือสิ่งที่ฉันคิด:
ฉันจะใช้ for loop แบบซ้อนเพื่อวนซ้ำทั้งสองรายการในขณะที่คูณแต่ละองค์ประกอบ แต่ฉันไม่แน่ใจว่าจะจัดการกับสถานการณ์การแบกอย่างไร ฉันได้ใช้ฟังก์ชันที่เพิ่มรายการจำนวนเต็มที่เชื่อมโยงสองรายการแล้ว ข้อมูลใด ๆ ที่จะได้รับการชื่นชม
ฉันจะใช้การเรียกซ้ำ (ถ้าคุณไม่เคยได้ยินเกี่ยวกับการเรียกซ้ำ คุณอาจเพิกเฉยต่อคำตอบนี้ได้ คุณจะได้เรียนรู้มันไม่ช้าก็เร็ว)
ฉันกำลังยกตัวอย่างการคูณ 152 * 463 เครื่องคิดเลขบอกฉันว่าผลลัพธ์ที่คาดหวังคือ 70376 แนวคิดของฉันคือแยก 2 ออกจาก 152 เพื่อให้ได้ 15 และ 2 แล้วคูณ 15 * 463 และ 2 * 463:
15 * 463 = 6945. Needs to be multiplied by 10 because the 15 were in the 10s’ position. 6945 * 10? Just add a zero: 69450.
2 * 463 = 926.
Product is 69450 + 926 = 70376.
ในรหัสของคุณ 15 * 463 ได้มาจากการเรียกซ้ำไปยังวิธีการคูณที่คุณกำลังเขียน การคูณ 10 เป็นเรื่องง่าย แค่เติมศูนย์ต่อท้าย 2 * 463 ง่ายกว่าเพราะเราคูณด้วยตัวเลข 1 หลัก เขียนวิธีการเรียกซ้ำใหม่สำหรับงานย่อยนี้ ฟังก์ชันที่คุณมีอยู่แล้วซึ่งเพิ่มรายการที่เชื่อมโยงสองรายการจะทำให้งานเสร็จสิ้น
O(n^2)หรือ Karatsuba แต่ระวัง Karatsuba ต้องการชิ้นส่วนพกพามากกว่านี้ ... - person Spektre schedule 06.07.2020