1. Чтобы показать, что переполнения не происходит, мы добавим к инварианту условия 0<=1<=п и -L<=u<n. В этом случае мы можем ограничить l+u. Аналогичные условия могут быть использованы, чтобы показать, что обращения к элементам за границами массива никогда не происходит. Мы можем формально определить высказывание mustbe(L, и) как x[l-l]<t и x[u+l]>t, если мы добавим фиктивные граничные элементы х[-1] и х[п], как это сделано в разделе 9.3 главы 9.
2. См. раздел 9.3 главы 9.
5. В качестве введения в эту открытую и широко известную математическую проблему можно прочитать статью Б. Ханеса (В. Hayes, On the ups and downs of hailstone numbers Scientific American, 1, 1984). Более детально проблема обсуждается н статье Лагариаса (J. С. Lagarias, The Зх+1 problem and its generalizations, American Mathematical Monthly, 1, 1985). На момент выхода этой книги составленная Лагарпасом библиография по указанной теме содержит 30 страниц, а на сайте http://www.research.att.com/~jcL/3x+l.html можно пайти сотни ссылок.
6. Процесс сходится, потому что на каждом шаге количество бобов в банке уменьшается на единицу. На каждом этапе может быть убрано только четное количество белых бобои (0 пли 2), поэтому их четность сохраняется. Последний оставшийся боб будет белым тогда и только тогда, когда в исходном состоянии количество белых бобов было нечетным.
7. Поскольку сегменты линий, формирующих лестницу, расположены по возрастанию ординаты, две линии, ограничивающие точку, могут быть найдены двоичным поиском. Лежащая в основе двоичного функция сравнения должна возвращать информацию о том, лежит ли точка выше данной прямой, ниже ее или непосредственно на ней. Как бы вы реализовали такую функцию?
8. См. раздел 9.3 гланы 9.
Опубликовал vovan666
April 17 2013 00:06:34 ·
0 Комментариев ·
3047 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
