Hướng dẫn xếp hàng không có 2 bạn nam nào cạnh nhau
Xét trường hợp có i học sinh nam trong n học sinh
Lớp có i học sinh nam và n - i học sinh nữ.
Để không có học sinh nam nào cạnh nhau thì ta sẽ xếp n - i học sinh nữ thành một hàng trước.
Và giữa n - i học sinh nữ này sẽ có n - i - 1 khoảng trống và thêm 2 khoảng trống ở đầu hàng và cuối hàng thì tất cả có n - i + 1 khoảng trống.
Ta sẽ xếp i học sinh nam vào n - i + 1 khoảng trống này.
Số cách xếp là (n - i + 1)Ci
Xét toàn bài
Với điều kiện như đề bài thì số học sinh nam có thể có là 1 cho đến n / 2 nếu n chẵn hoặc 1 cho đến (n + 1) / 2 nếu n lẻ.
Kết quả của bài toán sẽ là tổng của các trường hợp của i học sinh nam.
Cải tiến
Không hẳn là cải tiến mà mình chơi bẩn chút xíu. 
Viết code chạy trâu xong thì được một vài kết quả đầu như này:
2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764
Copy rồi paste lên google search thì sẽ ra dãy A000071.
Có công thức tổng quát là a[n] = fib(n) - 1
Vậy kết quả của bài toán này với đầu vào n là a[n - 2]. 
Giảm được từ O(n^2) xuống còn O(n). 
Bài này giống với topic cũ của bạn nè. Nhờ mod close topic cũ đi nha.
Xét N=2n, gọi số nam sinh là k thì đầu tiên xếp 2n-k nữ sinh thành một hàng, sau đó mỗi khoảng trống có thể xếp được một nam sinh, có 2n-k+1 khoảng trống (kể cả đầu và cuối hàng) nên số cách là C(2n-k+1, k), vậy số cách là F(2n) = sigma(k=1…n) C(2n-k+1, k) = sigma(k=0…n-1) C(2n-k+2, k+1)
Lập luận tương tự với N=2n+1, số cách là F(2n+1) = sigma(k=1…n+1) C(2n-k+2, k).
Lấy 1 + F(2n) cộng từng số hạng với F(2n+1) sẽ ra sigma(k=1…n+1) C(2n-k+3, k) (tam giác Pascal), hay F(2n+2) = F(2n) + F(2n+1) + 1.
Xét N = 2n-1 tương tự, suy ra pt F(n) = F(n-1) + F(n-2) + 1, với F(1) = 1 và F(2) = 2.
Thuần nhất hóa ta tính F(1) = 2, F(2) = 3 rồi cuối cùng trừ lại 1 là xong.
Giờ mới để ý giới hạn là 1000, hơi căng với bạn thớt.
Bài tương tự: Một cầu thang có n bậc, bạn có thể đi từng bậc hoặc một lần 2 bậc. Hỏi có bao nhiêu cách đi như vậy?
Kết quả là dãy Fibonacci 
F(n) = số cách xếp hàng n bạn trong đó số bạn nam từ 0 tới n, ko có 2 bạn nam nào cạnh nhau
F(n) chia làm 2 loại: loại 1 là bạn đứng cuối cùng là nữ, loại 2 là bạn đứng cuối là nam (và bạn đứng kế cuối phải là nữ). Trường hợp lớp học n bạn nam thì số cách là 0 ko tính :V
- số cách loại 1 chính là F(n-1) vì nếu ta bỏ bạn nữ cuối cùng, bây giờ lớp học còn n-1 bạn, và cũng có thể có từ 0 tới n-1 bạn nam (chỉ tới n-1 vì có 1 bạn nữ đứng cuối), vậy số cách này chính là F(n-1)
- số cách loại 2 chính là F(n-2) vì bỏ bạn nam đứng cuối ta biết bạn đứng kế cuối phải là nữ, nên bỏ 2 bạn cùng lúc cũng được :V Ban đầu số bạn nam là 1 tới n-1 (1 là vì có 1 bạn nam cuối cùng, chỉ tới n-1 vì n bạn nam thì số cách là 0 ko tính), bỏ 1 nam 1 nữ ta còn lớp học n-2 hs và có từ 0 tới n-2 bạn nam, hay số cách này chính là F(n-2)
vậy F(n) = F(n-1) + F(n-2) là dãy Fibonacci :V :V :V
trừ 1 là do lớp có ít nhất 1 bạn nam, vậy trừ 1 trường hợp lớp học toàn nữ là xong :V
F(1000) thì tính phép cộng cho số lớn cũng dễ mà :V
O(n^2) chứ vì mỗi phép tính là O(n) 
không phải O(1).
Dễ thấy Fibo(n-1) > Fibo(n-2) khi n >= 4 nên Fibo(n) > 2Fibo(n-2), hay Fibo(n) = Omega(sqrt(2)^n).
O(n) chứ a.
def sher(n):
f1 = f2 = 1
for i in range(n):
f2 += f1
f1 = f2 - f1
return f2 - 1
Nếu không code bằng Python/Java/C# thì mất thêm O(log10(fib(1000))) cộng số lớn nữa.
Thì do topic không có tag ngôn ngữ nào nên e mới nói vậy chứ. 
O(n) phép cộng mới đúng, còn mỗi phép tính vẫn là O(n).
Không phải cộng hai machine word là O(1), vậy cộng n cặp hai machine word là O gì
Cái này có 1 phép cộng thôi
def foo(n: int) -> int:
if n <= 0: raise ValueError
f1, f2 = 1, 1
for i in range(n):
f1, f2 = f1 + f2, f1
return f1 - 1cần gì f3 f1, f2 = f2, f1 + f2 là được rồi :V
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?