UVA 10077 - Почему это бинарный поиск? - PullRequest
Новая
       5

UVA 10077 - Почему это бинарный поиск?

0 голосов
/ 10 января 2020

Я пытаюсь поправиться в СР. Я сталкивался с этой проблемой - Ссылка . Хотя я имел в виду наивное решение BFS O (2 ^ N), оно, очевидно, дало мне TLE. 

string bfs(int t1,int t2)
{
    queue<pair<VII,string>> st;
    st.push({{0,1,1,2,1,1},"L"});
    st.push({{1,1,2,1,1,0},"R"});
    while(!st.empty())
    {
        VII u=st.front().first;
        string v=st.front().second;
        st.pop();
        //cout<<u[2]<<' '<<u[3]<<endl;
        if(u[2]==t1 && u[3]==t2)
        return v;
        st.push({{u[0],u[1],u[0]+u[2],u[1]+u[3],u[2],u[3]},v+"L"});
        st.push({{u[2],u[3],u[2]+u[4],u[3]+u[5],u[4],u[5]},v+"R"});
    }
    return "";
}

Выше приведен код, который я смог придумать. Я знаю, что есть решение для двоичного поиска, но я не мог понять, как разделить пространство поиска. Было бы здорово, если бы кто-нибудь мог объяснить мне интуицию, стоящую за этим. Спасибо!

1 Ответ

1 голос
/ 10 января 2020

Вы пытаетесь найти целевое число в бесконечном интервале lo=(0,1) hi=(1,0). Как сказано в PDF, вы можете найти середину интервала, выполнив mid = (lo[0]+hi[0])/(lo[1]+hi[1]). Решение go влево или вправо зависит от сравнения mid и вашего целевого числа. Если вы go ушли, вы излучаете L и начинаете поиск в интервале lo=lo hi=mid. Если вы go правы, вы излучаете R и начинаете поиск в интервале lo=mid hi=hi. Повторяйте до mid == target.

Вот быстрое решение в Python: 

from fractions import Fraction
def walk(lo, hi, tgt):
    mid = (lo[0] + hi[0], lo[1] + hi[1])
    fmid = Fraction(mid[0], mid[1])
    if tgt == fmid:
        return
    if tgt < fmid:
        yield 'L'
        yield from walk(lo, mid, tgt)
    else:
        yield 'R'
        yield from walk(mid, hi, tgt)

print(list(walk((0,1), (1,0), Fraction(878, 323))))
...