Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Hoán vị không có điểm cố định

Đếm số cách sắp xếp n phần tử sao cho không phần tử nào ở lại vị trí ban đầu.

Bạn sẽ học được gì

  • Biến một lập luận đếm thành công thức truy hồi
  • Lặp công thức truy hồi từ các trường hợp cơ sở
  • Xử lý trường hợp n = 0 và n = 1

Đề bài

Xem bản gốc (English)

Năm người bạn bỏ mũ vào một đống, rồi mỗi người lấy lại ngẫu nhiên một chiếc. Có bao nhiêu cách để không ai lấy đúng mũ của mình? Một cách sắp xếp n phần tử mà không phần tử nào ở lại vị trí cũ được gọi là hoán vị không có điểm cố định (derangement). Số cách như vậy lần lượt là 1, 0, 1, 2, 9, 44 và tuân theo công thức D(n) = (n − 1) × (D(n − 1) + D(n − 2)).

Hãy viết derangements(n).

Đầu vào

n: Số phần tử.

Đầu ra

Trả về số hoán vị không có điểm cố định của n phần tử. D(0) bằng 1 (cách sắp xếp rỗng không có phần tử nào có thể đứng yên) và D(1) bằng 0.

Ràng buộc

0 ≤ n ≤ 20

Ví dụ

Ví dụ 1
Đầu vào:
n = 3

Kết quả mong đợi:
expected = 2
Đầu vào:
long long n = 3;

Kết quả mong đợi:
long long expected = 2;
Đầu vào:
long n = 3;

Kết quả mong đợi:
long expected = 2;

Giải thích

Với các phần tử A, B, C, chỉ có BCA và CAB là làm mọi phần tử đổi chỗ, nên đáp án là 2.

Ví dụ 2
Đầu vào:
n = 4

Kết quả mong đợi:
expected = 9
Đầu vào:
long long n = 4;

Kết quả mong đợi:
long long expected = 9;
Đầu vào:
long n = 4;

Kết quả mong đợi:
long expected = 9;

Giải thích

D(4) = 3 × (D(3) + D(2)) = 3 × (2 + 1) = 9.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Bắt đầu từ D(0) = 1 và D(1) = 0.

Gợi ý 2

Mỗi giá trị tiếp theo dùng hai giá trị trước đó và n hiện tại.

Gợi ý 3

Tại mỗi thời điểm chỉ cần hai giá trị gần nhất.

Độ phức tạp mong đợi

thời gian O(n), bộ nhớ phụ O(1)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.