algorithm - Python while loop never stops even though it should -

-

i've been going through exercises book on algorithms (with emphasis on python), , strange behavior when try solve problem. exercise straightforward , goal generate random integer k range(n), , locate number through sequence of "yes / no" questions. following code works long n isn't large, when infinite loop. shouldn't happen because in worst case step_size equal 1 , position crawl towards value of k until position == k.

when print both step_size , position seems position isn't updating when gets large, i'm guessing has value getting approximated , truncated (this why tried explicitly cast long, may not in fact doing anything). minor parts of code unnecessary, wanted have work general n. ideas what's going on (you have increase n behavior i'm talking about)?

from random import randrange math import ceil  n = 10**15 k = randrange(n)  success = false step_size = ceil(n / 2.0) position = long(ceil(n / 2.0))  print(k)  while success == false:     if position == k:         success = true         print(str(int(position)) + ' value of k.')     elif k < position:         step_size = ceil(step_size / 2.0)         position -= step_size         print(step_size, position)     else:         step_size = ceil(step_size / 2.0)         position += step_size         print(step_size, position)

you need use position += long(step_size) , position -= long(step_size)

  if position == k:         success = true         print(str((position)) + ' value of k.')     elif k < position:         step_size = ceil(step_size / 2.0)         position -= long(step_size)         print(step_size, position,k)     else:         step_size = ceil(step_size / 2.0)         position += long(step_size)         print(step_size, position)

if don't position float not long.

with change n = 10 ** 200 value of:

11008769984569663730780658772914869218303604494435631537943840906720756507580926318660187453313745419228469341648307070867052432521026422402953409000922062458195678772749579263632191432518529106302726 11008769984569663730780658772914869218303604494435631537943840906720756507580926318660187453313745419228469341648307070867052432521026422402953409000922062458195678772749579263632191432518529106302726 value of k.

Comments

Post a Comment

Popular posts from this blog

yii2 - Yii 2 Running a Cron in the basic template -

-
i have seen instructions on running cron in advanced template, cant figure out how on basic template. have following controller in basic controllers folder. <?php namespace app\controllers; use yii\console\controller; /** * cron controller */ class croncontroller extends controller { public function actionindex() { echo "cron service runnning"; } public function actionmail($to) { echo "sending mail " . $to; } } i have navigated root of application , tried these comands yii cron php yii cron im getting unknown comand "cron" i know old question failed find actual answer this. if @ code yii exec file you'll notice requires /common/config/aliases.php file console/config/main.php. can naturally change these or copy on these advanced template. hope solves problem wanting same thing.
Read more

asp.net - 'System.Web.HttpContext' does not contain a definition for 'GetOwinContext' Mystery -

-
i realize question might seem trivial some, it's these types of things find myself fighting quite bit , want make sense of despite seeming losing battle in .net (for me anyway). so, if following: using system.web; ... applicationuser user = system.web.httpcontext.getowincontext().getusermanager<applicationusermanager>().findbyid(system.web.httpcontext.user.identity.getuserid()); that produces error in title , red getowincontext() , error cannot resolve symbol 'getowincontext()' however, if following (remove system.web in front of httpcontext ), works expected (or @ least no errors): using system.web; ... applicationuser user = httpcontext.getowincontext().getusermanager<applicationusermanager>().findbyid(system.web.httpcontext.user.identity.getuserid()); however, if (same line that's working using system.web commented out): //using system.web; ... applicationuser user = httpcontext.getowincontext().getusermana...
Read more

mercurial graft feature, can it copy? -

-
there new feature in mercurial 3, called 'graft' (graft local). job of moving change-set different branch. is there way "copy" change-set branch? i interested in in moving stuff qa branch production branch, still need code reside in qa. want copy. found , have tried few things, maybe it'll become clear more tinkering , reading... does have better way of 'cherry picking' change-sets move cross branch (or trunk)??? graft copies changesets, doesn't move them. hg graft (emphasis mine): this command uses mercurial's merge logic copy individual changes other branches without merging branches in history graph. known 'backporting' or 'cherry-picking' . default, graft copy user, date, , description source changesets.
Read more