Tôi đã làm việc thông qua vấn đề Chuỗi Snapper và đến đây tìm kiếm giải thích về cách thuật toán twiddling bit mà tôi gặp phải trong các giải pháp đã làm việc. Tôi tìm thấy một số thông tin tốt nhưng nó vẫn còn cho tôi một thời gian tốt để tìm ra cho bản thân mình, là một chút noob.
Đây là nỗ lực của tôi trong việc giải thích thuật toán và cách tìm ra thuật toán. Nếu chúng ta liệt kê tất cả các khả năng có thể và trạng thái ON/OFF cho mỗi cá hồng trong một chuỗi, chúng ta sẽ thấy một mẫu. Với trường hợp thử nghiệm N = 3, K = 7 (3 cá hồng, 7 snaps), chúng ta thấy sức mạnh và ON bang/OFF cho mỗi cá cho mọi thứ k chụp:
1 2 3
0b:1 1 1.1 1.0 0.0 -> ON for n=1
0b:10 2 1.0 0.1 0.0
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2
0b:100 4 1.0 0.0 1.0
0b:101 5 1.1 1.0 1.0 -> ON for n=1
0b:110 6 1.0 0.1 0.1
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3
Các bóng đèn là khi tất cả cá hồng đang bật và nhận nguồn, hoặc khi chúng ta có k lần chụp thứ k kết quả là n 1s.Thậm chí đơn giản hơn, bóng đèn bật khi tất cả các thiết bị bật tắt được BẬT, vì tất cả chúng đều phải nhận nguồn điện để BẬT (và do đó là bóng đèn). Điều này có nghĩa cho mỗi k snaps, chúng ta cần n 1s. Hơn nữa, bạn có thể lưu ý rằng k là tất cả các số nhị phân 1 không chỉ cho k = 7 thỏa mãn n = 3, mà còn đối với k = 3, satisifes n = 2 và k = 1 có giá trị là n = 1. Hơn nữa, đối với n = 1 hoặc 2, chúng ta thấy rằng mọi số lượng snaps bật bóng đèn, n chữ số cuối của k luôn là 1. Chúng ta có thể cố gắng khái quát rằng tất cả ks thỏa mãn n snappers sẽ là số nhị phân kết thúc bằng n chữ số 1.
Chúng ta có thể sử dụng các biểu ghi nhận của một tấm áp phích sớm hơn 1 < < n - 1 luôn mang đến cho chúng tôi n chữ số nhị phân 1, hoặc trong trường hợp này, 1 < < 3-1 = 0b111. Nếu chúng ta xử lý chuỗi các snappers của chúng ta như là một số nhị phân trong đó mỗi chữ số đại diện cho on/off, và chúng ta muốn n chữ số của một, điều này cho chúng ta đại diện của chúng ta.
Bây giờ chúng tôi muốn tìm những trường hợp 1 < < n - 1 là tương đương với một số k kết thúc bằng chữ số n nhị phân trong tổng số 1, mà chúng tôi làm bằng cách thực hiện một Bitwise-và: k & (1 < < n - 1) để lấy n chữ số cuối của k, và sau đó so sánh số đó với 1 < < n - 1.
Tôi cho rằng kiểu suy nghĩ này tự nhiên hơn sau khi làm việc với các loại vấn đề này, nhưng nó vẫn đáng sợ với tôi và tôi nghi ngờ tôi sẽ tự mình đưa ra giải pháp như vậy!
Đây là giải pháp của tôi trong perl:
$tests = <>;
for (1..$tests) {
($n, $k) = split//, <>;
$m = 1 << $n - 1;
printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF';
}
để giúp bạn liên quan, thu hồi '10.000-1 = 9999', khoảng điều tương tự xảy ra trong hệ nhị phân – Anycorn
@aaa Thật vậy !. Nó có ý nghĩa hơn bây giờ. – srandpersonia
Tôi thích (k^(k + 1)) >> n –