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

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К лабораторным работам

По курсу

«ИНФОРМАТИКА»
Лабораторный практикум

Лабораторная работа № 1.

Кодирование информации и элементы алгебры логики

 

Кодирование информации в компьютере

 

· Система счисления - способ наименования и изображения чисел с помощью символов, имеющих определенные количественные значения.

В зависимости от назначения и применения различают внутренние коды (для представления данных в ЭВМ), коды, предназначенные для обмена данными и их передачи по каналам связи и коды для специальных применений.

Внутренние коды базируются на использовании позиционных систем счисления с основанием P. В общем случае число Z_P может быть представлено в виде:

Z_P=A_N*B^N+A_N-1*B^N-1+..+A₁*B¹+A₀*B⁰,

где N - номер позиции или разряд.

A₀, A₁,.., A_N - разрядные коэффициенты, которые могут принимать значения цифр, соответствующей системы счисления.

 

Основные системы счисления,

используемые для представления информации в ЭВМ

Система счисления	Основание P	Символы AI
Двоичная		0, 1
Восьмеричная		0,1,2,3,4,5,6,7
Десятичная		0,1,2,3,4,5,6,7,8,9
Шестнадцатеричная		0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F 10 11 12 13 14 15

Десятичная система счисления

Используемые символы: 0,1,2,3,4,5,6,7,8,9.

Примеры чисел: 245₁₀, 38₁₀, 1379₁₀.

Степени числа 10:

10⁰=1

10¹=10

10²=100 и т.д.

Нумерация разрядов начинается с нуля справа налево.

Представление числа в виде степеней числа 10.

245₁₀ = 2×10² + 4×10¹ + 5×10⁰.

Двоичная система счисления

Используемые символы: 0,1.

Примеры чисел: 10111₂, 1111₂, 01101010₂.

Степени числа 2:

2⁰ = 1

2¹ = 2

2² = 4

2³ = 8

2⁴ = 16

2⁵ = 32

2⁶ = 64

2⁷ = 128

2⁸ = 256

2⁹ = 512

2¹⁰ = 1024

2¹¹ = 2048

2¹² = 4096

Нумерация разрядов начинается с нуля справа налево.

Представление числа в виде степеней числа 2.

10111₁₀ = 1×2⁴ +0×2³ +1×2² +1×2¹ +1×2⁰ = 16 + 4 +2+1 = 23₁₀.

 

Перевод из десятичной системы счисления в двоичную: необходимо представить десятичное число в виде суммы степеней числа 2; если какая-либо степень отсутствует в сумме, в соответствующем разряде двоичного числа будет 0, если присутствует, то 1.

8 7 6 5 4 3 2 1 0

Например:

456 = 256 + 128 + 64 + 8 = 2⁸ +2⁷ +2⁶ +2³ = 111001000₂.

 

Правила сложения двоичных чисел:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = (1) 0

 

Примеры.

 

Представление отрицательных чисел в двоичном коде.

Для того, чтобы получить отрицательное двоичное число, необходимо:

1) инвертировать все разряды положительного двоичного числа;

2) прибавить к младшему разряду единицу.

 

Пример: Вычислить в двоичной форме.

123₁₀-38₁₀ = 85₁₀.

 

1 этап. Переводим числа 123 и 38 в двоичную форму.

	6 5 4 3 2 1 0

123₁₀ = 64+32+16+8+2+1 = 2⁶ +2⁵ +2⁴ +2³+2¹ +2⁰ = 1111011

 

38₁₀ = 32+ 4+2 = 2⁵ +2² +2¹= 100110₂ = 0100110₂ (Выравниваем количество разрядов).

2 этап. Переводим 38₁₀ в - 38₁₀:

1) инвертируем все разряды

¯

2) прибавляем к младшему разряду единицу

 

0000001

- 38₁₀ = 1011010₂

3 этап. Выполняем сложение 123₁₀ + - 38₁₀:

⁺ 1011010

(1)1010101 (старшая единица в разряд переноса)

4 этап. Переводим 1010101₂ = 2⁶ +2⁴ +2² +2⁰ = 64+16+4+1=85₁₀.

 

Умножение двоичных чисел:

Пример: 15×15 = 225.

1111

1111.

 

Восьмеричная система счисления

 

Используемые символы: 0,1,2,3,4,5,6,7.

Примеры чисел: 123₈, 10₈, 437₈.

Степени числа 8:

8⁰= 1

8¹= 8

8²= 64

8³= 512

8⁴= 4096

Нумерация разрядов начинается с нуля справа налево.

Представление числа в виде степеней числа 8.

123₈ = 1×8² + 2×8¹ + 3×8⁰ = 64+16+3=83₁₀.

 

Перевод из десятичной системы счисления в восьмеричную: необходимо представить десятичное число в виде суммы степеней числа 8; при этом степени могут включены несколько раз.

500₁₀ = 7×8² + 6×8¹ + 4×8⁰ = 764₈.

Перевод из восьмеричной системы счисления в двоичную: каждая восьмеричная цифра заменяется триадой (своим двоичным представлением в трех разрядах)

573₈ = 101 111 011₂

Перевод из двоичной системы счисления в восьмеричную: каждая триада заменяется на соответствующую восьмеричную цифру, при этом выделение триад начинается с младшего (нулевого) разряда. Недостающие старшие разряды дополняются нулями.

1 111 011 101 011₂ = 001 111 011 101 011₂ = 17353₈.

 

Шестнадцатеричная система счисления

Используемые символы: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.

A - 10 D - 13

B - 11 E - 14

C - 12 F - 15

Примеры чисел: 123₁₆, A10₁₆, 4F₁₆, CD₁₆, E2A₁₆.

Степени числа 16:

16⁰= 1

16¹= 16

16²= 256

16³= 4096

 

Нумерация разрядов начинается с нуля справа налево.

 

Представление числа в виде степеней числа 16.

E2A₈ = 14×16² + 2×16¹ + 10×16⁰ = 14×256 + 2×16 + 10×1 = 3584+32+10= =3626₁₀.

 

Перевод из десятичной системы счисления в шестнадцатеричную: необходимо представить десятичное число в виде суммы степеней числа 16; при этом степени могут включены несколько раз.

 

901₁₀ = 3×16² + 8×16¹ + 5×16⁰ = 385₁₆.

 

Перевод из шестнадцатеричной системы счисления в двоичную: каждая шестнадцатеричная цифра заменяется тетрадой (своим двоичным представлением в четырех разрядах)

 

2F3D₁₆ = 0010 1111 0011 1101₂

 

Перевод из двоичной системы счисления в шестнадцатеричную: каждая тетрада заменяется на соответствующую шестнадцатеричную цифру, при этом выделение тетрад начинается с младшего (нулевого) разряда. Недостающие старшие разряды дополняются нулями.

 

11 1101 0001 1011₂ = 0011 1101 0001 1011₂ = 3D1B₈.

 

Элементы алгебры логики

Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики или булева алгебра.

Дж. Буль – английский математик 19 века. Булева алгебра оперирует с логическими переменными, которые могут принимать только 2 значения: истина и ложь, обозначаемые соответственно 1 и 0.

· Совокупность значений логических переменных , ,…, называется набором переменных. Набор логических переменных удобно изображать в виде n-разрядного двоичного числа, каждый разряд которого равен значению одной из переменных. Количество наборов логических переменных в n двоичных разрядах равно 2 ⁿ.

· Логической функцией от набора логических переменных f(, ,…, ) называется функция, которая может также принимать только 2 значения: истина или ложь.

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

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

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

Наиболее часто используемая система логических функций: инверсия (ù, отрицание, NOT), конъюнкция (), логическое умножение, AND, &), дизъюнкция (Ú, логическое сложение, OR).

 

 

№	Перевод из 16 в 10	Перевод из 16 в 8	Сложить в двоичном виде	Построить таблицу истинности для логической функции на всех наборах ее переменных
	BE				F(X1, X2, X3) = (X1 Ú X2) ÙØ((X1 Ú X3) Ù(X2 Ú X3))
	1F	1F2			F(X1, X2, X3) = Ø(X1 Ú X2) Ù (X1 Ú X3) Ù(X2 Ú X3)
	3D	4D3			F(X1, X2, X3) = (X1 Ú X2) Ù (X1 Ú X3) ÙØ(X2 Ú X3)
	6A				F(X1, X2, X3) = (X1 Ù X2) Ú (X1 Ù X3) ÚØ(X2 Ù X3)
	DA	2A4			F(X1, X2, X3) = Ø(X1 Ù X2) Ú (X1 Ù X3) Ú (X2 Ù X3)
	FC	A22			F(X1, X2, X3) = (X1 Ù X2) Ú Ø (X1 Ù X3) Ú (X2 Ù X3)
	4D	3DC			F(X1, X2, X3) = Ø ((X1 Ù X2) Ú Ø (X1 Ù X3)) Ú (X2 Ù X3)
		B3A			F(X1, X2, X3) = Ø ((X1 Ù X2) Ú (X1 Ù X3))Ú (X2 Ù X3)
	9B				F(X1, X2, X3) = (X1 Ù X2) Ú Ø ((X1 Ù X3) Ú (X2 Ù X3))
	2E	62A			F(X1, X2, X3) = Ø (X1 Ù X2) Ú Ø((X1 Ù X3) Ú (X2 Ù X3))
	6A	77D			F(X1, X2, X3) = (X1 Ú ØX) ÙØ ((X1 Ú X3) Ù(X2 Ú X3))
		AAB			F(X1, X2, X3) = Ø(X1 Ú X2) Ù (X1 ÚØ X3) Ù(X2 Ú X3)
		DDD			F(X1, X2, X3) = (X1 Ú ØX2) Ù (X1 Ú X3) ÙØ(X2 Ú X3)
	FF	37F			F(X1, X2, X3) = (ØX1 Ù X2) Ú (X1 Ù X3) ÚØ(X2 Ù X3)
	E3	21F			F(X1, X2, X3) = Ø(X1 ÙØ X2) Ú (X1 Ù X3) Ú (X2 Ù X3)
	C6				F(X1, X2, X3) = (X1 Ù X2) Ú Ø (X1 Ù X3) Ú (ØX2 Ù X3)
	9A	98A			F(X1, X2, X3) = Ø ((X1 Ù X2) Ú Ø (X1 Ù X3)) Ú (ØX2 Ù X3)
	BB	65F			F(X1, X2, X3) = Ø ((X1 Ù X2) Ú (X1 Ù X3))Ú (X2 ÙØ X3)
	2B	22F			F(X1, X2, X3) = (X1 Ù X2) Ú Ø ((X1 Ù X3) Ú (X2 Ù ØX3))
	AA	45A			F(X1, X2, X3) = Ø (X1 Ù X2) Ú Ø((X1 Ù ØX3) Ú (X2 Ù X3))
		5CB			F(X1, X2, X3) = (X1 Ú X2) ÙØ((X1 Ú ØX3) Ù(X2 Ú X3))
	DD	37A			F(X1, X2, X3) = Ø(X1 Ú X2) Ù (X1 Ú X3) Ù(X2 Ú X3)
	7C				F(X1, X2, X3) = (X1 Ú X2) Ù (ØX1 Ú X3) ÙØ(X2 Ú X3)
	EE				F(X1, X2, X3) = (X1 Ù X2) Ú (ØX1 Ù X3) ÚØ(X2 Ù X3)

 

№	Перевод из 16 в 10	Перевод из 16 в 8	Сложить в двоичном виде	Построить таблицу истинности для логической функции на всех наборах ее переменных
	CA				F(X1, X2, X3) = Ø(X1 Ù ØX2) Ú (X1 Ù X3) Ú (X2 Ù X3)
	2C				F(X1, X2, X3) = (X1 Ù ØX2) Ú Ø (X1 Ù X3) Ú (X2 Ù X3)
	AC	18D			F(X1, X2, X3) = Ø ((X1 Ù ØX2) Ú (X1 Ù X3)) Ú (X2 Ù X3)
	8F	10C			F(X1, X2, X3) = Ø ((X1 Ù X2) Ú (ØX1 Ù X3))Ú (X2 Ù X3)
		44A			F(X1, X2, X3) = (X1 Ù X2) Ú Ø ((X1 Ù ØX3) Ú (X2 Ù X3))
		7B8			F(X1, X2, X3) = Ø (X1 Ù X2) Ú Ø((ØX1 Ù X3) Ú (X2 Ù X3))

 

Лабораторная работа № 2

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

 

Алгоритм и его программная реализация тесно взаимосвязаны.

· Программа – упорядоченная последовательность инструкций компьютера (команд) для решения задачи.

· Программное обеспечение – совокупность программ обработки данных и необходимых для их эксплуатации документов.

· Программирование – теоретическая и практическая деятельность, связанная с созданием программ.

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

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

 

Структура программы на языке Паскаль

 

Program <имя программы>;

uses <имена модулей>; {Раздел использования модулей}

type <имя типа> = <определение типа>; {Раздел описания собственных типов}

var <переменная>: <имя типа>; {Раздел описания переменных}

 

{Раздел описания подпрограмм - процедур и функций}

рrocedure <имя процедуры [(список параметров)]>;

var <список переменных процедуры>;

Begin

{Тело процедуры}

end;

function <имя функции [(список параметров)]>: <тип результата>;

var <список переменных процедуры>;

Begin

{Тело функции}

end;

Begin {Основная программа}

{Тело программы}

End.

 

 

Язык программирования Паскаль

Описание 1 способ: задается целочисленный массив фиксированной длины 10 var A: array [1..10] of integer; i:integer; {индекс элементов массива}   2 способ: задается целочисленный массив фиксированной длины 10. В программе в качестве длины массива используется константа n. const n=10; var A: array [1..n] of integer; i:integer; {индекс элементов массива}

3 способ: задается целочисленный массив длиной не более 10 (nmax). В программе в качестве фактической длины массива используется переменная константа n. const nmax=10; type vector = array [1..nmax] of integer; var A:vector; i:integer; {индекс элементов массива} n:integer; {фактическое количество элементов массива}

Ввод for i:=1 to n do readln(A[i]);

Вывод for i:=1 to n do writeln(A[i]);

Задание к лабораторной работе:

Cоставить алгоритм и написать программу:

 

1. Для одномерного целочисленного массива из 20 элементов решить задачу поиска максимального элемента и его номера.

2. Для одномерного целочисленного массива из 20 элементов решить задачу поиска суммы положительных элементов.

3. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества четных элементов.

4. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества элементов, больших своего предыдущего.

5. Для одномерного целочисленного массива из 20 элементов решить задачу поиска среднего арифметического положительных элементов.

6. Для одномерного целочисленного массива из 20 элементов решить задачу поиска суммы четных элементов.

7. Для одномерного целочисленного массива из 20 элементов решить задачу поиска среднего арифметического нечетных элементов.

8. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества ненулевых элементов.

9. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества элементов, неравных своему предыдущему.

10. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера первого отрицательного элемента.

11. Для одномерного целочисленного массива из 20 элементов решить задачу поиска суммы нечетных элементов.

12. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера последнего отрицательного элемента.

13. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества нулевых элементов.

14. Для одномерного целочисленного массива из 20 элементов решить задачу поиска среднего арифметического четных элементов.

15. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества элементов, меньших своего предыдущего.

16. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера первого положительного элемента.

17. Для одномерного целочисленного массива из 20 элементов решить задачу поиска суммы ненулевых элементов.

18. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества отрицательных элементов.

19. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера последнего положительного элемента.

20. Для одномерного целочисленного массива из 20 элементов решить задачу поиска среднего арифметического отрицательных элементов.

21. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера первого нечетного элемента.

22. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества элементов, равных своему предыдущему.

23. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества положительных элементов.

24. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера первого нулевого элемента.

25. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера последнего четного элемента.

26. Для одномерного целочисленного массива из 20 элементов решить задачу поиска среднего арифметического ненулевых элементов.

27. Для одномерного целочисленного массива из 20 элементов решить задачу поиска номера первого четного элемента.

28. Для одномерного целочисленного массива из 20 элементов решить задачу поиска количества нечетных элементов.

29. Для одномерного целочисленного массива из 20 элементов решить задачу поиска суммы отрицательных элементов.

30. Для одномерного целочисленного массива из 20 элементов решить задачу поиска минимального элемента и его номера.

 

Лабораторная работа № 3