Алгоритмизация и программирование решения задач на языке СИ (90

Рекуррентной формулой называется формула, связывающая (p + 1) соседних элементов некоторой последовательности. Задав p первых элементов последовательности, можно с помощью этой формулы шаг за шагом определить (p + 1)-й, (p + 2)-й, (p + 3)-й, … элементы. Заметим, что все заданные последовательности a1, a2, a3, a4 , a5, … получены с применением рекуррентной формулы вида ai = b*ai-1+c, связывающей два соседних элемента ai и ai-1, т.е. p = 1. Алгоритм вычисления суммы s первых n элементов числовой последовательности должен содержать:

-ввод значения n;

-задание значения s, равного значению a1;

-для каждого значения i от 2 до n увеличение s на значение ai, вычисляемое по рекуррентной формуле;

-вывод значения s.

Коэффициенты b и c рекуррентной формулы можно определить путем решения системы уравнений {a2 = ba1 + c, a3 = ba2 + c}.

21

5 Обработка массивов данных

Цель работы: ознакомиться с данными типа массив и основными приемами программирования задач обработки массивов.

5.1 Методические указания к выполнению работы

5.1.1 Одномерные и двумерные массивы

Под массивом понимают набор данных одного и того же типа, собранных под одним именем. Каждый элемент массива определяется именем массива и порядковым номером элемента, который называется индексом. Индекс в языке С всегда целое число. Чтобы использовать массив, надо его объявить – выделить место в памяти. Основная форма объявления массива размерности N такова:

тип <имя массива>[размер1][размер2]…[ размер N]

Чаще всего используются одномерные массивы:

тип <имя массива>[размер];

Тип – базовый тип элементов массива, размер – количество элементов одномерного массива. При описании двумерного массива его объявление имеет следующий вид:

тип <имя массива>[размер1][размер2];

В этом описании можно трактовать объявление двумерного массива как объявление массива массивов, т. е. массив размера [размер2], элементами которого являются одномерные массивы <имя массива>[размер1].

Типом массива называется тип массива это тип входящих в него элементов. Массивы могут быть разных типов — int, float, char, и т.д. Массив объявляют так же, как и обычные переменные, но после имени массива в квадратных скобках записывается его размер.

Например,

int A[10], B[20]; // 2 массива на 10 и 20 целых чисел float C[12]; // массив из 12 вещественных чисел

При объявлении массива можно сразу заполнить его начальными значениями, перечисляя их внутри фигурных скобок, например:

int A[4] = { 2, 3, 12, 76 };

22

Если в списке в фигурных скобках записано меньше чисел, чем элементов в массиве, то оставшиеся элементы заполняются нулями. Если чисел больше, чем надо, транслятор сообщает об ошибке. Например,

int A[4] = { 2 }; // последние три элементы равны 0

Каждый элемент массива имеет свой порядковый номер. Чтобы обратиться к элементу массива, надо написать имя массива и затем в квадратных скобках номер нужного элемент.

Важно запомнить одно важное правило: элементы массивов в языке Си нумеруются с нуля. Таким образом, если в массиве 10 элементов, он содержит элемен-

ты: A[0], A[1], A[2], ..., A[9]

Номер элемента массива также называется его индексом. Вот примеры обращения к массиву:

x = (A[3] + 5)*A[1]; // прочитать значения A[3] и A[1] A[0] = x + 6; // записать новое значение в A[0].

При работе с двумерными массивами в языке Си каждый индекс записывается отдельно в квадратных скобках. Каждую строку и каждый столбец матрицы можно рассматривать как обычный одномерный массив. Поэтому можно сказать, что матрица – это массив из массивов. Необходимо при этом помнить, что все элементы матрицы должны быть одинакового типа и все строки матрицы должны быть одинаковой длины.

Двумерные массивы объявляются также, как и простые массивы, но у них не один индекс, а два. При объявлении в отдельных квадратных скобках указывается количество строк и количество столбцов.

Например, оператор int В[20][10] выделит место в памяти под матрицу целых чисел, имеющую 20 строк и 10 столбцов (всего 200 элементов).

В языке Си элементы матрицы располагаются по строкам, то есть сначала изменяется последний индекс. Например, объявлена матрица X[2][3], элементы массива при этом располагаются так:

X[0][0], X[0][1], X[0][2], X[1][0], X[1][1], X[1][2].

Для повышения универсальности программы размер массива лучше определять через константу. В этом случае для переделки программы для массива другого размера надо только поменять значение этой константы. Директива препроцессора define используется, что бы создать константы. Синтаксис директивы #define:

#define идентификатор значение

Перед компиляцией программы, во всех местах, где используется идентификатор, будет произведена замена его на значение, которое указана там же.

Когда вместо того, чтобы пользоваться переменными памяти, создаете константы с помощью директив #DEFINE, вы сокращаете потребление памяти, повышаете производительность и упрощаете программы.

Чтобы создать константу с помощью директивы #DEFINE, задайте в аргументе идентификатор имя константы, а в аргументе значение ее значение. В процессе компиляции программы производится подстановка текста: имя константы заменяется выражением значения константы везде, где это имя встречается в программе.

23

Существует много способов в зависимости от вашей задачи:

–элементы массива вводятся с клавиатуры вручную;

–массив заполняется случайными числами (например, для моделирования случайных процессов);

–элементы массива читаются из файла;

–элементы массива поступают через порт с внешнего устройства (например, сканера, модема и т.п.);

–массив заполняется в процессе вычислений.

5.1.2 Сортировка массивов

Сортировка – это расстановка элементов некоторого списка в заданном по-

рядке.

Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь процедурой сравнения элементов. Рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания.

На сегодняшний день существует несколько алгоритмов решения задач сортировки. Это связано с тем, что одни алгоритмы осуществляют при определенных условиях ранжирование быстрее, чем другие. Самыми распространенные методы ранжирования:

-метод « всплывающего пузырька»;

-метод выбора минимального элемента;

-сортировка Шелла;

-метод парных перестановок и т.д..

Пузырьковая сортировка. Название этого метода произошло от известного физического явления – пузырек воздуха в воде поднимается вверх. В этом методе сначала поднимается «наверх» (к началу массива) самый «легкий» элемент (минимальный), затем следующий и т.д.В последовательности сравниваются два соседних элемента, например, К и К+1, допустим, произошла перестановка этих элементов. В этом случае далее делается проверка для всех элементов от К-го до первого, т. е. движение «вверх» по последовательности с перестановкой соответствующих элементов.

Чтобы не просматривать массив каждый раз с самого начала, можно запомнить место (индекс) последнего обмена. Все пары соседних элементов с индексами, меньшими запомненного, уже расположены в нужном порядке.

Метод пузырька работает медленно, особенно на больших массивах. Можно показать, что при увеличении размера массива в 10 раз время выполнения программы увеличивается в 100 раз (метод имеет порядок N2).

Пример программы сортировки пузырьком:

#include<stdio.h>

#include<conio.h> #define N 10

24

main()

{

int i, j, A[N], temp;

printf("\nВведите массив A: \n"); for ( i = 0; i < N; i ++ ) scanf("%d", &A[i]);

for ( i = 0; i < N-1; i ++ ) for ( j = N-2; j >= i; j -- )

if ( A[j] > A[j+1] )

{

temp = A[j]; A[j] = A[j+1]; A[j+1] = temp;

}

printf("\nОтсортированный масив:\n"); for ( i = 0; i < N; i ++ )

printf("%d ", A[i]); getch();

}

Выбор минимального элемента. Еще один недостаток метода пузырька состоит в том, что приходится слишком часто переставлять местами соседние элементы. Этого можно избежать, если использовать метод выбора минимального элемента. Он заключается в следующем. Ищем в массиве минимальный элемент и ставим его на первое место. Затем из оставшихся элементов также ищем минимальный и ставим на следующее место и т.д. В сравнении с методом пузырька, этот метод требует значительно меньше перестановок элементов (в худшем случае N-1). Он дает значительный выигрыш, если перестановки сложны и занимают много времени.

Пример программы сортировки выбором минимального элемента:

#include<stdio.h> #define N 10 #include<conio.h> main()

{

inti, j, nMin, A[N], temp; printf("\nВведите массив :\n"); for ( i = 0; i < N; i ++ ) scanf("%d ", &A[i]);

for ( i = 0; i < N-1; i ++ )

{

25

nMin = i;

for ( j = i+1; j < N; j ++ )

{

if ( A[j] < A[nMin] ) nMin = j;

}

if ( nMin != i )

{

temp = A[i]; A[i] = A[nMin]; A[nMin] = temp;

}

}

printf("\nОтсортированный массив:\n"); for ( i = 0; i < N; i ++ )

printf("%d ", A[i]); getch(); }

5.2 Примеры работы с массивами

Пример 1. Ввести с клавиатуры массив из 10 элементов, умножить все элементы на 2 и вывести полученный массив на экран.

Чтобы ввести массив в память, надо каждый его элемент обработать отдельно (например, вызвав для него функцию ввода scanf).

Ввод с клавиатуры применяется в простейших программах, когда объем вводимой информации невелик. Для ввода массива будем использовать цикл for. Напомним, что массив надо предварительно объявить, то есть выделить под него память. Вводить можно столько элементов массива, сколько ячеек памяти выделено. Помните, что элементы массива нумеруются с нуля, поэтому если массив имеет всего 10 элементов, то последний элемент имеет номер 9. Если пытаться записывать в 10-ый элемент, произойдет выход за границы массива, и программа может работать неверно. При вводе массива желательно выдать на экран общую подсказку для ввода всего массива и подсказки для каждого элемента.

Для умножения элементов массива на 2 надо снова использовать цикл, в котором за один раз обрабатывается 1 элемент массива.

Вывод массива на экран выполняется также в цикле for. Элементы выводятся по одному. Если в конце строки формата в операторе printf поставить пробел, то элементы массива будут напечатаны в строчку, а если символ \n – то в столбик.

26

Пример 2. Необходимо транспонировать матрицу 2 на 3. Транспонирование матрицы − это замена строк столбцами и наоборот. Необходимо производить запись элементов строк исходной матрицы в столбцы новой матрицы.

printf("\nВывод транспонированной матрицы :\n"); for(i=0; i<N; i++)

{

for(j=0; j<M; j++) printf("%d ", B[i][j]); printf("\n");

}

}

27

5.3Варианты индивидуальных заданий

5.3.1 Обработка одномерных массивов

1.Дан массив А(10). Найти сумму и количество положительных элемен-

тов.

2.Дан массив А(10). Найти минимальный элемент массива и его порядко-

вый номер.

3.Дан массив А(10). Найти максимальный элемент массива и его порядко-

вый номер.

4.Дан массив А(10). Найти те члены массива, которые кратны 5.

5.Дан массив А(10). Обменять местами последний и минимальный эле-

менты

6.Дан массив А(10). В массиве все положительные элементы заменить их квадратами, а отрицательные их кубами

7.Дан массив А(10). Определить сумму и количество отрицательных эле-

ментов.

8.Дан массив А(10). Найти сумму и количество нечетных положительных

элементов.

9.Дан массив А(10). В массиве все элементы меньше двух заменить нуля-

ми.

10.Дан массив А(10). Определение суммы минимального и максимального элементов

11.Даны массивы А(10) и В(10). Вычислить суммы соответствующих элементов массивов.

12.Дан массив А(10). Заменить каждый элемент на минимальный элемент

13.Дан массив А(10). Вычислить произведение отрицательных элементов

массивов.

14.Дан массив А(10). Переписать массив в обратном порядке.

15.Дан массив А(10). Найти наименьший положительный элемента среди элементов с четными номерами массива.

16.Составить программу для нахождения наименьшего из отрицательных элементов массива А(10).

17.Найти наибольший среди элементов массива А(10), остальные обну-

лить.

18.Дан массив А(10). Элементы массива, которые меньше 10, увеличить в два раза, а остальные уменьшить на 10.

19.Дан массив А(10). Необходимо упорядочить элементы по убыванию.

20.Определение количества всех элементов, больших числа с.

21.Определение произведения всех положительных элементов.

22.Упорядочение всех элементов по возрастанию.

23.Определение суммы всех элементов, меньших числа с.

24.Обмен местами первого и максимального элементов.

28

5.3.2 Обработка двумерных массивов

1.Найти сумму положительных элементов матрицы А(3,5).

2.В матрице А(3,3) найти количество нулевых элементов.

3.В матрице А(3,5) найти произведение положительных элементов.

4.В матрице А(4,3) необходимо определить количество элементов, больших числа а.

5.Найти количество отрицательных элементов матрицы А(4,4).

6.Дан массив А(5,5). Найти минимальный элемент среди элементов, расположенных в нечетных строках массива.

7.Дан массив А(5,5). Упорядочить элементы массива в каждой строке по возрастанию.

8.Дан массив А(8,8). Найти максимальный элемент среди элементов строк.

9.Найти среднее арифметическое четных элементов матрицы А(4,4).

10.В матрице А(3,3) необходимо определить сумму всех элементов, меньших числа а.

11.Дан массив А(5,5). Упорядочить элементы массива в каждой строке по

убыванию.

12.Дан массив А(5,5). Необходимо заменить каждый элемент, больше числа

с, на данное число с.

13. Определение среднего арифметического всех элементов строк масси-

ва А(5,5).

14.Дан массив А(8,8). Найти минимальный элемент среди элементов строк.

15.Обмен местами элемента последней строки, последнего столбца и минимального элемента в массиве А(5,5).

16.Дан массив А(8,8). Необходимо найти минимальный элемент и индекс минимального элемента.

17. Необходимо обменять местами элемент последней строки, последнего столбца и максимальный элемент.

18.Размещение элементов строк в обратном порядке.

19.Замена каждого элемента, меньшего числа с, на с.

20.Определение суммы минимального и максимального элементов.

21.Определение индексов максимального элемента Определение максимального элемента.

22.Обмен местами элемента первой строки, первого столбца и максимального элемента.

23.Обмен местами соответствующих элементов первого и последнего

столбцов.

24.Определение произведения всех элементов, меньших числа с.

29

6 Основные требования к содержанию и оформлению работы

Расчетно-графическая работа (контрольная работа) состоит из решения 6 задач по вариантам. Номер варианта контрольной работы определяется номером в списке. Решение задач должно содержать:

-постановку задачи;

-блок-схему алгоритма;

-листинг программы;

-результат программы (отображение внешнего вид окна).

Обязательными элементами расчетно-графического задания (контрольной работы) работы являются:

1)титульный лист;

2)задание;

3)содержание;

4)решение задач;

5)список использованных источников.

Дополнительными элементами расчетно-графического задания (контрольной работы) являются приложения.

Оформление расчетно-графического задания (контрольной работы) следует осуществлять с обязательным использованием стандарта организации СТО 02069024.101-2010 «Работы студенческие. Общие требования и правила оформления».

Защита расчетно-графического задания (контрольной работы) предполагает выявление уровня ориентации студента в алгоритмизации, способности аргументировать положения работы. На защите студент должен показать самостоятельность выполнения работы, продемонстрировать владение материалом, уметь отвечать на вопросы как теоретического, так и практического характера, относящиеся к теме работы.

30