Дело было в начале 80-х. Компания только что приобрела первые персональные компьютеры. Установив и настроив основные программы, я рекомендовал сотрудникам искать возможности автоматизации офисных задач с помощью новых машин. Фирма занималась опросами общественного мнения, и одна из сотрудниц предложила автоматизировать задачу выбора случайных представителей из списка избирательных участков. Поскольку решение задачи вручную требовало часа работы с таблицей случайных чисел, сотрудница предложила следующую программу:
На вход подается список названий участков и целое число т. На выходе должен получиться список из т случайно выбранных избирательных участков. В исходном списке обычно присутствует несколько сотен названий (каждое из которых представляет собой строку длиной не более десятка символов), а т обычно лежит в интервале 20..40.
Так представляла себе программу одна из пользователей. Хотите ли вы высказать какие-нибудь предложения по формулировке задачи до того, как мы попытаем ее реализовать программно?
Я ответил сотруднице, что это замечательная идея. Задача отлично подходила для автоматизации. Затем я отметил, что набрать несколько сотен имен, возможно, проще, чем работать с большой таблицей случайных чисел, но это все равно утомительное занятие, в процессе которого легко наделать ошибок. Да и вообще глупо вводить кучу данных, если все равно большая их часть использована не будет. Поэтому я предложил поставить задачу в альтернативной форме.
На вход программы подается два целых числа: тип, причем т<п. На выходе должен получаться список из т случайных целых чисел в диапазоне 0. .п-1 , причем никакое число не должно встретиться дважды. С точки зрения теории вероятностей, мы должны реализовать выбор без возвратау причем вероятность выбора всех элементов должна быть одинакова.
Для т = 20 и п = 200 программа должна выдать список из 20 чисел, который может начинаться, к примеру, так: 4,15,17,... Пользователь может выбрать 20 случайных названий из списка избирательных округов, в котором этих округов 200, отсчитывая их от начала списка и помечая 4, 15, 17-е и последующие. Числа на выходе должны быть отсортированы, потому что список на бумаге не пронумерован.
Эта спецификация была встречена с энтузиазмом со стороны потенциальных пользователей. После написания программы они получали бы возможность за несколько минут делать то, на что раньше требовался бы час.
Взгляните на задачу с другой стороны: как бы вы ее решили? Предположим, у вас есть функция bigrand(), возвращающая большое случайное целое число (много большее m и п) и функция randint(i, j), возвращающая случайное число из интервала i. ,j (с однородным распределением). Задача 1 посвящена реализации таких функций.
Опубликовал vovan666
April 17 2013 00:02:52 ·
0 Комментариев ·
3142 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.