-{k-NliyiN

Здесь используется нормальная аппроксимация - известная кривая в форме колокола. На рис. 3.2 показан вывод программы 3.7 для 1000 экспериментов подбрасывания монеты по 32 раза. Дополнительные сведения о распределении Бернулли и нормальной аппроксимации можно найти в любом учебнике по теории вероятностей. Эти понятия вновь встретятся в главе 13. Пока остановимся на вычислениях, в которых используются числа и индексы массива для определения частоты выпаданий. Способность поддерживать этот вид операций - одно из основных достоинств массивов.

Программа 3.7 Имитация подбрасываний монеты

Если подбросить монету N раз, ожидается выпадение N/2 решек, но это число может быть любым в диапазоне от О до N. Данная программа выполняет эксперимент М раз, принимая аргументы М и N из командной строки. Она использует массив f для отслеживания частоты выпадений i решек для О < i < N, а затем распечатывает гистограмму результатов эксперимента. Каждые 10 выпаданий обозначаются одной звездочкой.

Основная операция программы - индексация массива по вычисляемым значениям - важный фактор эффективности многих вычислительных процедур.

#include <iostream.h> #include <stdlib.h> int heads 0

{ return randO < RAND MAX/2; } int main(int argc, char *argv[]) { int i, j, cnt; int N = atoi(argv[1]), M = atoi(argv[23); int *f = new int[N+13; for (j = 0; j <= N; j++) f[j] = 0; for (i = 0; i < M; i++, f[cnt]++) for (cnt = 0, j = 0; j <= N; j++) if (heads 0) cnt++; for (j = 0; j <= N; j++) {

if (f[j] == 0) cout

for (i =0; i < f[j3; i+=10) cout

cout endl;

РИСУНОК 3.2 ИМИТАЦИЯ ПОДБРАСЫВАНИЙ МОНЕТЫ

Эта таблица демонстрирует результат выполнения программы 3.7 при N=32 и М= 1000. Имитируется 1000 экспериментов подбрасывания монеты по 32 раза. Количество выпаданий решки аппроксимируется нормальной функцией распределения, график которой показан поверх данных.

*t if м

В программах 3.5 и 3.7 вычисляются индексы массива по имеющимся данным. В некотором смысле, когда используется вычисленное значение для доступа к массиву размером N, с помощью единственной операции обрабатывается N вероятностей. Это существенно повыщает эффективность. В дальнейщем будут рассматриваться алгоритмы, где массивы используются подобным же образом.

Массивы применяются для организации всего многообразия объектов, а не только целых чисел. В языке С++ можно объявлять массивы данных любых встроенных либо определяемых пользователем типов (другими словами, составных объектов, объявленных как структуры). Программа 3.8 иллюстрирует использование массива структур для точек на плоскости. Описание структуры рассматривалось в разделе 3.1. Кроме того, демонстрируется типовое использование массивов: организованное хранение данных при обеспечении быстрого доступа к ним в процессе вычислений.

Между прочим, программа 3.8 также интересна в качестве прототипа алгоритма проверки всех пар набора из Л элементов данных, в результате чего затрачивается время, пропорциональное N. В этой книге при любом использовании подобных алгоритмов изыскиваются усовершенствования, поскольку с увеличением значения 7V данное решение становится труднореализуемым. В разделе 3.7 демонстрируется использование составных структур данных для вычислений в линейном масштабе времени, соответствующих данному примеру.

Программа 3.8 Вычисление ближайшей точки

Эта программа демонстрирует использование массива структур и представляет типичный случай, когда элементы сохраняются в массиве для последующей обработки в процессе некоторых вычислений. Подсчитывается количество пар из N сгенерированных случайным образом точек на плоскости, соединяемых прямой, длина которой меньше d. При этом используется тип данных для точек, описанный в разделе 3.1. Время выполнения составляет O(N), поэтому программа не может применяться для больших значений N. Программа 3.20 обеспечивает более быстрое решение.

#include <inath.h> #include <iostream.h> #include <stdlib.h> #include Point.h float randFloatO

{ return 1.0* rand()/RAND MAX; } int main(int argc, char *argv[]) { float d = atof(argv[2]); int i, cnt = 0, N = atoi (argv[l] ) ; point *a = new point [N] ; for (i = 0; i < N; i++)

{ a[i].x = randFloatO; a[i].y = randFloatO; } for (i = 0; i < N; i++)

for (int j = i+1; j < N; j++)

if (distance(a[i], a[j]) < d) cnt++; cout cnt pairs within d endl;

Подобным образом можно создавать составные типы произвольной сложности: не только массивы структур, но и массивы массивов либо структур, содержащих массивы. Эти возможности будут подробно рассматриваться в разделе 3.7. Однако сначала

ознакомимся со связными списками (linked lists), которые служат главной альтернативой массивов при организации коллекций объектов.

Упражнения

о 3.10 Предположим, а объявлена как int а[99]. Определить содержимое массива после выполнения следующих двух операторов:

for (i = 0; i < 99; i++) a[i] = 98-i; for (i = 0; i < 99; i++) a[i] = a[a[i]];

3.11 Изменить реализацию рещета Эратосфена (программа 3.5) для использования массива (i) символов и (ii) разрядов. Определить влияние этих изменений на расход пространства памяти и времени, используемого программой.

О 3.12 С помощью рещета Эратосфена определить количество простых чисел, меньших Л, для N= 10, 10, 10 и 10*.

о 3.13 С помощью решета Эратосфена построить график зависимости jVot количества простых чисел, меньших N, для значений Л от 1 до 1000.

о 3.14 Стандартная библиотека С++ в качестве альтернативы массивам содержит тип данных Vector. Найти способ использования этого типа данных в своей системе и определить его влияние на время выполнения, если заменить в профамме 3.5 массив типом Vector.

3.15 Эмпирически определить эффект удаления проверки a[i] из внутреннего цикла программы 3.5 для jV= 10, 10, 10 и 10 и объяснить его.

О 3.16 Написать программу вычисления количества различных целых чисел, меньших 1000, которые встречаются в потоке ввода.

о 3.17 Написать программу, эмпирически определяющую количество случайных положительных целых, меньших 1000, генерацию которых можно ожидать перед получением повторного значения.

о 3.18 Написать программу, эмпирически определяющую количество случайных положительных целых, меньших 1000, генерацию которых можно ожидать перед получением каждого значения хотя бы один раз.

3.19 Изменить программу 3.7 для имитации случая, когда решка выпадает с вероятностью р. Выполнить 1000 попыток эксперимента с 32 подбрасываниями при р = 1/6 для получения вывода, который можно сравнить с рис. 3.2.

3.20 Изменить программу 3.7 для имитации случая, когда решка выпадает с вероятностью X/N. Выполнить 1000 попыток эксперимента с 32 подбрасываниями для получения вывода, который можно сравнить с рис. 3.2. Получается классическое распределение Пуассона.

о 3.21 Изменить программу 3.8 для распечатывания координат пары ближайших точек.

3.22 Изменить программу 3.8 для выполнения тех же вычислений в -мерном пространстве.