Vấn đề mã hóa hàng ngày: Số tam giác và ước số lớn

Chào mừng mọi người trở lại với một vấn đề khác cần giải quyết! Hôm nay, chúng ta sẽ nói về các số tam giác và các ước của chúng: đặc biệt là các số lớn!

Mặc dù chúng ta có thể chiêm ngưỡng sự thể hiện nghệ thuật tuyệt vời của tôi về các số tam giác trong tự nhiên, nhưng chúng ta hãy có những tuyên bố từ chối trách nhiệm thông thường:

1. Vấn đề này được cung cấp bởi trang web tuyệt vời ProjectEuler.net , mà bạn có thể đăng ký đây ! Có hơn 800 bài toán và lập trình để giải và một kho lưu trữ rộng lớn các cuộc thảo luận về chúng. Nó thực sự là công cụ hoàn hảo để bạn vò đầu bứt tai và tìm hiểu điều gì đó mới mẻ! Hãy kiểm tra nó và cố gắng giải quyết những thách thức của bạn!

   
   

2. Tôi không phải là một lập trình viên chuyên nghiệp: chỉ là một người thích viết về những thứ này và thích chia sẻ những bức ảnh của mình. Tôi chắc chắn rằng đây sẽ không phải là giải pháp tối ưu, vì vậy nếu bạn có giải pháp tốt hơn hoặc bất kỳ ý tưởng nào về cách tối ưu hóa giải pháp đó, bạn rất hoan nghênh nếu muốn chia sẻ!

Nói đủ rồi, hãy xem vấn đề hôm nay mang lại điều gì:

Dãy số tam giác được tạo bằng cách cộng các số tự nhiên. Vậy số tam giác thứ 7 sẽ là 1+2+3+4+5+6+7=28. Mười số hạng đầu tiên sẽ là: 1,3,6,10,15,21,28,36,45,55,…

Hãy để chúng tôi liệt kê các yếu tố của bảy số tam giác đầu tiên:

Ta có thể thấy rằng 28 là số tam giác đầu tiên có trên 5 ước số.

Giá trị của số tam giác đầu tiên có hơn năm trăm ước là bao nhiêu?

Vấn đề khá đơn giản: chúng tôi được yêu cầu hiểu số tam giác đầu tiên có hơn 500 ước số là gì. Đầu tiên, chúng ta hãy tìm hiểu kỹ hơn về số tam giác là gì và ước số là gì.

số tam giác

Số tam giác là một tập hợp con cụ thể của các số được hình thành bởi tổng của tất cả các số tự nhiên cho đến một số nhất định. Chúng được gọi là hình tam giác vì bạn luôn có thể sắp xếp chúng thành một hình tam giác . Dưới đây là một số ví dụ:

Trong hình trên, đó là số tam giác thứ 3, thứ 4 và thứ 5. Vì vậy, ví dụ, số thứ 3 được tạo thành 1+2+3 = 6, số thứ 4 là 1+2+3+4 = 10, v.v. Nói chung, số tam giác nᵗʰ, Tₙ, bằng

Tất nhiên, đây là một trong những chuỗi nổi tiếng nhất trong toán học, cũng được trình bày bởi Gauss , người đã phát biểu rằng tổng các số nguyên liên tiếp bằng:

Vì vậy, về cơ bản, nếu chúng ta muốn tính số tam giác thứ 3, chẳng hạn, chúng ta chỉ cần tính 3*4/2 = 6. Điều này sẽ rất hữu ích khi chúng ta bắt đầu viết lời giải!

các ước số

Để đưa ra định nghĩa về ước (hoặc thừa số ) của một số n, rất đơn giản: đó là một số j có thể được nhân với một số nguyên k khác để lại ra n . Ví dụ, 3 là ước của 18, vì chúng ta có thể nhân 3 với 6 để lại được 18.

Tuy nhiên, 5 không phải là ước của 18, vì không có số k nào nhân với 5 được 18.

Theo định nghĩa, chúng ta cũng thu được một tính chất quan trọng: nếu j là ước của n vì nó có thể nhân với k để được n, thì k cũng là ước của n vì nó có thể nhân với j để được n.

Bằng cách này, chúng ta có thể chắc chắn rằng một số n luôn có ít nhất hai ước j và k (thực tế, j luôn có thể là 1 và k là n ).

Ngoài ra, nói cách khác, số j là ước của số n nếu số dư của n / j bằng 0 . Vì vậy, ví dụ, 18/3 = 6 và phần còn lại là 0.

Chúng ta có thể chính thức hóa khái niệm này tốt hơn bằng số học mô-đun nói rằng j là ước của n nếu n % j = 0. Nói cách khác, chúng ta có được thuộc tính thứ hai này:

Tính chất thứ ba và cũng là tính chất cuối cùng mà chúng ta quan tâm là không thể có ước số nào của một số n lớn hơn n/2, chứ không phải chính n . Điều này khá đơn giản để hiểu. Từ thuộc tính đầu tiên, chúng ta biết rằng các thừa số bằng cách nào đó được “liên kết” với nhau trong phạm vi 1,…,n.

Điều này là do một lần nữa, nếu j \ n, thì đó là vì j * k = n. Do đó, cũng k \ n. Hãy lấy lại số 18 làm ví dụ, tìm các ước số của nó và tô màu chúng để phản ánh tính chất này.

Vì vậy, ví dụ, nếu j = 3, k = 6, và ngược lại nếu j = 6, k = 3, điều này có nghĩa là j nhỏ nhất chúng ta có thể sử dụng, ngoài 1, là 2, mang lại cho chúng ta k lớn nhất có thể, n/2 (9 trong trường hợp của chúng tôi) . Những công việc này:

• đối với các số chẵn, trong trường hợp đó, thừa số lớn nhất sẽ bằng một nửa của n;

• đối với số lẻ: nếu n không chia được cho 2 (vì n lẻ sẽ cho ta số hữu tỉ); điều này có nghĩa là chúng ta chỉ có thể sử dụng j > 2, điều này sẽ luôn cho chúng ta kết quả k < n/2.

  
  

Cuối cùng, chỉ có một trường hợp mà j và k có thể bằng nhau: khi n là số chính phương. Ví dụ: khi n = 36, một thừa số có thể j = 6 sẽ tạo ra một thừa số khác k = 6. Chúng ta sẽ thảo luận thêm về trường hợp này sau trong phần code.

Tất nhiên, những khái niệm này khá tầm thường, nhưng chúng sẽ rất quan trọng trong giải pháp của chúng ta!

Mật mã

Mã sẽ được viết bằng Go , vì đây thực sự là một ngôn ngữ nhanh mà vẫn duy trì mức độ dễ đọc tuyệt vời. Chúng ta sẽ chia giải pháp thành hai phần: đầu tiên, chúng ta sẽ tạo một hàm để tìm các ước của một số, sau đó chúng ta sẽ áp dụng hàm đó cho các số tam giác .

Trước tiên hãy xem chức năng:

Chúng ta tạo hàm chấp nhận số nguyên n và trả về một mảng số nguyên out , hàm này sẽ chứa các ước của chúng ta. Sau đó, chúng ta out các thừa số tầm thường, cụ thể là chính 1 và n .

Sau đó, chúng tôi bắt đầu lặp j từ 2 đến n/2 (từ thuộc tính thứ hai; cũng lưu ý rằng chúng tôi không quan tâm đến chính n/2 vì trong trường hợp n chẵn, k = n/2 sẽ được thêm vào các ước của j = 2 lần lặp: đây là lý do tại sao chúng tôi dừng lại ở j<n/2 chứ không phải j≤ n/2 ).

Bằng cách này, chúng ta chỉ có thể kiểm tra các ước trong nửa đầu của n , tăng tốc quá trình lên một chút.

Tại mỗi vòng lặp, chúng tôi kiểm tra 3 điều:

• Câu lệnh if thứ ba thực sự kiểm tra xem n%j==0 hay không, nói cách khác, nếu 0 ≡ n (mod j). Nếu vậy, chúng tôi đã tìm thấy một yếu tố và chúng tôi thêm j vào danh sách. Chúng ta cũng có thể thêm phần đối ứng của nó k vào danh sách, bằng cách tính n/j và sau đó chuyển sang phần tiếp theo j ;

• Câu lệnh if thứ hai kiểm tra xem n có phải là số vuông hay không và vì vậy j là nghiệm của n . Nếu vậy, chỉ một ước số j sẽ được thêm vào out , vì vậy để tránh trùng lặp, sau đó thuật toán sẽ tiếp tục.

  
  

  Giả sử n = 36 : nếu khối nhỏ này bị thiếu, câu lệnh if thứ ba sẽ được kích hoạt, khiến out nhận được j = 6 và k = n/j = 36/6 = 6 , do đó, tạo ra một bản sao.

• Câu lệnh if đầu tiên là phức tạp nhất: mục đích của nó là để kiểm tra xem chúng ta có bắt đầu có các cặp jk lặp lại hay không. Nếu vậy, chúng ta có thể ngắt vòng lặp ngay lập tức, vì tất cả các yếu tố của chúng ta đều đã có sẵn trong out .

  
  

Cụ thể về điểm thứ ba này, có hai trường hợp cần kiểm tra: out[len(out)-1] == j hay out[len(out)-2] == j .

Trường hợp đầu tiên là trường hợp cổ điển: lấy số T₇ = 28 làm ví dụ:

Khi j = 7 , nó sẽ bằng với giá trị cuối cùng được chèn vào. Do đó, chúng ta có thể phá vỡ vòng lặp.

Trường hợp thứ hai chỉ xảy ra khi chúng tôi tìm thấy một hình vuông n . Lấy lại 36, ví dụ:

Khi j = 9 , nó sẽ bằng giá trị cuối cùng được thêm vào trước căn bậc hai của n , giá trị này chỉ xuất hiện một lần. Do đó, tại thời điểm này, chúng ta có thể phá vỡ vòng lặp.

Cuối cùng, chúng ta có thể chỉ cần return out để có ước số của mình.

Áp dụng kết quả

Bây giờ chúng ta đã có hàm của mình, chúng ta có thể áp dụng nó cho mọi số tam giác. Chúng tôi sẽ tạo một bộ đếm c sẽ đóng vai trò là bộ tạo cho các số tam giác của chúng tôi. Chúng tôi tính toán số tam giác liên quan tn bằng phương trình Gauss và kiểm tra xem nó có bao nhiêu ước số.

Nếu nó lớn hơn 500, chúng tôi sẽ trả về kết quả là tn .

Nhưng…có một nhược điểm!

ProjectEuler.net thực sự là một dự án đáng yêu: bên cạnh việc trình bày các câu đố và bài toán, trọng tâm chính của họ là cung cấp một công cụ để bắt đầu học, suy nghĩ và lập luận về toán học .

Và tôi thích điều đó: họ cam kết đến mức việc xuất bản kết quả và hướng dẫn cho các vấn đề của họ thực sự bị cấm (đây là một trong 100 vấn đề đầu tiên, vì vậy tôi hiểu là được phép).

Với điều này, tôi không nghĩ sẽ công bằng nếu chỉ đưa ra giải pháp sao chép-dán và đạt được thành tích . Vì lý do này, tôi sẽ không cung cấp cho bạn giải pháp thực tế: hãy tự mình thử và cố gắng tìm ra thuật toán tốt hơn thuật toán của tôi (Có rất nhiều giải pháp). Xin lỗi các bạn! 😅

Thời gian phức tạp

Tôi tự tin rằng có nhiều giải pháp tốt hơn vì tôi cảm thấy đây là một cú đánh khá tệ!

Hàm FindDivisor chạy trong thời gian tuyến tính: vì nó phụ thuộc vào kích thước của thể hiện n và nó cũng chạy tối đa n/2 vòng lặp; chúng ta có thể coi nó là một O(n).

Tuy nhiên, trước tiên chúng ta phải tính toán từng số tam giác, việc này cũng mất thời gian O(tn), trong đó tn là kết quả (số cuối cùng chúng ta thực sự tính toán). Với điều này, độ phức tạp thời gian xấp xỉ của toàn bộ thuật toán phải là O(tn*n).

Vì tn trở thành đối số hoặc hàm của chúng ta và chúng ta chạy tối đa n/2 vòng lặp bên trong nó, nên chúng ta có thể viết lại độ phức tạp thời gian thành O(tn*tn/2) = O(tn²/2) = O(tn²). Vì vậy, một giải pháp thời gian bậc hai , thật không may!

Tôi đã rất ngạc nhiên rằng ngay cả khi thuật toán có độ phức tạp như vậy, nó vẫn chạy khá nhanh. Để đưa ra kết quả trên máy của tôi (AMD Ryzen 5, trung bình ck. 2700 MHz), phải mất 322,564227 ms.

Tuy nhiên, việc cố gắng tìm số tam giác đầu tiên vượt quá 1000 ước mất 3,827144472 giây, do đó, có thể thấy rõ rằng mức tiêu thụ thời gian đang tăng lên nhanh chóng.

Phần kết luận

Cuối cùng chúng tôi đã làm được! Tôi hy vọng các bạn thích bài viết này và tôi hy vọng bạn có thể rút ra điều gì đó thú vị từ nó: nếu vậy, vui lòng để lại một hoặc hai tràng vỗ tay và chia sẻ bài viết với những người có thể quan tâm đến chủ đề này!

Xin gửi lời cảm ơn sâu sắc tới ProjectEuler một lần nữa vì công việc tuyệt vời này: Tôi thực sự muốn đề nghị bạn đi và xem những gì họ có thể cung cấp; Tôi chắc rằng bạn sẽ thấy nó siêu thú vị!

Và như mọi khi, cảm ơn vì đã đọc.

Nicola