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