Задача
Ним-сумма.Будем говорить, что числоnявляется ним-суммой чиселmиk(m$\oplus$k=n), если оно получается из чиселmиkпосле следующих преобразований. 1)mиkзаписываются в двоичной системе счисления
m = (ms...m1m0)2, k = (ks...k1k0)2
(меньшее
число дополняется спереди нулями).
2) Полученные наборы цифр как векторы складываются покомпонентно
по модулю 2:
(ms,..., m1, m0) + (ks,..., k1, k0) $\displaystyle \equiv$ (ns,..., n1, n0)(mod 2).
3) Набор цифр(ns,...,n1,n0) переводится в числоn:
(ns...n1n0)2 = n.
Например,4$\oplus$7 = 3, так как
4 = (100)2, 7 = (111)2, (1, 0, 0) + (1, 1, 1) $\displaystyle \equiv$ (0, 1, 1)(mod 2), (011)2 = 3.
Докажите, что ним-сумма удовлетворяет следующим свойствам:
а)m$\oplus$m= 0; б)m$\oplus$k=k$\oplus$m; в)(m$\oplus$t)$\oplus$k=m$\oplus$(t$\oplus$k);
г) еслиn$\ne$0 и| m1 $\displaystyle \oplus$ m2 $\displaystyle \oplus$...$\displaystyle \oplus$ ml = n, | (5.1) |
то найдется такой номерj(1$\leqslant$j$\leqslant$l), для которогоmj$\oplus$n<mj.
Решение
г) Пустьn= (ns...n1n0)2, гдеns= 1. Тогда у одного из чиселm1,m2, ...,mlвs-ом разряде также стоит единица. Еслиmj — одно из таких чисел, тоmj$\oplus$n<mj.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет