Содержание 1. постройте таблицы истинности фор к какому из видов они относятся: - a) (x; y)= x = x/y; б) ф(а, в) = a - (a — в); в) ф(xi, x, x3) = (xi-x2) - (x, x, x3). 2. докажите с таблицы исти
достаточно часто требуется уметь переводить число из одной системы счисления в другую. давайте научимся выполнять такое действие. преобразование целых чисел и правильных дробей выполняется по разным правилам. в действительном числе преобразование целой и дробной части производят по отдельности.
преобразование целых чисел
для перевода необходимо исходное число разделить на основание новой системы счисления до получения целого остатка, который является младшим разрядом числа в новой системе счисления (единицы). полученное частное снова делим на основание системы и так до тех пор, пока частное не станет меньше основания новой системы счисления. все операции выполняются в исходной системе счисления.
рассмотрим для примера перевод числа из десятичной системы счисления в двоичную систему счисления.
возьмём десятичное число а10 = 124 и поделим его на основание двоичной системы, то есть число 2. деление будем производить уголком:
в результате первого деления получим разряд единиц (самый младший разряд). в результате второго деления получим разряд двоек. деление продолжаем, пока результат деления больше двух. в конце операции преобразования мы получили двоичное число 002.
теперь то же самое число переведём в восьмеричную систему счисления. для этого число 12410 разделим на число 8:
как мы видим, остаток от первого деления равен 4. то есть младший разряд восьмеричного числа содержит цифру 4. остаток от второго деления равен 7. то есть второй разряд восьмеричного числа – это цифра 7. старший разряд получился равным 1. то есть в результате многократного деления мы получили восьмеричное число 1748.
проверим, не ошиблись ли мы в процессе преобразования? для этого преобразуем получившееся двоичное число в десятичную систему по обычной формуле разложения:
1×82+7×81+4×80=6410+5610+410=124
; а можно ли осуществить перевод из восьмеричной системы счисления в двоичную делением? можно! но деление нужно произвести по правилам восьмеричной арифметики. правила работы в восьмеричной системе счисления мы рассмотрим в следующей главе. тем не менее, для полноты материала, рассмотрим пример перевода в двоичную форму полученного ранее восьмеричного числа 1748. разделим его на основание новой системы счисления 2.
как мы убедились выполнять деление в восьмеричной системе неудобно, ведь подсознательно мы делим в десятичной системе счисления. давайте обратим внимание на то, что число 8 является степенью числа 2. то есть можно считать восьмеричную систему счисления просто более короткой записью двоичного числа. это означает, что для представления восьмеричной цифры можно использовать три двоичных бита (8=23). давайте составим таблицу соответствия. она в таблице 1.
таблица 1. таблица соответствия восьмеричных цифр и двоичного кода
двоичный код
восьмеричная цифра
десятичный эквивалент
000
0
0
001
1
1
010
2
2
011
3
3
100
4
4
101
5
5
110
6
6
111
7
7
используя эту таблицу можно просто заменить каждую восьмеричную цифру тремя двоичными битами. три двоичных бита обычно называют триадой или трибитом. теперь давайте переведём восьмеричное число 1748 в двоичную форму при таблицы 7:
аналогично можно выполнить перевод числа из двоичной системы в восьмеричную. для этого двоичное число разбивают на триады относительно крайнего правого разряда (или двоичной запятой) и, используя таблицу 7, каждой триаде ставят в соответствие восьмеричную цифру.
аналогичным образом можно выполнить перевод числа из шестнадцатеричной формы в двоичную и обратно. в этом случае для представления шестнадцатеричной цифры потребуется четыре двоичных разряда. четыре двоичных разряда обычно называют тетрадой. иногда при переводе иностранных книг используется термин нибл.
давайте составим таблицу соответствия двоичных тетрад и шестнадцатеричных цифр. для этого мы будем просто прибавлять единицу к значению предыдущей строки в каждом столбце таблицы, в соответствии с используемой в этом столбце системой счисления. результат в таблице 2.
в качестве примера использования таблицы 2 переведем шестнадцатеричное число 7с16 в двоичную форму представления:
таблица 2. таблица соответствия шестнадцатеричных цифр и двоичного кода
двоичный код
восьмеричная цифра
десятичный эквивалент
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
4
0101
5
5
0110
6
6
0111
7
7
1000
8
8
1001
9
9
1010
a
a
1011
b
b
1100
c
c
1101
d
d
1110
e
e
f
f
пример преобразования двоичного числа в восьмеричную и шестнадцатеричную форму на рисунке 1.
рисунок 1. пример преобразования двоичного числа в восьмеричную и шестнадцатеричную форму.
на этом рисунке внизу выделены двоичные тетрады и соответствующие им шестнадцатеричные цифры. их соответствие можно проверить при таблицы 2. сверху выделены триады и соответствующие им восьмеричные цифры. старшая триада получилась неполной. её нужно дополнить старшими незначащими нулями для того, чтобы можно было бы воспользоваться таблицей 1.
Для начала попробуем разобрать один из решения подобных задач.
Рассмотрим контрольный пример. Входные данные: 5 - это количество врачей, т.е. нижеследующих строчек. 2 3 5 - 1-й врач. У него 2 предшественника - врачи 3 и 5 2 3 5 - 2-й врач. У него 2 предшественника - врачи 3 и 5 1 5 - 3-й врач. У него 1 предшественник - врач 5 3 1 3 5 - 4-й врач. У него 3 предшественника - врачи 1, 3 и 5 0 - 5-й врач. У него нет предшественников. Вариант результата: 5 3 1 2 4 - в таком порядке посещаются врачи.
Изобразим эти данные графически. В кружочках проставим номера врачей и соединим кружочки стрелками, отображающими взаимосвязи (первое вложение). Полученный рисунок - ни что иное, как ориентированный граф.
Решение будет состоять в поиске порядка посещения всех вершин графа ("врачей") в соответствии с доступными путями ("очередностью"). Очевидно, что первой нужно посетить вершину, из которой пути только выходят. Если ни одной такой вершины нет - задача решения не имеет. В нашем случае такая вершина есть - номер 5 и она помечена зеленым. После посещения мы удаляем эту вершину и все ведущие из нее пути. Получаем картину, представленную вторым вложением. Повторяем наше рассуждение и находим вершину 3. Снова удаляем её и выходящие из нее пути. В третьем вложении мы видим, что доступны сразу две вершины - 1 и 2. Их можно посетить в любом порядке, т.е. решение не единственное. Будем придерживаться порядка возрастания и и вычеркнем 1 с путём, а затем и 2. В чевертом вложении остается свободная вершина 4. Посещаем её, вычеркиваем - граф исчез, задача решена. И порядок посещения совпал с контрольным решением.
Теперь, когда "ручное" решение понятно, можно строить алгоритм. Мы использовали граф, а граф в программировании представляется парой множеств: множеством вершин и множеством путей, их соединяющих. Эти множества классически представляются двумя матрицами - матрицей смежности (отображает вершины и наличие связей) и матрицей инцидентности (отображает направление связей и, возможно, длины путей). Другие варианты - списки или деревья, но они требуют набора процедур для соответствующих манипуляций.
В связи с относительной простотой задачи был выбран собственный вариант отображения графа на квадратную матрицу размера (n+1)×n, где n- количество вершин (врачей). Первая строка матрицы является служебной, остальные отображают граф. В пятом вложении приведена принятая схема отображения. Собственно, из этой схемы понятна основная идея реализации. Создаем матрицу, расписываем её нулями, затем заносим единицы, создавая связи. Решение состоит в последовательном переборе колонок до нахождения столбцов, содержащих все нули. Найденный столбец "вычеркивается" (записывается 1 в нулевой строке), а его номер - это номер посещенной вершины. Процесс повторяется, пока в служебной строке не будут все единицы, либо пока не будет n раз сделан проход по столбцам (от зацикливания при отсутствии решения).
Поскольку программа может показаться нетривиальной, в нее внесены операторы отладки, позволяющие по шагам проследить решение. Как управлять отладкой, ясно из комментариев. Если отладка не нужна, достаточно из программы удалить все строки, отмеченные \\-
// PascalABC.NET 3.2, сборка 1417 от 28.03.2017 // Внимание! Если программа не работает, обновите версию!
begin var n:=ReadInteger; // первая строка - число врачей var a:=MatrFill(n+1,n,0); // матрица посещений var t:integer; for var i:=1 to n do begin // цикл ввода по каждому врачу var k:=ReadInteger; // количество врачей-предшественников for var j:=1 to k do begin Read(t); a[t,i-1]:=1 end; end; t:=0; var res:=''; var debug:=true; //- debug:=false блокирует отладочную выдачу if debug then begin //- Writeln('исходная матрица'); //- a.Println(2); Writeln //- end; //- for var m:=1 to n do begin for var j:=1 to n do begin var c:=a.Col(j-1); if c[0]=0 then begin if c.All(x->x=0) then begin Res+=j+' '; if debug then Writeln(Res); //- a[0,j-1]:=1; for var i:=0 to n-1 do a[j,i]:=0; if debug then begin //- a.Println(2); Writeln //- end //- end end; end; if a.Row(0).All(x->x=1) then begin t:=1; break end; end; if t=0 then Writeln(-1) else Writeln(Res) end.
Пример решения с выключенной отладкой 5 2 3 5 2 3 5 1 5 3 1 3 5 0 5 3 1 2 4
Пример со включенной отладкой (можно исходные данные для удобства все писать в одной строке) 5 2 3 5 2 3 5 1 5 3 1 3 5 0 исходная матрица 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 1 1 1 0
ответ:
объяснение:
достаточно часто требуется уметь переводить число из одной системы счисления в другую. давайте научимся выполнять такое действие. преобразование целых чисел и правильных дробей выполняется по разным правилам. в действительном числе преобразование целой и дробной части производят по отдельности.
преобразование целых чисел
для перевода необходимо исходное число разделить на основание новой системы счисления до получения целого остатка, который является младшим разрядом числа в новой системе счисления (единицы). полученное частное снова делим на основание системы и так до тех пор, пока частное не станет меньше основания новой системы счисления. все операции выполняются в исходной системе счисления.
рассмотрим для примера перевод числа из десятичной системы счисления в двоичную систему счисления.
возьмём десятичное число а10 = 124 и поделим его на основание двоичной системы, то есть число 2. деление будем производить уголком:
в результате первого деления получим разряд единиц (самый младший разряд). в результате второго деления получим разряд двоек. деление продолжаем, пока результат деления больше двух. в конце операции преобразования мы получили двоичное число 002.
теперь то же самое число переведём в восьмеричную систему счисления. для этого число 12410 разделим на число 8:
как мы видим, остаток от первого деления равен 4. то есть младший разряд восьмеричного числа содержит цифру 4. остаток от второго деления равен 7. то есть второй разряд восьмеричного числа – это цифра 7. старший разряд получился равным 1. то есть в результате многократного деления мы получили восьмеричное число 1748.
проверим, не ошиблись ли мы в процессе преобразования? для этого преобразуем получившееся двоичное число в десятичную систему по обычной формуле разложения:
1×82+7×81+4×80=6410+5610+410=124
; а можно ли осуществить перевод из восьмеричной системы счисления в двоичную делением? можно! но деление нужно произвести по правилам восьмеричной арифметики. правила работы в восьмеричной системе счисления мы рассмотрим в следующей главе. тем не менее, для полноты материала, рассмотрим пример перевода в двоичную форму полученного ранее восьмеричного числа 1748. разделим его на основание новой системы счисления 2.
как мы убедились выполнять деление в восьмеричной системе неудобно, ведь подсознательно мы делим в десятичной системе счисления. давайте обратим внимание на то, что число 8 является степенью числа 2. то есть можно считать восьмеричную систему счисления просто более короткой записью двоичного числа. это означает, что для представления восьмеричной цифры можно использовать три двоичных бита (8=23). давайте составим таблицу соответствия. она в таблице 1.
таблица 1. таблица соответствия восьмеричных цифр и двоичного кода
двоичный код
восьмеричная цифра
десятичный эквивалент
000
0
0
001
1
1
010
2
2
011
3
3
100
4
4
101
5
5
110
6
6
111
7
7
используя эту таблицу можно просто заменить каждую восьмеричную цифру тремя двоичными битами. три двоичных бита обычно называют триадой или трибитом. теперь давайте переведём восьмеричное число 1748 в двоичную форму при таблицы 7:
аналогично можно выполнить перевод числа из двоичной системы в восьмеричную. для этого двоичное число разбивают на триады относительно крайнего правого разряда (или двоичной запятой) и, используя таблицу 7, каждой триаде ставят в соответствие восьмеричную цифру.
аналогичным образом можно выполнить перевод числа из шестнадцатеричной формы в двоичную и обратно. в этом случае для представления шестнадцатеричной цифры потребуется четыре двоичных разряда. четыре двоичных разряда обычно называют тетрадой. иногда при переводе иностранных книг используется термин нибл.
давайте составим таблицу соответствия двоичных тетрад и шестнадцатеричных цифр. для этого мы будем просто прибавлять единицу к значению предыдущей строки в каждом столбце таблицы, в соответствии с используемой в этом столбце системой счисления. результат в таблице 2.
в качестве примера использования таблицы 2 переведем шестнадцатеричное число 7с16 в двоичную форму представления:
таблица 2. таблица соответствия шестнадцатеричных цифр и двоичного кода
двоичный код
восьмеричная цифра
десятичный эквивалент
0
0
0001
1
1
0010
2
2
0011
3
3
0100
4
4
0101
5
5
0110
6
6
0111
7
7
1000
8
8
1001
9
9
1010
a
a
1011
b
b
1100
c
c
1101
d
d
1110
e
e
f
f
пример преобразования двоичного числа в восьмеричную и шестнадцатеричную форму на рисунке 1.
рисунок 1. пример преобразования двоичного числа в восьмеричную и шестнадцатеричную форму.
на этом рисунке внизу выделены двоичные тетрады и соответствующие им шестнадцатеричные цифры. их соответствие можно проверить при таблицы 2. сверху выделены триады и соответствующие им восьмеричные цифры. старшая триада получилась неполной. её нужно дополнить старшими незначащими нулями для того, чтобы можно было бы воспользоваться таблицей 1.