屑俺日記

☆ 思いつきの二分探索みたいなもの

argv[1] が正解、 argv[2]が最大値。
思ったほど簡単にはできなかった。

#!/usr/bin/env python
from sys import argv
ans = int(argv[1])
largest = int(argv[2])
last = 0
 
def mlarger(num):
  last = num
  return int(round(num/2.0))
 
def smaller(num):
  return int(num + last/2+1)
 
while largest != ans:
  print (largest, end=',')
  if largest >  ans:
    largest = mlarger(largest)
  elif largest < ans:
    largest = smaller(largest)
 
print (largest, 'is', ans)

$  for x in `seq 10`; do python3 div2.py3 $x 10; done
10,5,2,1 is 1
10,5,2 is 2
10,5,2,3 is 3
10,5,2,3,4 is 4
10,5 is 5
10,5,6 is 6
10,5,6,7 is 7
10,5,6,7,8 is 8
10,5,6,7,8,9 is 9
10 is 10

試した範囲内(1000)では一応たどり着くが、 後のほうはかなり非効率だったりする。

$ python3 div2.py3 29 30
30,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29 is 29

☆ もう少しまともなはず

手書きの何かはまだ必要なようだ。

#!/usr/bin/env python3
from sys import argv
from time import sleep
from math import ceil
 
ans = int(argv[1])
largest = int(argv[2])
 
mynum = 0
temp = largest
 
while mynum != ans:
# sleep(0.3)
 print(mynum,end=',')
 if mynum < ans:
   temp = int(ceil(temp / 2))
   mynum = mynum + temp
 elif mynum > ans:
   temp = int(ceil(temp / 2))
   mynum = mynum - temp 
 
print (mynum, ' is' , ans)

$ python3 two_div.py3 29 30
0,15,23,27,29  is 29

1000以下で試したが、探索の最大が11回だった。

$ for x in `seq 1000`
>  do python3 two_div.py3 $x 1000 |
>     awk -F, '{print NF, $NF}'
>  done | sort -nr | head
11 999  is 999
11 997  is 997
11 995  is 995
11 993  is 993
11 991  is 991
11 99  is 99
11 989  is 989
11 987  is 987
11 985  is 985
11 983  is 983

$ python3 two_div.py3 985 1000
0,500,750,875,938,970,986,978,982,984,985  is 985