Как решить такую задачу на булеву алгебру? Столкнулся с онлайн-тестом, есть некоторые непонятные для меня моменты в задаче.Какие утверждения справедливы для последовательности чисел, генерируемой алгоритмом? (только один ответ)for i = 0..2^k-1
output(i^(i>>1))
Где ^ - побитовый XOR
>> - сдвиг на один бит вправо
1. Следующее число всегда больше предыдущего
2. i-й бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i.
b_i = ( \sum_{j=0} ^ {i} a_i ) % 2
3. Битовое представление следующего числа отличается от предыдущего только в одном бите.
4. Без первого элемента последовательность совпадает со следующей:
seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq seq(2^{k-1})
seq(1) = 1
Что я могу и уже сделал:
1. Взял некое k и получил последовательность промежуточных результатов, чтобы посмотреть. Это занимает большое время, очевидно тут надо работать не руками.
2. Понимаю, что такое xor
3. Понимаю, что сдвиг на один бит вправо даёт деление по модулю 2
4. Погуглил по синтаксису секвенций из ответов - не нашёл.
Мои вопросы:
1. Не понимаю синтаксис описанных секвенций, в гугле не нашёл, видимо не могу составить верный запрос по теме.
2. Не понимаю как быстро описать правило результирующей последовательности. Очевидно, что расписывать всю таблицу истинности для некоего k и искать потом закоомерность глазами - не то, что ожидается, учитывая, что на решение отводится минимум минут.
3. Видимо что-то не совсем знаю про свойства XOR в сочетании со сдвигом и вычитанием.
Помогите, пожалуйста, разобраться с принципом решения.
P.S. Я не хочу пройти тест за ваш счёт, в следующий раз вопросы всё равно будут другие. Моя задача - изучить тему и освоить подход.
Как решить такую задачу на булеву алгебру? Столкнулся с онлайн-тестом, есть некоторые непонятные для меня моменты в задаче.Какие утверждения справедливы для последовательности чисел, генерируемой алгоритмом? (только один ответ)for i = 0..2^k-1
output(i^(i>>1))
Где ^ - побитовый XOR
>> - сдвиг на один бит вправо
1. Следующее число всегда больше предыдущего
2. i-й бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i.
b_i = ( \sum_{j=0} ^ {i} a_i ) % 2
3. Битовое представление следующего числа отличается от предыдущего только в одном бите.
4. Без первого элемента последовательность совпадает со следующей:
seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq seq(2^{k-1})
seq(1) = 1
Что я могу и уже сделал:
1. Взял некое k и получил последовательность промежуточных результатов, чтобы посмотреть. Это занимает большое время, очевидно тут надо работать не руками.
2. Понимаю, что такое xor
3. Понимаю, что сдвиг на один бит вправо даёт деление по модулю 2
4. Погуглил по синтаксису секвенций из ответов - не нашёл.
Мои вопросы:
1. Не понимаю синтаксис описанных секвенций, в гугле не нашёл, видимо не могу составить верный запрос по теме.
2. Не понимаю как быстро описать правило результирующей последовательности. Очевидно, что расписывать всю таблицу истинности для некоего k и искать потом закоомерность глазами - не то, что ожидается, учитывая, что на решение отводится минимум минут.
3. Видимо что-то не совсем знаю про свойства XOR в сочетании со сдвигом и вычитанием.
Помогите, пожалуйста, разобраться с принципом решения.
P.S. Я не хочу пройти тест за ваш счёт, в следующий раз вопросы всё равно будут другие. Моя задача - изучить тему и освоить подход.
output(i^(i>>1))
Где ^ - побитовый XOR
>> - сдвиг на один бит вправо
1. Следующее число всегда больше предыдущего
2. i-й бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i.
b_i = ( \sum_{j=0} ^ {i} a_i ) % 2
3. Битовое представление следующего числа отличается от предыдущего только в одном бите.
4. Без первого элемента последовательность совпадает со следующей:
seq(2^k)
seq(2^k) = seq(2^{k-1}) 2^k seq seq(2^{k-1})
seq(1) = 1
Что я могу и уже сделал:
1. Взял некое k и получил последовательность промежуточных результатов, чтобы посмотреть. Это занимает большое время, очевидно тут надо работать не руками.
2. Понимаю, что такое xor
3. Понимаю, что сдвиг на один бит вправо даёт деление по модулю 2
4. Погуглил по синтаксису секвенций из ответов - не нашёл.
Мои вопросы:
1. Не понимаю синтаксис описанных секвенций, в гугле не нашёл, видимо не могу составить верный запрос по теме.
2. Не понимаю как быстро описать правило результирующей последовательности. Очевидно, что расписывать всю таблицу истинности для некоего k и искать потом закоомерность глазами - не то, что ожидается, учитывая, что на решение отводится минимум минут.
3. Видимо что-то не совсем знаю про свойства XOR в сочетании со сдвигом и вычитанием.
Помогите, пожалуйста, разобраться с принципом решения.
P.S. Я не хочу пройти тест за ваш счёт, в следующий раз вопросы всё равно будут другие. Моя задача - изучить тему и освоить подход.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Давайте разбираться по порядку.
Утверждение 1: "Следующее число всегда больше предыдущего" - неверно. Примером может служить последовательность чисел 0, 1, 3, 2, 6, 4, 12, 7, 14, 8, 24, ...
Утверждение 2: "i-й бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i" - верно. Это свойство побитовой операции XOR.
Утверждение 3: "Битовое представление следующего числа отличается от предыдущего только в одном бите" - неверно. В этом алгоритме битовое представление следующего числа отличается от предыдущего числа в нескольких битах.
Утверждение 4: "Без первого элемента последовательность совпадает со следующей" - верно. Так как seq(2^k) = seq(2^{k-1}) 2^k seq seq(2^{k-1}) - это свойство побитовой операции XOR.
Таким образом, единственным правильным ответом на ваш вопрос является утверждение 2.