Java: mengalikan angka besar menggunakan daftar tertaut

Saya seharusnya menulis fungsi yang mengalikan dua angka besar yang ada dalam dua daftar tertaut. Saya butuh bantuan untuk menemukan algoritme yang melakukan hal itu dengan cara yang sama seperti Anda menyelesaikannya di pena dan kertas. inilah yang saya pikirkan:

Saya akan menggunakan loop for bersarang untuk mengulangi kedua daftar sambil mengalikan masing-masing elemen tetapi saya tidak yakin bagaimana menangani situasi pembawaan. Saya telah menerapkan fungsi yang menambahkan dua daftar bilangan bulat tertaut. masukan apa pun akan dihargai.


java algorithm multiplication linked-list
person Texasy04    schedule 06.07.2020    source sumber
comment
Apakah rekursi merupakan suatu pilihan?   -  person Ole V.V.    schedule 06.07.2020
comment
Bisakah Anda menunjukkan kode yang telah Anda tulis? Akan lebih mudah untuk menjelaskan sesuatu berdasarkan sesuatu yang sudah Anda pahami, daripada mengemukakan sesuatu yang baru yang mungkin akan semakin membingungkan Anda.   -  person Joni    schedule 06.07.2020
comment
lihat Perhitungan bignum square yang cepat jadi gunakan pendekatan O(n^2) yang naif atau Karatsuba. Namun berhati-hatilah, Karatsuba membutuhkan lebih banyak barang bawaan...   -  person Spektre    schedule 06.07.2020

Jawaban (1)


arrow_upward
0
arrow_downward

Saya akan memilih rekursi (jika Anda belum pernah mendengar tentang rekursi, Anda mungkin dapat mengabaikan jawaban ini; cepat atau lambat Anda akan mempelajarinya).

Saya mengambil perkalian 152*463 sebagai contoh. Kalkulator saya memberi tahu saya bahwa hasil yang diharapkan adalah 70376. Ide saya adalah membagi 2 dari 152 untuk mendapatkan 15 dan 2 lalu mengalikan 15 * 463 dan 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.

Dalam kode Anda 15 * 463 diperoleh melalui panggilan rekursif ke metode perkalian yang Anda tulis. Mengalikan dengan 10 itu mudah, cukup tambahkan angka nol. 2 * 463 lebih sederhana karena kita mengalikannya dengan angka 1 digit. Tulis metode rekursif baru untuk subtugas ini. Fungsi yang sudah Anda miliki yang menambahkan dua daftar tertaut akan menyelesaikan pekerjaannya.

person Ole V.V.    schedule 06.07.2020