Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
Tiger_Lee
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 2
1

Деление двоичных чисел столбиком

05.02.2013, 13:09. Просмотров 2673. Ответов 5
Метки нет (Все метки)

Всем доброго времени суток! Пытаюсь реализовать алгоритм деления двоичных чисел столбиком на паскале. Вообще суть задачи была именно делении столбиком. Проще сделать в двоичной системе счисления используя вычитание и сравнение. Вот собственно сам алгоритм:
Кликните здесь для просмотра всего текста
Алгоритм деления столбиком для двоичных чисел (собственно, он же подходит для произвольной n-ичной системы)
1. "Отщипываем голову" от делимого до тех пор, пока она не станет больше делителя
2. Ищем наибольшую цифру, которая при домножении на делитель будет меньше "головы" (для двоичной это наверняка 1)
3. Вычисляем разницу между "головой" и произведением частного (точнее, это первые цифры частного) и делителя, домножаем на 10 (т.е. 2 по-нашему) и "сносим" следующую цифру делимого.
4. Ищем наибольшую цифру, которая при умножении на делитель даст число, меньше "снесенного".
Для двоичной системы можно проще: если остаток меньше делителя, то ноль, иначе единица.
5. Повторяем с шага 3, если у делимого ещё остались цифры.

101 / 10 = 1

1.-2. 1 (первая цифра)<10 (делитель)
10(первые две цифры)=10 (делитель) -> в частное записываем 1

3. 10 ("голова") - 10 (делитель)*1 (частное) = 0
0 (результат)*10 + 1 (последняя цифра 101) = 1
4. 1(остаток)<10(делитель) -> дописываем 0.
5. алгоритм окончен.
был написан пользователем Mysterious Light.
Сразу проблема с первым пунктом. Как именно сделать это "Отщипывание" . Тот же Mysterious Light даёт совет использовать длинную арифметику. Ссылаясь на [ссылка удалена] другой форум. Честно говоря для моего начинающего ума тяжеловато разобраться с этим. Есть ли варианты по проще кроме как использовать сдвиг в длинной арифметике? Напишете если есть идеи, уже потратил много времени на поиски решения проблемы, хотя всё казалось не так сложно на первый взгляд. Помогите кто чем может. Желательно с подробным объяснением=)

Что касается алгоритма, а как хотя бы примерно реализовать его, хоть на паскале. Пытался сделать с помощью строкового типа и массива целых чисел, всё равно загвоздка на первом пункте. Как именно происходит это "Отщипывание" ???Помогите кто чем может.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2013, 13:09
Ответы с готовыми решениями:

Умножение двух двоичных чисел
Помогите создать подпрограмму для умножения двух чисел в двоичной системе!(паскаль)

Умножение двоичных чисел в дополнительном коде
Нужно написать программу для умножения двоичных чисел в дополнительном коде, чтобы каждое действие...

Найти сумму пяти двоичных чисел. Найдите ошибку
Помогите найти ошибку. Выдает неверный ответ. Условие программы вычеслить сумму пяти двоичных...

Написать программу умножения двух двоичных вещественных чисел
Доброго времени суток, уважаемые участники форума. Поюзал поиск и не нашёл чего-то похожего (каюсь,...

Деление комплексных чисел
Найти частное от деление двух комлексных чисел Вот сделал программку: type complex=record...

5
Mysterious Light
Эксперт по математике/физике
4096 / 2005 / 410
Регистрация: 19.07.2009
Сообщений: 3,025
Записей в блоге: 22
05.02.2013, 17:58 2
Пусть, например, у Вас определён тип длинного целого и сопутствующие ему операции сложения, умножения, сравнения:
Pascal
1
2
3
const b = 2; { основа }
const dmax = 64; { наибольшее количество цифр }
type num = array[0..dmax] of byte; { тип длинного числа }
Пусть к тому же порядок цифр little-endian, то есть число типа num мы интерпретируем так:
http://www.cyberforum.ru/cgi-bin/latex.cgi?a\colon\mathrm{num} \quad\leftrightarrow\quad \sum\limits_{k=0}^{\mathrm{dmax}} a_k b^k \in \mathbb{N}
На основе этого можно написать деление длинного на длинное.

Не по теме:

Я попробовал поискать какую-нибудь статью с кодом на паскале и подробным объяснением происходящего в яндексе. Наверняка что-то такое есть у нашего Puporev'а или ещё какого-нибудь нашего гуру, но первое, что я нашел, находится на другом форуме.
Я оставляю ссылку, а модерация пусть не удаляет её, пока не найдёт что-то взамен.


Длинная арифметика, числа > longint
В этой статье исполькуются все соглашения, описанные выше, только называются немного по-другому.
Просмотрите внимательно приведённые там процедуры. В некоторых (например, в ReadLong и WriteLong) нужно совершать замену неявно предполагаемой основы 10 на 2. Большинство процедур ведут себя хорошо при замене константы _osn (основы системы). В программе процесс «отщепления» происходит в качестве передачи некоторым функциям дополнительного аргумента — сдвига, который определяет, сколько нулей нужно дописать у одного из аргументов-чисел; в самом делении сдвиг знаменателя (т.е. дописывание нулей справа) определяется переменной, которая монотонно уменшается до нуля, тогда алгоритм завершается.
1
Tiger_Lee
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 2
06.02.2013, 14:49 3
Спасибо за ваш ответ, но для меня сложновато будет перенести его в конкретную ситуацию. В условиях чётко было сказано использовать вычитание и сравнение. Может быть есть более простой вариант? Напишите пожалуйста=)
0
Том Ардер
Модератор
Эксперт по математике/физике
3894 / 2500 / 334
Регистрация: 15.06.2009
Сообщений: 4,622
06.02.2013, 15:14 4
Цитата Сообщение от Tiger_Lee Посмотреть сообщение
В условиях чётко было сказано использовать вычитание и сравнение
Кто видел эти условия? Хотите получить нормальный ответ - формулируйте задачу нормально.

По теме: алгоритм Евклида для деления.
1
Русофоб
0 / 0 / 0
Регистрация: 24.04.2015
Сообщений: 9
19.05.2015, 01:06 5
Mysterious Light, можете помочь написать программу для деления 2 х двоичных чисел вводимых с клавиатуры друг на друга
0
ZX Spectrum-128
Модератор
Эксперт Pascal/Delphi
4879 / 3423 / 4022
Регистрация: 05.06.2014
Сообщений: 17,103
19.05.2015, 12:25 6
Русофоб, два года спустя-то?
Лучше уж вам пробежаться поиском по форуму.
0
19.05.2015, 12:25
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2015, 12:25

Деление четыр чисел на 133 и 134
Составить программу поиска четырехзначных чисел, которые при делении на 133 дают в остатке 125, а...

Вычитание, умножение и деление для чисел в 4 сс
Пишу калькулятор для четверичной системы счисления. У меня вещественные числа и со сложением...

Деление чисел в файле и запись остатка
Напишите, пожалуйста, программу:). Есть два файла input.txt, output.txt, в input записаны два...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.