Author |
Message |
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
В продолжение топика: http://www.nedopc.org/forum/viewtopic.php?t=44
Сформулировано математическое доказательство достоверности данного предположения. На человеческом языке оно звучит примерно таким образом:
- Сумма и разность чётного количества нечётных чисел в результате представляет собой чётное число.
- Если при подсчёте количества ненулевых разрядов числа записанного в уравновешенной троичной системе счисления основанной на ряду степеней нечётного числа (1,3,9,27 и т.д.) получается чётное число, то и само исходное число является чётным.
_________________ Extreme Entertainment
|
16 Jan 2005 13:26 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
На практике дело обстоит следующим образом:
а) берём произвольное n-разрядное число записанное в троичной уравновешенной системе счисления
б) считаем количество ненулевых разрядов в числе
в) считаем количество ненуневых разрядов в полученном на предыдущем шаге числе, до тех пор, пока получаемое количество не станет 2-х разрядным (при представлении в уравновешенной троичной системе), другими словами: пока оно не станет меньше +5, но больше -5
г) если оба разряда нулевые - исходное число было 0, если только один разряд нулевой - исходное число нечётное, иначе - исходное число чётное
_________________ Extreme Entertainment
|
09 Feb 2005 02:42 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22616 Location: Silicon Valley
|
Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?
|
09 Feb 2005 22:16 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Нет, исключений не обнаружил. Только подумал что раз вся логика троичная, то надо сократить информацию о количестве ненулевых разрядов. Вот как раз до двух троичных разрядов это дело и можно сократить
_________________ Extreme Entertainment
|
10 Feb 2005 04:38 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22616 Location: Silicon Valley
|
Дык считать надо не так, а вот как (анализируемое число в аккумуляторе): 1. обнулить переменную четности 2. если младший трит ноль, то идти на 5 3. если переменная 0, то записать в нее +1 и идти на 5 4. если переменная +1, то записать в нее 0 и идти на 5 5. сдвинуть аккумулятор вправо с обнулением старшего трита 6. если аккумулятор не ноль, то идти на 1 После не более чем N итераций (где N - разрядность аккумулятора) в переменной четности будет хранится 0 - если число в аккумуляторе было четное и +1 - если нечетное.
|
10 Feb 2005 07:17 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Можно и так
_________________ Extreme Entertainment
|
10 Feb 2005 07:40 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Обнаружил ещё один многопроходный способ определения, который очень похож на предложенный мной ранее. Заключается в последовательном сумммировании ненулевых разрядов исходного числа, а затем ненулевых разрядов полученной суммы до тех пор, пока не останется один разряд. Если в результате получается 0 - исходное число было чётным.
Недостатки по отношению к моему методу - не позволяет определить было ли исходное число равно нулю. Точнее, считается, что нуль - чётное число.
_________________ Extreme Entertainment
|
17 Nov 2005 21:59 |
|
|
CHRV
God
Joined: 29 Dec 2003 01:00 Posts: 1101 Location: Москва
|
А что мешает суммировать все разряды ?
|
18 Nov 2005 07:18 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Ни что. Это одно и тоже.
_________________ Extreme Entertainment
|
18 Nov 2005 10:41 |
|
|
CHRV
God
Joined: 29 Dec 2003 01:00 Posts: 1101 Location: Москва
|
Ага и решается проблема нуля
|
18 Nov 2005 12:37 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Каким образом ? В результате выполнения получается всего два варианта: 1 (нечетное) и 0 (четное). А у меня три варианта: -1 (нечетное), 0 (нуль) и +1 (четное).
_________________ Extreme Entertainment
|
18 Nov 2005 23:31 |
|
|
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 22616 Location: Silicon Valley
|
Ну ноль вроде всегда четным считался
|
18 Nov 2005 23:37 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Не у всех Читал литературу, где нуль не относился ни к четным ни к нечетным числам.
_________________ Extreme Entertainment
|
19 Nov 2005 01:06 |
|
|
Ronin
Maniac
Joined: 29 Mar 2005 06:06 Posts: 304 Location: Krasnodar
|
это в двоичной системе ноль относится к четным потму как третьего не дано
|
22 Nov 2005 00:09 |
|
|
Mac Buster
Retired
Joined: 03 Aug 2003 22:37 Posts: 1474 Location: Moscow
|
Даже в зарубежной литературе его выделяют. Открываем книжку "Функциональное программирование", первую же главу первой части. И что же мы там видим ?
_________________ Extreme Entertainment
|
16 Dec 2005 01:30 |
|
|