Построение алгоритма реализации численного метода «быстрой сортировки»

Получим 0.6₁₀ = 0.99₁₆ , значит,

313₁₀ » 139.99₁₆ 

139.99₁₆ = (     )₂

      Каждый  символ числа 139.99₁₆ запишем в двоичной системе счисления: 1₁₆=0001₂ ; 3₁₆=0011₂ ; 9₁₆=1001₂ .

Получим 139.99₁₆ = 100111001.10011001₂ 

139.99₁₆ = (     )₈

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

Сначала переводим целую часть числа, делим на основание 8:

 

Дальше  делить нельзя, поэтому собираем все  остатки, начиная с конца и учитываем конечный результат от деления т.е. 20/8=4. Получим 139₁₆ = 471₈

      Теперь  переводим дробную часть числа, умножаем на основание 8:

Получим 0.99₁₆ = 0.4620₈ , значит,

139.99₁₆ » 471.4620₈ 
 

139.99₁₆ = (     )₁₀

 

139.99₁₆ = 9*16^-2 + 9*16^-1 + 9*16⁰ + 3*16¹ + 1*16² = 0.0351 + 0.5625 + 9 + 48 +

+ 256 = 313.5976₁₀ » 313.6₁₀ 

2. Выполнение  арифметических операций над числами, представленными  в ПСС

      Операции  над числами в двоичной, восьмеричной, шестнадцатеричной системе счисления  выполняются по тем же правилам, что и арифметические операции над  числами в десятеричной системе  счисления. 

      Задание.

      А) Сложить числа (А)₁₆ и (В)₁₆

(А)₁₀ = 307₁₀ = 133₁₆ (В)₁₀ = 6.6₁₀ = 6.99₁₆

 

      Б) Вычесть из числа (А)₈ число (В)₈

(А)₁₀ = 307₁₀ = 463₈ (В)₁₀ = 6.6₁₀ = 6.46₈

 

      В) Умножить числа (С)₂ и (В)₂

(С)₁₀ = 91₁₀ = 1011011₂  (В)₁₀ = 6.6₁₀ = 110.1001₂

 

      В) Разделить число (С)₂ на (В)₂

(С)₁₀ = 91₁₀ = 1011011₂  (В)₁₀ = 6.6₁₀ = 110.1₂

 
 
 
 
 
 
 
 
 

2. Формы представления данных в ЦА

 

1. Кодирование и формы представления  чисел в ЦА
1. Представление чисел в машинных кодах для выполнения арифметических операций

      Прямой  код – это двоичный код числа, записанный в разрядной сетке, в  старшем разряде которого указывается знак числа.

      Для положительных чисел прямой код  числа совпадает с обратным и  дополнительном кодом т.е. [A]_пр = [A]_обр = [A]_доп .

      В противном случае, когда число  отрицательное:

• обратный код получается из прямого, путем инверсии всех разрядов, за исключением знакового;
• дополнительный код получается путем прибавления единицы к обратному коду т.е. [A]_доп = 1 + [A]_обр .

      Модифицированный  обратный (дополнительный) код –  аналог обратного (дополнительного) кода, с той лишь разницей, что на знак выделяются два старших разряда.

      Задание. Числа А, –А, С и –С представить в прямом, обратном, дополнительном, модифицированном обратном и модифицированном дополнительном кодах.

      А = 307₁₀ = 100110011₂  С = 91₁₀ = 1011011₂

      [A]_пр = [A]_об = [A]_доп = 0|000000100110011

      [A]_мод.об = 00|00000100110011

      [A]_{мод.доп} = 00|00000100110011

      [–A]_пр = 1|000000100110011

      [–A]_об = 1|111111011001100

      [–A]_мод.об = 11|11111011001100

      [–A]_доп = 1|111111011001100+1 = 1|111111011001101

      [–A]_{мод.доп} = 11|11111011001100+1 = 11|11111011001101

      [C]_пр = [C]_об = [C]_доп = 0|000000001011011

      [C]_мод.об = 00|00000001011011

      [C]_{мод.доп} = 00|00000001011011

      [–C]_пр = 1|000000001011011

      [–C]_об = 1|111111110100100

      [–C]_мод.об = 11|11111110100100

      [–C]_доп = 1|111111110100100+1 = 1|111111110100101

      [–C]_{мод.доп} = 11|11111110100100+1 = 11|11111110100101 
 
 

2. Представление чисел в формате  с фиксированной  запятой

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

      Например:

      111.101 * 2⁴  = 1111010  – целый вид;

      111.101 * 2^–3 = 0.111101  – дробный вид,

      где 2⁴ и 2^–3 – маштабный коэффициент. 

      Задание. Числа A, –A, B и –B представить в формате с фиксированной точкой (в 16-ти разрядах). При этом числа A и B привести к целому виду, а   –A и –B к дробному с 4-мя знаками после запятой.

      А = 307₁₀ = 100110011₂  

      A = 0000000100110011      – целый вид;

      A = 100110011*2^–4 = 000000010011.0011   – дробный вид.

      В = 6.6₁₀ = 110.1₂

      B = 110.1*2¹ = 0000000000001101    – целый вид;

      B = 110.1*2^–3 = 000000000000.1101    – дробный вид. 
 
 
 

3. Представление чисел в формате  с плавающей запятой

      Любое число N в системе счисления с  основанием q можно записать в виде N=M*q^p, где M называется мантиссой числа, а p – порядком. Такой способ записи чисел называется представлением с плавающей точкой.

      Мантисса  должна быть правильной дробью, первая цифра  дробной части которой  отлична от нуля: M из диапазона [0.1; 1).  

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

      Мантиссу и порядок q-ичного числа принято записывать в системе с основанием q, а само основание – в десятичной системе.

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

Например: 753.15 = 0.75315*10^3. 

      Задание. Числа A, –A, B и –B представить в формате с плавающей точкой.

      А = 307 = 0.307*10³  

     В = 6.6 =0.66*10¹ 
 

2. Кодирование и формат представления  символьной информации

      В большинстве первых компьютеров использовался семибитный код КОИ-7 (код обмена информацией, семизначный). В таком коде можно было закодировать 2⁷=128 символов. Но с развитием техники это стало довольно неудобно.

      Новый код был уже восьмибитным и  основывался на американском стандартном коде обмена информацией ASCII (American Standard Code for Information Interchange). В восьмибитном коде можно закодировать уже 2⁸=256 символов. Этого вполне хватает чтобы без всяких проблем использовать в тексте большие и маленькие буквы русского и латинского алфавитов, знаки препинания, цифры, специальные символы.