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

⇐ ПредыдущаяСтр 4 из 4

Компьютер может обрабатывать данные, которые представлены в специальном виде - только с помощью нулей и единиц. Каждый 0 или 1 называют битом. Один бит - это минимальная единица информации, описывающая только 2 возможных состояния. Восемь битов объединяются в байт: 00101011, 00000000, 11111111, 10101010. Байт - основная единица представления информации в компьютере. В итоге вся информация в компьютере представляется как набор огромного (сотни тысяч и миллионы) числа нулей и единиц, разбитых на отдельные байты. Такое представление информации называют цифровым или двоичным. Обработка двоичных данных выполняется с помощью специальных правил, определяемых так называемой двоичной арифметикой.

В зависимости от решаемой задачи байт может содержать закодированное представление различных типов данных.

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

00000000₂ = 0₁₀ 00000001₂ = 1₁₀.......... 11111111₂ = 255₁₀

Диапазон целых чисел, кодируемых одним байтом, определяется числом возможных комбинаций из восьми нулей и единиц. Это число равно 28, т.е. 256. Если надо закодировать число больше 255, то два байта объединяются вместе и используется 16 битов. Это дает 216, т.е. 65536 комбинаций. Еще большие целые числа можно представить с помощью 4 байтов или 32 битов. Для представления чисел со знаком один бит отводится под знак.

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

В ЭВМ используются три вида чисел: с фиксированной точкой (запятой), с плавающей точкой (запятой) и двоично-десятичное представление. Точка (запятая) - это подразумеваемая граница целой и дробной частей числа.

У чисел с фиксированной точкой в двоичном формате предполагается строго определенное место точки (запятой). Обычно это место определяется или перед первой значащей цифрой числа, или после последней значащей цифрой числа. Если точка фиксируется перед первой значащей цифрой, то это означает, что число по модулю меньше единицы. Диапазон изменения значений чисел определяется неравенством

Если точка фиксируется после последней значащей цифры, то это означает, что п- разрядные двоичные числа являются целыми. Диапазон изменения их значений составляет:

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

Другой формой представления чисел является представление их в виде чисел с плавающей точкой (запятой). Числа с плавающей точкой представляются в виде мантиссы m_a и порядка р_a, иногда это представление называют полулогарифмической формой числа. Например, число A10= 373 можно представить в виде 0.373 • 10³, при этом т = 0.373, р = 3, основание системы счисления подразумевается фиксированным и равным десяти. Для двоичных чисел А2 в этом представлении также формируется тa и порядок рa при основании системы счисления равным двум.

что соответствует записи

Порядок числа р_a определяет положение точки (запятой) в двоичном числе. Значение порядка лежит в диапазоне –р_a max < =р_a< =р_a max, где величина pamах определяется числом разрядов к, отведенных для представления порядка

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

Значение р'_a носит название «характеристика числа». Обычно под порядок (модифицированный порядок - характеристику) выделяют один байт. Старший разряд характеристики отводится под знак числа, а семь оставшихся разрядов обеспечивают изменение порядка в диапазоне

Модифицированный порядок р'_a вычисляется по зависимости

Этим самым значения р'_a формируются в диапазоне положительных чисел

Мантисса числа m_a представляется двоичным числом, у которого точка фиксируется перед старшим разрядом, т. е.

где k - число разрядов, отведенных для представления мантиссы.

Если

то старший значащий разряд мантиссы в системе счисления с основанием N отличен от нуля. Такое число называется нормализованным. Например, A₂ =(100; 0.101101)₂ -нормализованное число А₂= 1011.01 или А₁₀= 11.25, а то же самое число А₂ = (101; 0.0101101) - число ненормализованное, так как старший разряд мантиссы равен нулю.

Диапазон представления нормализованных чисел с плавающей точкой определяется

где r и k - соответственно количество разрядов, используемых для представления порядка и мантиссы.

Третья форма представления двоичных чисел - двоично-десятичная. Ее появление объясняется следующим. При обработке больших массивов десятичных чисел (например, больших экономических документов) приходится тратить существенное время на перевод этих чисел из десятичной системы счисления в двоичную для последующей обработки и обратно - для вывода результатов. Каждый такой перевод требует выполнения двух - четырех десятков машинных команд. С включением в состав отдельных ЭВМ специальных функциональных блоков или спецпроцессоров десятичной арифметики появляется возможность обрабатывать десятичные числа напрямую, без их преобразования, что сокращает время вычислений. При этом каждая цифра десятичного числа представляется двоичной тетрадой. Например, A₁₀=3759, A_2-10= 0011 0111 0101 1001. Положение десятичной точки (запятой), отделяющей целую часть от дробной, обычно заранее фиксируется. Значение знака числа отмечается кодом, отличным от кодов цифр. Например, «+» имеет значение тетрады «1100», а «-» - «1101» [17].

16. Операторы языка С/С++.

Операторы управляют процессом выполнения программы. Набор операторов языка C++ содержит все управляющие конструкции структурного программирования.

Составной оператор ограничивается фигурными скобками. Все другие операторы заканчиваются точкой с запятой.

Пустой оператор –;

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

Составной оператор – {...}

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

Оператор обработки исключений

try { < операторы> }

catch (< объявление исключения> ) { < операторы> }

...

catch (< объявление исключения> ) { < операторы> }

Условный оператор

if (< выражение> ) < оператор 1> [else < оператор 2> ]

Оператор-переключатель

switch (< выражение> )

{ case < константное выражение 1>: < операторы 1>

case < константное выражение 2>: < операторы 2>

...

case < константное выражение N>: < операторы N>

[default: < операторы> ]

}

Оператор-переключатель предназначен для выбора одного из нескольких альтернативных путей выполнения программы. Вычисление оператора-переключателя начинается с вычисления < выражения>, после чего управление передается < оператору>, помеченному < константным выражением>, равным вычисленному значению < выражения>. Выход из оператора-переключателя осуществляется оператором break. Если значение < выражения> не равно ни одному < константному выражению>, то управление передается < оператору>, помеченному ключевым словом default, если он есть.

Оператор цикла с предусловием

while (< выражение> ) < оператор>

Оператор цикла с постусловием

do < оператор> while < выражение>;

В языке C++ этот оператор отличается от классической реализации цикла с постусловием тем, что при истинности < выражения> происходит продолжение работы цикла, а не выход из цикла.

Оператор пошагового цикла

for ([< начальное выражение> ];

[< условное выражение> ];

[< выражение приращения> ])

< оператор>

Тело оператора for выполняется до тех пор, пока < условное выражение> не станет ложным (равным 0). < Начальное выражение> и < выражение приращения> обычно используются для инициализации и модификации параметров цикла и других значений. < Начальное выражение> вычисляется один раз до первой проверки < условного выражения>, а < выражение приращения> вычисляется после каждого выполнения < оператора>. Любое из трех выражений заголовка цикла, и даже все три могут быть опущены (не забывайте только оставлять точки с запятой). Если опущено < условное выражение>, то оно считается истинным, и цикл становится бесконечным.

Оператор пошагового цикла в языке C++ является гибкой и удобной конструкцией, поэтому оператор цикла с предусловием while используется в языке C++ крайне редко, т.к. в большинстве случаев удобнее пользоваться оператором for.

Оператор разрыва

break;

Оператор разрыва прерывает выполнение операторов while, do, for и switch. Он может содержаться только в теле этих операторов. Управление передается оператору программы, следующему за прерванным. Если оператор разрыва записан внутри вложенных операторов while, do, for, switch, то он завершает только непосредственно охватывающий его оператор.

Оператор продолжения

continue;

Оператор продолжения передает управление на следующую итерацию в операторах цикла while, do, for. Он может содержаться только в теле этих операторов. В операторах do и while следующая итерация начинается с вычисления условного выражения. В операторе for следующая итерация начинается с вычисления выражения приращения, а затем происходит вычисление условного выражения.

Оператор возврата

return [< выражение> ];

Оператора возврата заканчивает выполнение функции, в которой он содержится, и возвращает управление в вызывающую функцию. Управление передается в точку вызывающей функции, непосредственно следующую за оператором вызова. Значение < выражения>, если она задано, вычисляется, приводится к типу, объявленному для функции, содержащей оператор возврата, и возвращается в вызывающую функцию. Если < выражение> опущено, то возвращаемое функцией значение не определено.

С формальной точки зрения операторы break, continue и return не являются операторами структурного программирования. Однако их использование в ограниченных количествах оправдано, когда они упрощают понимание программы и позволяют избегать больших вложенных структур. Например, мы проверяем входные данные на аномалии. Если не использовать эти операторы, то всю обработку придется вложить в условный блок, что ухудшает читабельность программы. Вместо этого можно написать небольшой условный блок, который организует выход из функции при неверных исходных данных.

Ввод/вывод не является частью языка C++, а осуществляется функциями, входящими в состав стандартной библиотеки. Для подробной информации см. лекцию 4.

17. Рекуррентные соотношения (например, вычисление чисел Фиббоначи и др.)

При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского " recurrere" - " возвращаться" ).

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

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

Пусть - число пар кроликов в популяции по прошествии месяцев, и пусть эта популяция состоит из пар приплода и " старых" пар, то есть

Таким образом, в очередном месяце произойдут следующие события: Старая популяция в -й момент увеличится на число родившихся в момент времени . Каждая старая пара в момент времени производит пару приплода в момент времени В последующий месяц эта картина повторяется:

Объединяя эти равенства, получим следующее рекуррентное соотношение:

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

Рассмотрим эту задачу немного иначе.

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца

, то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение

Так как, по условию, и , то последовательно находим и т.д.

В частности,

Числа называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через .

Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

⇐ Предыдущая 1 2 34