nedoPC.org

Electronics hobbyists community established in 2002
Atom Feed | View unanswered posts | View active topics It is currently 28 Mar 2024 03:58



Reply to topic  [ 62 posts ]  Go to page 1, 2, 3, 4, 5  Next
Определение чётности числа в уравновешенной троичной системе 
Author Message
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
В продолжение топика: http://www.nedopc.org/forum/viewtopic.php?t=44

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

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

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

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

_________________
Extreme Entertainment


16 Jan 2005 13:26
Profile
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
На практике дело обстоит следующим образом:

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

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

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

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

_________________
Extreme Entertainment


09 Feb 2005 02:42
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Mac Buster wrote:
На практике дело обстоит следующим образом:

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

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

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

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


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

_________________
:dj: https://mastodon.social/@Shaos


09 Feb 2005 22:16
Profile WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Code:
Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?

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

_________________
Extreme Entertainment


10 Feb 2005 04:38
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Mac Buster wrote:
Code:
Все таки проще за один проход узнать четное или нечетное кол-во ненулевых разрядов есть в числе и на основе этого сделать выводы о четности - или ты уже нашел исключение из этого правила?

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


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

_________________
:dj: https://mastodon.social/@Shaos


10 Feb 2005 07:17
Profile WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Можно и так :D

_________________
Extreme Entertainment


10 Feb 2005 07:40
Profile
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Обнаружил ещё один многопроходный способ определения, который очень похож на предложенный мной ранее. Заключается в последовательном сумммировании ненулевых разрядов исходного числа, а затем ненулевых разрядов полученной суммы до тех пор, пока не останется один разряд. Если в результате получается 0 - исходное число было чётным.

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

_________________
Extreme Entertainment


17 Nov 2005 21:59
Profile
God
User avatar

Joined: 29 Dec 2003 01:00
Posts: 1101
Location: Москва
Reply with quote
Post 
Mac Buster wrote:
Обнаружил ещё один многопроходный способ определения, который очень похож на предложенный мной ранее. Заключается в последовательном сумммировании ненулевых разрядов исходного числа, а затем ненулевых разрядов полученной суммы до тех пор, пока не останется один разряд. Если в результате получается 0 - исходное число было чётным.

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

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


18 Nov 2005 07:18
Profile ICQ WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Ни что. Это одно и тоже.

_________________
Extreme Entertainment


18 Nov 2005 10:41
Profile
God
User avatar

Joined: 29 Dec 2003 01:00
Posts: 1101
Location: Москва
Reply with quote
Post 
Mac Buster wrote:
Ни что. Это одно и тоже.

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


18 Nov 2005 12:37
Profile ICQ WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
CHRV wrote:
Ага и решается проблема нуля :)

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

_________________
Extreme Entertainment


18 Nov 2005 23:31
Profile
Admin
User avatar

Joined: 08 Jan 2003 23:22
Posts: 22409
Location: Silicon Valley
Reply with quote
Post 
Mac Buster wrote:
CHRV wrote:
Ага и решается проблема нуля :)

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


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

_________________
:dj: https://mastodon.social/@Shaos


18 Nov 2005 23:37
Profile WWW
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Shaos wrote:
Ну ноль вроде всегда четным считался ;)

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

_________________
Extreme Entertainment


19 Nov 2005 01:06
Profile
Maniac
User avatar

Joined: 29 Mar 2005 06:06
Posts: 304
Location: Krasnodar
Reply with quote
Post 
Mac Buster wrote:
Shaos wrote:
Ну ноль вроде всегда четным считался ;)

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


это в двоичной системе ноль относится к четным :D потму как третьего не дано :)


22 Nov 2005 00:09
Profile ICQ
Retired

Joined: 03 Aug 2003 22:37
Posts: 1474
Location: Moscow
Reply with quote
Post 
Shaos wrote:
Ну ноль вроде всегда четным считался ;)

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

_________________
Extreme Entertainment


16 Dec 2005 01:30
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 62 posts ]  Go to page 1, 2, 3, 4, 5  Next

Who is online

Users browsing this forum: No registered users and 10 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software.