 |
static void Exampl ( void )
|
|
|
|
Статическое и динамическое размещение переменных.
Переменные, объявленные в программе, размещаются компилятором в оперативной памяти статически или динамически:
– при статическом выделении памяти место для хранения переменной выделяет памяти компилятор. Далее компилятор использует закрепленный за переменной адрес в машинных командах, выполняющих чтение или запись в нее данных. Примером статического размещения является объявление переменной вне функции – для нее выделяется место в сегменте данных на этапе компиляции;
– при динамическом выделении место для хранения переменной выделяется специальными функциями или операторами уже во время работы программы. Переменным, объявленным внутри функций или других блоков (внутри фигурных скобок) память выделяется динамически. Эта память выделяется в стеке при входе в блок, а при выходе из блока стек освобождается.
Способ размещения переменных порождает различия в их области видимости и времени жизни.
Пусть в программе объявлена глобальная переменная double A и из функции main() вызывается функция Func1(), в которой объявлена локальная переменная int A:
void Func1(double Par);
void Func2(void);
double A;
Void main(void)
{
A =12; Это запись в глобальную переменную double A. Во время выполнения этого оператора локальной переменной int A просто физически не существует, только при вызове функции Func1() компилятор организует резервирование в стеке места для хранения локальных переменных.
Func 1(12);
После завершения функции, ячейки, которые выделялись для хранения параметров и локальных переменных, удаляются из стека.
}
Void Func 1(double Par)
{
A =0.0; Переменная int A становится доступной, только в строчках, расположенных ниже ее объявления. Поэтому данный оператор записывает ноль в глобальную переменную double A.
|
|
|
.
.
.
int A =7;
.
.
.
A = A + Par; Когда в области видимости оказываются две переменных с одинаковым именем (глобальная и double A локальная int А), то видима та, объявление которой находится во внутреннем блоке. То есть, данный оператор обращается к локальной переменной A и заносит в нее число 19.
Func2()
printf(“%d”,A);
}
Void Func2(void)
{
// extern int B;
В [] сказано, что таким образом можно распространить область видимости объявленной ниже переменной B на весь блок и сделать доступной локальную переменную B следующем операторе:
//B=7;
В среде Visual C++ слово extern, даже записанное внутри блока однозначно указывает на то, что есть глобальная переменная B, объявленная в другом файле (со всеми вытекающими последствиями
нельзя присвоить строкой extern int B начального значения;
– при отсутствии объявления int B; компилятор не сообщит об ошибке, но появится сообщение на этапе компоновки и пр.)
.
.
.
int B;
B =2;
.
.
.
A = A + B; Функция Func2() вызывается из Func1(). Поскольку работа Func1() еще не завершена, в стеке находится ее локальная переменная A и компилятор, в принципе, может организовать к ней доступ. Но функция Func2() не вложена в Func2() (В С++ нельзя, как в Паскале, описать Func2() внутри блока функции Func1()).
Поэтому во время выполнения данного оператора в к глобальной переменной A прибавляется число 2 и оператор
printf (“% lf ”, A); выведет на экран ее значение 2.
}
Отсюда следуют общие правила определения времени жизни и области видимости переменных:
– глобальные, объявленные вне всех функций, переменные существуют имеют глобальное время жизни (существуют в течение всего времени работы программы) и глобальную область видимости (если не закрыты одноименными локальными переменными, то видимы из всех функций, описанных в данном файле, для доступа из других файлов, перед объявлением пишется слово extern);
|
|
|
– локальные переменные существуют в пределах того блока, в котором они объявлены и видимы только в строках, расположенных ниже объявления;
– кроме операторов того блока, в котором объявлены, локальные переменные доступны операторам вложенных в него блоков (если вложенные блоки расположены ниже объявления и в них не объявлено одноименных переменных).
Замечания
1. В приведенном ниже фрагменте
{ //Внешний блок
for (int i =0; i<10; i++)
{ //Внутренний блок
printf (“% d ”, i); // Этот оператор выводит значение параметра цикла.
int i =5; //После этого объявления значение параметра цикла //становится недоступным во внутреннем блоке.
}
//Переменная i (параметр цикла) доступна до конца внешнего блока.
}
параметр цикла i объявлен в заголовке цикла, то есть, во внешнем по отношению к телу цикла блоке. Поэтому она видима до конца внешнего блока.
2. Различием размещения объясняется то, что неинициализированная статическая переменная по умолчанию равна нулю, а значение динамической переменной не определено – оно определяется текущим состоянием стека.
3. Компилятор С++ выделяет разные участки памяти для инициализированных и неинициализированных переменных. Это легко проверить - объявим
# include < stdio. h >
int I =7, j;
int k=8,n;
int * pI;
Void main(void)
{j=1;
n=2;
pI=&I;
printf(" %i %i", *pI,*(pI+1));
pI=&j;
printf(" %i %i", *pI,*(pI+1));
}
Скорее всего, переменным I, k будут выделены соседние ячейки в одном сегменте, а j,n - в другом. Поэтому первый оператор выведет числа 7,8, а второй 1,2. Но это необязательно - стандарт гарантирует, что непрерывный, без пропусков блок памяти выделяется только элементам одного массива. Не только между последовательно объявленными переменными, но даже между полями структуры могут находиться неиспользуемые байты, если установки среды или директива компилятора #pragma pack требуют выровнять поля по границам слов или двойных слов.
4. С появлением объектно-ориентированного программирования введен новый тип данных – класс. В языке C++ статической переменной класса стали называть переменную, которая создается в единственном экземпляре и не повторяется в каждом объекте класса. Но пока мы этого не знаем, будем говорить кратко: «динамическая» или «статическая» переменная имея в виду ее статическое или динамическое размещение.
|
|
|
Классы памяти
Выше динамическое и статическое размещение переменных определялось компилятором автоматически – по месту, в котором переменная объявлена. Программист может управлять этим процессом, указывая перед объявлением переменной класс памяти для ее размещения: auto, register, extern или static.
Если переменная объявлена как
auto int V;
это означает, что место для ее хранения выделяется в стеке. В объявлениях глобальных переменных запрещено указывать класс auto, а локальные переменные размещаются в стеке по умолчанию. Поэтому в своей практике мне пока не удавалось осмысленно использовать в программе служебное слово auto.
Мы помним, что машинные команды с регистрами выполняются быстрее, чем с ячейками памяти. При объявлении переменных, к которым программа обращается особенно часто, можно указать класс register, как пожелание разместить переменную в регистре:
register int V;
На процессорах Intel для этой цели выделяют два регистра SI, DI (ESI,EDI), поэтому если регистровыми объявить больше двух переменных, лишние будут размещены в ОЗУ. Вы можете встретить советы не использовать явное назначение переменных регистровыми, поскольку современные компиляторы сами очень эффективно используют регистры SI, DI для размещения переменных. И это разумный совет: если требования по скорости работы фрагмента программы настолько жесткие, то лучше весь фрагмент переписать на языке ассемблера – получим больший выигрыш в скорости и с меньшими размышлениями. Но при этом надо помнить, что если Вы используете ассемблерную вставку, то содержимое таких регистров, как аx, dx, cx, bx можно изменять, не заботясь о сохранении их значений, а значения регистров SI, DI необходимо сохранять и восстанавливать перед возвратом в C++, чтобы не испортить какую-нибудь переменную. (В среде Visual C++ вставка начинается словом _asm со знаком подчеркивания, а в Borland С++ используют asm без подчеркивания):
Void Func(void)
{
|
|
|
int M1=2;
_asm {
Push esi
Push edi
Mov eax,M1
.
.
.
Pop edi
Pop esi
}
}
.
.
.
}
Регистр EBP лучше вообще не использовать в ассемблерных вставках, для корректной работы программы сохранения и восстановления этого регистра может быть недостаточно. Команды внутри вставки могут обращаться как статическим, так и к динамическим переменным программы по их именам, если они находятся в пределах области видимости. При обращении к динамическим переменным компилятор заменяет имя переменной обращением к стеку, например, команда mov eax,M1 может компилироваться как mov eax,[ebp-4].
Служебное слово extern включает в текущую область видимости глобальную переменную. Об этом уже не раз было сказано. Обратим внимание только на следующую деталь. В рассмотренном выше примере удалим в функции Func2()
знак комментария из строки //extern int B:
void Func2(void)
{
extern int B;
int B;
B=2;
.
.
.
}
В этом случае объявление локальной переменной B вызовет ошибку компиляции. Явное указание программиста на то, что в данном блоке должна быть видима объявленная где-то в этом или другом файле глобальная переменная int B, как обычно, имеет приоритет перед соглашениями по умолчанию.
Теперь объявленная строчкой ниже локальная переменная int B уже не может закрыть глобальную, в области видимости оказываются две одноименных переменных, что и порождает сообщение error C2086: 'B': redefinition (компилятор Visual C++).
Чтобы устранить ошибку, ссылку на внешнюю переменную можно вынести за пределы функции,
extern int B;
void Func2(void)
{
int B;
B=2;
.
.
.
}
но это уже будет совсем другая программа – глобальная переменная B станет недоступной из Func2().
Если необходимо объявить внутри блока статически размещаемую переменную double V2 или ограничить область видимости функции, перед ними пишется слово static:
static void Exampl (void)
{
double V 1=3.5; - эта переменная размещена динамически, в стеке.
static double V 2=7.25; - эта переменная размещена статически, в сегменте данных.
.
.
.
V 2=3;
}
Инициализированным динамическим переменным начальное значение присваивается заново при каждом входе в блок, а статические переменные получают свое значение один раз, при пуске программы. Это относится и к локальным переменным: что бы ни записала функция Exampl() в переменную V1, при ее повторном вызове начальное значение V1 будет равно 3.5. Переменная V2 при первом вызове будет равна 7.25 а повторном вызове будет сохранять записанное в нее значение 3.
Слово static в заголовке функции сужает ее область видимости. Такая функция видима только в пределах того файла, в котором она описана. Использование слова static позволяет разместить в нескольких файлах разные функции с одинаковыми заголовками.
|
|
|
1.1.2. Организация динамической памяти
Динамические локальные переменные создаются во время работы программы, но размер выделяемой для них памяти определяется еще на этапе компиляции. То есть, можно объявить локальный массив из 10 вещественных чисел, но нельзя объявить массив из N элементов и отложить определение конкретного значения N до этапа выполнения (ввести его потом с клавиатуры, из файла, или вычислить в функции от других переменных). Вместе с тем, очень часто необходимый размер переменной определяется уже во время работы программы. В этом случае переменная размещается в динамически распределяемой области памяти (или куче), а доступ к ней осуществляется из программы при помощи указателя.
Следует отметить многогранность термина динамическая память. Например, микросхемы ОЗУ делятся на статическую и динамическую память по своей физической реализации. Мы будем говорить «динамическая память», имея в виду динамически распределяемую область оперативной памяти.
Для работы с динамической памятью Си предусматривает функции запроса и освобождения памяти, проверки ее наличия. Шаблоны этих функций находятся в заголовочном файле alloc.h.
Запрос памяти выполняется функциями
void *malloc(int)
void *calloc(int,int),
которым передается размер памяти, необходимый для размещения переменной. Функции malloc(int) передается необходимое количество байтов, а функции calloc(int,int) – количество блоков и размер блока в байтах.
Пример – выделить место для двадцати вещественных чисел и записать в указатель адрес первого из этих чисел можно так:
double *pF=malloc(20*sizeof(double));
или так pF= с alloc(20,sizeof(double));.
Данные функции возвращают указатель типа void *, который в Си был совместим по присваиванию с любым указателем. В С++ при любом запросе памяти приходится переопределять тип возвращаемого функцией значения:
double pF=(double *)malloc(20*sizeof(double));.
Заполним выделенный участок динамически распределяемой памяти числами, кратными трем:
for (I=0;I<20; I++) *(pF+I)=3*i;
Вспомнив связь указателей и массивов, можно работать с полученным участком как с массивом:
for (I=0;I<20; I++) pF[I]=3*i;.
Когда заполняем массив данными с клавиатуры, функции scanf() требуется передавать адрес переменной. При передаче указателя
for (I =0; I <20; I ++) scanf (“% lf ”; pF + I);
оператор ввода выглядит компактнее, чем делающий то же самое оператор
for (I=0;I<20; I++)scanf(“%lf”; &pF[I]);.
Полученный участок динамической памяти можно освободить вызовом функции free(pF). Как видим, ей не передается размер освобождаемого блока памяти, а только указатель на его начало.
Если указатель pF содержит адрес запрошенного у системы блока памяти, повторного запроса блока и занесения его адреса в pF приведет к тому, что ранее выделенный блок будет невозможно освободить. Использование для доступа к данным указателя pF после того, как блок возвращен системе, также приводит к нарушению работы программы. Поэтому хорошо бы по значению pF знать, выделен ли ему блок памяти. Для этого служит пустой указатель NULL, но функция free(pF) получает указатель по значению, а не по ссылке и, значит, не может занести в pF значение NULL. Аккуратный программист должен делать это сам:
if (pF){ free (pF); pF = NULL;}
и проверять значение указателя перед операциями с динамической памятью:
if(!pF){ pF= с alloc(20,sizeof(double));;}
Управлением динамической памятью занимается не язык, а операционная система. При работе под управлением MS DOS полученный по запросу malloc() или calloc() блок памяти состоит из заголовка (два слова) и следующей за ним области данных. Функции запроса возвращают адрес начала области данных, а не адрес начала блока (адрес заголовка). В заголовке содержится адрес области данных следующего блока (первое слово - смещение, потом сегмент). Заметим, что блоки выделяются, начиная с границы параграфа – адреса, кратного 16. Поэтому младшее слово заголовка занятого блока всегда равно четырем. Все выделенные программе и свободные блоки динамической памяти связаны содержимым заголовков в единый список, упорядоченный по возрастанию адресов. Этого достаточно, чтобы функция free() уменьшив смещение на 4, нашла заголовок блока, по его содержимому самостоятельно вычислила размер освобождаемой области памяти и объединила ее со следующим блоком, если тот тоже свободен.
Чтобы различать в этом списке свободные и занятые блоки при освобождении блока содержимое заголовка переписывается в начало области данных освобожденного блока (блок меньше 16 байтов не бывает, поэтому в области данных всегда есть для этого место). Оба слова заголовка заполняются нулями в качестве признака свободного блока.
Операторы new и delete
В авторской версии Паскаля была процедура запроса памяти new(), которая не требовала указания размера запрашиваемой памяти. Компилятор определял его по типу указателя. Это не всегда удобно, поэтому позже в него была включена функция getmem(), аналогичная malloc().
Аналогичное развитие можно наблюдать в языке С++ – в него введен оператор new, которому передают имя типа, а он возвращает указатель на полученный тип. Компилятор сам определяет, сколько байтов требуется для хранения переменной.
Пусть объявлены структура и два указателя ps и ps1.
Struct _t
{ int a[5];
double c;
} * ps;
struct _ t ps 1;
Выделить место для хранения структуры можно оператором
ps = new struct _ t;
Здесь слово struct можно не указывать: пишем ps=new _t; - результат будет тот же.
Если нужно выделить в динамической памяти место для нескольких элементов типа _t, их количество указывается в квадратных скобках:
ps 1= new struct _ t [10];
Используя указатели, можно получить доступ к элементам созданных структур, например,
ps -> a [2]=2.5;
ps 1[5]. a [0]=7;
Память выделенная оператором new, освобождается оператором delete:
delete ps;
delete ps 1;.
Такое создание динамических объектов нагляднее и не требует переопределения типа указателя.
1.1.3. Задача поиска простых чисел
В качестве примера использования динамической памяти для хранения одномерных массивов рассмотрим задачу поиска простых чисел.
По определению простое число делится без остатка только на 1 и на себя. Отсюда вытекает лобовое решение (назовем его алгоритмом последовательного деления) – для проверки числа N пробовать делить его на все числа от 2 до N/2. И если хотя бы раз получится нулевой остаток, то N – число составное.
Проверку числа N выполним отдельной функцией int Simpl(int N), которая получает N и возвращает ноль, если это составное число. Если число N простое, оно возвращается как результат работы функции:
Int Simpl(int N)
{
for (int i=2; i<=N/2;i++) if(! (N%i))return 0;
return N;
}
В главной программе c клавиатуры вводится максимальное проверяемое значение Max, для всех чисел от 2 до Max вызывается проверочная функция Simpl(), и возвращаемые ею простые числа выводятся на экран:
Void main (void)
{int Max,Res;
printf(“Input Max ”); scanf(“%d”,&Max);
for (int i=2;i<=Max;i++)if(Res=Simpl(int N)) printf(“%d ”,Res);
getch ();
}
Но при этом с увеличением значения Max слишком быстро растет объем вычислений: для поиска всех чисел, не превосходящих Max потребуется около Max2/4 длинных операций деления. Наиболее эффективным в вычислительном отношении считается алгоритм поиска всех простых чисел, не превосходящих Max, который называется «Решето Эратосфена».
Сущность алгоритма заключается в следующем:
1) массив из Max элементов заполняется числами натурального ряда от 0 до N;
первое простое число (обозначим его Smpl) известно – это 2. На следующем шаге используем его, что бы удалить из массива все заведомо составные числа;
3) используем простое число Smpl, чтобы удалить из массива все кратные Simpl, а, следовательно, заведомо составные числа. Для этого вычеркиваем из массива элементы, позиция которых равна 2* Smpl, 3*Smpl и т.д. В программе не потребуется выполнять умножение. Для Smpl = 2 вычеркиваем из массива, начиная с позиции номер Smpl, каждое второе число, для Smpl = 3, каждое третье, потом каждое пятое, седьмое и т. д.;
4) после выполнения пункта 3 находим в массиве ближайший после Smpl не вычеркнутый элемент, заносим его в переменную Smpl и если Smpl<=Max/2 повторяем процесс вычеркивания переходом к пункту 3.
Если Smpl>Max/2 (будем считать, что на участке от Max/2 до Max есть хотя бы одно простое число), кратный ему элемент находится за пределами массива, процесс вычеркивания закончен, в массиве остаются только простые числа.
При реализации алгоритма учтем, что в массиве нет необходимости хранить значения натуральных чисел. Достаточно двух чисел: если в ячейке хранится 1 – число не вычеркнуто, если 0 – вычеркнуто. Сами значения простых чисел можно определить по позициям единиц в массиве. Это позволит уменьшить потребность в памяти, создавая массив из байтов, а не элементов типа int. Заполнить массив единицами можно циклом for, но значительно быстрее эту задачу выполнит функция
memset(<адрес первого байта>,<содержимое байта>,<количество заполняемых байтов>);
Прототип функции в среде Borland C находится в файле mem.h, а при использовании Visual C++ в файле memory.h. (В этом же файле находятся прототипы других полезных функций:
int __cdecl memcmp(const void *, const void *, size_t); – сравнение массивов;
void * __cdecl memcpy(void *, const void *, size_t); – копирование массивов;
Ускорения поиска при применении решета Эратосфена обусловлено двумя факторами:
– длинные операции деления заменены короткими операциями сложения и вычеркивания. Так, в первом алгоритме к числу Max надо применить Max/2 операций деления, во втором алгоритме ему соответствуют Max/2 вычеркиваний из массива числа 2;
– в первом алгоритме операции деления применяются ко всем проверяемым числам натурального ряда, а процесс вычеркивания порождается только простыми числами.
Поскольку неизвестно, какой процент от общего количества чисел составляют простые, мы не можем аналитически оценить, во сколько раз алгоритм Эратосфена эффективнее последовательного деления, но можем проверить это экспериментально. Для создания просеиваемого массива необходимо получить блок динамической памяти в виде непрерывного массива байтов. Программы для DOS могут запросить не более одного сегмента (65532 байтов данных). Поэтому алгоритмы поиска целых чисел были реализованы как консольные приложения Windows. Это позволяет запрашивать блоки в сотни миллионов байтов.
В параграфе «Операции со структурами» мы рассматривали функцию получения времени MyTime() при работе в среде DOS. В программах для Windows есть стандартная функция timeGetTime(), возвращающая значение системного времени в миллисекундах. Прототип функции подключается при помощи заголовочного файла windows.h. Необходимо также включить в список для компоновки библиотеку winmm.lib, которая отсутствует в настройках проекта по умолчанию. Для включения библиотеки в список компоновщика, необходимо в среде разработки выбрать пункты Project/Setting, в появившемся диалоговом окне выбрать вкладку Link и добавить название библиотеки к списку в поле Object/Library Modules вкладки Link.
В приведенной ниже программе запрос и освобождение памяти выполняется операторами new и delete:
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
Функция поиска простых чисел получает указатель N на первый элемент массива и его размер Max.
void Eratosfen (char *N, int Max)
{ int tSmpl=2;
while(tSmpl<=Max/2) При tSmpl>Max/2 вычеркнуты все составные числа.
{ for (int i = 2*tSmpl; i<Max; i=i+ tSmpl)N[i]=0;
for (i = tSmpl+1; i<Max; i++)if(N[i]!=0){tSmpl=i; break;}
} Первый из операторов for вычеркивает элементы, кратные простому tSmpl.
} Второй оператор for выполняет поиск в массиве следующего простого числа.
Void main (void)
{int Max, Res=0;
char *N=NULL;
printf("Input Max "); scanf("%d",&Max); Ввод диапазона чисел.
if (! N) Очевидно, что N=NULL, но мы привыкаем к заботиться о надежности.
N = new char [ Max ]; Запросили блок памяти
if (! N){ printf (“Недостаточно памяти»”); exit (1);}
memset(N,1,Max);
unsigned int Time1=timeGetTime();
Eratosfen (N, Max); Вызов функции поиска простых чисел.
unsigned int Time2=timeGetTime();
printf("Time= %d ms\n", Time2- Time1); Индикация времени поиска.
for (int i = 2; i<Max; i=i++)if(N[i]!=0) Res++;
printf (" Number = % d \ n ", Res); Вывод количества простых чисел.
for (int i = Max-1; i>0; i--)
if (N [ i ]!=0) { printf ("% d ", i); break;} Самое большое простое число.
//for (int i = 2; i<Max; i=i++) Индикация всех простых чисел.
// if(N[i]!=0) printf("%d ", i);
if (N) delete N; N = NULL; Здесь мы могли просто написать delete N, но в больших программах надежнее проверить, что указатель ссылается на запрошенный блок памяти и занести в него после освобождения памяти значение NULL.
getch ();
}
На рис 3.1 показаны результаты работы данной программы при поиске простых чисел до ста тысяч, десяти и одиннадцати миллионов. Из рисунка мы можем оценить количество простых чисел в участке натурального ряда из 100 тысяч элементов. Как видим, в области больших чисел простые встречаются несколько реже, чем в первых ста тысячах.
Сравнение времени работы программ показывает, что в алгоритме последовательного деления зависимость времени выполнения от диапазона Max действительно имеет квадратичный характер. Абсолютные цифры зависят от модификации процессора. У меня на процессоре с тактовой частотой 200 Мгц поиск простых чисел в диапазоне от 0 до 100000 длился 45 секунд, до 200000 приблизительно вчетверо больше – 160 секунд. Проверять, что поиск простых чисел, не превышающих 500 тысяч, будет продолжаться в 25 раз дольше я не стал. Вы можете убедиться в этом самостоятельно.
При применении решета Эратосфена я увеличивал диапазон Max до тех пор, пока не получил простые числа в диапазоне до 100 миллионов. Затраты времени при этом увеличивались линейно – приблизительно по 80 миллисекунд на каждые сто тысяч диапазона. То есть, уже в диапазоне 100000 решето Эратосфена работает в тысячу раз быстрее последовательного деления. Сравнивая показатели, не могу не вернуться еще раз к утверждению о том, что «современные ЭВМ практически безынерционны», поэтому разработчик должен думать о надежности и понятности своих программ, а в вопросе о скорости положиться на оптимизирующие возможности компилятора. Как видим, есть задачи, где программист не может себе позволить применение понятных, но неэффективных алгоритмов.
Алгоритм Эратосфена имеет определенный недостаток – для его работы необходим большой буфер в оперативной памяти. На моем компьютере с памятью 256 Mбайт после запроса буфера в 300 миллионов байтов программа вывела предусмотренное в ней сообщение о нехватке памяти.
Вы можете учесть, что каждая ячейка буфера находится в одном из двух возможных состояний, и выделить для каждого числа не байт, а бит. Это еще в восемь раз расширит диапазон поиска простых чисел. Попробуйте написать соответствующую программу самостоятельно.
Несколько изменим постановку задачи. Пусть нам задан не диапазон, в котором надо найти простые числа, а их количество. Например, требуется найти первые десять или сто миллионов простых чисел. Ориентируясь на рис 3.1 можно сделать предположение о необходимом размере буфера для натурального ряда.Но его точный размер неизвестен, к тому же он может оказаться слишком большим. В этом случае мы можем выделить для поиска буфер B фиксированного размера r, меньшего, чем требуется для работы решета Эратосфена и последовательно помещать в него участки натурального ряда из r элементов, содержащие числа (0, r-1), (r, 2*r-1), (2*r,3*r-1) и т.д.
Алгоритм поиска в этом случае будет использовать массив S для хранения найденных простых чисел и вспомогательный буфер B размера r для хранения участка натурального ряда, начинющегося со значения Start. Это значение задает начало области натурального ряда, в которой еще не выполняли просеивание в поисках простых чисел.
Поиск заданного количества простых чисел N, будет включать следующие шаги:
1). Ввод с клавиатуры количества простых чисел N и размера вспомогательного буфера r. Запрос блоков памяти необходимого размера.
2). Назначение буферу B диапазона значений (0, r). Поиск простых чисел в диапазоне (0,r) при помощи алгоритма Эратосфена и запись их в массив S. В результате выполнения этого шага в массив S будет записано Ns простых чисел.
3) Назначение буферу B диапазона значений (r,2*r). Для поиска простых чисел в этом диапазоне необходимо вычеркнуть из буфера все ячейки, позиции которых кратны числам из массива S. Элементы, кратные простым числам, найденным в буфере B,вычеркивать не придется, так как даже позиция B[0]+Start, кратная первому элементу B[0], выходит за пределы буфера.
4). Выполнение для каждого из простых чисел S[k], k=0,1,2,…, Ns из массива S следующих действий, позволяющих вычеркнуть из буфера B все составные числа:
вычисление позиции первого вычеркиваемого элемента I= S[k]*((Start-1)/ S[k]+1)- Start. Замечание – если брать I= S[k]*(Start / S[k]+1)- Start, то при Start кратном S[k] пропустим первый элемент.
вычеркивание всех элементов с позициями I+S[k], I+2*S[k],...
5). Ячейки, оставшиеся не вычеркнутыми после шага 4, соответствуют простым числам. Эти числа переписываются в массив S, значение Start увеличивается на размер буфера r и все элементы буфера объявляются невычеркнутыми.
Пункты 4, 5 повторяются до тех пор, пока в массив S не будет записано N чисел.
#include <windows.h>
#include <stdio.h>
#include <conio.h>
#include <memory.h>
void Eratosfen (char *N,int Max) Повторяем текст процедуры
{ int tSmpl =2; просеивания из предыдущего примера.
while(tSmpl<=Max/2)
{ for (int i=2*tSmpl;i<Max;i=i+tSmpl)N[i]=0;
for (i=tSmpl+1; i<Max;i++)if(N[i]!=0){tSmpl=i;break;}
}
}
Void main (void)
{ int N; Требуемое количество простых чисел.
int Ns =0; Количество уже полученных простых чисел.
unsigned *S=NULL;
char *B=NULL;
unsigned r; // размер рабочего буфера
printf ("\ n введите количество простых чисел "); scanf ("% i ",& N);
printf ("\ n введите размер вспомогательного буфера "); scanf ("% i ",& r);
if (!S) S=new unsigned[N];
if (!S){printf("No memory");exit(1);}
if (!B) B=new char[r];
if (!B){printf("No memory");exit(1);}
memset (B,1, r);
Eratosfen (B, r); Поиск простых чисел в диапазоне (0,r) и
for (int i=2;i<r;i=i++)if(B[i]!=0)S[Ns++]=i; запись их в массив S.
unsigned Start = r; Ч исло, соответствующее первому элементу рабочего буфера
while (Ns < N) // пока найдено меньше заданного числа N простых чисел
{memset(B,1,r*sizeof(char));
for (unsigned k =0; k < Ns;++ k) Берем все уже полученные простые числа и
{ unsigned j = S [ k ]*((Start -1)/ S [ k ])- Start; вычисляем первую позицию в буфере B.
while ((j += S [ k ])< r) B [ j ]=0; Вычеркиваем из B все кратные простому S[k].
} // end for(;k<Ns;++k)
for(i=0;i<r;i++)
if(B[i]==1){S[Ns++]=Start+i;if (Ns>=N)break;} Пересылаем простые числа в S.
Start += r; Смещаем начало буфера на необработанный участок натурального ряда.
} // end while (Ns<N)
//for(i=0;i<N;i++) printf("%5i",S[i]); Поиск закончен. Выводим простые числа.
printf ("%5 i ", S [ N -1]); Последнее найденное число.
if(S)delete S;S=NULL;
if(B)delete B;B=NULL;
getch ();
}
После реализации рассмотренного алгоритма у нас возникает вопрос - интересно, насколько размер буфера ускоряет вычисления? Необходимые эксперименты Вы можете выполнить самостоятельно.
Но если уменьшить буфер до предела – брать только одно новое натуральное число и проверять его делением на все ранее найденные простые числа, программа заметно упрощается. Возможно, из-за этого она станет в каком-то диапазоне поиска работать даже быстрее. (Принципиальное отличие такого алгоритма от последовательного деления в том, что здесь при проверке числа M оно делится не на все, а только на простые числа, меньшие M.)
Такая версия алгоритма, которая проверялась в MS DOS, представлена ниже.
#include <stdio.h>
#include <conio.h>
# include < alloc. h >
long int * S = NULL; Ссылка на массив с найденными простыми числами.
long Start =3; Очередное натуральное число – претендент на простое.
long B; Рабочая переменная.
int k, N; N – требуемое количество простых чисел.
int Ns =1; Ns –количество уже найденных простых чисел.
Void main (void)
{
printf ("\введите количество простых чисел "); scanf ("% i ",& N);
S=new long[N]; if(!S)return;
S[0]=2;
while (Ns<N)
{
for(B=1,k=0;k<Ns;++k) if(!(B=Start%S[k]))break; Цикл проверки на кратность.
if (B) S [ Ns ++]= Start; Start ++; Если при завершении цикла B не равно
} нулю, Start – простое число.
for (k =0; k < N; k ++) printf ("%9 li ", S [ k ]); Вывод простых чисел.
getch ();
Delete S;
}
Самостоятельно проверьте работу приведенных программ и время их выполнения при разных значениях N и размере рабочего буфера и ответьте на следующие вопросы:
Выводят ли программы одинаковые числа?
Зависит ли время выполнения программы, использующей рабочий буфер B от его размеров?
Есть ли значения N (количество простых чисел) при которых последняя программа работает быстрее предыдущей независимо от размеров рабочего буфера?
Есть ли при заданном значении N оптимальных размер рабочего буфера или увеличение его размера всегда приводит к ускорению программы.
1.1.4. Динамические матрицы
Пусть необходимо запрограммировать задачу, требующую работы с матрицами, а по условиям задачи размерность матрицы заранее неизвестна и должна задаваться с клавиатуры во время работы программы. Язык С++ и язык Паскаль позволяют объявлять только массивы фиксированной размерности (количество элементов массива – константа и не может вводиться с клавиатуры.)
Но динамические матрицы (матрицы, необходимый размер которых определяется во время работы программы) можно создавать, запрашивая для каждой строки матрицы блок из динамически распределяемой памяти.
Принцип формирования матрицы объяснялся в параграфе «Динамические многомерные массивы» при изучении Паскаля. Там же находится рисунок, демонстрирующий структуру данных, которая реализует динамическую матрицу.
Кратко напоминаем. Для формирования целочисленной матрицы A размером M*N необходимо объявить указатель на указатель на целое:
int **A
Занести в него ссылку на массив из M указателей на целое
A==(int**)calloc(M,sizeof(int*));
Обращение к i-тому элементу этого массива выглядит как A[i].
Поскольку A[i], это указатели на целое, мы можем занести в каждый из них ссылку на блок памяти, предназначенный для хранения N целых чисел. Тогда J-тое целое число в таком блоке будет доступно как A [i][j].
Пример функции, создающей квадратную вещественную матрицу показан ниже:
float ** CreateMatrix (int n)
{ float ** A =(float **) calloc (n, sizeof (float *)); Оператор функции выделяет место в
куче для n указателей.
for (int i =0; i < n; i ++) Оператор цикла в каждый из этих указателей
A [ i ]=(float *) calloc (n, sizeof (float)); записывает адрес массива из n вещественных чисел.
return A;
}
Из-за того, что в С++ разадресация указателя вида (A+i) имеет другое обозначение A[i], обращение к элементам массивов вещественных чисел выглядит также, как работа с элементами матрицы. A[i][j]. Так, создать единичную матрицу размером 10*10 можно следующими операторами
float **M= CreateMatrix(10);
for(int i=0;i<10;i++)
for(int j=0;j<10;j++) M[i][j]=0;
for (j =0; j <10; j ++) M [ j ][ j ]=1;
Синтаксически работа с динамической матрицей неотличима о
|
|
|
