Алгоритм Флойда из решения задачи 9 из главы 12 может быть реализован с помощью класса IntSet следующим образом
11. Именно в этой постановке задача была предложена мной в качестве домашней контрольной работы по курсу разработки прикладных алгоритмов. Студенты, предложившие способ получить ответ за несколько минут компьютерного времени, получили нулевые баллы. Ответ «я бы поговорил с преподавателем статистики» получил половину максимального количества баллов, а лучшие ответы звучали так:
Числа 4..16 па игру не влияют, поэтому их можно отбросить. Карта выигрывает, если выбраны числа 1 и 2 (в произвольном порядке) до числа 3. Это происходит в том случае, если число 3 оказывается выбрано последним, что происходит в одном случае из трех. Поэтому вероятность выигрыша при случайном выборе составляет 1/3. Не давайте условиям задачи ввести себя в заблуждение. Не обязательно использовать компьютер только потому, что он есть.
12. В разделе 5.9 (глава 5 данной книги) рассказывается о книге Кери и га на и Пайка «Практика программирования». В разделе 6.8 их книги описан процесс тестирования программы с вероятностным поведением (аналогичная программа для той же задачи описана в разделе 15.3 главы 15).
Решения к главе 13
1. Алгоритм Флойда из решения задачи 9 из главы 12 может быть реализован с помощью класса IntSet следующим образом:
void genfloyd(int m, int maxval)
{ i nt *v = new int[m] ;
1ntSetSTL S(m. maxva1 ) : for (int j = maxval-m. j < maxval j++) { int t = bigrand() % (j + 1). int oldsize = S size() .
S.insert(t) .
if (S sizeO == oldsize) /it уже есть в S S insert(j) .}
S report(v ).
for (int i = 0. i < m, i+ +) cout << v[i] << " \n" .}
Когда значения m и maxvaL равны, элементы помещаются в набор в порядке возрастания, то есть мы получаем самый худший случай для двоичных деревьев поиска.
Опубликовал vovan666
April 17 2013 00:07:04 ·
0 Комментариев ·
6091 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
