Tổng các số lẻ Python codewars

Hôm qua, tôi đã tìm thấy một vấn đề hay trong codewars. com. dành cho những bạn chưa biết, lập trình viên là một nền tảng để rèn luyện kỹ năng lập trình của bạn, giải quyết các vấn đề lập trình bằng cách sử dụng một số loại ngôn ngữ lập trình khác nhau. Đó là một bài tập tốt cho những bạn mơ ước trở thành kỹ sư phần mềm

Được rồi, hãy quay lại cuộc thảo luận chính của chúng ta. Các thử thách về mật mã [các nhà viết mã gọi nó là “kata”] mà tôi tìm thấy có tên là “Row of The Odd Triangle”

Hàng tam giác lẻ

Codewars là nơi các nhà phát triển đạt được thành thạo mã thông qua thử thách. Luyện tập kata trong võ đường và đạt đến…

www. chiến mã. com

Trong bài toán này, chúng ta được cho một tam giác gồm các số lẻ liên tiếp. Tam giác như hình bên dưới được gọi là tam giác có các số lẻ liên tiếp

tam giác và hệ thống chỉ số

Thử thách là chúng ta được yêu cầu tìm ra hàng của tam giác nếu biết chỉ số [trong bài toán này, chỉ số của tam giác bắt đầu từ 1, không phải 0]. giả sử chúng ta được chỉ số = 1. sau đó, chúng ta phải sản xuất đầu ra [1]. nếu chúng tôi được cung cấp chỉ số = 2, thì chúng tôi sẽ tạo đầu ra [3, 5], v.v. [vui lòng đọc hướng dẫn câu hỏi chi tiết hơn trong liên kết ở trên]. đây đại khái là cách mã của chúng tôi hoạt động

odd_row[1]  ==  [1]
odd_row[2]  ==  [3, 5]
odd_row[3]  ==  [7, 9, 11]

Vấn đề trên cũng giải thích rằng một trong những điều quan trọng nhất cần lưu ý là mã chúng ta tạo phải đủ tối ưu để xử lý đầu vào ở dạng số rất lớn. Làm thế nào để giải quyết vấn đề này ?

Nếu để ý kĩ các em sẽ thấy độ dài một hàng trong tam giác bằng chỉ số của hàng đó. ví dụ, độ dài của dòng thứ 3 là 3. cũng như các dòng khác. số phần tử của hàng thứ 7 là 7, số phần tử của hàng thứ 8 là 8, số phần tử của hàng thứ 9 là 9, v.v.

Hãy lưu thông tin này trước. những gì chúng ta cần làm bây giờ là tạo ra các số lẻ sẽ được đặt trong tam giác trên. Làm thế nào để tạo ra số lẻ? . nếu chúng ta bắt đầu đếm liên tục từ số một và cộng với 2, thì mọi số chúng ta tạo ra đều là số lẻ. theo cách này, chúng ta có thể tạo ra các số 1, 3, 5, 7, 9, v.v. Một sự thật khác là sự khác biệt giữa phần tử cuối cùng trong hàng thứ n và phần tử đầu tiên của hàng thứ [n+1] là 2. ví dụ, sự khác biệt giữa phần tử cuối cùng trong hàng thứ 2 và phần tử đầu tiên của hàng thứ 3 là 2

từ đây chúng ta có thể nhận được 2 thông tin quan trọng

1. khoảng cách giữa các phần tử gần nhau nhất trong cùng một hàng là 2
2. khoảng cách giữa phần tử cuối cùng của một hàng và phần tử đầu tiên của hàng tiếp theo là 2. nói cách khác, khoảng cách giữa phần tử cuối cùng của hàng thứ n và phần tử đầu tiên của hàng thứ n+1 là 2

Vì vậy, nếu muốn tạo một danh sách/mảng chứa các số lẻ, chúng ta chỉ cần thực hiện lặp đi lặp lại phép cộng giữa các số 1 và 2. Nếu chúng ta muốn tạo ra 3 số lẻ đầu tiên thì đây là cách thực hiện thuật toán sử dụng python

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

câu hỏi bây giờ là, làm thế nào để chúng ta tạo một hình tam giác giống như một vấn đề được mô tả ở trên?

quy trình chúng ta cần làm tương tự như quy trình trên. chúng ta cần tạo một danh sách/mảng chứa các số lẻ và chúng ta áp dụng quy trình này cho tất cả các hàng trong tam giác bằng vòng lặp for. sự khác biệt là, trong trường hợp này, chúng ta phải đặt lại giá trị row_temp thành một danh sách/mảng trống mỗi khi quá trình tạo số lẻ kết thúc trên một hàng. điều này cần được thực hiện để giá trị ở hàng trước không nằm ở hàng hiện tại. nếu chúng ta không làm điều đó, thì tam giác chúng ta tạo ra sẽ như thế này

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

trong quá trình này, chúng tôi sử dụng 2 lần quy trình lặp bằng cách sử dụng

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

2. trong quy trình đầu tiên, chúng tôi lặp lại nhiều giá trị như chỉ số do vấn đề đưa ra [hãy gọi nó là

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

0], vì vậy chúng tôi có thể viết nó là

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

1. trong khi đó, trong quy trình thứ hai, chúng tôi lặp lại

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

2 lần, trong đó

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

2 cho biết chúng tôi đang ở dòng nào. Nói một cách đơn giản, trong thuật toán này, chúng tôi muốn nói rằng đối với dòng thứ i, độ dài của dòng cũng phải là

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

2. Chúng tôi thực hiện bước này theo thông tin chúng tôi có được ở đầu bài viết này. Nếu chúng ta áp dụng thuật toán trên bằng python, chúng ta sẽ tìm thấy giải pháp sau

________số 8

Chúng ta xong rồi. đoạn mã trên có thể giải quyết vấn đề codewars ở trên. tuy nhiên, mã chỉ hoạt động tốt đối với đầu vào nhỏ. tại sao ?

Đối với những bạn đã khá quen thuộc với các thuật toán và cấu trúc dữ liệu, bạn có thể quen thuộc với thuật ngữ big-O notation. Ký hiệu này cho thấy độ phức tạp về thời gian của một thuật toán. về độ phức tạp của thời gian, ký hiệu Big-O cho biết mức độ ảnh hưởng của kích thước đầu vào đối với tốc độ của thuật toán của chúng tôi. Ký hiệu Big-O cho thuật toán tôi đã viết ở trên là O[n²]. nghĩa là, khi kích thước đầu vào tăng lên, thời gian mà thuật toán này yêu cầu sẽ tăng theo phương trình bậc hai. đây là tác dụng của vòng lặp lồng nhau mà chúng ta làm ở thuật toán trên [có lẽ mình sẽ nói sâu về vấn đề này ở bài sau]

Biểu đồ độ phức tạp thời gian của thuật toán của chúng tôi

Biểu đồ trên minh họa cách kích thước đầu vào ảnh hưởng đến thuật toán chúng tôi đã viết trước đó. Dựa trên biểu đồ trên, chúng tôi biết rằng thuật toán rất kém hiệu quả. Vì vậy, chúng ta cần một giải pháp tốt hơn

Một giải pháp tốt hơn

Yếu tố khiến thuật toán trước hoạt động kém hiệu quả là có quá nhiều quá trình lặp được thực hiện. Để tránh điều đó, hãy thử giải bài toán trên bằng phương pháp toán học. Đầu tiên, hãy mô tả rõ hơn các điều kiện của bài toán trên

chúng ta được cho một bài toán dạng tam giác chứa tập hợp các số lẻ [xem hình minh họa ở trên]. Sau đó, chúng ta được yêu cầu xác định tất cả các số có trong một cột trong tam giác, theo đúng thứ tự và thứ tự. và quan trọng nhất là thuật toán mình làm phải chạy tốt cho đầu vào lớn

Để giải bài toán này ta chỉ cần tìm cách đếm phần tử đầu tiên ở mỗi hàng trong tam giác. tại sao chúng ta chỉ cần phần tử đầu tiên? . ví dụ, chúng ta biết rằng phần tử đầu tiên trong hàng thứ ba là 7. từ mô tả trước chúng ta cũng biết rằng có nhiều phần tử ở hàng thứ ba là 3. Do đó, các phần tử ở hàng thứ ba là 7,

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

5 hoặc

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

6. Một ví dụ khác là hàng thứ 5. phần tử đầu tiên của hàng thứ 5 là 21. vì hàng thứ 5 có 5 phần tử nên tất cả các phần tử của hàng thứ 5 là

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

7 hoặc

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

8. Vì vậy, nếu ta đã biết phần tử đầu tiên của một hàng tam giác thì việc biết các phần tử khác trong hàng đó không khó. đơn giản, phải không?

Công thức phái sinh

Hãy cùng xem hình minh họa bên dưới

Dựa vào minh họa trên ta nhận thấy như sau

1. chỉ có 1 phần tử ở hàng đầu tiên, đó là 1
2. phần tử đầu tiên của hàng thứ 2 là 1+2 = 3 [phần tử cuối cùng của hàng đầu tiên được thêm bởi 2]
3. phần tử đầu tiên của hàng thứ 3 là 5+2 = 7 [phần tử cuối cùng của hàng thứ 2 — là 5 — cộng 2]
4. phần tử đầu tiên của hàng thứ 4 là 13+2 = 15[phần tử cuối cùng của hàng thứ 3 — là 13 — cộng 2]

nếu chúng ta biểu diễn phần tử đầu tiên của hàng thứ n là a_n và phần tử cuối cùng của hàng thứ n là z_n, thì bằng cách làm theo mẫu trên, chúng ta có thể thấy rằng

bởi vì mọi khoảng cách giữa các phần tử gần nhất trong một hàng là 2 và độ dài của hàng thứ n là n, khi đó

theo cách đó, chúng ta có thể chỉ ra mối quan hệ của mỗi hàng trong tam giác như

áp dụng các quy tắc tương tự, chúng ta có thể tạo ra công thức sau

nó giống như một hàm đệ quy. thật dễ dàng, phải không?

Bây giờ những gì chúng ta phải làm là sắp xếp công thức trên để nó tạo thành một hàm a_n chỉ phụ thuộc vào biến độc lập n

từ các lớp trung học, bạn biết rằng 1+2+3+4+…+n bằng n*[n+1]/2. thì trong trường hợp này, tổng của các số hạng trên bằng n*[n-1]/2

được rồi, đây là công thức cuối cùng chúng ta có. với công thức này, chúng ta có thể tìm thấy phần tử đầu tiên của mỗi hàng trong tam giác. ví dụ: phần tử đầu tiên của hàng đầu tiên [a_1] là 1+1*[1–1] = 1. phần tử đầu tiên của hàng thứ hai là 1+2*[2–1] = 3. phần tử đầu tiên của hàng thứ ba là 1+3 *[3–1] = 7, v.v.

Xác định phần tử khác của một hàng

như tôi đã đề cập trước đó, với công thức trên, chúng ta cũng có thể tìm ra các yếu tố khác trong hàng liên quan. Nhưng bằng cách nào?

Hình trên giải thích rằng khoảng cách giữa 2 phần tử gần nhau nhất trong một hàng là 2. bởi vì chúng ta biết phần tử đầu tiên, với khái niệm này, chúng ta cũng có thể xác định phần tử thứ hai, thứ ba, v.v. giả sử phần tử đầu tiên của một hàng là b, sau đó phần tử thứ hai là b+2, phần tử thứ ba là b+2+2, phần tử thứ tư là b+2+2+2, v.v. Vì vậy, nói chung, chúng ta có thể kết luận rằng mỗi phần tử của một hàng trong tam giác trên có thể được biểu thị bằng

tuy nhiên, vì hệ thống lập chỉ mục trong hầu hết các ngôn ngữ lập trình [bao gồm java và python] bắt đầu từ 0, nên công thức trên cần được sửa đổi thành

Mọi thứ sẽ trở nên dễ dàng ngay bây giờ

tin tôi đi, khó khăn duy nhất trong vấn đề này là tìm công thức trên. nếu bạn đã tìm ra công thức trên thì bạn nên vui mừng vì vấn đề này sẽ dễ dàng hơn rất nhiều

Triển khai Java

khi bạn mở trang vấn đề này trong codewars và chọn

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

9 làm ngôn ngữ của mình, bạn sẽ nhận được mẫu mã sau

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

4

bây giờ, chúng ta có thể thực hiện công thức trước đó. như tôi đã đề cập ở phần đầu, hàng thứ n chứa n phần tử. chúng ta có thể tạo một mảng đại diện cho hàng này bằng cách gõ

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

0. Tiếp theo, chúng ta có thể gán các giá trị phù hợp cho từng phần tử trong hàng đó bằng công thức trên. đây là việc thực hiện

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

6

hãy xem, ngay cả khi sử dụng ngôn ngữ Java nổi tiếng với cú pháp phức tạp, chúng ta chỉ cần thêm 3 dòng mã. Phương pháp này hiệu quả hơn nhiều so với phương pháp trước. hiệu quả hơn về mặt cú pháp và cũng hiệu quả hơn về độ phức tạp của thời gian

Triển khai Python

khi bạn mở trang vấn đề này trong codewars và chọn

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

1 làm ngôn ngữ của mình, thì bạn sẽ thấy mẫu mã sau

row = []
a = 1
for i range[3]:
   row = row + [a]
   a = a + 2print[row]

8

chúng ta có thể triển khai cùng một phương thức bằng ngôn ngữ python, nhưng với cú pháp hơi khác một chút. Vì chúng tôi đang sử dụng python nổi tiếng với cú pháp đơn giản, nên chúng tôi có thể biểu diễn các hàng trong tam giác dưới dạng một mảng [danh sách python] bằng cách nhập

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

2. sau đó, chúng ta có thể sử dụng công thức trên để xử lý phép gán cho từng phần tử trong mảng kết quả. Đây là việc thực hiện

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

0

trên thực tế, nếu bạn nhìn vào các giải pháp được đưa ra bởi những người tham gia khác, bạn sẽ tìm thấy những giải pháp thậm chí còn tuyệt vời hơn

[1]
[[1], [3], [5]]
[[1], [3], [5], [7], [9], [11], [13]]

1

vâng, chỉ 1 dòng mã. Bằng cách sử dụng toán học, chúng ta có thể tiết kiệm một vài dòng mã và tăng hiệu quả của chương trình. nói về hiệu quả, còn độ phức tạp về thời gian của thuật toán trên thì sao? . tốt hơn nhiều phải không?