Факториальная система счисления сообщение

Обновлено: 02.07.2024

Теория о системах счисления. Смешанные, факториальные, непозиционные, биномиальные, позиционные системы счисления. Система остаточных классов. Система счисления разных народов, их особенности: древнеегипетская, алфавитная, еврейская, система майя.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	13.02.2016
Размер файла	53,5 K

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

1) Перевести числа N1 и N2 из одной системы счисления в другую

2) Выполнить операции сложения, вычитания и умножения для чисел N1 и N2 в трех системах счисления

3) Построить таблицы сложения и умножения для 16-ой системы счисления

4) Найти дополнительный код для чисел (-) и (-)

5) Выполнить перевод чисел в десятичную систему счисления

1. Теоретическая часть

1.1 Теория о системах счисления

1.2 Смешанные системы счисления

1.3 Факториальная система счисления

1.4 Непозиционные системы счисления

1.5 Биномиальная система счисления

1.6 Позиционные системы счисления

1.7 Система остаточных классов (СОК)

1.8 Системы счисления разных народов

1.8.1 Древнеегипетская система счисления

1.8.2 Алфавитные системы счисления

1.8.3 Еврейская система счисления

1.8.4 Система счисления майя

2. Архитектура ЭВМ

3. Практическая часть

Список использованных источников

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

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

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

Информатику можно рассматривать как науку, как технологию и как индустрию.

1. Теоретическая часть

1.1 Теория о системах счисления

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

1) даёт представления множества чисел (целых или вещественных)

2) даёт каждому числу уникальное представление (или, по крайней мере, стандартное представление)

3) Отражает алгебраическую и арифметическую структуру чисел.

Системы счисления подразделяются на позиционные, не позиционные и смешанные.

1.2 Смешанные системы счисления

Смешанная система счисления является обобщением b-ричной системы счисления и также зачастую относится к позиционным системам счисления. Основанием смешанной системы счисления является возрастающая последовательность чисел и каждое число x представляется как линейная комбинация:

где на коэффициенты a_k (называемые как и прежде цифрами) накладываются некоторые ограничения.

Записью числа x в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k, начиная с первого ненулевого.

Наиболее известным примером смешанной системы счисления являются представление времени в виде количества суток, часов, минут и секунд. При этом величина d дней h часов m минут s секунд соответствует значению секунд.

1.3 Факториальная система счисления

В факториальной системе счисления основаниями являются последовательность факториалов b_k = k!, и каждое натуральное число x представляется в виде:

1.4 Непозиционные системы счисления

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

1.5 Биномиальная система счисления

Представление, использующее биномиальные коэффициенты

1.6 Позиционные системы счисления

В позиционных системах счисления один и тот же числовой знак в записи числа имеет различные значения в зависимости от того места (разряда), где он расположен. К числу таких систем относится современная десятичная система счисления, возникновение которой связано со счётом на пальцах. В средневековой Европе она появилась через итальянских купцов, в свою очередь заимствовавших её у мусульман.

Под позиционной системой счисления обычно понимается b-ричная система счисления, которая определяется целым числом b > 1, называемым основанием системы счисления. Целое число x в b-ричной системе счисления представляется в виде конечной линейной комбинациистепеней числа b:

где a_k -- это целые числа, называемыецифрами, удовлетворяющие неравенству .

Каждая степень b k в такой записи называется весовым коэффициентомразряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя k (номером разряда). Обычно для ненулевого числа x требуют, чтобы старшая цифра a_n _{? 1} в b-ричном представлении x была также ненулевой.

Если не возникает разночтений (например, когда все цифры представляются в виде уникальных письменных знаков), число x записывают в виде последовательности его b-ричных цифр, перечисляемых по убыванию старшинства разрядов слева направо:

Например, число сто три представляется в десятичной системе счисления в виде:

Наиболее употребляемыми в настоящее время позиционными системами являются:

2 - двоичная (в дискретной математике, информатике, програмировании);

10 - десятичная (используется повсеместно);

12 - двенадцатеричная (счёт дюжинами);

1.7 Система остаточных классов (СОК)

Представление числа в системе остаточных классов основано на понятии вычета. СОК определяется набором взаимно простых модулей с произведением так, что каждому целому числу x из отрезка [0,M ? 1] ставится в соответствие набор вычетов , где

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка [0,M ? 1].

В СОК арифметические операции (сложение, вычитание, умножение, деление) выполняются покомпонентно, если про результат известно, что он является целочисленным и также лежит в [0,M ? 1].

Недостатками СОК является возможность представления только ограниченного количества чисел, а также отсутствие эффективных алгоритмов для сравнения чисел представленых в СОК. Сравнение обычно осуществляется через перевод аргументов из СОК в смешанную систему счисления по основаниям .Система счисления Штерна-Броко

Система счисления Штерна-Броко -- способ записи положительных рациональных чисел, основанный на дереве Штерна-Броко.

1.8 Системы счисления разных народов

1.8.1 Древнеегипетская система счисления

Древнеегипетская десятичная непозиционная система счисления возникла во второй половине третьего тысячелетия до н. э. Для обозначения чисел 0, 1, 10, 10І, 10і, 10 4 , 10 5 , 10 6 , 10 7 использовались специальные цифры. Числа в египетской системе счисления записывались как комбинации этих цифр, в которых каждая из цифр повторялась не более девяти раз. Значение числа равно простой сумме значений цифр, участвующих в его записи.

1.8.2 Алфавитные системы счисления

Алфавитными системами счисления пользовались древние армяне, абхазы, грузины, греки (ионическая система счисления), арабы (абджадия), евреи (см. гематрия) и другие народы Ближнего Востока. В славянских богослужебных книгах греческая алфавитная система была переведена на буквы кириллицы. [1]

1.8.3 Еврейская система счисления

Еврейская система счисления в качестве цифр используются 22 буквы еврейского алфавита. Каждая буква имеет своё числовое значение от 1 до 400. Ноль отсутствует. Наиболее часто можно встретить цифры, записанные таким образом в нумерации лет по иудейскому календарю.

1.8.4 Система счисления майя

Майя использовали 20-ричную систему счисления за одним исключением: во втором разряде было не 20, а 18 ступеней, то есть за числом (17)(19) сразу следовало число (1)(0)(0). Это было сделано для облегчения расчётов календарного цикла, поскольку (1)(0)(0) = 360 примерно равно числу дней в солнечном году.

счисление биномиальный народ майя

2. Архитектура ЭВМ

Термин “архитектура” используется в популярной литературе по вычислительной технике достаточно часто, однако определение этого понятия и его содержание могут у разных авторов достаточно различаться. Разберемся в этом вопросе более тщательно.

Ниже приводится перечень тех наиболее общих принципов построения ЭВМ, которые относятся к архитектуре:

* структура памяти ЭВМ;

* способы доступа к памяти и внешним устройствам;

* возможность изменения конфигурации компьютера;

Суммируя все вышеизложенное, получаем следующее определение архитектуры:

“Архитектура - это наиболее общие принципы построения ЭВМ, реализующие программное управление работой и взаимодействием основных ее функциональных узлов”.

2. Классическая архитектура ЭВМ и принципы фон Неймана

Основы учения об архитектуре вычислительных машин заложил выдающийся американский математик Джон фон Нейман. Он подключился к созданию первой в мире ламповой ЭВМ ENIAC в 1944 г., когда ее конструкция была уже выбрана. В процессе работы во время многочисленных дискуссий со своими коллегами Г. Голдстайном и А. Берксом фон Нейман высказал идею принципиально новой ЭВМ. В 1946 г. ученые изложили свои принципы построения вычислительных машин в ставшей классической статье “Предварительное рассмотрение логической конструкции электронно-вычислительного устройства”. С тех пор прошло полвека, но выдвинутые в ней положения сохраняют актуальность и сегодня.

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

В факториальной системе счисления основаниями являются последовательность факториалов , и каждое натуральное число представляется в виде:

, где .

Факториальная система счисления используется при декодировании перестановок списками инверсий: имея номер перестановки, можно воспроизвести её саму следующим образом: число, на единицу меньшее номера (нумерация начинается с нуля) записывается в факториальной системе счисления, при этом коэффициент при числе i! будет обозначать число инверсий для элемента i+1 в том множестве, в котором производятся перестановки (число элементов меньших i+1, но стоящих правее его в искомой перестановке)

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

Основная статья: Фибоначчиева система счисления

Фибоначчиева система счисления основывается на числах Фибоначчи. Каждое натуральное число в ней представляется в виде:

, где — числа Фибоначчи, , при этом в коэффициентах есть конечное количество единиц и не встречаются две единицы подряд.

Непозиционные системы счисления

Биномиальная система счисления

Представление, использующее биномиальные коэффициенты

, где .

Система остаточных классов (СОК)

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

При этом китайская теорема об остатках гарантирует однозначность представления для чисел из отрезка .

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

© 2014-2022 — Студопедия.Нет — Информационный студенческий ресурс. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав (0.003)

В факториальной системе счисления базис образует
последовательность факториалов натуральных чисел: 1! = 1, 2! =
2, 3! = 6, … . Другой ее особенностью является то, что количество
цифр, используемых в том или ином разряде (так называемая
размерность алфавита), неодинаково — оно увеличивается с
ростом номера разряда. В первом разряде могут быть только
цифры 0 и 1, во втором — 0, 1 и 2, в k-м — 0, 1, 2, …, k и так далее.
Следовательно, запись числа в факториальной системе имеет
вид d1 · 1! + d2 · 2! + d3 · 3! + … + dn · n!

Десятичному числу 100 соответствует 100/2 = 50(0), 50/3 = 16(2), 16/4
=4(0), 4/5 = 0(4) =4020f (буква f в виде индекса говорит о записи числа
в факториальной системе).
Обратное преобразование числа F из факториальной системы
счисления в десятичную или двоичную форму записи выполняется
пересчетом согласно формуле. Например, в десятичной системе N =
4020f = 4*4! + 0*3! + 2*2! + 0*1! = 100.

ПЕРЕСТАНОВКИ / ФАКТОРИАЛЬНАЯ СИСТЕМА СЧИСЛЕНИЯ / FACTORIAL NUMBER SYSTEM / ДВОИЧНОЕ КОДИРОВАНИЕ ФАКТОРИАЛЬНЫХ ЧИСЕЛ / BINARY CODING OF FACTORIAL NUMBERS / ПРЕОБРАЗОВАНИЕ ДВОИЧНОГО ЧИСЛА В ФАКТОРИАЛЬНОЕ И ОБРАТНО / TRANSFORMATION OF BINARY NUMBER INTO A FACTORIAL ONE AND BACK / РАЗМЕЩЕНИЯ / СОЧЕТАНИЯ ЭЛЕМЕНТОВ / COMBINATIONS OF ELEMENTS / PERMUTATIONS / DISTRIBUTIONS

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Поляков В.И., Скорубский В.И., Экало Ю.В.

Рассматриваются свойства факториальной системы счисления и некоторые новые сферы ее применения для решения ряда комбинаторных задач в программировании и проектировании компьютерных систем. Факториальные числа могут быть однозначно пронумерованы десятичными или двоичными числами и интерпретированы перестановками элементов любого типа. Декодирование двоично-кодируемой записи перестановки в факториальной системе счисления позволяет каждой перестановке однозначно поставить в соответствие размещение дискретных объектов (элементов, ссылок и др.) в некотором фиксированном дискретном пространстве. Перестановки и размещения могут быть применены в задачах автоматизации конструкторского проектирования, коммутации каналов вычислительных систем и в защите данных.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Поляков В.И., Скорубский В.И., Экало Ю.В.

Анализ основных характеристических свойств элементов рядов факториальных множеств в процессе защиты информационных систем

ПРИМЕНЕНИЕ ФАКТОРИАЛЬНОЙ СИСТЕМЫ ДЛЯ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ

В. И. Поляков1, В. И. Скорубский1, Ю. В. Экало

1Университет ИТМО, 197101, Санкт-Петербург, Россия E-mail: v.i.polyakov@mail.ru 2ОАО „НИЦЭТУ", 197376, Санкт-Петербург, Россия

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

Введение. Среди множества систем счисления в вычислительной технике наиболее используемыми остаются десятичная и двоичная. От большинства других систем счисления [1] пришлось отказаться, так как присущие им недостатки превалировали над достоинствами. Однако не исключено, что с развитием информационных технологий и техники интерес к использованию нетрадиционных систем счисления будет расти. Ряд задач, связанных с размещением элементов конечного множества в конструктиве или с коммутацией каналов и устройств в вычислительных устройствах, носят комбинаторный характер. Факториальная система кодирования чисел [2] позволяет интерпретировать перестановки применительно к различным конечным множествам элементов. В настоящей работе рассматриваются свойства этой системы и приводится пример использования в ряде практических задач, решаемых средствами как программирования, так и схемотехники.

Факториальная система счисления. Позиционная система счисления обеспечивает запись натурального числа N в виде цифрового слова Г = /„ /п-1 . _/!, состоящего из упорядоченного набора символов /¡, взятых из множества основных символов А (алфавита системы счисления). Число 0 записывается в виде цифрового слова 0. В факториальной записи числа каждый символ _// записи цифры /-го разряда числа Г выбирается из множества ^=, каждому натуральному числу N однозначно соответствует запись в факториальной системе

(р(г) — вес i-го разряда) и существует рекурсивный алгоритм преобразования

или по рекурсивной формуле

Таким образом, с целью получения последовательности цифрf1,f2, . fn факториального числа для исходных десятичного или двоичного чисел находим или в виде рекурсивного алгоритма

Например, если N =100, то , f =50 % 3 =2, S3 =16>, , /4 = 4 % 5 = 4, S5 = 0>.

Следовательно, число 100 в факториальной системе счисления представляется в виде F = f4 /з f2 f1 = 4020/

В программе преобразования на языке Си выбранный порядок нумерации для некоторых индексов меняется, так как он определяет порядок доступа к ячейкам памяти, для которых принят унифицированный порядок BigEndian — нулевой индекс массива F[0], младший индекс и далее размещаются, последовательно доступны элементы F[1], F[2], . с адресами +1, +2, +3, . c индексами 1, 2, 3, .

Приведем фрагмент программы преобразования двоичного числа в факториальное на языке программирования Си.

char M=5; //количество разрядов факториального числа char F[4], .N=100; j=3; // j=3,2,1,0 — номер позиции элемента в F[j]

(5&1) >1; 1++;>; //просмотр 1 бит в 5 — пропуск единиц

1£(с1£) ; //расчет индекса размещения >

2) Автоматизация проектирования. Задача конструкторского проектирования топологии печатных плат связана с размещением однотипных электронных компонентов, например микросхем, на многослойной плате, и трассировкой соединений по выбранному критерию.

Алгоритмически задача решается перебором перестановок R, для каждой из которых вычисляется значение функционала F(R), определяющего, например, число электрических переходов с одного слоя платы на другой или суммарную длину электрических соединений, и выбором перестановки R0, на которой достигается минимум этого функционала [6, 7].

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

Для решения задачи защиты доступа, устранения искажений и восстановления информации в системах передачи и хранения данных может быть использована перестановка битов кодов. Кодирование перестановками обеспечивает высокую защищенность символьных данных. Уровень защищенности можно оценить объемом вычислений, необходимых для идентификации кода перестановки. Для повышения надежности и защиты возможно применение массива перестановок, такой подход использовался при защите программ в микроконтроллерах Mcs51FA фирмы Intel [8].

4) Хеширование в распределении памяти данных в компьютерах. В высокопроизводительных ЭВМ используется страничная организация памяти с формированием адресов при распределении страниц методом хеширования, предполагающим случайный неповторяющийся выбор с использованием перестановок битов. Этот метод позволяет снизить вероят-

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

5) Задачи анализа надежности вычислительных систем. Предлагаемый алгоритм можно использовать при построении и исследовании устройств реконфигурации отказоустойчивых многофункциональных вычислительных систем на основе перестановок настроек [9, 10].

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

1. Системы счисления. Факториальная система [Электронный ресурс]: .

2. Скорубский В. И., Экало Ю. В. Факториальная система счисления // Изв. вузов. Приборостроение. 1977. Т. 20, № 5. С. 70—73.

3. А. с. № 766011. Коммутатор / М. Л. Александров, Г. Д. Андреев, В. И. Скорубский, Ю. В. Экало. Госреестр изобретений СССР. 28.05.1980.

4. Ланкастер П. Теория матриц. М.: Наука, 1982. 272 с.

5. Spécification of the Bluetooth System. 2014. 1081 р.

6. Андреев Г. Д., Экало Ю. В. Алгоритм оптимального и локально-оптимального разбиения печатных соединений на два слоя платы // Обмен опытом в радиопромышленности. 1977. № 2. С. 33—37.

7. Андреев Г. Д., Скорубский В. И., Экало Ю. В. Алгоритм размещения // Применение вычислительных машин в проектировании и производстве печатного монтажа. Л.: ЛДНТП, 1975.

8. Сташин В. В., Урусов А. В., Мологонцева О. Ф. Проектирование цифровых устройств на однокристальных микроконтроллерах. М.: Энергоатомиздат, 1990. 223 c.

9. Богатырев В. А. О модификации функции „перманент матрицы" и ее применении в комбинаторных методах анализа надежности вычислительных систем // Информационные технологии. 2002. № 1. С. 5—11.

10. Богатырев В. А. Надежность вычислительных систем с функциональной реконфигурацией на основе перераспределения задач // Информационные технологии. 2001. № 7. С. 22—27.

Сведения об авторах

Владимир Иванович Поляков — канд. техн. наук, доцент; Университет ИТМО, кафедра вычислительной техники; E-mail: vxpolyakov@mail.ru Владимир Иванович Скорубский — канд. техн. наук, доцент; Университет ИТМО, кафедра вычислительной техники; E-mail: vlis@km.ru Юрий Владимирович Экало — канд. техн. наук, доцент; ОАО „НИЦ ЭТУ"; генеральный директор;

Рекомендована кафедрой Поступила в редакцию

вычислительной техники 30.06.14 г.

Ссылка для цитирования: Поляков В. И., Скорубский В. И., Экало Ю. В. Применение факториальной системы для решения комбинаторных задач // Изв. вузов. Приборостроение. 2015. Т. 58, № 6. С. 436—442.

APPLICATION OF FACTORIAL SYSTEM TO COMBINATORIAL PROBLEMS SOLVING

V. I. Polyakov1, V. I. Skorubsky1, Yu. V. Ekalo2

Properties of the factorial number system are analyzed and several new fields of its application to combinatorial problems in programming and computer systems design are considered. Factorial numbers may be univalently enumerated with decimal or binary integers and interpreted as permutations of elements of any type. Decoding of binary-coded record of permutation in the factorial number system makes it possible to relate each permutation to a unique distribution of discreet objects (elements, references, etc.) in a specific discreet space. Permutations and distributions may be used in solving the problems of automation of design and commutation of calculating system channels, as well as in data protection.

Keywords: permutations, factorial number system, binary coding of factorial numbers, transformation of binary number into a factorial one and back, distributions, combinations of elements.

Reference for citation: Polyakov V. I., Skorubsky V. I., Ekalo Yu. V. Application of factorial system to combinatorial problems solving // Izvestiya Vysshikh Uchebnykh Zavedeniy. Priborostroenie. 2015. Vol. 58, N 6. P. 436—442 (in Russian).

Читайте также: