Билет 7
Оглавление
Структуры данных определяют классификацию данных и отношения между ними. Структуры могут быть простыми (элементарными) и сложными (составными). Различают следующие структуры: константу, переменную, массив, запись и таблицу. Константу и переменную можно считать элементарными данными, единичными, неделимыми элементами более сложных систем организации данных.
Константа - это число, текст или логическое значение, которые не изменяются в процессе реализации алгоритма, решения задачи на компьютере.
Переменная - это единица организации данных, которой в процессе обработки информации могут присваиваться различные значения. Переменная имеет имя — идентификатор и тип: числовой, символьный (литерный, строковый), логический. Переменные могут сопровождаться словами, указывающими на их тип.
Массив - это объединенное одним именем (идентификатором массива) множество однотипных элементов. К основным параметрам массивов относят его тип (числовой, символьный, логический),размерность (одномерный, двухмерный и т.д.)и размер (количество элементов массива в каждом измерении).
Типы данных:
QBasic Turbo Pascal 7.0
Структура программы Program имя (input, output);
Label; - раздел меток;
Const- раздел констант; Const; - раздел констант;
Type - раздел типов; Type; - раздел типов;
DEF - раздел переменных; Var; - раздел переменных;
Procedure - раздел процедур и Procedure - раздел функций; процедур и функций;
Function Function
BEGIN
оператор 1 оператор 1;
оператор 2 оператор 2;
. . …………..
оператор n-1 оператор n-1;
оператор n оператор n;
END. END.
Переменная - это величина, которая может меняться при выполнении программы. Объявляя переменную или константу заданного типа, Вы отводите в памяти место, где будет храниться ее значение. Тип определяет размер и структуру памяти под переменную.
Типы данных в BASIC
|
Суффикс |
Тип переменной |
Объявление DEF_тип |
Описание AS_тип |
Занимаемый объем |
|
% |
Целые |
DEFINT |
INTEGER |
2 байта |
|
& |
Длинные целые |
DEFLNG |
LONG |
4 байта |
|
! |
Обычной точности |
DEFSNG |
SINGLE |
4 байта |
|
# |
Двойной точности |
DEFDBL |
DOUBLE |
8 байт |
|
$ |
Строка переменной длины |
DEFSTR |
STRING |
1 байт на каждый символ + 4 байта на описатель |
|
$ |
Строка фиксированной длины |
|
STRING*N |
N байт |
Целочисленные типы переменных
|
Тип |
Диапазон возможных значений |
Формат |
|
Shorting |
-128.. 127 |
1 байт со знаком |
|
Integer |
-32768..32767 |
2 байта со знаком |
|
Longint |
-2147483648..2147483647 |
4 байта со знаком |
|
Byte |
0..255 |
1 байт без знака |
|
Word |
0..65535 |
2 байта без знака |
Вещественные типы переменных
|
Тип |
Диапазон возможных значений |
Точность |
Формат |
|
Real |
2.9Е-39..1.7Е38 |
11—12 знаков |
6 байт |
|
Single |
1.5Е-45..3.4Е38 |
7—8 знаков |
4 байта |
|
Double |
5.0E-324..1.7E308 |
15—16 знаков |
8 байт |
|
Extended |
3.4Е-4932..1.1Е4932 |
19-20 знаков |
10 байт |
|
Comp |
-9.2Е18..9.2Е18 |
19—20 знаков |
8 байт |
Обработка массивов
В математике, экономике, информатике часто используются упорядоченные наборы данных, например последовательности чисел, таблицы, списки фамилий. Для обработки наборов данных одного типа вводится понятие массива.
• Массив обозначается одним именем.
• Каждый элемент массива обозначается именем массива с индексом. Элементы массива упорядочены по значениям индекса.
• В языке Qbasic индекс заключается в круглые скобки.
• В Turbo Pascal 7.0 в квадратные.
• Для рассмотренного примера элементами массива А являются:
• На QBasic А(1)=1.6, А(2)=14.9, А(3)= -5.0, А(4)=8.5, А(5)=0.46.
• На Turbo Pascal 7.0 А[1]:=1.6, А[2]:=14.9, А[3]:= -5.0, А[4]:=8.5, А[5]:=0.46.
• Таким образом - индекс определяет положение элемента массива данных относительно его начала.
Работа с массивами одна из наиболее часто встречающихся операций обработки информации. Способов ввода массивов в программу множество. Применение того или иного способа зависит от многих факторов. Во-первых, служат ли данные массива для получения рабочего результата или только для отладки программы . Во-вторых, должен ли массив обладать некоторыми заранее заданными свойствами или требования к массиву не определены. В-третьих, размерность массива задана или написана для общего случая и т. д. Выбор способа ввода позволяет экономить время, например, устраняет необходимость ввода данных при каждом запуске программы, может сделать ввод более надежным, контролируемым.
Основные операторы для работы с массивом:
DATA – хранит в программе строковые и числовые константы, READ – считывает величины из списка, задаваемого оператором DATA.
DIM – оператор объявляет массивы и переменные, очищает и резервирует для них память.
Способы объявления массивов: DIM(8, 3) DIM(0 TO 8, 0 TO 3) DIM(0 TO 8, 3) – объявление двумерного массива.
Рассмотрим некоторые из способов ввода.
|
Способы ввода массива |
Пояснения |
|
Простейший ввод массива при малом количестве элементов можно выполнить операторами DATA и READ. |
|
|
DATA 4, -.8, 5.3E-3, 6 READ A(0), A(1), A(2), A(3)
|
Запись значений в программе Чтение данных в нужном месте |
|
DATA 4, -.8, 5.3E-3, 6 FOR i=0 TO 3 READ A(i) NEXT
|
Запись значений в программе Ввод массива с помощью цикла |
|
Ввод массива с экрана |
|
|
INPUT N DIM A(N) FOR i=1 TO N INPUT A(i) NEXT i
|
Вводим число элементов массива Оператор объявляет одномерный массив Считывание массива с помощью цикла c экрана монитора |
|
Ввод массива из случайных чисел |
|
|
INPUT N DIM A(N) RANDOMIZE TIMER FOR i=1 TO N A(i) = INT (RND *10) NEXT i
|
Вводим число элементов массива Оператор объявляет одномерный массив Включение генератора случайных чисел Считывание случайного массива с помощью цикла |
Рекурсия - это такая организация алгоритма, при которой процедура обращается к самой себе. Сама процедура называется рекурсивной.
В жизни вам не раз приходилось сталкиваться с рекурсией. Вспомните хотя бы стихотворение "У попа была собака" или то, как, сидя в поезде, вы ловили свое отражение в зеркале, которое отражалось в зеркале напротив, которое отражалось в зеркале напротив...
Самым ярким примером является традиционное вычисление чисел Фибоначчи рекурсивным и итеративным способами.
Напомню, что числами Фибоначчи называются числа, принадлежащие
следующей последовательности:
F0 = 0;
F1 = 1;
Fn = Fn-1 + Fn-2 для n > 1.
Задача. В последовательности Фибоначчи первые два члена равны единице, а все последующие – сумме двух предыдущих. Написать программу, находящую определенный член последовательности (найти седьмой член).
|
Решение: 1 способ – итеративный (повторный, многократный)
|
2 способ - рекурсии (переводящих вычислимые функции снова в вычислимые)
|
|
INPUT “ “ , n IF n=1 OR n =2 THEN PRINT 1 ELSE A1 = 1 A2 = 1 FOR I =3 TO n A3 = A1 +A2 A1= A2 A2 = A3 NEXT I PRINT A2 END IF
|
INPUT n DIM A(n) A(1) = 1 A(2) = 1 FOR i = 3 TO n A(i) = A(i - 1) + A(i - 2) NEXT i PRINT A(n)
|
Дополнительно
Задача о кроликах или числа Фибоначчи
В 1202 году итальянский купец Леонардо из Пизы (1180—1240), более известный под прозвищем Фибоначчи, один из самых значительных математиков средневековья, сформулировал такую задачу:
Некто поместил пару кроликов в некоем месте, огороженном со всех сторон стеной, чтобы узнать, сколько пар кроликов родится при этом в течение года, если природа кроликов такова, что через месяц пара кроликов производит на свет другую пару, а рождают кролики со второго месяца после своего рождения.
Рост численности кроликов можно проследить на схеме, выполненной в виде Flash-анимации:
Решая задачу Фибоначчи, мы получаем ряд чисел: 1, 1, 2, 3, 5, 8, 13,… где каждое следующее число равно сумме двух предыдущих. Эта последовательность, получившая название ряда Фибоначчи, обладает удивительными свойствами.
Во-первых, отношение двух соседних чисел приближенно равно числу «фи», и чем дальше пара чисел находится от начала последовательности, тем точнее это приближение.
Во-вторых, с парами чисел Фибоначчи связаны, как ни странно, форма цветков, расположение листьев на стебле растений и зерен в подсолнухе. Об этом написано в разделе Золотое сечение… в природе:
Интерес к этому ученых (да и любителей) отнюдь не случаен. Он вызван прежде всего тем, что повторяющиеся элементы создают симметричные структуры — паттерны, и в них совершенно четко прослеживаются числовые закономерности. Установлено, что почки и листья на ветках растений, чешуйки шишек располагаются точно по спиралям, причем число спиралей, закрученных в правую сторону и число спиралей, закрученных в левую — совпадают с соседними числами ряда Фибоначчи: (1 1 2 3 5 8 13 21 34 55... — здеь каждое следующее число равно сумме двух предыдущих).