О дихотомии
Mar. 27th, 2014 12:52 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
techworkСегодня наши пытерцы решили начать просвещать Казань :) на самом деле прикольно - народ в прострации.
Однако мне тут мысля пришла.
Пример загадано число до 1000. Согласно правилу дихотомии необходимо такое количество (X) итераций ответов да или нет, которое равно минимальному 2^X>значениt. Классика - первый курс ( зачем только надо было тащить этого мужика в Казань ???? :-/ ) .
Однако на самом деле это условие вполне можно нарушить и вот как.
Если на вопрос ответ уже ясен к моменту совершения операции его можно не задавать. Мы имеем дело не с какими то инопланетными числами , а с вполне земными. У них есть свойства. Если число до 1000 можно описать девятью свойствами то следовательно нам и понадобиться всего девять, а не десять операций. А теперь тадддаммм - большинство математических свойств чисел несовместимы. Например число не может быть одновременно простым и делиться на восемь. И т.д. Следовательно при правильном построении алгоритма на каждом узле ветвления в любой цепочке будет хотя бы один вопрос ответ на который из-за ограничений совместимости будет известен заранее. И следовательно его можно не задавать. А значит и решение будет за меньшее количество вопросов. :) Да Да - теоретики забыли о банальном - о том что большинство свойств чисел не совместимы. ;) Я конечно этого не сказал - сиграл в шланга - просто чтобы оживить гробовую обстановку лекции на которой большинство просто стеснялось задать вопрос. Я старался не мешать - сидел крепился, но под конец просто не выдержал - зал не смог ответить на простейшую "диллему заключённого" - бред дядюшки Неша. Чему вообще этот молодняк учат....
Однако мне тут мысля пришла.
Пример загадано число до 1000. Согласно правилу дихотомии необходимо такое количество (X) итераций ответов да или нет, которое равно минимальному 2^X>значениt. Классика - первый курс ( зачем только надо было тащить этого мужика в Казань ???? :-/ ) .
Однако на самом деле это условие вполне можно нарушить и вот как.
Если на вопрос ответ уже ясен к моменту совершения операции его можно не задавать. Мы имеем дело не с какими то инопланетными числами , а с вполне земными. У них есть свойства. Если число до 1000 можно описать девятью свойствами то следовательно нам и понадобиться всего девять, а не десять операций. А теперь тадддаммм - большинство математических свойств чисел несовместимы. Например число не может быть одновременно простым и делиться на восемь. И т.д. Следовательно при правильном построении алгоритма на каждом узле ветвления в любой цепочке будет хотя бы один вопрос ответ на который из-за ограничений совместимости будет известен заранее. И следовательно его можно не задавать. А значит и решение будет за меньшее количество вопросов. :) Да Да - теоретики забыли о банальном - о том что большинство свойств чисел не совместимы. ;) Я конечно этого не сказал - сиграл в шланга - просто чтобы оживить гробовую обстановку лекции на которой большинство просто стеснялось задать вопрос. Я старался не мешать - сидел крепился, но под конец просто не выдержал - зал не смог ответить на простейшую "диллему заключённого" - бред дядюшки Неша. Чему вообще этот молодняк учат....
