не могу решить задачу на "хороший" массив
Задача:Рассмотрим массив из 5 чисел, каждое из которых представлено в двоичной системе счисления. Назовем массив хорошим, если его элементы можно переставить таким образом, что
каждый элемент (кроме первого) отличается от предыдущего ровно в одном бите.
Например, массив [1000, 0100, 1001, 0101, 1101] является хорошим, так как после перестановки
элементов можно получить массив [1000, 1001, 1101, 0101, 0100], где каждый элемент (кроме
первого) отличается от предыдущего ровно в одном бите.
Какой из следующих массивов является хорошим?
(a) [0000, 1010, 1001, 1101, 0111]
(b) [0000, 1010, 1110, 0101, 1011]
(c) [1001, 1010, 1011, 0011, 0111]
(d) [0000, 0100, 1100, 0010, 1011]
(e) [1010, 0110, 1001, 0101, 1101]
(f) [0010, 1010, 0101, 0011, 0111]
(g) [1000, 1100, 0010, 0110, 0101]
(h) [1000, 0100, 1110, 0001, 0111]
<помогите пожалуйста>
Ответы (2 шт):
самое очевидное и топорное решение - брать каждый массив и каждую его перестановку проверять на то, что он крассивый(напишите функцию проверки самостоятельно, там всё просто, если использовать операцию xor напимер)
Начните именно с функции проверки массива на красоту, дальше вы всё сами поймете. Хорошее решение пока раскрывать не буду)
Это в случае если вам нужна программа, а если программа не нужна то ответ ну ССССтыдно ССССпрашивать
Намекну, как проверить, что бинарные представления двух чисел отличаются ровно одним битом... Операция xor (^) дает в отличающемся бите 1. Значит,
z = x^y
Должно быть ненулевым и иметь ровно один бит.
Если вычислить z = z&(z-1), то это значение равно 0 тогда и только тогда, когда либо z равно 0, либо имеет ровно один установленный бит.
Так что проверяйте результат xor на нуль (т.е. не равны ли два числа... хотя в массивах таких и не наблюдается, но береженого Бог бережет), а потом применяйте к нему указанное вычисление и опять проверяйте на нуль.