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:  Vấn đề này được cung cấp bởi trang web tuyệt vời  , mà bạn có thể đăng ký  ! 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!   ProjectEuler.net   đây  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   đầu tiên có hơn 500   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 ước số  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ì   . Dưới đây là một số ví dụ:  bạn luôn có thể sắp xếp chúng thành một hình tam giác  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   , người đã phát biểu rằng tổng các số nguyên liên tiếp bằng: Gauss  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ề   (hoặc   ) của một số   rất đơn giản: đó là   Ví dụ, 3 là ước của 18, vì chúng ta có thể nhân 3 với 6 để lại được 18. ước thừa số n, một số   có thể được nhân với một số nguyên   khác để lại ra   . j k n  Tuy nhiên, 5 không phải là ước của 18, vì không có số   nào nhân với 5 được 18. k  Theo định nghĩa, chúng ta cũng thu được một tính chất quan trọng: nếu   là ước của   vì nó có thể nhân với   để được   thì   cũng là ước của   vì nó có thể nhân với   để được  j n k n, k n j n.    (thực tế,   luôn có thể là 1 và   là   ). Bằng cách này, chúng ta có thể chắc chắn rằng một số   luôn có ít nhất hai ước   và  n j k j k n  Ngoài ra, nói cách khác,   . Vì vậy, ví dụ, 18/3 = 6 và phần còn lại là 0. số   là ước của số   nếu số dư của   bằng 0 j n n / j  Chúng ta có thể chính thức hóa khái niệm này tốt hơn bằng   nói rằng   là ước của   nếu   Nói cách khác, chúng ta có được thuộc tính thứ hai này:  số học mô-đun j n n % j = 0.  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à   Đ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. không thể có ước số nào của một số   lớn hơn   chứ không phải chính   . n n/2, n  Điều này là do một lần nữa, nếu   thì đó là vì   Do đó, cũng   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.  j \ n, j * k = n. k \ n.  Vì vậy, ví dụ, nếu   và ngược lại nếu   điều này có nghĩa là   nhỏ nhất chúng ta có thể sử dụng, ngoài 1, là 2, mang lại cho chúng ta   lớn nhất có thể,   (9 trong trường hợp của chúng tôi)   Những công việc này: j = 3, k = 6, j = 6, k = 3, j k n/2 .  đố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   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   điều này sẽ luôn cho chúng ta kết quả  n j > 2, k < n/2.  Cuối cùng,   Ví dụ: khi   một thừa số có thể   sẽ tạo ra một thừa số khác   Chúng ta sẽ thảo luận thêm về trường hợp này sau trong phần code. chỉ có một trường hợp mà   và   có thể bằng nhau: khi   là số chính phương. j k n n = 36, j = 6 k = 6.  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   , 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   . Go 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:   https://Gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true  Chúng ta tạo hàm chấp nhận số nguyên   và trả về một mảng số nguyên   , hàm này sẽ chứa các ước của chúng ta. Sau đó, chúng ta   các thừa số tầm thường, cụ thể là chính 1 và   . n out out n  Sau đó, chúng tôi bắt đầu lặp   từ 2 đến   (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   vì trong trường hợp   chẵn,   sẽ được thêm vào các ước của   lần lặp: đây là lý do tại sao chúng tôi dừng lại ở   chứ không phải   ). j n/2 n/2 n k = n/2 j = 2 j<n/2 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   , tăng tốc quá trình lên một chút. n  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   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   vào danh sách. Chúng ta cũng có thể thêm phần đối ứng của nó   vào danh sách, bằng cách tính   và sau đó chuyển sang phần tiếp theo   ; n%j==0 j k n/j j  Câu lệnh if thứ hai kiểm tra xem   có phải là số vuông hay không và vì vậy   là nghiệm của   . Nếu vậy, chỉ một ước số   sẽ được thêm vào   , vì vậy để tránh trùng lặp, sau đó thuật toán sẽ tiếp tục. n j n j out  Giả sử   : 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   nhận được   và   , do đó, tạo ra một bản sao. n = 36 out j = 6 k = n/j = 36/6 = 6  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   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   . jk out  Cụ thể về điểm thứ ba này, có hai trường hợp cần kiểm tra:   hay   . out[len(out)-1] == j 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   , 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. j = 7  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   . Lấy lại 36, ví dụ: n  Khi   , nó sẽ bằng giá trị cuối cùng được thêm vào trước căn bậc hai của   , 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. j = 9 n  Cuối cùng, chúng ta có thể chỉ cần   để có ước số của mình. return out   Á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   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   bằng phương trình Gauss và kiểm tra xem nó có bao nhiêu ước số. c tn  Nếu nó lớn hơn 500, chúng tôi sẽ trả về kết quả là   . tn   https://Gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go  Nhưng…có một nhược điểm!    bên cạnh việc trình bày các câu đố và bài toán,   . ProjectEuler.net thực sự là một dự án đáng yêu: 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,   . 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! 😅 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   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   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   và nó cũng chạy tối đa   vòng lặp; chúng ta có thể coi nó là một O(n). FindDivisor n n/2  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ì   trở thành đối số hoặc hàm của chúng ta và chúng ta chạy tối đa   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   , thật không may! tn n/2 giải pháp thời gian bậc hai  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

Read My Stories

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

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

About Author

BÌNH LUẬN

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI

Related Stories

85 Stories To Learn About Productivity Hacks

94 Stories To Learn About John Locke

178 Stories To Learn About Essay

61 Stories To Learn About Polotical Philosophy

85 Stories To Learn About Productivity Hacks

94 Stories To Learn About John Locke

178 Stories To Learn About Essay

61 Stories To Learn About Polotical Philosophy

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps