Python-сообщество

py.user.next
Это обычный бинарный поиск (в основе лежит принцип дихотомии). Максимальное количество шагов равно log2(1000) ~= 9.96

 >>> import math
>>> N=1000
>>> 1 << math.floor(math.log2(N))
512
>>> 

Отредактировано vic57 (Окт. 28, 2017 11:55:20)

> да ну?

Ты мне сейчас хочешь рассказать что он 488 не найдёт?

 rodegast@rodegast:~$ python3 ./game.py
500
<
250
>
375
>
437
>
468
>
483
>
490
<
487
>
488

Rodegast
Ты мне сейчас хочешь рассказать что он 488 не найдёт?

 def f(delta,val):
    summ = 0
    while delta:
        if summ < val: summ += delta
        elif summ > val: summ -= delta
        delta >>= 1
    return summ
d = 1000
out = {}
for i in range(440,450):
    s = f(d,i)
    if s != i: print('error',s,i)

 error 442 440
error 442 441
error 444 445
error 448 447
>>> 

> и не только

Тогда почему оно у меня все эти числа находит? Я наверное что-то нетак делаю…

Отредактировано Rodegast (Окт. 28, 2017 14:28:46)

Rodegast
Я наверное что-то нетак делаю…

http://python.su/forum/topic/33906/?page=1#post-185432

vic57
а для точности нахождения из множества 0…N начальное число должно быть
…
512

Отредактировано py.user.next (Окт. 28, 2017 14:49:40)

py.user.next
По условию границы равны 1 и 1000 включительно.
Медиана множества будет равна (1 + 1000) / 2 = 500.5.

Rodegast
if S > 1: S //= 2

vic57
по такому условию ряд в целых числах не сойдется