Пособие по практике программирования
Обратите внимание на алгоритм случайного
Обратите внимание на алгоритм случайного выбора элемента, когда число всех элементов нам неизвестно. В переменной nmatch подсчитывается количество совпадений при сканировании списка. Выражение
rand()
++nmatch == 0
увеличивает nmatch и является истинным с вероятностью 1/nmatch. Таким образом, первый подходящий элемент будет выбран с вероятностью 1, второй заменит его с вероятностью 1/2, третий заменит выбранный из предыдущих с вероятностью 1/3 и т. п. В каждый момент времени каждый из k просмотренных элементов будет выбран с вероятностью i/k.
Вначале мы устанавливаем prefix в стартовое значение, которое с гарантией присутствует в хэш-таблице. Первые найденные значения Suffix будут первыми словами документа, поскольку только они следуют за стартовым префиксом. После этого суффикс выбирается случайным образом. В цикле вызывается lookup для поиска в хэш-таблице элемента (множества суффиксов), соответствующего данному префиксу; после этого случайным образом выбирается один из суффиксов, он печатается, а префикс обновляется.
Если выбранный суффикс оказывается NONWORD, то все заканчивается, поскольку это означает, что мы достигли состояния, относящегося к концу введенного текста. Если суффикс не NONWORD, то мы его печатаем, а далее с помощью вызова memmove удаляем первое слово из префикса и делаем суффикс вторым словом нового префикса, после чего цикл повторяется.
Теперь все написанное можно свести воедино в функцию main, которая читает стандартный ввод и генерирует не более заданного количества слов:
