Từ 1 tới 2 trên tổng số 2 kết quả

Đề tài: Nhân 2 số nguyên lớn bằng phương pháp đệ quy.

  1. #1
    Ngày gia nhập
    11 2017
    Bài viết
    0

    Mặc định Nhân 2 số nguyên lớn bằng phương pháp đệ quy.

    Mình cần giải bài này theo pp đệ quy. ai bk phương pháp và cách làm như thê nào giúp mình với ?

  2. #2
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất đông người
    Bài viết
    514

    Một số nguyên 2 chữ số (a,b) có giá trị là a*c + b, với a là chữ số hàng chục, b là chữ số hàng đơn vị, c là cơ số.

    (a,b)*(a',b') = (a*c+b)*(a'*c+b') = a*a'*c^2 + (a*b' + b*a')*c + b*b'

    Và bạn có công thức làm 1 phép nhân 2 chữ số bằng 4 phép nhân 1 chữ số. (Một phép nhân với c hay c^2 thật ra chỉ xê dịch chữ số từ hàng thấp lên hàng cao, nên không được tính là 1 phép nhân.)

    Đối với 4, 8, 16,... chữ số cũng làm tương tự. Tổng quát, một phép nhân 2^n chữ số có thể quy về 4 phép nhân 2^(n-1) chữ số.

    Và 4 phép nhân ấy lại có thể quy về 16 phép nhân 2^(n-2) chữ số. Và 64 phép nhân 2^(n-3) chữ số. Và v.v. và v.v.

    Cuối cùng, đệ quy dừng ở 4^n phép nhân 1 chữ số.

    Để lập trình cho máy tính hiệu quả nhất, nên chọn c = 2^w trong đó w là độ dài từ máy. Ví dụ trên PC, laptop,... nên chọn w = 32 và, như thế, một chữ số là một uint32_t. Chú ý rằng kết quả của phép nhân 1 chữ số là một số có 2 chữ số, nghĩa là cần dùng thêm kiểu uint64_t.

    Bạn cần biết làm sao tính được các số âm bằng kiểu unsigned.

    Ngoài ra, cũng nên tìm công thức tính 1 phép nhân 2 chữ số chỉ bằng 3 phép nhân 1 chữ số (nhờ đó, giảm độ phức tạp xuống còn 3^n). Xem thêm https://en.wikipedia.org/wiki/Karatsuba_algorithm
    Đã được chỉnh sửa lần cuối bởi Ada : 08-10-2018 lúc 05:12 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

Tags của đề tài này

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn