Задача 8.
Точки с целочисленными координатами из 1-го квадранта помечаются числами 0,1,2,... слева направо и снизу вверх таким образом, что очередной точке приписывается минимальное число, отсутствующее в вертикали и горизонтали, проходящей через точку. Первой помечается точка (0,0).
Написать программу, которая
1. По заданным координатам x и y, x>=0, y>=0, x,y- целые, определяет пометку точки.
2. По заданной координате x и пометке точки y, x>=0, y>=0, x, y - целые, определяет вторую координату точки.
|
Решение задачи 8.
Если рассмотреть битовые представления числа A[i,j], помечающего точку (i,j) и чисел i и j, то обнаруживается, что A[i,j]=i XOR j, откуда получается, что A[i,j] XOR i=j,
A[i,j] XOR j=i.
Покажем, что A[i,j]=i XOR j.
1. Число A[i,j]=i XOR j не встречалось еще ни в строке i, ни в столбце j. От противного: существует такое j', что i XOR j = i XOR j' => i XOR j XOR i = i XOR j' XOR i => j'=j;
2. Пусть существует такое k<i XOR j, что k=i XOR L = j XOR M, и k еще не встречалось в строке i и столбце j (напомним, что по предположению все остальные уже заполненные элементы равны i XOR j, поэтому L>j и M>i).
Тогда, так как M>i, то существует бит с номером t такой, что для любого R>t биты Mr и ir равны, t-ый бит Mt=1, it=0. Но так как j XOR M < j XOR i, то Jt=1.
Так как L>j и L XOR i=j XOR M, то L = j XOR M XOR i. Рассмотрим i XOR M. В силу вышесказанного для любого бита с номером R, R>t, (i XOR M)r=0, а (i XOR M)t=1.
При этом Jt=1, следовательно
(i XOR j XOR M)r = Jr для r>t и
(i XOR j XOR M)t = 0 для r=t,
то есть L<j ?! Противоречие.
|
