Определение чётности числа в уравновешенной троичной системе

Mac Buster · Post by **Mac Buster** » 16 Jan 2005 13:26

В продолжение топика: viewtopic.php?t=44

Mac Buster wrote:- Выдвинуто и проверено предположение о простом способе определения чётности числа в уравновешенной троичной систем счисления: чётное число содержит чётное количество ненулевых разрядов. На данный момент это предположение экспериментально подтвержено для всех чисел в диапазоне от 1 до 172 миллионов.

Сформулировано математическое доказательство достоверности данного предположения. На человеческом языке оно звучит примерно таким образом:

- Сумма и разность чётного количества нечётных чисел в результате представляет собой чётное число.

- Если при подсчёте количества ненулевых разрядов числа записанного в уравновешенной троичной системе счисления основанной на ряду степеней нечётного числа (1,3,9,27 и т.д.) получается чётное число, то и само исходное число является чётным.

Mac Buster · Post by **Mac Buster** » 09 Feb 2005 02:42

На практике дело обстоит следующим образом:

а) берём произвольное n-разрядное число записанное в троичной уравновешенной системе счисления

б) считаем количество ненулевых разрядов в числе

в) считаем количество ненуневых разрядов в полученном на предыдущем шаге числе, до тех пор, пока получаемое количество не станет 2-х разрядным (при представлении в уравновешенной троичной системе), другими словами: пока оно не станет меньше +5, но больше -5

г) если оба разряда нулевые - исходное число было 0, если только один разряд нулевой - исходное число нечётное, иначе - исходное число чётное

Shaos · Post by **Shaos** » 09 Feb 2005 22:16

Mac Buster wrote:На практике дело обстоит следующим образом:

а) берём произвольное n-разрядное число записанное в троичной уравновешенной системе счисления

б) считаем количество ненулевых разрядов в числе

в) считаем количество ненуневых разрядов в полученном на предыдущем шаге числе, до тех пор, пока получаемое количество не станет 2-х разрядным (при представлении в уравновешенной троичной системе), другими словами: пока оно не станет меньше +5, но больше -5

г) если оба разряда нулевые - исходное число было 0, если только один разряд нулевой - исходное число нечётное, иначе - исходное число чётное

Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?

Mac Buster · Post by **Mac Buster** » 10 Feb 2005 04:38

Code: Select all

Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?

Нет, исключений не обнаружил. Только подумал что раз вся логика троичная, то надо сократить информацию о количестве ненулевых разрядов. Вот как раз до двух троичных разрядов это дело и можно сократить

Shaos · Post by **Shaos** » 10 Feb 2005 07:17

Mac Buster wrote:
Code: Select all
Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?
Нет, исключений не обнаружил. Только подумал что раз вся логика троичная, то надо сократить информацию о количестве ненулевых разрядов. Вот как раз до двух троичных разрядов это дело и можно сократить

Дык считать надо не так, а вот как (анализируемое число в аккумуляторе):
1. обнулить переменную четности
2. если младший трит ноль, то идти на 5
3. если переменная 0, то записать в нее +1 и идти на 5
4. если переменная +1, то записать в нее 0 и идти на 5
5. сдвинуть аккумулятор вправо с обнулением старшего трита
6. если аккумулятор не ноль, то идти на 1
После не более чем N итераций (где N - разрядность аккумулятора) в переменной четности будет хранится 0 - если число в аккумуляторе было четное и +1 - если нечетное.

Mac Buster · Post by **Mac Buster** » 10 Feb 2005 07:40

Можно и так

Mac Buster · Post by **Mac Buster** » 17 Nov 2005 21:59

Обнаружил ещё один многопроходный способ определения, который очень похож на предложенный мной ранее. Заключается в последовательном сумммировании ненулевых разрядов исходного числа, а затем ненулевых разрядов полученной суммы до тех пор, пока не останется один разряд. Если в результате получается 0 - исходное число было чётным.

Недостатки по отношению к моему методу - не позволяет определить было ли исходное число равно нулю. Точнее, считается, что нуль - чётное число.

CHRV · Post by **CHRV** » 18 Nov 2005 07:18

Mac Buster wrote:Обнаружил ещё один многопроходный способ определения, который очень похож на предложенный мной ранее. Заключается в последовательном сумммировании ненулевых разрядов исходного числа, а затем ненулевых разрядов полученной суммы до тех пор, пока не останется один разряд. Если в результате получается 0 - исходное число было чётным.

Недостатки по отношению к моему методу - не позволяет определить было ли исходное число равно нулю. Точнее, считается, что нуль - чётное число.

А что мешает суммировать все разряды ?

Mac Buster · Post by **Mac Buster** » 18 Nov 2005 10:41

Ни что. Это одно и тоже.

CHRV · Post by **CHRV** » 18 Nov 2005 12:37

Mac Buster wrote:Ни что. Это одно и тоже.

Ага и решается проблема нуля

Mac Buster · Post by **Mac Buster** » 18 Nov 2005 23:31

CHRV wrote:Ага и решается проблема нуля

Каким образом ? В результате выполнения получается всего два варианта: 1 (нечетное) и 0 (четное). А у меня три варианта: -1 (нечетное), 0 (нуль) и +1 (четное).

Shaos · Post by **Shaos** » 18 Nov 2005 23:37

Mac Buster wrote:
CHRV wrote:Ага и решается проблема нуля
Каким образом ? В результате выполнения получается всего два варианта: 1 (нечетное) и 0 (четное). А у меня три варианта: -1 (нечетное), 0 (нуль) и +1 (четное).

Ну ноль вроде всегда четным считался

Mac Buster · Post by **Mac Buster** » 19 Nov 2005 01:06

Shaos wrote:Ну ноль вроде всегда четным считался

Не у всех

Читал литературу, где нуль не относился ни к четным ни к нечетным числам.

Ronin · Post by **Ronin** » 22 Nov 2005 00:09

Mac Buster wrote:
Shaos wrote:Ну ноль вроде всегда четным считался
Не у всех Читал литературу, где нуль не относился ни к четным ни к нечетным числам.

это в двоичной системе ноль относится к четным

потму как третьего не дано

Mac Buster · Post by **Mac Buster** » 16 Dec 2005 01:30

Shaos wrote:Ну ноль вроде всегда четным считался

Даже в зарубежной литературе его выделяют. Открываем книжку "Функциональное программирование", первую же главу первой части. И что же мы там видим ?