Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 25.05.2008, 20:13
ZRCsoll

 
Сообщений: n/a

Да если просто применить бин. поиск, то будет находится не совсем то решение нужно чтобы выводилось число первое ну например если вводится q=2; то должно вывестись 10! а не факт что мы его найдём ну мы с помощью этого поиска можем найти не 10 а 14 и это тоже будет правильно по количеству нулей, но он не первый вот( а как находить наименьший или первый я что то не знаю((
  #12  
Старый 25.05.2008, 20:44
ZRCsoll

 
Сообщений: n/a

Спасибо большое за помощь разобрался с задачей получил АС)), но вот только всё равно не понятно как бин. поиском находить первый экземпляр в своём роде вот(
  #13  
Старый 25.05.2008, 23:38
cmd cmd вне форума
Пользователь

Отправить личное сообщение для cmd Посмотреть профиль Найти все сообщения от cmd
 
Регистрация: 10.12.2006
Адрес: VSTU[Volgograd]
Сообщений: 53

После бин поиска можно проверить 5 рядом стоящих чисел
  #14  
Старый 26.05.2008, 00:43
ZRCsoll

 
Сообщений: n/a

Да я можно сказать так и делал я просто вычитал mid- mid mod 5 это как раз и будет ответом!) Вопрос этот уже скорей не по задаче, а просто в реализ. ну в других задачах нужно искать бин. поиском и находить первого представителя своего рода, а как это сделать я не заню(( я умею просто в бин. поиске находить какого-нить любого представителя, но не заданного вот как можно найти 1-го может кто знает подскажите пожалуйста?
  #15  
Старый 26.05.2008, 00:54
гость

 
Сообщений: n/a

Нужно просто грамотно написать двоичный поиск. О такой вещи как 'инвариант' когда нибудь слышали?
Код:
if Q=0 then <рассмотреть случай Q=0>

l = 0; r = 1;
while f(r) < Q do r := r * 2;       { Ищем правую границу }

while r - l > 1 do begin
    { инвариант: f(l) < x, f(r) >= x. }
    mid := (l + r) div 2;
    if f(mid) < x then
        l := mid
    else
        r := mid;
    { Обратите внимание что инвариант по прежнему сохраняется,
       а величина r-l строго уменьшается }
end;

{ r = l+1;  f(l) < x, r(r) >= x }
if f(r) = Q then
    writeln(r)
else
    writeln('No solution');
  #16  
Старый 26.05.2008, 00:56
гость

 
Сообщений: n/a

Поправка: в коде выше в комментариях x заменить на Q
  #17  
Старый 26.05.2008, 03:32
ZRCsoll

 
Сообщений: n/a

Ну только слышал, но незнаю что это и как применять(
а что такое х и вобще зачем он нужен я честно не понял, и почему вы он может быть равен правой границе, а не левой или там всё равно?
  #18  
Старый 26.05.2008, 03:40
гость

 
Сообщений: n/a

x - опечатка. Замени все вхождения x на Q.

Инвариант 'f(l) < Q, f(r) >= Q' нужен для того чтобы найти самое первое n такое что f(n) = Q.
Если переписать код так чтобы всегда было f(l) <= Q, f(r) > Q, то тогда он будет искать самое последнее такое n.
  #19  
Старый 28.05.2008, 15:10
ZRCsoll

 
Сообщений: n/a

Спасибо большое разобрался вроде бы всё ясно
  #20  
Старый 21.03.2010, 18:44
Новичок

Отправить личное сообщение для 4uterok Посмотреть профиль Найти все сообщения от 4uterok
 
Регистрация: 13.12.2009
Сообщений: 8

спасибо, за идею...
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
количество букв? гость Сортировка и поиск 5 20.05.2008 09:46
Без 2-х нулей гость Задачи 14 10.05.2008 12:16
количество вариантов размещения шаров в корзинах BreakPoint Математические алгоритмы (другое) 10 11.07.2007 12:24
разместить максимальное количество кругов в прямоугольнике ibobak Задачи 2 01.03.2007 00:28
разместить максимальное количество кругов в прямоугольнике ibobak Вычислительная геометрия 1 25.02.2007 18:05