Иногда требуется проверять число на простоту очень быстро. Тогда может помочь хранение простых чисел в массиве. Знакомимся с алгоритмом, известным как решето Эратосфена. Числа из рассматриваемого диапазона после вычеркивания кратных записываем в массив. А если организовать массив как множество, то прямым доступом за время О(1) можно определить, простое число или нет. Если же записать в массив сами простые числа, то возникает проблема быстрого поиска натурального числа в массиве. Поскольку простые числа в массиве упорядочены, то эффективным будет двоичный (бинарный) поиск.
Знакомимся с работой с файлами. Часто полученные результаты надо сохранить в файле. Файлы полезны также при тестировании программы на больших наборах данных.
На следующем занятии будем знакомиться с сортировками на массиве. Но сначала рассматриваем самый эффективный алгоритм - сортировку подсчетом, которая, к сожалению, требует, чтобы сортируемые числа были целыми и находились в ограниченном диапазоне. Поэтому и применение ее ограничено.
Знакомимся с работой с файлами. Часто полученные результаты надо сохранить в файле. Файлы полезны также при тестировании программы на больших наборах данных.
На следующем занятии будем знакомиться с сортировками на массиве. Но сначала рассматриваем самый эффективный алгоритм - сортировку подсчетом, которая, к сожалению, требует, чтобы сортируемые числа были целыми и находились в ограниченном диапазоне. Поэтому и применение ее ограничено.
Комментариев нет:
Отправить комментарий