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!!!!!
its been quite a journey cp too hard for me i am quitting
gregson không làm được bài 5000 codeforces là không bằng tao rồi
tôi là nô lệ của 67 còn bạn là 3667
anh 7 là người 36 còn bạn là 67
Các bạn không biết rằng, thực ra AVX là một lời nói dối.
Các nhà sản xuất cho bạn biết là AVX là công cụ xử lý vector, nhưng thực ra có 1 bóng ma trong CPU đang biến đổi dữ liệu.
Mỗi một lần thực hiện lệnh AVX là một lần bạn gọi hồn, nên thực hiện nhiều lệnh quá có thể dẫn đến máy bị lạnh thấu xương.
Và các CPU thực ra càng nóng hoạt động sẽ càng nhanh. Nên trong những pha ép xung cực đỉnh, người ta phải dùng cồn (trừ tà) đun trên CPU để xua đuổi các cô hồn...
Nếu bạn không biết, các CPU của Intel và AMD không có tuổi so với MT6750. 9850X3D là con chip 8 nhân yếu nhất thế giới, còn MT6750 lưu dấu ấn mãi mãi trong lòng chúng ta...
Đến bây giờ chưa có công ty nào ngoài MediaTek biết cách sản xuất chip mạnh như MT6750 😭😭😭...
Đề 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! **