Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм перевода чисел из десятичной системы счисления в двоичную.Содержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Для перевода чисел из десятичной системы счисления в двоичную используют так называемый "алгоритм замещения", состоящий из следующей последовательности действий: 1. Делим десятичное число А на 2. Частное Q запоминаем для следующего шага, а остаток a записываем как младший бит двоичного числа. 2. Если частное q не равно 0, принимаем его за новое делимое и повторяем процедуру, описанную в шаге 1. Каждый новый остаток (0 или 1) записывается в разряды двоичного числа в направлении от младшего бита к старшему. 3. Алгоритм продолжается до тех пор, пока в результате выполнения шагов 1 и 2 не получится частное Q = 0 и остаток a = 1. Например, требуется перевести десятичное число 247 в двоичное. В соответствии с приведенным алгоритмом получим:
Таким образом, искомое двоичное число равно 111101112. Перевод чисел из двоичной системы в десятичную. Задача перевода чисел из двоичной системы счисления в десятичную чаще всего возникает уже при обратном преобразовании вычисленных либо обработанных компьютером значений в более понятные пользователю десятичные цифры. Алгоритм перевода двоичных чисел в десятичные достаточно прост (его иногда называют алгоритмом замещения): Например, требуется перевести двоичное число 10110110 в десятичное. В этом числе 8 цифр и 8 разрядов (разряды считаются, начиная с нулевого, которому соответствует младший бит). В соответствии с уже известным нам правилом представим его в виде суммы степеней с основанием 2: 101101102=(1·27)+(0·26)+(1·25)+(1·24)+(0·23)+(1·22)+(1·21)+(0·20)= 128+32+16+4+2 = 18210 Из этого примера видно, в частности, что десятичная система счисления более компактно отображает числа - 3 цифры (т.е. бита) вместо 8 цифр в двоичной системе счисления.
Теория графов. Основные понятия теории графов. Определение. Если на плоскости задать конечное множество V точек и конечный набор линий Х, соединяющих некоторые пары из точек V, то полученная совокупность точек и линий будет называться графом. При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами. В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами. Количество одинаковых пар (v, w) в Х называется кратностью ребра (v, w). Множество V и набор Х определяют граф с кратными ребрами – псевдограф. G = (V, X) Псевдограф без петель называется мультиграфом. Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом. Если пары в наборе Х являются упорядочными, то граф называется ориентированным или орграфом. Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины. Определение. Если х = { v, w } – ребро графа, то вершины v, w называются концами ребра х. Если х = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х. Определение. Вершины v, w графа G = (V, X) называются смежными, если { v,w }ÎX. Два ребра называются смежными, если они имеют общую вершину. Определение. Степенью вершины графа называется число ребер, которым эта вершина принадлежит. Вершина называется изолированной, если ее степень равна единице и висячей, если ее степень равна нулю. Определение. Графы G1(V1, X1) и G2(V2, X2) называются изоморфмными, если существует взаимно однозначное отображение j: V1 ® V2, сохраняющее смежность. Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v1x1v2x2v3…xkvk+1. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути). Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью. Определение. Замкнутый маршрут (путь) называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом. Определение. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w (маршрут, соединяющий v и w). Определение. Граф (орграф) называется связным, если для любых двух его вершин существует маршрут (путь), который их связывает. Орграф называется односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой. Определение. Псевдографом D(V,X), ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X0) в котором Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные пары (v, w). Определение. Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф. Определение. Цепь (цикл) в псевдографе G называется эйлеровым, если она проходит по одному разу через каждое ребро псевдографа G. Теорема 26.1. Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными. Теорема 26.2. Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени. Определение. Цикл (цепь) в псевдографе G называется гамильтоновым, если он проходит через каждую вершину псевдографа G ровно один раз. Пример 26.1.
- в графе есть и эйлеровый и гамильтонов циклы
- в графе есть эйлеров цикл, но нет гамильтонова
- в графе есть гамильтонов, но нет эйлерова цикла
- в графе нет ни эйлерова, ни гамильтонова цикла
Граф G называется полным, если каждая его вершина смежна со всеми остальными вершинами. В полном графе всегда существуют гамильтоновы циклы. Также необходимым условием существования гамильтонова цикла является связность графа.
|
||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-12-14; просмотров: 1531; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.118.30.153 (0.007 с.) |