Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.73/15: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Tiger_Lee
1

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

05.02.2013, 13:09. Просмотров 2989. Ответов 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 даёт совет использовать длинную арифметику. Ссылаясь на [ссылка удалена] другой форум. Честно говоря для моего начинающего ума тяжеловато разобраться с этим. Есть ли варианты по проще кроме как использовать сдвиг в длинной арифметике? Напишете если есть идеи, уже потратил много времени на поиски решения проблемы, хотя всё казалось не так сложно на первый взгляд. Помогите кто чем может. Желательно с подробным объяснением=)

Что касается алгоритма, а как хотя бы примерно реализовать его, хоть на паскале. Пытался сделать с помощью строкового типа и массива целых чисел, всё равно загвоздка на первом пункте. Как именно происходит это "Отщипывание" ???Помогите кто чем может.
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.02.2013, 13:09
Ответы с готовыми решениями:

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

умножние столбиком 2-ух натуральных чисел в графическом режиме
Ребят помогите пожалуйста с программой (умножение столбиком 2-ух введённых натуральных чиселв...

Вывести на экран столбиком для чисел от 1 до 10 пару - число и его квадрат
вывести на экран столбиком для чисел от 1 до 10 пару: число и его квадрат

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

5
Эксперт по математике/физике
4123 / 2028 / 416
Регистрация: 19.07.2009
Сообщений: 3,077
Записей в блоге: 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 мы интерпретируем так:
https://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
06.02.2013, 14:49 3
Спасибо за ваш ответ, но для меня сложновато будет перенести его в конкретную ситуацию. В условиях чётко было сказано использовать вычитание и сравнение. Может быть есть более простой вариант? Напишите пожалуйста=)
Модератор
Эксперт по математике/физике
3969 / 2559 / 350
Регистрация: 15.06.2009
Сообщений: 4,879
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
Модератор
Эксперт Pascal/Delphi
6171 / 4162 / 4570
Регистрация: 05.06.2014
Сообщений: 20,469
19.05.2015, 12:25 6
Русофоб, два года спустя-то?
Лучше уж вам пробежаться поиском по форуму.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2015, 12:25

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

Деление столбиком
Доброго времени суток. Напечатать столбиком пример на деление с остатком двух заданных натуральных...

Написать калькулятор - сложение, умножение, вычитание, деление столбиком
Завтра экзамен, надо сдать три задачи, кто сможет ? 1. Написать калькулятор (сложение,...

Вывод чисел столбиком
Необходимо быстренько решить маленькую задачку

Составить программу «умножения столбиком» 2 чисел
Даны два натуральных числа, каждое из которых не превосходит 30000. Составить программу их...


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

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

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