2. Представление чисел в ЭВМ. Формализованное понятие алгоритма

2. Представление чисел в ЭВМ. Формализованное понятие алгоритма

32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса попадают в диапазон 00000 – FFFFF. Байты памяти могут объединяться в поля как фиксированной, так и переменной длины. Словом называется поле фиксированной длины, состоящее из 2 байтов, двойным словом – поле из 4 байтов. Адреса полей бывают четные и нечетные, при этом для четных адресов операции выполняются быстрее.

Числа с фиксированной точкой в ЭВМ представляются как целые двоичные числа, и занимаемый ими объем может составлять 1, 2 или 4 байта.

Целые двоичные числа представляются в дополнительном коде. Дополнительный код положительного числа равен самому числу, а дополнительный код отрицательного числа может быть получен по такой формуле:

x = 10n – x, где n – разрядность числа.

В двоичной системе счисления дополнительный код получается путем инверсии разрядов, т. е., заменой единиц нулями и наоборот, и прибавлением единицы к младшему разряду.

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

Формализованное понятие алгоритма

Алгоритм может существовать только тогда, когда в то же самое время существует некоторый математический объект. Формализованное понятие алгоритма связано с понятием рекурсивных функций, нормальных алгоритмов Маркова, машин Тьюринга.

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

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

Базовыми функциями и их сопутствующими алгоритмами могут выступать:

1) функция n независимых переменных, тождественно равная нулю. Тогда, если знаком функции является ?n, то независимо от количества аргументов значение функции следует положить равным нулю;

2) тождественная функция n независимых переменных вида ? ni. Тогда, если знаком функции является ? ni, то значением функции следует взять значение i-го аргумента, считая слева направо;

3) ?—функция одного независимого аргумента. Тогда, если знаком функции является ?, то значением функции следует взять значение, следующее за значением аргумента.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Формат чисел

Из книги автора

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


3. Представление чисел в ЭВМ

Из книги автора

3. Представление чисел в ЭВМ 32-разрядные процессоры могут работать с оперативной памятью емкостью до 232-1, а адреса могут записываться в диапазоне 00000000 – FFFFFFFF. Однако в реальном режиме процессор работает с памятью до 220-1, а адреса попадают в диапазон 00000 – FFFFF. Байты памяти


4. Формализованное понятие алгоритма

Из книги автора

4. Формализованное понятие алгоритма Алгоритм может существовать только тогда, когда в то же самое время существует некоторый математический объект. Формализованное понятие алгоритма связано с понятием рекурсивных функций, нормальных алгоритмов Маркова, машин


1. Понятие вспомогательного алгоритма

Из книги автора

1. Понятие вспомогательного алгоритма Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.Подпрограмма – это некоторый вспомогательный алгоритм, многократно использующийся в


3.1.1. Аппаратное представление целых чисел

Из книги автора

3.1.1. Аппаратное представление целых чисел Delphi относится к языкам, в которых целые типы данных максимально приближены к аппаратной реализации целых чисел процессором. Это позволяет выполнять операции с целочисленными данными максимально быстро, но заставляет


5.1. Представление чисел в языке Ruby

Из книги автора

5.1. Представление чисел в языке Ruby Если вы знакомы с любым другим языком программирования, то представление чисел в Ruby не вызовет у вас никакого удивления. Объект класса Fixnum может представлять число со знаком или без знака:237  # Число без знака (положительное).+237 # То же, что


7.10. Написание собственного алгоритма

Из книги автора

7.10. Написание собственного алгоритма ПроблемаДля диапазона требуется выполнить алгоритм, и ни один из стандартных алгоритмов не удовлетворяет требованиям.РешениеНапишите алгоритм в виде шаблона функции и с помощью имен параметров шаблона укажите свои требования к


11.20. Представление больших чисел фиксированного размера

Из книги автора

11.20. Представление больших чисел фиксированного размера ПроблемаТребуется выполнить операции с числами, размер которых превышает размер типа long int.РешениеШаблон BigInt в примере 11.38 использует bitset из заголовочного файла <bitset> для того, чтобы можно было представить целые


СОРТИРОВКА ЧИСЕЛ

Из книги автора

СОРТИРОВКА ЧИСЕЛ      Одним из наиболее распространенных тестов для машин является сортировка. Мы хотим разработать программу для сортировки целых чисел. Снова применим принцип черного ящика и подумаем в терминах ввода и вывода. Наш общий замысел, показанный на рис. 10.4,


Пример 25-8. Пример реализации алгоритма Решето Эратосфена

Из книги автора

Пример 25-8. Пример реализации алгоритма Решето Эратосфена #!/bin/bash# sieve.sh# Решето Эратосфена# Очень старый алгоритм поиска простых чисел.# Этот сценарий выполняется во много раз медленнее# чем аналогичная программа на C.LOWER_LIMIT=1 # Начиная с 1.UPPER_LIMIT=1000 # До 1000.# (Вы можете


Форматирование чисел

Из книги автора

Форматирование чисел Мы уже познакомились с функцией языка XPath string, которая конвертирует свой аргумент в строку. Эта функция может преобразовать в строку и численное значение, но возможности ее при этом сильно ограничены.К счастью, XSLT предоставляет мощные возможности


17.4. Проверка чисел

Из книги автора

17.4. Проверка чисел Для сравнения чисел можно воспользоваться операторами другого рода. Общий формат:"число" числовой_оператор "число" или[ "число" числовой_оператор "число" ]где в качестве выражения числовой_оператор могут фигурировать следующие операторы: -eq Два числа


2.3. Представление чисел в компьютере

Из книги автора

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


6. Понятие вспомогательного алгоритма

Из книги автора

6. Понятие вспомогательного алгоритма Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.Подпрограмма – это некоторый вспомогательный алгоритм, многократно использующийся в