Лекция: Уровень B
1. Определить, является ли целое число симметричным, т. е. таким числом, которое одинаково читается слева направо и справа налево (палиндром, перевертыш). Например, числа 123321, 202, 9889, 5555, 8 — палиндромы.
2. Перевести целое число из 10-тичной системы счисления в 16 с.с.
3. Перевести целое число из десятичной системы счисления в двоичную.
4. Найти приближенно, с точностью до 0,001, минимум функции на отрезке [u, v ].
5. Найти, где = –функция, a, b — отрезок изменения х, целое n задано. Массив x не формировать.
6. Вычислить y= с заданной погрешностью e, используя следующую формулу: Вычисления прекращаем, если .
Г л а в а 3
Введение в массивы
В этой главе будет введено понятие массивов и показано, как работать с одномерными массивами с фиксированной размерностью в стиле языка Pascal, то есть с помощью индексов, без использования указателей.
Основные понятия
Массив— это сложный (составной, структурированный) тип данных, который характеризуется следующим:
· все элементы массива имеют одинаковый тип;
· каждый элемент массива занимает одинаковый объём памяти;
· массив располагается в оперативной памяти, а не на внешнем устройстве;
· элементы массива занимают подряд идущие ячейки.
Доступ к элементам массива в С++ осуществляется двумя способами. Первый, с помощью порядкового номера элемента массива (индекса), характерен для многих языков программирования. Он более простой и привычный для тех, кто изучал язык Pascal или другой язык. В качестве индекса можно использовать выражение, в том числе константу или переменную целого или совместимого с ним типа, и нельзя использовать выражение вещественного типа. Профессионально в С++, в отличие от более простых языков, есть возможность обрабатывать массивы, используя специальный тип данных, который называется указателем. Переменная такого типа содержит адрес ячейки, то есть в упрощённом виде номер её первого байта. В С++ существует связь между массивами и указателями. Этот способ будет рассмотрен позже.
Массивы могут иметь одну или несколько размерностей. Их изучение начинаем с более простого одномерного массива, который называют вектором, подразумевая вектор в n-мерном пространстве. Для доступа к элементу такого массива достаточно одного индекса. Работа с двухмерными массивами (матрицами) рассматривается позже. Теоретически разрешены массивы с тремя и более размерностями, но на практике они используются редко, так как такие массивы занимают большой объём оперативной памяти.
Одномерный массив с фиксированной размерностью, который назовём статический, объявляется в общем виде следующим образом: тип имя [N]; Здесь тип — тип элементов массива. Вначале будем рассматривать простые типы (int, float, char). Имя записывается по правилам идентификаторов. Каждый элемент массива имеет одно и то же имя, меняется только индекс или номер элемента. N — размерность (или размер) массива в виде целочисленной константы или константного выражения. Эта величина определяет количество элементов массива, а, следовательно, и количество ячеек оперативной памяти, зарезервированной для массива. Например: float A[10];. Но лучше второй вариант: const n=10; float A[n]; и вместо константы 10 используется её имя, то есть n. Преимущество второго способа следующее. Если надо будет изменить размерность массива, то это достаточно сделать в одном месте программы при определении константы, В первом способе в тексте программы надо найти несколько раз встречающуюся константу 10 и заменить её другим числом.
С точки зрения времени (этапа), когда распределяется память под массив, существуют два их вида. Кроме рассматриваемого статического можно создавать динамический массив, размерность которого может быть не только константой, а и переменной. Память для такогомассива выделяется во время выполнения программы, и если массив не нужен, память для него можно освободить.
В отличие от динамического массива, для статического память для размещения n чисел указанного типа (10 вещественных чисел) резервируется на этапе компиляции. Для массива требуется память объёмом k*n =4*10=40 байт, где k — количество байт для размещения одного элемента указанного типа (в примере одного числа типа float). Эта память сохраняется на всё время выполнения функции или блока, где описан массив. Программно необходимый объём памяти можно определить с помощью операции sizeofследующим образом: M=sizeof (тип)*N; или M= sizeof (имя); или M= sizeof имя; где M — переменная целого типа, определяющая размер массива в байтах. В операции sizeof тип обязательно записывается в скобках, а имя может быть без скобок. Следующая программа выведет дважды число 40.
const n=10; float A[n]; int M1, M2;
M1=sizeof(float)*n; /* ноM1=sizeof float *n;— ошибка! */
M2=sizeof(A); /* или M2=sizeof A; */
cout<<M1<<endl<<M2;
Во многих современных системах программирования, в том числе и в С++, нумерация элементов массива начинается с 0. Тогда если n — количество элементов, тоA[n-1] — последний элемент массива. Это связано с использованием указателей при работе с массивами (см. вторую часть книги). Поэтому в нашем примере индекс изменяется от до n-1 включительно, то есть индекс последнего элемента массива на единицу меньше его размерности. Элементы массива обозначаются следующим образом: A[0], A[1], A[2] ,…, A[n-1]. В С++ отсутствует проверка границ массивов. Можно выйти за его границу и записать значение в некоторую переменную или даже в код программы. О таком контроле должен позаботиться сам программист.
При использовании статических массивов возникают проблемы в случае, если размер массива заранее мы не знаем. В таком случае объявляем массив максимальной размерности, которая для некоторых задач может быть известна. Реальную размерность вводим и используем её далее в программе, например, в циклах и для других целей: const nmax=100; float X[nmax]; int n;
cout<<”Input the size of array <100”; cin>>n;
Дальше работаем с n (а не с nmax) элементами массива. Такой способ проще, но неэффективен с точки зрения распределения памяти, так как мы “запрашиваем” больше памяти, чем реально используем. В таких случаях профессионально используются более эффективные динамические массивы.
Во время объявления можно проинициализировать массив, т. е. задать значения его элементов: тип имя [N]={список значений}; В фигурных скобках записываются константы соответствующего типа, разделённые запятыми. Например: const n=5; float A[n]={-1.1, 22, 3, -4.4, 50}; При этом если в списке меньше n значений, то недостающие элементы массива примут нулевое значение. Наоборот, если указать больше n значений, “компилятору это не понравится”. Размерность массива при таком способе указывать необязательно. Она будет определена в зависимости от количества записанных элементов. Например, int V[]={11, 2, -3, 44, -5}; объявляет и инициализирует целочисленный массив из пяти элементов. Указанный способ определения массива удобен для отладки программы, так как не надо тратить время на многократный ввод его элементов. При тестировании для нового теста достаточно изменить несколько элементов массива.
Пример 1. Найти сумму всех элементов одномерного массива.
// объявление и инициализация массива.
const n=5; int a[n] ={1, 22, -3, -4, 5};
/* Учитывая рассмотренные в предыдущем параграфе возможности оператора for, суммирование можно выполнить одним из следующих способов.
1) Наиболее понятный для тех, кто знает основы языка Pascal */
int Sum=0; for ( int i=0; i<n; i++ ) Sum=Sum+a[i];
cout<<endl<<Sum ;
/* 2) В первом выражении несколько присваиваний через запятую */
int i; for ( Sum=0, i=0; i<n; i++ ) Sum+=a[i];
cout<<endl<<Sum ;
/* 3) Здесь отсутствует тело цикла, и только в этом случае в конце заголовка записывается “;”. Важен порядок операторов третьей части. Почему? */
for ( Sum=0, i=0; i<n; Sum+=a[i], i++); cout<<endl<<Sum ;
/* 4)Более компактный по сравнению с предыдущим */
for ( Sum= i=0; i<n; Sum+=a[i++] ); cout<<endl<<Sum ;
/* Но не такой вариант!
for ( Sum= i=0; i<n; Sum+=a[++i] ); cout<<endl<<Sum ;
Объяснить ошибку!*/
/* 5)Отсутствуют все три выражения заголовка цикла*/
Sum=0; i=0; for (;; ) { if ( i>=5) break; Sum+=a[i]; i++; }
cout<<endl<<Sum ;
Из приведенных вариантов наиболее простым для понимания является первый вариант, а компактным, профессиональным — вариант 4.
Пример 2. Найти сумму и количество положительных чисел массива
const n=5; int a[n]= {1, 22, -3, -4, 5}; float Sum=0; int K=0;
Первый вариант цикла без continue:
for (int i=0; i<n; i++) if (a[i]>0) { Sum+=a[i]; K++; }
cout<<endl<<Sum<<" "<<K;
Здесь фигурные скобки для for не писали, так как в теле цикла один условный оператор if. Внутренние скобки для if обязательны, так как два оператора либо выполняются, либо пропускаются.
Второй вариант c использованием оператора continue:
Sum=0; K=0; for (int i=0; i<n; i++)
{ if (a[i]<=0) continue;
Sum+=a[i]; K++; } // 1
cout<<endl<<Sum<<" "<<K;
Для неположительных чисел операторы в строке //1 пропускаются, выполняется i++, затем проверяем i<n и, если это неравенство истинно, анализируется a[i] (a[i]<=0). Если на каком-то шаге последнее неравенство ложно, без никакого else выполняются операторы в строке //1, затем, как обычно, i++ и т.д. Здесь фигурные скобки для for обязательны, а для if они не нужны.
Оператор сontinue пропускает оставшуюся часть тела цикла. В операторах while и do … while он передаёт управление на повторную проверку условия цикла, то есть после него вычисляется и анализируется выражение, записанное после while в скобках, а затем, если оно истинно, продолжается работа цикла. В случае оператора forвычисляется третье выражение, затем второе и, если оно истинно, выполняется тело цикла.