2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 НАМ, вычисляющий остаток от деления двух натуральных чисел
Сообщение19.04.2010, 22:31 
Здравствуйте, помогите построить нормальный алгоритм Маркова, вычисляющий остаток от деления двух натуральных чисел. Что такое НАМ, я знаю. Но вот сам алгоритм для выполнения этой задачи построить не могу(никак не могу понять с чего начать). Есть предположение, что числа нужно переводить в унарную систему и каким-то образом по шагам несколько раз удалять делитель из делимого(используя сравнение), не знаю как это можно реализовать . Заранее спасибо)

 
 
 
 Re: НАМ, вычисляющий остаток от деления двух натуральных чисел
Сообщение20.04.2010, 12:29 
Следующий алгоритм можно использовать, если абсолютно не интересует время его работы. Также я считаю, что делимое неотрицательно, а делитель положителен.
Итак, допустим записаны 2 числа в двоичной форме: делимое и делитель, между ними стоит буква "и", например 101и10.
Вначале правила перевода в единичную систему:
1. "|0" -> "0||"
2. "1" -> "0|"
3. "0" -> ""
(В примере результат должен быть такой |||||и||)
Теперь я хочу скопировать правую строчку и поставить слева символ A.
4. "и" -> "ABCD"
5. "D|" -> "dD"
6. "D" -> ""
(В примере результат должен быть такой |||||ABCdd)
7. "|d"->"d|"
8. "Cd"->"|C|"
9. "|A"->"A|"
(В примере результат должен быть такой A|||||B||C||)
Теперь сокращаем палочки
10. "|B|"->"B"
Если палочки между B и C закончились, запускаем процесс копирования по новой.
11. "BC"->"BCD"
Придем к строке вида AB|...|C|...|
(В примере результат должен быть такой AB|C||)
Ответ --- разность между количеством палочек слева и спава от C
12. "AB"->"E"
13. "E|"->"|E"
14. "|EC|"->"EC"
(В примере результат должен быть такой EC|)
Если ответ в унарной системе устраивает, то
15. "EC"->.""
Если нет, то надо во первых вместо 1, 2, 3, 4 (верхние четыре правила) в начало списка правил написать следующее
(сначала переименовываем, а потом переводим в унарную систему)
1.1 "и"->"FABCDG"
2.1 "0F"->"Fa"
2.2 "1F"->"Fb"
2.3 "F"->""
3.1 "G0"->"aG"
3.2 "G1"->"bG"
3.3 "G"->""
4.1 "|a"->"a||"
4.2 "1"->"a|"
4.3 "b"->""
а во вторых (вместо 15) дописать правила перевода обратно
15. "EC"->"H0"
16. "H1"->"H01"
16. "0|"->"1"
17. "1|"->"2"
18. "02"->"10"
19. "12"->"20"
20. "H01"->."1" (Убираем 0 в старшем разряде и временную букву H)
21. "H0"->."0" (В случае, если ответ 0, убирать 0 в старшем разряде не надо)

Этот алгоритм работает за экспоненциальное по длине входных данных время. Можно за полиномиальное, но это сложнее. Понадобится раз в 5 больше правил. Кстати, тут количество правил не минимально. Многое сделано для удобства правилописателя (то есть меня) и правилочитателя (то есть вас) :)

Разбирайтесь, ищите ошибки :)

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group