Tìm GCD của mảng trong Python

Trong bài viết này, chúng tôi đã trình bày thuật toán tìm Ước chung lớn nhất [GCD] của tất cả các phần tử của mảng một cách hiệu quả.

Giới thiệu

mã giả

phức tạp

Thực hiện

Các ứng dụng

Thời gian đọc. 10 phút. thời gian mã hóa. 5 phút

Ước chung lớn nhất [GCD] của hai hoặc nhiều số nguyên có thể được định nghĩa là số nguyên dương lớn nhất chia hết tất cả các số nguyên
Ví dụ,

gcd[4, 8, 10] = 2

vì 2 là số lớn nhất chia hết cho ba số

GCD có thể được tính bằng nhiều phương pháp như bằng cách sử dụng

• Nguyên tố
• Thuật toán Euclid
• Thuật toán GCD nhị phân

Đối với bài viết này, chúng tôi sẽ sử dụng thuật toán euclide để thực hiện các phép tính GCD

Tìm gcd của mảng bằng cách tính toán lặp đi lặp lại gcd trung gian tại mỗi phần tử

Các bước của thuật toán bao gồm

• khởi tạo kết quả thành giá trị đầu tiên trong mảng
• cho mỗi phần tử tiếp theo
  • tìm GCD bằng thuật toán euclid của kết quả trung gian và phần tử hiện tại
  • gán lại giá trị này cho biến kết quả
• trả lại kết quả

Các bước của thuật toán Euclid bao gồm

• Tại mỗi bước trong quá trình lặp
  • thay a bằng b
  • thay thế b bằng [a mod b]
• cho đến khi cặp cuối cùng là [d, 0], trong đó d là ước chung lớn nhất

function gcd[a, b]
    while b != 0 do
        a, b = b, a % b
    end
    return a

result = arr[0]
for i = 1 to n-1
    result = gcd[result, arr[i]]

Khi chúng ta thực hiện thuật toán Euclid n lần cho một mảng có kích thước n, độ phức tạp về thời gian sẽ là n * T[Euclid's]

• Trường hợp xấu nhất thời gian phức tạp. _______________, khi nào _______________. Điều này xảy ra khi a và b là hai số Fibonacci liên tiếp
• Độ phức tạp thời gian trường hợp trung bình. ________số 8_______. Điều này được tính bằng cách sử dụng phân phối xác suất
• Độ phức tạp thời gian trường hợp tốt nhất. O[n], điều đó xảy ra khi tất cả các phần tử mảng giống nhau và thuật toán Euclid chỉ lấy O[1] cho mỗi lần lặp
• Độ phức tạp của không gian. Θ[1]

Sau đây là cách triển khai phương pháp của chúng tôi trong Python

def gcd[a, b]:
   while b:
       a, b = b, a % b

def gcd_arr[arr, n]:
   res = arr[0]
   for i in range[1, n]:
       print["gcd[", res, ",", arr[i], "]", end=""]
       res = gcd[res, arr[i]]
       print["=", res]
   return res

arr = [2, 4, 6, 80]
print["GCD of the array is :", gcd_arr[arr, 4]]

• Giảm phân số cho toán học
• Để tính toán nghịch đảo mô-đun cho thuật toán RSA
• Giải phương trình tuyến tính mô-đun
• Một ví dụ cổ điển về việc sử dụng
  • Một sàn nhà hình chữ nhật có kích thước 300 cm × 195 cm. Những viên gạch hình vuông lớn nhất có thể được sử dụng để trải sàn chính xác là bao nhiêu?

Câu hỏi

GCD của mảng {11, 121, 264, 143} sẽ là gì

gcd[11, 121] = 11 => gcd[11, 264] = 11 => gcd[11, 143] = 11

Với bài viết này tại OpenGenus, bạn phải nắm vững cách tìm GCD của một bộ số

Tuyên bố vấn đề - Chúng ta sẽ được cung cấp một dãy số và chúng ta cần tìm ước chung lớn nhất

Nếu chúng ta cần tìm gcd của nhiều hơn hai số, thì gcd bằng tích của các thừa số nguyên tố chung cho tất cả các số được cung cấp làm đối số. Nó cũng có thể được tính bằng cách lặp đi lặp lại các GCD của các cặp số đối số

Ở đây chúng tôi sẽ thực hiện phương pháp sau

Vì vậy, bây giờ, hãy xem việc thực hiện

Thí dụ

Bản thử trực tiếp

def findgcd[x, y]:
   while[y]:
      x, y = y, x % y
   return x
l = [22, 44, 66, 88, 99]
num1=l[0]
num2=l[1]
gcd=findgcd[num1,num2]
for i in range[2,len[l]]:
   gcd=findgcd[gcd,l[i]]
print["gcd is: ",gcd]

đầu ra

Gcd is: 11

Tất cả các biến và hàm được khai báo trong phạm vi toàn cầu như trong hình bên dưới –

Phần kết luận

Trong bài này, chúng ta đã tìm hiểu phương pháp tìm ước chung lớn nhất của một dãy số cho trước

GCD [Mẫu số chung lớn nhất], còn được gọi là HCF [Nhân số chung cao nhất] là số lớn nhất là ước chung của cả hai số

Thí dụ

Tìm ƯCLN của hai số sau

nhập numpy dưới dạng np

số1 = 6
số2 = 9

x = np. gcd[số1, số2]

in[x]

trả lại. 3 vì đó là số lớn nhất mà cả hai số có thể chia hết cho [6/3=2 và 9/3=3]

Tìm GCD trong Mảng

Để tìm Thừa số chung cao nhất của tất cả các giá trị trong một mảng, bạn có thể sử dụng phương thức reduce[]

Phương thức reduce[] sẽ sử dụng ufunc, trong trường hợp này là hàm gcd[], trên mỗi phần tử và giảm mảng đi một chiều

gcd[] trong python là gì?

Python có chức năng gcd tích hợp không?