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

Автор: Пользователь скрыл имя, 03 Октября 2011 в 16:41, курсовая работа

Описание работы

В своей курсовой работе я ставлю следующие задачи:

научиться представлять данные в ЦА;
изучить методы контроля работы ЦА и научиться строить код Хемминга;
изучить реализацию алгоритма численного метода «быстрой сортировки» и построить его блок-схему.

Содержание

Введение

Глава 1. Представление данных в цифровых автоматах (ЦА)

Глава 2. Методы контроля работы ЦА

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

Список используемых источников

Работа содержит 1 файл

курсавик.doc

— 302.00 Кб (Скачать)

Получим 0.610 = 0.9916 , значит,

31310 » 139.9916 

139.9916 = (     )2

      Каждый  символ числа 139.9916 запишем в двоичной системе счисления: 116=00012 ; 316=00112 ; 916=10012 .

Получим 139.9916 = 100111001.100110012 

139.9916 = (     )8

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

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

  139 8
100 27
39  
38  
1  
27 8
20 4
7  

 

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

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

* 99   * С8   * 40  
8   8   8  
4 С8   6 40   2 00  

Получим 0.9916 = 0.46208 , значит,

139.9916 » 471.46208 
 

139.9916 = (     )10

1 3 9 . 9 9 Число
2 1 0   -1 -2 Разряды числа
 

139.9916 = 9*16-2 + 9*16-1 + 9*160 + 3*161 + 1*162 = 0.0351 + 0.5625 + 9 + 48 +

+ 256 = 313.597610 » 313.610 

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

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

      Задание.

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

(А)10 = 30710 = 13316 (В)10 = 6.610 = 6.9916

+ 133.00
6.99
  139.99
 

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

(А)10 = 30710 = 4638 (В)10 = 6.610 = 6.468

463.00
6.46
  454.31
 

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

(С)10 = 9110 = 10110112  (В)10 = 6.610 = 110.10012

* 1011011
110.1001
1011011
+       1011011000
101101100000
1011011000000
  1001010101.0011
 

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

(С)10 = 9110 = 10110112  (В)10 = 6.610 = 110.12

1011011 110.1     Þ
   
 
10110110 1101
01101   1110.0
010011  
001101    
0001101  
0001101  
0000000  
 
 
 
 
 
 
 
 
    1. Формы представления данных в ЦА
 
      1. Кодирование и формы представления  чисел в ЦА
        1. Представление чисел в машинных кодах для выполнения арифметических операций

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

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

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

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

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

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

      А = 30710 = 1001100112  С = 9110 = 10110112

      [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 
 
 

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

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

      Например:

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

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

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

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

      А = 30710 = 1001100112  

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

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

      В = 6.610 = 110.12

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

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

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

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

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

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

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

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

                                 

Например: 753.15 = 0.75315*103. 

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

      А = 307 = 0.307*103  

     В = 6.6 =0.66*101 
 

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

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

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

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