Mình xin phép ngừng đăng bài 1 thời gian vì sắp cuối năm rồi, lượng bài ngày càng nhiều mà thời gian ngày càng ít
Vì vậy, mình xin phép sẽ đăng các bài về kiến thức sau nhé, nhưng ít nhất phải đến hè
Cảm ơn các bạn!
Xin chào các bạn, hôm nay mình có bài tập này, thấy hay và cơ bản nên tôi sẽ chia sẻ các cách giải với các bạn
Bài tập này cũng cơ bản, nhưng mình muốn thêm vào để các bạn thấy tầm quan trọng của đọ phức tạp!
Đề bài: Cho trước 1 mảng độ lớn bằng n. Hãy tính toán tổng dãy con liên tiếp lớn nhất.
Đề bài này có thể sẽ đơn giản với 1 số người, nhưng việc thêm số âm vào khiến nó trở nên hay với thú vị hơn!
Từ giở, để dễ cho một số bạn chưa học về hàm thì sẽ có một số bài mình code luôn trong main nhé!
Hôm nay, mình sẽ trình bày 3 lời giải cho các bạn
Các ví dụ mình cho đều là số nguyên dương nhé, các bạn có thể thử với số âm =))))
LG1: Brute-force 💀💀💀
Thôi, khỏi trình bày nhiều nhé =))))
3 vòng lặp và chấm hết, ai cũng viết được
Code source:
3 vòng lặp nên đơn giản, O(n^3)
Không tối ưu lắm nhỉ??
LG2: Giảm thiểu 1 vòng lặp(Thêm 1 brain cells là nghĩ ra ý mà =))))
Nhiều bạn đã lập trình quen có thể thấy 1 vòng lặp không cần thiết trong LG1, là tạo thêm 1 vòng lặp sau khi tạo ra đoạn dãy con!
Code source:
Tuy nhiên, chưa đủ tối ưu với 1 vấn đề như thế này. Độ phức tạp 0(n^2)
LG3:
Để mình phân tích bài toán nhé
Đến 1 phần tử nào đó, các khả năng có thể là:
Chỉ có duy nhất phần tử đó trong 1 dãy con
Dãy con trước kết thúc ở k-1 và giờ thêm 1 phần tử nữa
Vì thế, dãy con ở k-1 cần là dãy con tổng lớn nhất thì tiếp tục tìm
Do đó, ta có lời giải tối ưu sau:
Vì chỉ lặp 1 lần nên độ phức tạp O(n)!
Với lời giải 1, thời gian sẽ trên 10s với n>=10^4, lời giải 2 thì 10^6, lời giải 3 thì 10^7 vẫn chạy tốt
Qua đó, ta hiểu được tầm quan trọng của độ phức tạp!!!!
Mong các bạn học được nhiều điều từ bài đọc này! Tuy nhiên, nếu có lỗi gì hoặc chưa hiểu thì bạn hãy cứ nhắn nhé! Mình sẵn sàng trả lời!
Trước hết, chúc mừng ngày cá tháng tư, tuy nhiên, blog này đều nói sự thật (Wait what??)
Như các bạn đã biết, tính toán và quá thời gian luôn là một vấn đề trong lập trình!
Vì vậy, hôm nay mình sẽ cố gắng giải thích cho các bạn phương pháp dùng các hàm tính lên các số lớn!
Như các bạn đã biết, long long và int chỉ có thể hỗ trợ đến một lượng chữ số nhất định
Tuy nhiên, có một loại biến mà có tính sử dụng rất tố, đó là string
Nếu như không thể cộng một cách bình thường, thì ta sẽ xử lý xâu và tính cộng, trừ có nhớ (Như hồi lớp 1 ý hihi=))))) sẽ xử lý được các số lớn
Hôm nay, mình sẽ chỉ làm cộng với trừ thôi nhé!
Nhưng lưu ý, đây chỉ là cách tôi viết, còn nếu các bạn có cách tối ưu hơn thì có thể chia sẻ nhé!
Đầu tiên, tôi sẽ nói về cộng
Cách để làm thì quay về tiểu học là hiểu ngay ý mà, cộng theo hàng là xong =)))))
Source code:(Có giải thích!)
Tương tự, sẽ có trừ:
Source code:
Mong các bạn học được nhiều điều từ bài đọc này! Tuy nhiên, nếu có lỗi gì hoặc chưa hiểu thì bạn hãy cứ nhắn nhé! Mình sẵn sàng trả lời!!!!!
Đề bài: Cho N ô vuông sắp xếp từ 1->N, và có chú ếch đang đứng ở ô đầu. Mỗi lượt, chú ếch có thể nhảy lên 1 hoặc 2 ô tiếp theo. Tìm số cách để chú ếch này đi đến ô thứ N.
P1: Phân tích
Với N=4, có các lời giải:
1->2->3->4
1->2->4
1->3->4
Với một số những người lập trình mới, đề bài này có thể khá là khê =))
Tuy nhiên, nếu nhìn 1 cách kỹ càng, sẽ dễ đặt câu hỏi là "Ủa, đây là dãy Fibonacci mà??"
Nếu bạn nghĩ thế, chúc mừng, bạn đã đúng!
P2: Làm thôi!
Mình tạo 2 lời giải nhé
LG1: Đệ quy
Cách này độ phức tạp 2^n, ko tối ưu lắm đâu nhé!
LG2: Quy hoạch động
Nếu bạn chưa biết, quy hoạch động là thuật toán thần thánh để giảm thiểu thời gian cần thiết cho 1 lời giản đệ quy!
Phương pháp này dùng để giải nếu phải tính đi tính lại các phần tử nhiều lần, thì mình tính sẵn phần tử và lưu nó vào trong 1 mảng
Nếu cần tính lại thì cách đệ quy sẽ tính lại, còn quy hoạch động thì có sẵn biến rồi
Code luôn nhé!
Độ phức tạp từ O(2^n) xuống O(n) rồi! Tối ưu nhỉ
* *Nếu bạn thấy bài đọc này hay, thì cảm ơn bạn đã đọc. Mong bạn học được thêm nhiều điều hữu ích! **
Bài cần làm: Cho 1 mảng có n phần tử, tìm số lớn thứ hai DUY NHẤT, nếu không có thì trả về -1, độ phức tạp cần là O(n)!
Lời giải 1: Đơn giản nhất, dùng sort! Viết luôn, khỏi giải thích nhé =))
Code source:
Tuy nhiên, dễ thấy đây là lời giải chưa tối ưu
Phức tạp thời gian: O(n*log(n))!
Lời giải 2: Tìm số lớn nhất rồi lại scan thêm lần nữa để tìm số nhỏ thứ nhì!
Ủa, nghe cứ sao sao ý nhỉ =)))
Thôi, đùa tí, code ở dưới này:
Có lẽ, lời giải này chưa đủ tối ưu nhỉ, cùng tính độ phức tạp nhé!
Mình đang đi qua mảng 2 lần, nên độ phức tạp là O(2n)! Chưa đủ nhỉ, phải tìm cách nữa thôi
Cách 3: Đi qua mảng 1 lần rồi cập nhật 2 biến lớn thứ nhất và nhì luôn!
Bằng cách này thì sẽ không bị lặp lại thêm 1 lần đi qua mảng nên sẽ tối ưu hơn, 2 lần lận so với cách 2 luôn nhé!
Tối ưu nhất luôn nhé!
Hmm, độ phức tạp O(n) rồi!
Yay, làm được rồi!
Mong bạn học được thêm nhiều qua bài đọc này, cảm ơn vì đã đọc nhé!