<< | к задаче | главная | печатать | обсудить(0 сообщений) >>
Задача: Вездесущий двоичный поиск...
Псевдокод: Листинг 4.1. Набросок программы двоичного поиска управление:
  1. initialize range to 0 n-1
  2. /* инициализируем диапазон 0 n-1 */
  3. loop
  4. /* цикл */
  5. { invariant: t mustbe in (range)}
  6. /* инвариант: число t должно быть в диапазоне range */
  7.  
  8. if range is empty
  9. break and report that t is not in array
  10. /* диапазон - пуст, завершение цикла
  11. и завершение программы неудачей */
  12.  
  13. compute m: the middle of the range
  14. /* находим m - середину диапазона range */
  15.  
  16. use m as a probe to shrink the range
  17. /* используем значение m для сужения диапазона */
  18.  
  19. if t is found during the shrinking process
  20. break and report its position
  21. /* если при этом находим t - завершаем цикл
  22. и возвращаем позицию t */

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.004042 секунд
Количество запросов к БД: 3, gzip: 2.7kb/7.5kb(65%)