Задача: Разделить число A = 10110102 на число B = 100102 в двоичной системе счисления. Решение: 1) Впишем делимое A в 8-ми разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули. Разр.76543210A: 01011010Обратите внимание! Так как для выполнения деления требуется производить операцию вычитания, это требует использования знаковой ариaметики. И поэтому в нашем случае 7-й разряд является знаковым (0 - соответствует положительному числу, 1 - отрицательному), а старшим разрядом числа является 6-й разряд. 2) Впишем делитель В в 8-ми разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули. Разр.76543210B: 00010010Здесь также как и с числом A 7-й разряд является знаковым, а старшим разрядом числа является 6-й разряд. Эти знаковые разряды будут показывать нам знаки, образующихся в процессе деления, частичных остатков. Они не имеет никакого отношения к знакам исходных операндов и знаку результата, а играют чисто технологическую роль. 3) Предварительный сдвиг делителя. Сдвинем делитель B влево так, чтобы позиция старшей значащей единицы, в нем, совпала с позицией старшей значащей единицы в делимом A. Количество необходимых для этого сдвигов запомним в числе k В нашем случае старшая значащая единица в делимом Aрасположена в 6-м разряде, a в делителе B - в 4-м разряде. Следовательно нам необходимо сдвинуть число B влево на 2 разряда (k = 2). Сдвинутый делитель выглядит следующим образом : Разр.76543210B: 010010004) Так как в процессе деления множитель B придется не только прибавлять но и вычитать, то нам необходимо иметь число -B. Для этого представим B в дополнительном коде. Перевод в дополнительный код осуществим в два этапа: 4.1)Вначале получим обратный код. Для этого просто проинвертируем каждый разряд регистра (заменим "0" на "1", а "1" на "0"). Разр.76543210Bобр 10110111 4.2) Прибавим к числу в обратном коде единицу и получим дополнительный код. Разр.c76543210111Bобр10110111+00000001Bдоп10111000Таким образом -B = Bдоп5) Процесс деления будет следующий: 5.1) Вычитаем из делимого А делитель В (т.е. прибавляем -В). 5.2) Анализируем знак полученного частичного остатка (7-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае. Помним, что отрицательному числу соответствует наличие единицы в 7-м разряде и наоборот. 5.3) Сдвигаем частичный остаток на один разряд влево. При этом крайний правый (младший) разряд заполняется нулем, а знаковый разряд (7-й) в процессе сдвига не участвует. 5.4) Прибавляем к частичному остатку делитель В если остаток отрицательный либо вычитаем делитель в противном случае. 5.5) Анализируем знак полученного частичного остатка (7-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае. 5.6) Действия описанные в пунктах 6.3-6.5 выполняем k раз (если k=0, то ни разу не выполняем). Но, если после очередной операции сложения/вычитания частичный остаток, по модулю, будет меньше чем исходный (несдвинутый) делитель, то операция деления прекращается, а частное дополняется нулями так, чтобы число разрядов частного равнялось k+1. В нашем случае процесс деления выглядит следующим образом : Разр.c 765432 1011111 Частное А 01011010- B 101110001=000100101<--00100100- B101110000=1101110011111<--10111000+ B010010001=00000000 Здесь в колонке "Частное", сверху вниз, записаны разряды искомого частного, начиная со старших. Обратите внимание - значение разряда частного - это просто иверсия 7-го (знакового) разряда частичного остатка. В следующем столбце - символика действий предпринимаемых в зависимости от знака частичного остатка. Смысл этих символов следующий: + В - делитель В прибавляется к регистру делимого A; - В - делитель В вычитается из регистра делимого A (технически здесь прибавляется Вдоп ); <-- - частичный остаток сдвигается на один разряд влево; " = " - показывается значение частичного остатка полученного после сложения.6) Определяем остаток от деления. Для этого анализируем последний частичный остаток. В нашем случае он равен "00000000". То есть деление произвелось нацело без остатка. 7) Определяем знак результата. Если знаки исходных операндов одинаковы, то результирующее частное положительно и наоборот. В нашем случае знаки совпадают, следовательно результирующее частное положительно. ответ: 10110102 : 100102 = 1012.
Var A: array[1..100, 1..100] of integer; B: array[1..100]of integer; i, j, k, n, m, imax: integer; manual: boolean;
begin writeln('Ручной ввод (true/false)==>'); read(manual);
if manual then begin writeln('Размер массива n, m ==>'); read(n, m); end else begin n := random(10) + 5; m := random(10) + 5; end;
for i := 1 to n do begin writeln(); for j := 1 to m do begin if manual then read(a[i, j]) else begin a[i, j] := random(100) - 50; write(a[i, j]:3, ' '); end; end; end;
writeln(); writeln();
for j := 1 to m do if j mod 2 = 1 then begin k := k + 1; b[k] := 1; for i := 1 to n do b[k] := b[k] * a[i, j]; write(b[k], ' '); end;
writeln();
for i := 1 to k - 1 do begin imax := i; for j := i + 1 to k do if b[j] > b[imax] then imax := j; n := b[i]; b[i] := b[imax]; b[imax] := n; end;
Разделить число A = 10110102 на число B = 100102 в двоичной системе счисления.
Решение:
1) Впишем делимое A в 8-ми разрядный регистр, начиная с младших разрядов (нумерация разрядов начинается с нуля). В недостающие разряды записываем нули.
Разр.76543210A: 01011010Обратите внимание! Так как для выполнения деления требуется производить операцию вычитания, это требует использования знаковой ариaметики. И поэтому в нашем случае 7-й разряд является знаковым (0 - соответствует положительному числу, 1 - отрицательному), а старшим разрядом числа является 6-й разряд.
2) Впишем делитель В в 8-ми разрядный регистр, начиная с младших разрядов. В недостающие разряды записываем нули.
Разр.76543210B: 00010010Здесь также как и с числом A 7-й разряд является знаковым, а старшим разрядом числа является 6-й разряд. Эти знаковые разряды будут показывать нам знаки, образующихся в процессе деления, частичных остатков. Они не имеет никакого отношения к знакам исходных операндов и знаку результата, а играют чисто технологическую роль.
3) Предварительный сдвиг делителя. Сдвинем делитель B влево так, чтобы позиция старшей значащей единицы, в нем, совпала с позицией старшей значащей единицы в делимом A. Количество необходимых для этого сдвигов запомним в числе k В нашем случае старшая значащая единица в делимом Aрасположена в 6-м разряде, a в делителе B - в 4-м разряде. Следовательно нам необходимо сдвинуть число B влево на 2 разряда (k = 2).
Сдвинутый делитель выглядит следующим образом :
Разр.76543210B: 010010004) Так как в процессе деления множитель B придется не только прибавлять но и вычитать, то нам необходимо иметь число -B. Для этого представим B в дополнительном коде. Перевод в дополнительный код осуществим в два этапа:
4.1)Вначале получим обратный код. Для этого просто проинвертируем каждый разряд регистра (заменим "0" на "1", а "1" на "0").
Разр.76543210Bобр 10110111
4.2) Прибавим к числу в обратном коде единицу и получим дополнительный код.
Разр.c76543210111Bобр10110111+00000001Bдоп10111000Таким образом -B = Bдоп5) Процесс деления будет следующий:
5.1) Вычитаем из делимого А делитель В (т.е. прибавляем -В).
5.2) Анализируем знак полученного частичного остатка (7-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае. Помним, что отрицательному числу соответствует наличие единицы в 7-м разряде и наоборот.
5.3) Сдвигаем частичный остаток на один разряд влево. При этом крайний правый (младший) разряд заполняется нулем, а знаковый разряд (7-й) в процессе сдвига не участвует.
5.4) Прибавляем к частичному остатку делитель В если остаток отрицательный либо вычитаем делитель в противном случае.
5.5) Анализируем знак полученного частичного остатка (7-й разряд). В регистр результата записываем "0" если остаток отрицательный и единицу в противном случае.
5.6) Действия описанные в пунктах 6.3-6.5 выполняем k раз (если k=0, то ни разу не выполняем). Но, если после очередной операции сложения/вычитания частичный остаток, по модулю, будет меньше чем исходный (несдвинутый) делитель, то операция деления прекращается, а частное дополняется нулями так, чтобы число разрядов частного равнялось k+1.
В нашем случае процесс деления выглядит следующим образом :
Разр.c 765432 1011111 Частное А 01011010- B 101110001=000100101<--00100100- B101110000=1101110011111<--10111000+ B010010001=00000000 Здесь в колонке "Частное", сверху вниз, записаны разряды искомого частного, начиная со старших. Обратите внимание - значение разряда частного - это просто иверсия 7-го (знакового) разряда частичного остатка.
В следующем столбце - символика действий предпринимаемых в зависимости от знака частичного остатка. Смысл этих символов следующий:
+ В - делитель В прибавляется к регистру делимого A;
- В - делитель В вычитается из регистра делимого A (технически здесь прибавляется Вдоп );
<-- - частичный остаток сдвигается на один разряд влево;
" = " - показывается значение частичного остатка полученного после сложения.6) Определяем остаток от деления. Для этого анализируем последний частичный остаток. В нашем случае он равен "00000000". То есть деление произвелось нацело без остатка.
7) Определяем знак результата. Если знаки исходных операндов одинаковы, то результирующее частное положительно и наоборот. В нашем случае знаки совпадают, следовательно результирующее частное положительно.
ответ: 10110102 : 100102 = 1012.