 |
алгоритмизация и программирование 9 глава
|
|
|
|
2. Каким образом реализуются итеративные процессы?
3. Какой алгоритм называется рекурсивным?
4. Какая функция называется прямо рекурсивной? Косвенно рекурсивной?
5. Что такое стек? В какой последовательности происходит заполнение стека и выбор элементов из стека?
6. Что должно обязательно присутствовать в теле рекурсивно описанной функции?
7. Перечислите различия между итерацией и рекурсией.
8. Что произойдет, если рекурсивный алгоритм будет вызывать сам себя «бесконечное» число раз?
9. Как предотвратить бесконечное выполнение рекурсивного алгоритма?
10. Верно ли, что решение задачи, реализуемое рекурсивным алгоритмом, можно выразить, используя итерацию?
Пример выполнения лабораторной работы
Задание. Для заданных границ интегрирования a и b вычислите значение определенного интеграла следующего вида:
Решение
1. Математическая модель
Аргументы: границы интегрирования a, b целого типа;
степень n1 целого типа.
Результаты: разность int_b - int_a вещественного типа.
Промежуточные величины: значение интеграла для нижней границы интегрирования int_a;значение интеграла для верхней границы интегрирования int_b (вещественного типа).
| Ввод a, b, n1 |
| Начало Вывод int_a- int_b |
| Вывод int_a-int_b |
| Конец int_a:= integral(n1, a) |
| int_a = Integrate (n1, a) |
| int_b= Integrate (n1, b) |
| Конец integral(n1, a) |
| Integrate (n, x) |
| n=1 |
Integrate = 
|
| + |
| – |
| n>1 |
|
| + |
| – |
| c = 2.0 |
3. Программа
// вычисление значения определенного интеграла
#include <iostream>
#include <conio.h>
#include <math.h>
using namespace std;
double Integrate(int n, double x);
int main()
{
double b, a;
int n1;
cout<<"Введите а и b, где b больше a: ";
cin>>a>>b;
cout<<endl;
cout<<"Введите степень n: ";
cin>>n1;
|
|
|
cout<<endl;
double int_a, int_b;
int_a = Integrate(n1, a);
int_b = Integrate(n1, b);
cout<<"Значение определённого интеграла при а = "<<a<<" и b = "<<b<<" равно "<<int_b-int_a;
_getch();
return 0;
}
double Integrate(int n, double x)
{
double c = 2.0; // значение константы а выбирается произвольно
if(n == 1) return (exp(c*x)/(c*c)*(c*x-1));
if(n > 1) return (pow(x, n)*exp(c*x)/c-(n/c)*Integrate(n-1, x));
}
4. Результат работы программы
Введите a и b, где b больше a: 2 4
Введите степень n: 3
Значение определенного интеграла при a = 2 и b = 4 равно 67328,1534
7. Одномерные массивы
7.1. Понятие структурированного типа данных
Синонимами названия «базовый тип» являются названия «стандартные», «предопределенные». Реализация этих типов заложена в стандарте языка, и программист не вправе изменить предопределенное. Производным типом (определяемым программистом) является такой тип, который должен быть описан пользователем перед употреблением. К производным типам можно отнести массивы, перечисления, функции, структуры, ссылки, объединения и классы. Полезно помнить, что тип данного определяет его размещение в памяти и набор операций.
Структурированный тип представляет собой набор элементов – данных, объединенных программистом в единый блок в соответствии с особенностями решаемой задачи. Данные, входящие в блок, могут быть однотипными или разнотипными, весь блок данных имеет общее имя. Каждый элемент отличается от других либо порядковым номером (индексом) – в массиве, либо своим именем и, возможно, типом – в структуре.
Любой из структурированных типов данных характеризуется множественностью образующих этот тип элементов. Переменная или константа структурированного типа всегда имеет несколько компонент. Каждая из этих компонент, в свою очередь, может принадлежать структурированному типу, что позволяет говорить о возможной вложенности типов.
В С++ можно выделить следующие структурированные типы: массивы, структуры, объединения, классы, файлы.
|
|
|
7.2. Понятие и описание типа массив
При использовании простых переменных каждой области памяти для хранения данных соответствует своё имя. Если с группой величин одинакового типа требуется выполнять однообразные действия, им дают одно имя, а различают по порядковому номеру. Это позволяет компактно записывать множество операций с помощью циклов. Конечная именованная последовательность однотипных величин называется массивом. Описание массива в программе отличается от описания простой переменной наличием после имени квадратных скобок, в которых задается количество элементов массива (размер).
Общий вид описания массива:
тип_данных имя_массива [количество_элементов 1]…[количество_элементов n ];
Здесь:
1) тип_данных – это тип элементов массива. Это может быть любой стандартный или ранее определённый пользователем тип данных. Например, можно определить массив координат точек на плоскости, тогда один элемент массива содержит две координаты одной точки. Можно определить массив сведений о студенте, тогда один элемент массива содержит разнообразные сведения о студенте, например, фамилия, имя, возраст, адрес и прочие. В этих случаях для определения типа одного элемента массива используется также производный тип, например, массив или структура;
2) имя_массива – правильный идентификатор;
3) количество_элементов – это константа, заданная явно или именованная (константное выражение). Использовать переменные нельзя!;
4) n – размерность массива.
При n = 1 описание соответствует одномерному массиву (вектору),
n = 2 – двумерному массиву (матрице),
n > 2 – многомерный массив.
На размерность массивов ограничений не налагается.
Размерность массива всегда равна количеству индексов (измерений).
Под размером обычно понимают количество элементов массива.
Пример фиксированного массива на С/С++
float a[10]; // описание одномерного массива из 10 вещественных чисел
int Array[10]; // одномерный массив целых чисел с размером 10
// нумерация элементов от 0 до 9
double Array[12][15]; // Двумерный массив вещественных чисел двойной
// точности размера 12 на 15. Нумерация
// по строкам от 0 до 11, по столбцам от 0 до 14
Замечание. При описании массивов квадратные скобки являются элементом синтаксиса, а не указанием на необязательность конструкции.
|
|
|
Элементы массива номеруются с нуля. Инициализирующие значения для массивов записываются в фигурных скобках. Значения элементам присваиваются по порядку. Если элементов в массиве больше, элементы, для которых значения не указаны, обнуляются:
int b[5] = {3, 2, 1};//b[0] = 3, b[1] = 2, b[2] = 1, b[3] = 0, b[4] = 0
Замечание. К каждому элементу массива имеется прямой доступ. Для этого необходимо указать имя массива и номер элемента (индекс) в квадратных скобках.
Размер массива вместе с типом его элементов определяет объем памяти, необходимый для размещения массива, которое выполняется на этапе компиляции, поэтому размер может быть задан только целой положительной константой или константным выражением. Если при описании массива не указан размер, должен присутствовать инициализатор, в этом случае компилятор выделит память по количеству инициализирующих значений.
7.3. Одномерные массивы
Одномерный массив – массив, с одним параметром (измерением), характеризующим количество элементов одномерного массива. Размерность n = 1.
На рисунке 7.1 показана структура целочисленного одномерного массива a. Размер этого массива – 10 элементов (ячеек).
| -5 | -6 | -3 | |||||||
| a[0] | a[1] | a[2] | a[3] | a[4] | a[5] | a[6] | a[7] | a[8] | a[9] |
Рисунок 7.1 – Одномерный массив в С++
Максимальный индекс одномерного массива a равен 9, но размер массива 10 ячеек, так как нумерация ячеек массива всегда начинается с 0. Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к каждой ячейке массива и выполнять какие-либо действия над ней (ячейкой).
int a[10];//пример объявления массива, изображенного на рисунке 7.1,
// где int – целочисленный тип данных;
// а – имя одномерного массива;
// 10 — размер одномерного массива a.
Обычно при описании массива его размер задается в виде именованной константы, например:
const int n = 6;
int a[n], b[n]; //описано два одномерных массива из 6 целых чисел
Над массивом как единой структурой никакие операции не определены. Все действия выполняются с отдельными элементами массива. Причем, с элементами массива допустимы все операции, определенные для переменных того же типа.
|
|
|
Для обращения к элементу массива после имени массива указывается номер элемента в квадратных скобках, например: а[4], b[1].
В следующем примере подсчитывается сумма элементов массива.
#include <iostream>
int main()
{
const int n = 10;
int i, sum;
int marks[n] = {3, 4, 5, 4, 4};
for (i = 0, sum = 0; i<n; i++) sum += marks[i];
cout <<”Сумма элементов: ” << sum;
return 0;
}
Размер массивов предпочтительнее задавать с помощью именованных констант, как это сделано в примере, поскольку при таком подходе для её изменения достаточно скорректировать значение константы всего лишь в одном месте программы.
Замечание. При обращении к элементам массива автоматический контроль выхода индекса за границу массива не производится, что может привести к ошибкам.
7.4. Основные действия над элементами массивов
1. Инициализация массива: присвоение каждому элементу начального значения:
а) инициализация:
int a[6] = {0, 5, -7, 100, 15}; //a[0] = 0, a[1] = 5, a[2] = -7,
//a[3] = 100, a[4] = 15, a[5] = 0
Инициализация одномерного массива выполняется в фигурных скобках после знака равно, каждый элемент массива отделяется от предыдущего запятой. Количество констант должно соответствовать числу элементов массива. В противном случае, если размер массива больше, чем количество инициаторов, то элементы, для которых значения не указаны, обнуляются.
int a[]={5,-12,9,10};//инициализация массива без определения его размера
В данном случае компилятор сам определит размер одномерного массива. Размер массива можно не указывать только при его инициализации, при обычном объявлении массива обязательно нужно указывать размер массива. Чтобы программно определить число элементов в таком массиве, используется операция sizeof:
int len; // число элементов
len = sizeof (month) / sizeof (int);
Итак, при описании массива можно выполнить начальную инициализацию значений его элементов, для этого нужно задать список инициализирующих значений. Например, в году всегда 12 месяцев, значение числа дней в каждом месяце известно, значит, такая структура может быть задана массивом:
int month[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
Эквивалентом инициализации является простое присваивание вида:
month[0] = 31; // Январь
…
month[11] = 31; // Декабрь
б) ввод элементов массива с клавиатуры:
const int n = 10;
int a[n];
for (i = 0; i < n; i++)
{
cout <<”Введите ”<<i<<” элемент: ”;
cin>>a[i];
}
в) формирование массива с помощью генератора псевдослучайных чисел:
#include <time.h> // для time(0)
#include <stdlib.h> // для srand() и rand()
...
const int n = 10;
int a[n], b[n];
srand(time(0)); // Записывается один раз в начале
for (i = 0; i < n; i++) a[i] = rand()%10; // a[i] Î [0, 10)
|
|
|
for (i = 0; i < n; b [i++] = rand()%51-25); // a[i] Î [-25, 25]
Функция srand() применяется для обновления базы генерации при использовании функции rand(), генерирующей псевдослучайные числа из интервала
[0, RAND_MAX], где RAND_MAX – константа, содержащая наибольшее возможное значение для типа, выбранного в качестве базы генерации. В примере, приведенном выше генерируются элементы типа int и значение RAND_MAX = 32767
г) вычисление элементов массива по формуле:
for (i = 0; i<n; i++) a[i] = 6 * i - 2;
2. Вывод массива на экран:
cout <<” Массив А: ” <<endl;
for (i = 0; i < n; i++) cout <<a[i] <<”\t”;
3. Обработка массива
При работе с одномерными массивами существует большое количество алгоритмов, которые считаются типовыми, т.е. часто встречающимися в практических задачах: ввод-вывод массива, вычисление значений элементов массива, поиск суммы и (или) произведения элементов массива, поиск максимального (минимального) элемента массива, упорядочивание элементов массива, добавление (вставка) новых элементов в массив, удаление данных из массива и т.д.
Пример. Дан массив действительных чисел из n элементов. Найти максимальный по модулю элемент и разделить все элементы массива на полученное значение. Вывести на экран монитора массив после обработки.
Возможный текст программы:
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
const int n = 5;
double x[n], max;
int i; // далее задаём массив из n действительных чисел
cout << "Input " << n << " numbers:" << endl;
for(i = 0; i < n; i++)
cin >> x[i];
// Поиск максимального по модулю элемента массива
// Предположим, что x[0] - это и есть максимальный
// по модулю элемент массива:
max = fabs(x[0]);
// А теперь пробуем себя опровергнуть:
for(i = 1; i < n; i++) //перебираем все элементы массива с первого
if(fabs(x[i]) > max) // сравниваем с текущим максимальным
max = fabs(x[i]); // выполняем переприсваевание
cout << "max=" << max << endl; // Максимум найден
for(i = 0; i < n; i++)
x[i] /= max; // Делим все элементы на max
cout << "Massiv:" << endl; // Распечатка массива
for(i = 0; i < n; i++)
cout << x[i] << endl;
return 0;
}
Лабораторная работа №7
Использование числовых одномерных массивов
ЦЕЛЬ РАБОТЫ: освоение способов описания массива, приобретение навыков организации ввода-вывода и обработки массива.
Выполнение работы: освоить теоретический материал, выполнить общее для всех задание I и в соответствии с вариантом составить программу (задание II), при необходимости реализовав пользовательскую функцию.
Задание I
Изучить порядок описания, ввода-вывода и обработки массивов:
1. Набрать и отладить программу нахождения суммы элементов массива, стоящих в нечетных позициях. Оформить в тетради, записав условие, код, блок-схему и результат работы, объяснить назначение операторов 0-4.
# include <time.h>
# include <stdlib.h>
int main()
{
setlocale(LC_ALL,”Rus”);
srand(time(0)); // Оператор 0
const int N=10;
int Arr[N];
int sum=0; // Оператор 1
for (int i=0;i<N;i++)
{
Arr[i]= rand()%100; // Оператор 2
cout<<Arr[i]<<"\t";
}
for (int i=1;i<N;i+=2) // Оператор 3
sum+=Arr[i]; // Оператор 4
cout<<"\nСумма = "<<sum<<endl;
return 0;
}
2. Набрать и отладить программу нахождения суммы элементов массива, кратных 3. Оформить в тетради, записав условие, код, блок-схему и результат работы, объяснить назначение операторов 0-3.
# include <time.h>
# include <stdlib.h>
int main()
{
time_t t;
srand((unsigned)time(&t)); // Оператор 0
const int N=10;
int Arr[N];
int sum=0; // Оператор 1
for (int i=0;i<N;i++)
{
Arr[i]=rand()%50; // Оператор 2
cout<<Arr[i]<<"\t";
}
for (int i=1;i<N;i++)
if (Arr[i]%3==0) sum+=Arr[i]; // Оператор 3
cout<<"\nSumma="<<sum<<endl;
return 0;
}
3. Набрать и отладить программу нахождения максимального элемента массива из N целых чисел с выводом номеров наибольших элементов. Оформить в тетради, записав условие, код, блок-схему и результат работы, объяснить назначение операторов 1-6.
# include <time.h>
# include <stdlib.h>
int main()
{
srand(time(0));
const int N=10;
int Arr[N];
int index[N]={0}; // Оператор 1
int max, k=0;
for (int i=0;i<N;i++){
Arr[i]=rand()%100-50; // Оператор 2
cout<<Arr[i]<<"\t";
}
max=Arr[0]; // Оператор 3
for (int i=1;i<N;i++)
if (Arr[i]>=max) // Оператор 4
{
max=Arr[i];
index[k]=i+1; // Оператор 5
k++;
}
k=0;
cout<<"\nMax="<<max<<"\nИндексы: ";
while (index[k]>0) // Оператор 6
{
cout<<index[k]-1<<"\t";
k++;
}
return 0;
}
Задание II
В соответствии с вариантом составить и реализовать программу:
1. Даны два массива разных размеров. Определить, какие элементы первого массива и сколько раз встречаются во втором массиве.
2. Массив содержит 2 n чисел. Из суммы первых n его элементов вычесть сумму последних n элементов.
3. Транспонировать массив, т.е. по а 1, а 2,..., аn сформировать аn, аn -1,..., a 1. В полученном массиве найти индекс минимального элемента.
4. Из заданного целочисленного массива удалить все повторяющиеся элементы, оставив только их первые вхождения, т.е. из заданного массива получить новый массив, состоящий из различных целых чисел.
5. Заменить отрицательные числа в массиве их квадратами, оставив остальные без изменения.
6. В заданном массиве найти среднее арифметическое положительных чисел, среднее арифметическое отрицательных чисел и число нулей.
7. В массиве из 2 n чисел найти сумму квадратов элементов с четными индексами и сумму кубов элементов с нечетными индексами.
8. Из чисел а 1, а 2,..., аn выбрать те, которые больше по модулю заданного числа с, и образовать из них новый массив, сохранив порядок следования элементов.
9. Из массива целых чисел составить три других, в первый из которых записать числа, кратные 5, во второй - числа, кратные 7, а в третий - остальные числа.
10. Задан массив из 100 целых случайных чисел, принадлежащих промежутку [0, 100]. Найти сумму тех элементов массива, которые больше 15, но меньше 45, а также вычислить количество этих элементов.
11. В линейном массиве заменить все элементы на число m (m – индекс максимального элемента).
12. Дан массив, состоящий как из положительных, так и отрицательных чисел. Нужно сначала записать положительные числа, а затем отрицательные в том же порядке, как они были расположены в исходном массиве. Если есть нули, записать их в последнюю очередь.
13. Найти сумму элементов данного массива. Разделить каждый элемент исходного массива на полученное значение.
14. Вычислить сумму и разность массивов одного размера.
15. Найти среднее арифметическое значение элементов заданного массива. Преобразовать исходный массив, вычитая из каждого элемента среднее значение.
16. Даны два массива одинакового размера. Рассматривая их как арифметические векторы, найти длины этих векторов и их скалярное произведение.
17. Заданы два массива разных размеров. Объединить их в один массив, включив второй массив между k -ым и (k + 1)-ым элементами первого (k вводится с клавиатуры).
18. Вычесть из положительных элементов данного массива элемент с номером k 1 а к отрицательным элементам прибавить элемент с номером k 2. Нулевые элементы заменить 1. Номера k 1 и k 2 вводятся с клавиатуры.
19. К четным элементам целочисленного массива прибавить данное число а, а из элементов с четными номерами вычесть данное число b.
20. Дан первый член геометрической прогрессии и ее знаменатель. Сформировать одномерный массив, элементами которого служат первые n членов этой прогрессии.
21. Сформировать массив из первых 30 членов последовательности Фибоначчи.
22. Вставить одно и то же число, введенное с клавиатуры, перед каждым отрицательным элементом заданного целочисленного массива.
23. Дан массив четного размера. Поменять местами его половины следующим образом: первый элемент - с последним, второй - с предпоследним элементом и т.д.
24. Даны два целочисленных массива одинакового размера. Получить третий массив того же размера, каждый элемент которого равен большему из соответствующих элементов данных массивов.
25. Задан массив из n целых случайных чисел, принадлежащих промежутку
[-25, 25]. Найти произведение тех элементов массива, которые больше 1, но меньше 15, а также вычислить количество четных элементов массива.
Контрольные вопросы
1. Дайте определение производного типа данных, структурированного типа.
2. Дайте определение массива.
3. Каким может быть тип элементов массива?
4. Имя, размер и размерность массива.
5. Какова структура одномерного массива?
6. Правила описания одномерного массива.
7. Как осуществляется доступ к элементам одномерного массива?
8. Как осуществляется ввод массива?
9. Какие способы ввода массива вы знаете?
10. Вывод линейного массива.
Пример выполнения задания II лабораторной работы
Задание. Массив D содержит 24 значения атмосферного давления за каждый час в течение суток. Определить, какое значение атмосферного давления было наибольшим и в какое время оно было зафиксировано.
Решение
1. Математическая модель
Значением атмосферного давления являются элементы массива D[24], значением времени – индексы элементов. Решение задачи сводится к поиску максимального элемента в массиве и определению его индекса.
Аргументы: D[24] – массив целого типа.
Результаты: imax целого типа – индекс максимального элемента;
D[imax] целого типа – значение максимального элемента.
Промежуточная величина: max целого типа – максимальное значение элемента массива.
| 2. Алгоритм | 3. Программа | |||||||||||||
| #include <iostream> #include <conio.h> #include <math.h> using namespace std; void Input(int mass[24]); void Print(int mass[24]); int main() { int D[24]; cout<<" Введите массив "<<endl; Input(D); cout<<" Массив значений давления:"<<endl; Print(D); int max = D[0], imax = 1; for(int i=0; i<24; i++) { if (D[i]>max) { imax = i+1; max = D[i]; } } cout<<" Максимальное значение давления: "<<D[imax-1]<<" в "<<imax<<" ч. "; _getch(); return 0; } void Input(int mass[24]) { for(int i=0; i<24; i++) { cin>>mass[i]; } } void Print(int mass[24]) { for(int i=0; i<24; i++) { cout<<mass[i]<<" "; } cout<<endl; } |
4. Результат работы программы:
Массив значений давления:
748 743 756 748 741 760 748 743 757 748 756 756 751 760 754
756 752 758 758 757 750 747 759 750
Максимальное значение давления 760 в 6 ч.
8. Двумерные массивы
Итак, массив представляет собой структуру данных, позволяющую хранить под одним именем совокупность данных любого, но только одного какого-то типа. Массив характеризуется своим именем, типом хранимых элементов, размером (числом хранимых элементов), нумерацией элементов и размерностью.
Объявление переменной как одномерного массива (массива с размерностью 1) имеет вид:
тип_данных идентификатор [константное_выражение];
Например, оператор
int A[10];// объявляет массив с именем A, содержащий 10 целых чисел
Доступ к элементам этого массива осуществляется выражением A[i], где i - индекс, являющийся в данном примере целым числом в диапазоне 0 - 9. Например, A[0] - значение первого элемента, A[1] - второго, A[9] - последнего.
Напомним, что объявление переменной массива можно совмещать с заданием элементам массива начальных значений. Например, оператор:
int A[10] = {0};//присваивает нулевые значения всем элементам массива
int A[10] = {1,2,3,4,5,6,7,8,9,10};//A[0] = 1, A[2] = 2, …, A[9] = 10
Если начальных значений меньше, чем элементов в массиве, оставшиеся элементы автоматически получают нулевые начальные значения.
Если массив при его объявлении не инициализирован, то его элементы имеют случайные значения. Элементы такого массива нельзя использовать в выражениях, пока им не будут присвоены какие-нибудь значения.
|
|
|
