Файл: Информационные системы и базы данных (1, 2)Врем Информационные системы.pdf

Массивы, системы счисления, представление целых чисел в ЭВМ (4, 6, 7)
1
????
Массивы, системы
счисления, представление
целых чисел в ЭВМ (4, 6, 7)
Время
4.Массивы и списки
4.1 Достоинства и недостатки массивов
Достоинства массивов:
лёгкость вычисления адреса элемента по его индексу одинаковое время доступа ко всем элементам малый размер элементов: они состоят только из информационного поля
Недостатки массивов:
для статического массива — отсутствие динамики, невозможность удаления или добавления элемента без сдвига других для динамического и/или гетерогенного массива — более низкое (по сравнению с обычным статическим) быстродействие и дополнительные накладные расходы на поддержку динамических свойств и/или гетерогенности.
при работе с массивом в стиле C (с указателями) и при отсутствии дополнительных средств контроля — угроза выхода за границы массива и повреждения данных
4.2 Динамические массивы. Алгоритм изменения размера
массива
Динамические массивы – массивы с возможностью изменения размера
1. Выделить память нового размера
@January 14, 2023 15:30-16:45

Массивы, системы счисления, представление целых чисел в ЭВМ (4, 6, 7)
2 2. Скопировать старые данные в новую область
3. Объявить новую память «старым» массивом
4. Освободить старую память
4.3 Динамические массивы. Проблемы роста.
Динамические массивы – массивы с возможностью изменения размера
Проблема линейного роста – в большом количестве выделяемой памяти
Общая проблема роста – кусочно-разбросанные остающиеся области памяти
4.4 Списки. Операции с элементами списков.
Список – структура с последовательным доступом
Основные операции для работы со списками - это индексирование, срезы, добавление и удаление элементов, а также проверка на наличие элемента в последовательности
6.Системы счисления
6.1 Отличительные особенности симметричной троичной
системы счисления
Благодаря тому что основание 3 нечётно, в троичной системе возможно симметричное относительно нуля расположение цифр: −1, 0, 1. Свойства:
Естественность представления отрицательных чисел;
Отсутствие проблемы округления: обнуление ненужных младших разрядов округляет — приближает число к ближайшему «грубому».
Для изменения знака представляемого числа нужно изменить ненулевые цифры на симметричные.
При суммировании большого количества чисел значение для переноса в следующий разряд растёт с увеличением количества слагаемых не линейно, а пропорционально квадратному корню числа слагаемых.
По затратам количества знаков на представление чисел она равна троичной несимметричной системе.
6.2 Отличительные особенности фибоначчиевой системы
счисления

Массивы, системы счисления, представление целых чисел в ЭВМ (4, 6, 7)
3
Алфавит – цифры 0 и 1.Базис (веса разрядов) – последовательность чисел
Фибоначчи: 1, 2, 3, 5, 8, 13, 21, 34, …
Преимущество кодов Фибоначчи для практики – в их «естественной» избыточности, которая может быть использована для целей контроля числовых преобразований.
Избыточность проявляет себя в свойстве множественности представлений одного и того же числа.
Разные представления:
операция свертки 011 → 100
операция развертки 100 → 011 3210 = 21*1 + 13*0 + 8*1 + 5*0 + 3*1 + 2*0 + 1*0 1010100fib - минимальная форма, в которой рядом не встречаются две единицы
1010011fib
1001111fib
0111111fib – максимальная (развернутая) форма, в которой рядом не встречаются два нуля
6.3 Минимальная и максимальная форма фибоначчиевой
системы счисления
3210 = 21*1 + 13*0 + 8*1 + 5*0 + 3*1 + 2*0 + 1*0 1010100fib - минимальная форма, в которой рядом не встречаются две единицы
1010011fib
1001111fib
0111111fib – максимальная (развернутая) форма, в которой рядом не встречаются два нуля
7.Представление целых чисел в памяти ЭВМ
7.1 Напишите формулу, показывающую диапазон значений,
доступный для хранения областью памяти размером K

Массивы, системы счисления, представление целых чисел в ЭВМ (4, 6, 7)
4
битов (знаковое кодирование). Частные случаи для
стандартных размеров памяти.
Знаковые (все биты – информационные), хранение только неотрицательных чисел
Знаковое кодирование K битов:
8 битов (char, shortint): [-128; 127]
16 битов (short int, integer): [-32768; 32767]
32 бита (long int, longint): [-2.1млрд; 2.1млрд]
64 бита (int64): [-263; 263-1]
7.2 Напишите формулу, показывающую диапазон значений,
доступный для хранения областью памяти размером K
битов (беззнаковое кодирование) Частные случаи для
стандартных размеров памяти.
Беззнаковые (старший бит – знаковый, остальные – информационные), имеется возможность хранения отрицательных значений
Беззнаковое кодирование K битов:
8 битов (unsigned char, byte) – [0; 255]
16 битов (unsigned short int, word) – [0; 65535]
32 бита (unsigned long int, cardinal) – [0; 4.2млрд]
64 бита (int64) – [0; 264-1]
[−2
; 2
−
K
−1
K
−1 1]
[0; 2 −
K
1]