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

Содержание

 

Введение

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

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

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

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

Приложение 1. Блок-схема  алгоритма  
Введение 

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

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

 

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

1. Представление чисел в позиционных  системах счисления (ПСС)

      Система счисления – это совокупность символов и правил их записи, необходимых  для записи чисел.

      В позиционной системе счисления  вес символа зависит от позиции в которой расположен символ. Например, число 222 – первый символ этого числа имеет вес 200, второй – 20, третий – 2.

      Основной  характеристикой ПСС является основание. Основание ПСС – это количество символов данной системы счисления, которые используются при составлении чисел. В зависимости от основания ПСС существует четыре основных системы счисления: двоичная, восьмеричная, десятеричная и шестнадцатеричная. Все эти системы счисления используются в ЦА и каждая имеет свои основные функции. Например, числа, записанные в двоичной системе счисления, используются в ЦА для операций производимых процессором: запись, считывание, сложение и т.д.; числа в шестнадцатеричной системе счисления – для адресации ячеек памяти. 

1. Перевод чисел из одной ПСС в другую

      При переводе чисел из десятичной системы счисления в систему с основанием P обычно используют следующий алгоритм:

      1) если переводится целая часть  числа, то она делится на  P, после чего запоминается остаток от деления. Полученное частное вновь делится на P, остаток запоминается. Процедура продолжается до тех пор, пока частное не станет равным нулю. Остатки от деления на P выписываются в порядке, обратном их получению;

      2) если переводится дробная часть  числа, то она умножается на  P, после чего целая часть запоминается и отбрасывается. Вновь полученная дробная часть умножается на P и т.д. Процедура продолжается до тех пор, пока дробная часть не станет равной нулю. Целые части выписываются после двоичной запятой в порядке их получения. Результатом может быть либо конечная, либо периодическая двоичная дробь. Поэтому, когда дробь является периодической, приходится обрывать умножение на каком-либо шаге и довольствоваться приближенной записью исходного числа в системе с основанием P.

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

      Чтобы перевести число из системы счисления  с основанием P 
в десятичную систему счисления, нужно найти сумму произведений содержимого разряда на вес этого разряда в системе счисления с основанием P. Где разряд – номер позиции в числе, нумеруются справа налево, начиная с нуля; вес разряда – число, равное основанию системы счисления в степени номера разряда.

      Чтобы перевести число из двоичной системы счисления  
в восьмеричную (шестнадцатеричную) систему счисления, нужно разбить число на тройки (четверки) цифр, в случае необходимости следует дополнить целую и дробную части числа нулями (целую слева, дробную справа). Затем заменить полученные группы цифр соответствующими им восьмеричными (шестнадцатеричными) цифрами. Например, число 11010010.10₂ нужно перевести в восьмеричную систему счисления. Разобьем число на тройки цифр: 011 010 010. 100 , заменим тройки цифр на соответствующими им восьмеричными цифрами. Получим 11010010.10₂ = 322.4₈

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

 

       Задание. Осуществить перевод числа (А+В), представленного в 10-ой системе из одной системы счисления в другие, по схеме рисунка.

           (А+В)₁₀

  

 

      Решение.

      А+В=307+6.6=313.6₁₀ 

313.6₁₀ = (     )₂

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

313/2=156  остаток – 1;

156/2=78  остаток – 0;

78/2=39  остаток – 0;

39/2=19  остаток – 1;

19/2=8  остаток – 1;

9/2=4   остаток – 1;

4/2=4   остаток – 0;

2/2=1   остаток – 0;

Дальше  делить нельзя, поэтому собираем все  остатки, начиная с конца и  учитываем конечный результат от деления т.е. 2/2=1. Получим 313₁₀=100111001₂

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

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

313₁₀ » 100111001.1001₂ 
 

100111001.1001₂ = (     )₈

      Разобьем  число на тройки цифр: 100 111 001. 100 100 , заменим  тройки цифр на соответствующими им восьмеричными  цифрами т.е. 100₂=4₈ ; 111₂=7₈ ; 001₂=1₈ . Получим 100111001.1001₂ =471.44₈ 

100111001.1001₂ = (     )₁₀

100111001.1001₂ = 1*2^-4 + 1*2^-1 + 1*2⁰ + 1*2³ + 1*2⁴ + 1*2⁵ + 1*2⁸ =

= 0.0652 + 0.5 + 1 + 8 + 16 + 32 + 256 = 313.5652₁₀ » 313.6₁₀ 

100111001.1001₂ = (     )₁₆

Разобьем число  на четверки цифр: 0001 0011 1001. 1001 , заменим четверки цифр на соответствующими им шестнадцатеричными цифрами т.е. 0001₂=1₁₆; 0011₂=3₁₆ ; 1001₂=9₁₆ . Получим 100111001.1001₂ =139.9₁₆ 

313.6₁₀ = (     )₈

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

313/8=39  остаток – 1;

39/8=4  остаток – 7.

Получим 313₁₀=471₈

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

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

313₁₀ » 471.4631₈ 

471.4631₈ = (     )₂

      Каждый  символ числа 471.4631₈ запишем в двоичной системе счисления: 4₈=100₂ ; 7₈=111₂ ; 1₈=001₂ ; 6₈=110₂ ; 3₈=011₂ .

      Получим 471.4631₈ = 100111001.100110011001₂ 

471.4631₈ = (     )₁₀

 

471.4631₈ = 1*8^-4 + 3*8^-3 + 6*8^-2 + 4*8^-1 + 1*8⁰ + 7*8¹ + 4*8² =

= 0.0002 + 0.0058 + 0.0937 + 0.5 + 1 + 56 + 256 = 313.5997₁₀ » 313.6₁₀ 

471.4631₈ = (     )₁₆

      Перевод числа из восьмеричной системы счисления  в шестнадцатеричную проведем в  два этапа: сначала переведем  число в десятеричную систему счисления, затем из десятеричной в шестнадцатеричную. Перевод числа 471.4631₈ в десятеричную систему счисления уже осуществлен выше: 471.4631₈ = 313.6₁₀ . Далее переведем 313.6₁₀ в шестнадцатеричную систему счисления: 

313.6₁₀ = (     )₁₆

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

313/16=19  остаток – 9;

19/16=1  остаток – 3.

Получим 313₁₀=139₁₆

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