Спросили у пользователя n и разместили в динамической памяти массив из n элементов типа float.
После окончания работы с массивом память необходимо освободить
free(a);
Возможен вариант в стиле C++:
int n;
float *a;
cout<<“n=”; cin>>n;
a=new int[n]; // Выделяем память.
… // Поработали с массивом
delete [] a; // Освобождаем память
С элементами массива можно работать как с обычными переменными, т. е. присваивать им значения (a[3] = 5.0;), спрашивать их значения у пользователя (scanf(“%f”, &a[2]); или cin >> a[2];), печатать (printf(“%6.2f”,a[2]); или cout << a[2]);) и т.п.
Но общее имя дает некоторые преимущества.
Пусть, например, нам нужно хранить 100 чисел. Если мы их храним в не связанных между собой переменных a0, a1, …, a99, то для того, чтобы спросить значения наших переменных у пользователя, придется писать программу из 100 строк:
cout << “a0=”; cin >> a0;
cout << “a1=”; cin >> a1;
…
cout << “a99=”; cin >> a99;
Если мы их храним в массиве a, программа будет значительно короче;
float a[100]; // Объявили массив из 100 элементов
for(int i=0;i<100;i++){ // Для i от 0 до 99 с шагом 1
cout << “a” << i << “=”; // Печатаем подсказку, чтобы видеть,
// какой элемент вводим. Например, при
// i=3 будет напечатано a3=
cin >>a[i]; // Спрашиваем a[i] у пользователя.
}
Возможен вариант в стиле С:
for(int i=0; i<100; i ++){
printf(“a%d=”,i);
scanf(“%d”, &a[i]);
}
Массивы и указатели.
Адрес переменной – это номер ячейки памяти, в которой она расположена.
Указатель – это переменная, предназначенная для хранения адреса некоторого объекта (например, другой переменной).
Объявление указателя:
int *p; // Объявили указатель p на переменную целого типа.
// Теперь в p можно хранить адрес переменной типа int.
Для работы с указателями есть 2 операции:
& - взятие адреса
* - снятие адреса (разадресация).
Если x – переменная, то &x – ее адрес.
Если p – указатель на переменную, то *p - значение этой переменной.
Имя массива – это адрес его нулевого элемента.
Пусть объявлен массив:
int a[5]={7,3,5,4,2};
Тогда a – это то же самое, что и &a[0].
*a – это то же самое, что и a[0]. В нашем случае *a = 7.
К указателю можно прибавить число.
Если a – это адрес элемента a[0], то a+3 – это адрес элемента a[3].
Операция сложения с константой учитывает размер адресуемых элементов.
Другими словами, если a – указатель на переменную типа int (т.е. номер ячейки, в которой содержится переменная типа int), то прибавление тройки увеличивает этот номер на 3*sizeof(int).
Таким образом,
a+3 – это то же самое, что и &a[3].
*(a+3) – это то же самое, что и a[3].
На самом деле, увидев обращение a[3], машина перепишет его в виде индексного выражения *(a+3).
Пример.
int a[5]={3,2,7,6,5};
printf(“%d”, 3[a]);
Что будет напечатано?
Выражение 3[a] будет переписано в виде *(3+a), это равно *(a+3), то есть a[3].
Будет напечатано число 6.
Указатели можно вычитать.
Пример.
int a[5]={3,2,7,6,5};
int *p1, *p2;
int m;
p1=&a[1];
p2=&a[4];
m=p2-p1;
В результате m=3.
Рассмотрим несколько простых алгоритмов работы с массивами.
Задача 1. Дан массив a. Найти сумму его элементов.
Решение.
Пусть массив содержит n элементов a[0], a[1], … a[n-1].
В переменной S будет накапливаться сумма. Сначала сделаем S=0.
Будем по одному добавлять к S наши слагаемые:
S=0;
S=S+a[0];
S=S+a[1];
…
S=S+a[n-1];
Эту программу легко переписать в виде цикла:
S=0;
Для i от 0 до n-1 с шагом 1 делать
S=S+a[i];
А также перевести на язык C++:
S=0;
for (int i=0; i<n; i++)
S+=a[i];
cout << “Сумма равна” << S; // или printf(“S=%7.2f”, S);
Задача 2. Дан массив a. Найти в нем наименьший элемент и его индекс.
Решение. Будем просматривать по порядку элементы нашего массива. В переменной nom будем хранить индекс наименьшего из просмотренных элементов. Сначала сделаем nom=0. Если очередной просматриваемый элемент меньше, чем a[nom], то кладем в nom его индекс. После просмотра всего массива печатаем ответ (наименьший элемент - a[nom], его индекс - nom).
Последовательность наших действий:
nom=0;
Если a[1] < a[nom], то nom=1;
Если a[2] < a[nom], то nom=2;
…
Если a[n-1] < a[nom], то nom=n-1;
Печатать a[nom] и nom.
Эту последовательность легко переписать в виде цикла:
nom=0;
Для i от 1 до n-1 с шагом 1
Если a[i] < a[nom],
то nom=i;
Печатать a[nom] и nom
Реализуем задачу на языке C. Поиск минимального элемента оформим в виде функции, которая будет зависеть от массива a и числа элементов в нем n и возвращать индекс наименьшего элемента.
#include<iostream.h>
int minimum(float a[], int n); // Объявление функции.
// Возможны варианты
// int minimum(float a[100], int n); или
// int minimum(float *a, int n);
int main(){
float b[5]={3,2,0,4,7};
int no;
no=minim(b,5);
cout << “Наименьший элемент b[” << no << “]=” << b[no];
//
// В стиле языка C предыдущая строка запишется так:
// printf(“Наименьший элемент b%d=%d”, no, b[no]);
//
return(0);
}
int minim(int a[],int n){
int nom=0;
for(int i=1;i<n;i++)
if(a[i]<a[nom])
nom=i;
return(nom);
}
Задача 3.
Написать программу, которая для целочисленного массива a из n элементов определяет, сколько простых чисел располагается между его максимальным и минимальным элементами.
Решение.
Запишем алгоритм решения задачи:
1. Найдем номера nmi и nma максимального и минимального элемента массива (см. задачу 2).
2. Определим кусок массива, который мы должны просмотреть. Левую границу просмотра положим равной min(nma,nmi), правую max(nma,nmi).
3. Просматриваем полученный кусок массива. Как только встретим простое число, счетчик простых чисел count увеличиваем на 1. Выяснять, будет ли данное число простым, будет отдельная функция prostoe().
Реализуем:
#include<iostream.h>
int a[100]; // Выделили память под 100 элементов массива.
int n; // Реально будем использовать n элементов.
void sprositMassiv(void); // Функция спрашивает у пользователя
// элементы массива a.
int prostoe(int n); // Функция возвращает 1, если x – простое
// и 0 в противном случае.
int main(){
int nmi, nma, lev, prav, count, i;
sprositMassiv();
nmi=0; nma=0;
for(i=1; i<n; i++) {
if(a[i]<a[nmi]) nmi=i;
if(a[i]>a[nma]) nma=i;
}
if (nmi > nma) { lev=nma; prav=nmi; }
else {lev = nmi; prav=nma; }
count = 0;
for (i=lev+1; i < prav; i++)
if (prostoe (a[i])) // т.е. if (prostoe(a[i])==1)
count++;
cout << “Количество простых равно ” << count;
return(0);
}
Осталось реализовать функции prostoe() и sprositMassiv().
int prostoe (int x) {
if (x==1) return(0); // 1- не простое число.
for(int i=2; i<x; i++){ //
if(x%i == 0) // Если x делится на i,
return(0); // то оно не простое.
}
return(1); // Если мы добрались до этой строчки,
// то x делится только на 1 и на себя.
// Тогда x – простое.
}
void sprositMassiv (void) { // Упражнение для МОСс.
cout << “n=”; cin >> n; // Написать вариант данной
for (int i=0; i<n; i++) { // функции
cout << “a[” << i << “]=”; // в стиле языка С.
cin >> a[i]; //
}
}
Задача 4. Упорядочить массив методом выбора.
Решение.
Метод выбора заключается в следующем:
Выбираем наименьшее из чисел a[0], …, a[n-1]. Меняем его с a[0].
Выбираем наименьшее из чисел a[1], …, a[n-1]. Меняем его с a[1].
…
Выбираем наименьшее из чисел a[n-2], a[n-1]. Меняем его с a[n-2].
Эти действия легко записать в виде цикла:
Для k от 0 до n-2 с шагом 1 {
Выбираем наименьшее из чисел a[k], …, a[n-1].
Меняем его с a[k].
}
Выбор наименьшего из чисел a[k], …, a[n-1] реализуется аналогично задаче 2 с заменой 0 на k.
Поменять значения переменных x и y можно с помощью последовательности действий t=x; x=y; y=t;
Реализуем:
for (k=0; k<n-1; k++) {
// ----------- Выбираем наименьшее из чисел a[k], …, a[n-1].
nmi = k;
for(i=k+1; i<n; i++) {
if (a[i] < a[nmi]) nmi = i;
}
// -------------Меняем его с a[k].---------------------------------------
t=a[k]; a[k]=a[nmi]; a[nmi]=t;
}
Задача 5. Упорядочить массив методом пузырька.
Решение.
Проделаем такую последовательность действий:
Если a[0] > a[1], то поменять a[0] с a[1].
Если a[1] > a[2], то поменять a[1] с a[2].
…
Если a[k-1] > a[k], то поменять a[k-1] с a[k].
Эти действия легко переписать в виде цикла
Для i от 0 до k-1 с шагом 1
Если a[i] > a[i+1], то поменять a[i] с a[i+1].
Нетрудно видеть, что в результате таких действий самое большое из чисел a[0], …, a[k] окажется на месте a[k].
Теперь, чтобы упорядочить массив a, нам нужно:
Поставить самое большое из чисел a[0], …, a[n-1] на место a[n-1].
Поставить самое большое из чисел a[0], …, a[n-2] на место a[n-2].
…
Поставить самое большое из чисел a[0], a[1] на место a[n-1].
Это тоже реализуется в виде одного цикла:
Для k от n-1 до 1 с шагом -1
Поставить самое большое из чисел a[0], …, a[k] на место a[k].
Переведем на язык С:
for (k=n-1; k >=1; k--) {
for (i=0; i<=k-1; i++) {
if (a[i] > a[i+1]) {
t=a[i]; a[i]=a[i+1]; a[i+1]=t;
}
}
}
Оба наши алгоритма сортировки требуют O(n2) действий.
Хорошие алгоритмы сортировки решают задачу за O(n*ln(n)) операций. В дальнейшем мы будем их рассматривать.