Модифицированная система счисления

[NL0]

В модифицированной четверичной системе счисления все цифры, кроме последней, четные. Тем не менее, диапазон изменения цифр выбран так, что любое натуральное число можно представить в этой системе, причем единственным способом.
a) Найдите в этой системе счисления сумму $263+241+201$.
b) Сформулируйте алгоритм умножения на $16$ в этой системе счисления.

В этой системе счисления пусть будут цифры $a,b,c,d$, тогда любое число $x$ можно представить в виде $x=a\cdot 4^3+b\cdot 4^2+c\cdot 4^1+d$, где $a,b,c$ -- делятся на $2$, а $d$ не делится на $2$.

$263=64a+16b+4c+d$

$a$ может быть только $2$, иные четные числа не подойдут. $263-128=135$

$16b+4c+d=135$

А вот здесь уже неоднозначность, потому как какая-то из цифр окажется более, чем $4$.

[DeBill]

NL0
Мне кажется, Вы неправильно понимаете задачу: числа

NL0 в сообщении #1139637 писал(а):

$263+241+201$.

уже записаны в извращенной системе...
При этом: наименьшее двузначное - это 8, так что диапазон, видимо, от 0 до 7....

[iifat]

NL0 в сообщении #1139637 писал(а):

$263=64a+16b+4c+d$

Не понял. Как понимаю, $264_4=60$ и никакие ваши $a,b,c\dots$ ни при чём.
Подозреваю, надо поподробнее разобраться в этой системе счисления.
Опередили Ну да пусть будет.

[NL0]

Аа, понял. Но почему наименьшее двухзначное это будет $8$?

-- 23.07.2016, 16:10 --

iifat в сообщении #1139652 писал(а):

NL0 в сообщении #1139637 писал(а):

$263=64a+16b+4c+d$

Не понял. Как понимаю, $264_4=60$ и никакие ваши $a,b,c\dots$ ни при чём.
Подозреваю, надо поподробнее разобраться в этой системе счисления.
Опередили Ну да пусть будет.

Да, я очень хочу разобраться в этой системе счисления. А как Вы так перевели 264?
С чего лучше начать разбираться в ней. Числа из нее переводить в обычную?

[svv]

Поскольку $a,b,c$ чётные, $a\cdot 4^3+b\cdot 4^2+c\cdot 4^1$ делится не только на $4$, но и на $8$. Тогда приходится разрешить последней цифре $d=x\operatorname{mod}8$ принимать значения от $0$ до $7$. Итак, $x-d$ кратно $8$, тогда $y=\frac{x-d}{2}$ кратно $4$. Найдём его запись в обычной четверичной системе:
$y=\tilde a\cdot 4^3+\tilde b\cdot 4^2+\tilde c\cdot 4^1+\tilde d\cdot 4^0$
Из сказанного ясно, что $\tilde d=0$. Теперь разложение $x=2y+d$ в модифицированной системе можно найти так: умножим каждую цифру $y$ на 2 (что обеспечит чётность) и вместо последнего нуля напишем $d$.

Эта процедура описана не столько для того, чтобы её реально проделывать, сколько для того, чтобы пояснить смысл цифр, их диапазон, и убедиться в единственности результата, полученного таким способом.

[NL0]

Хорошо, спасибо. Но не ясно как именно ищутся $\tilde a, \tilde b, \tilde c$

Про диапазон от нуля до семи понял. А у остальных цифр какой диапазон, я в замешательстве....

[svv]

Так же, как Вы поступаете, когда число, записанное в десятичной системе, надо записать в другой. Я свёл «извращённую», как её DeBill назвал, четверичную систему к обычной четверичной, предполагая, что с обычной у Вас проблем нет.

Последняя цифра от $0$ до $7$. Остальные тоже, но только чётные (т.е. реально до $6$).

[NL0]

svv в сообщении #1139669 писал(а):

Так же, как Вы поступаете, когда число, записанное в десятичной системе, надо записать в другой. Я свёл «извращённую», как её DeBill назвал, четверичную систему к обычной четверичной, предполагая, что с обычной у Вас проблем нет.

Последняя цифра от $0$ до $7$. Остальные тоже, но только чётные (т.е. реально до $6$).

Да, с обычной четверичной, думаю, что у меня проблем нет, но однако я не очень понял как вот эти коэффициенты с волнами определять в обычной четверичной...

-- 23.07.2016, 17:27 --

$a =2\tilde a$ ?

-- 23.07.2016, 17:31 --

В общем случае мне пока что-то не ясно. Можно ли на каком-то конкретном примере посмотреть?

[svv]

Давайте, например, числа из Вашей задачи переведём в десятичную систему, а потом наоборот. Десятичные числа не помечаются никак, четверичные индексом $4$, а модифицированные четверичные индексом $4M$.
$4M\to 10$:
$263_{4M}=2\cdot 4^2+6\cdot 4+3=59$

$10\to 4M$:
$d=59\operatorname{mod}8=3$
$y=\frac{59-3}{2}=28{\color{magenta}=}130_4$
$x=2y+d=2\cdot 130_4+3=263_{4M}$
Если переход, обозначенный ${\color{magenta}=}$, непонятен, значит, всё-таки есть проблемы и с переходом между двумя «обычными» системами счисления.

[NL0]

Спасибо, теперь все понял, только вот как складывать числа в этой системе модифицированной не знаю, потому, сделаю так:

$263_{4M}+241_{4M}+201_{4M}=(2+2+2)\cdot 4^2+(6+4+0)4+3+1+1=141$.

$10\to 4M$:

$d=141\operatorname{mod}4=1$

$y=\frac{141-1}{2}=70=1012_4$

$x=2y+d=2\cdot 1012_4+1=2025_{4M}$

Правильно ли?

-- 23.07.2016, 18:24 --

А про второй пункт задачи, мне кажется, что проще число сначала перевести в десятичное, потом умножить на 16, а затем уже в извращенную систему! Подойдет такой алгоритм?)

[svv]

Простите, я в примере ошибся, число $d$ — это остаток от деления $x$ на $8$, а не $4$ (в первом моём «теоретическом» сообщении было правильно, а в примере я уже исправил). На результаты это не влияет, просто в варианте $d=x\operatorname{mod}8$ последняя цифра 4M-записи — это сразу $d$, а в варианте $d=x\operatorname{mod}4$ её ещё надо находить сложением (которое, правда, никогда не даёт переноса и потому простое).

NL0 в сообщении #1139696 писал(а):

Подойдет такой алгоритм?)

Результаты у Вас правильные. Вы сами можете проверить:
$2025_{4M}=2\cdot 4^3+0\cdot 4^2+2\cdot 4^1+5\cdot 4^0=141$
И с умножением на $16$, конечно, тоже всё получится.

Но идейное возражение такое: это точно не то, что имел в виду преподаватель или автор задачника. Имелось в виду, что Вы разработаете правила сложения и умножения на $16$ не выходя за пределы модифицированной системы...
Представьте, что компьютер хранит числа в двоичном виде, а все операции с ними делает, переводя их предварительно в десятичную, а результат потом обратно в двоичную. Как-то не очень, правда?

[NL0]

Хорошо спасибо, да, действительно, не очень так. Правильно ли я понимаю, что в модифицированной системе, каждая из первых трех цифр будет принимать значения $0,2,4,6$, а последняя $0,1,2,3,4,5,6,7$?

Попробую получить умножение на $16$.

$x_M=a\cdot 4^3+b\cdot 4^2+c\cdot 4^1+d$

$16x_M=a\cdot 4^5+b\cdot 4^4+c\cdot 4^3+d\cdot 4^2=1024a+256b+64c+16d=A$

$d=A\operatorname{mod}8=0$

$y=\frac{A-9}{2}$

$x=2y+d=A_{4M}$

Какой-то каламбур получился...

[Батороев]

NL0 в сообщении #1139799 писал(а):

Какой-то каламбур получился..

"Каламбур" получился от того, что Вы не досчитали до конца $y$.

Как мне видится, число без $d$ уже "отформатировано" под систему, поэтому эту часть можно смело умножать на $100_4$, слагаемое же $16d$ "отформатировать".

[svv]

NL0 в сообщении #1139799 писал(а):

Правильно ли я понимаю, что в модифицированной системе, каждая из первых трех цифр будет принимать значения $0,2,4,6$, а последняя $0,1,2,3,4,5,6,7$?

Да, правильно. Конечно, всего цифр в числе может быть и больше четырёх (да хоть сто; это же Вы для простоты взяли $a,b,c,d$), поэтому так: каждая цифра, кроме последней, может быть $0,2,4,6$. Что мы и видим в условии Вашей задачи.

По поводу алгоритма сложения. Он очень простой. Достаточно его сформулировать для двух чисел, потому что, умея складывать два числа, Вы умеете складывать сколько угодно. Складываете Вы в столбик. У Вас, собственно, только один вопрос: что делать, если сумма цифр слагаемых в каком-то разряде (и, возможно, ещё переноса из предыдущего разряда) будет больше восьми? В противном случае всё так же, как при обычном сложении. Иными словами, как делать перенос?

Я немного подскажу. Вот Ваш пример, который я записал столбиком:

Вам предлагается разгадать использованные здесь правила (собственно, одно правило переноса). Ну, и супержелательно — обосновать их.

[iifat]

Точнее говоря, два вопроса — там перенос из первого разряда чуть посложнее, поскольку переносить надо непременно чётное.