Всем привет. Подскажите пожалуйста как реализовать такую вот плюшку.
Разработать машину тьюринга выполняющую сортировку последовательности двоичных чисел.
С реализацией простых плюшек вроде разобрался. Однако в голове не укладывается каким образом и какой алгоритм сортировке можно реализовать на ней ?
LinuxForum.Fans
Машина Тьюринга
Автор: marikk
17 сообщений
2352 просмотров
Используйте метод слияния, имхо самое простое. Код писать не буду, ненавижу такой brainfuck.
Используйте метод слияния, имхо самое простое.
Пожалуй уточню. Это точно можно на машинее тьюринге можно реализовать ?
Код писать не буду, ненавижу такой brainfuck.
Можете в краце словестно описать алгоритм ?
На машине Тьюринга реализовать можно, гуглить merge sort.
Удалось реализовать сортировку пузрьком. Программу демонстратор можно скачать по ссыле ниже.
Код не очень кашерный, т.к слеплен на скорую руку.
Показать
marikk, можно пользоваться https://bitbucket.org/ ?
яндекс-диск плохо подходит для публикации исходников.
и да, вы ссылку просили, вот: https://ru.wikipedia.org/wiki/%D1%EE%F0%F2%E8%F0%EE%E2%EA%E0_%F1%EB%E8%FF%ED%E8%E5%EC
Пузырьковый алгоритм самый плохой во всех случаях. Зря вы с ним мучились.
Есть ещё очень простой алгоритм сортировки "на месте", простые вставки:
text
0. надо отсортировать массив A длинной n, будем считать, что начало массива A, массив B, длинной k, уже отсортирован. Это так, потому что k==1.
1. вставляем в массив B эл-т A[k] (в начале k==1, индексы отсчитываем с нуля, потому A[k] это второй эл-т A)
1.1 k→i, A[i] → x
1.2 для этого сравниваем A[i-1] и x
1.3 если A[i-1]>x, то A[i-1]→A[i], k--, и если не дошли до начала, goto 1.2, иначе goto 2
1.4 если A[i-1]<=x, то x → A[i]
2 Вставка закончена, массив B становится на 1 больше, k++.
3. goto 1 для всех k.
Это самый лучший алгоритм "на месте", для небольших массивов (≤20).
drBatty, алгоритмы сортировки всем известны. Однако моей скромной фантазии хватило только на реализацию пузырька. По свободе нормально перепишу программулину и перезалью.
Это самый лучший алгоритм "на месте", для небольших массивов
Доктор, эти алгоритмы чем то схожи, с разницей что не требуется перезаписывать каждый раз ячейку.
Простая вставка кажется что он должен работать быстрее чем пузырек, тем не менее этот алгоритм использует одинаковое количество сравнений и побольше присваиваний чем в методе прямым обменом...
при 10 элементах разница в присваиваниях 54 и 36 уже не малая.
А если реализовать на ассемблере, то можно используя непосредственно обмен между регистром и памятью (не присваивание - команда xchg),
то скорость пузырька во всех случаях будет превосходить прямую вставку (до 10 элементов).
Зы: самый плохой во всех случаях прямым выбором
В принципе при использовании в машине Тьюринга сойдет, учитывая что сравнение идет по готовым константам 1 и 0, по этому и не требуется вспомогательной переменной X. Количество состояний вроде не сильно должно отличаться.
у вас куда-то не туда фантазия работает. Простые вставки намного лучше, а реализация по сложности сопоставима.алгоритмы сортировки всем известны. Однако моей скромной фантазии хватило только на реализацию пузырька.
По свободе нормально перепишу программулину и перезалью.
дык в https://bitbucket.org/ можно историю проекта вести, в DVCS mercurial. Если стесняетесь, есть приватные репы.
полный анализ смотрите у Кнута. Там не всё так просто. Но и не слишком сложно.Простая вставка кажется что он должен работать быстрее чем пузырек, тем не менее этот алгоритм использует одинаковое количество сравнений и побольше присваиваний чем в методе прямым обменом...
при 10 элементах разница в присваиваниях 54 и 36 уже не малая.
мериться будем?А если реализовать на ассемблере, то можно используя непосредственно обмен между регистром и памятью (не присваивание - команда xchg),
то скорость пузырька во всех случаях будет превосходить прямую вставку (до 10 элементов).
Зы: самый плохой во всех случаях прямым выбором
очень познавательно.
стоп-стоп-стоп!В принципе при использовании в машине Тьюринга сойдет, учитывая что сравнение идет по готовым константам 1 и 0
там что, только 0 и 1? Тогда их можно очень просто отсортировать за O(n)
1. считаем число нулей, к примеру получилось z нулей.
2. записываем в массив z нулей, и n-z едииц.
всё. https://ru.wikipedia.org/wiki/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0
стоп-стоп-стоп!
там что, только 0 и 1? Тогда их можно очень просто отсортировать за O(n)
1. считаем число нулей, к примеру получилось z нулей.
2. записываем в массив z нулей, и n-z едииц.
всё. https://ru.wikipedia.org/wiki/%D0%91%D0 … 0%BA%D0%B0
Доктор, это же не ЯП, чтобы иметь массивы под рукой. Просто имеется лента с записью единиц и нулей, которые надо отсортировать. Считывающая головка, считывает данные и в зависимости от того 1 или 0 дает команду переместиться к следующей ячейке, записать единицу либо ноль, либо перейти к предыдущей ячейке и т.д. это в зависимости в каком состоянии находится машина в данный момент времени...
По крайней мере обычно не дают сильно сложные задания, обычно должно получиться что то типа 0000111.
не имеет значения. Если биты считаются по одному, то нужен radix sort, без вариантов.Доктор, это же не ЯП, чтобы иметь массивы под рукой. Просто имеется лента с записью единиц и нулей, которые надо отсортировать.
Вот если-бы нули/единицы группировались-бы, тогда другое дело.
ну я же говорю: сначала делаем сумматор, который умеет инкремент и декремент. Потом считаем нули этим сумматором. Потом пишем нули и делаем декремент. Потом забиваем остаток единицами. Когда-то давно я это уже реализовал на МТ.По крайней мере обычно не дают сильно сложные задания, обычно должно получиться что то типа 0000111.
PS: и да, любой тьюринг-полный ЯП эквивалентен МТ и наоборот. Если задачка решается на сишке, то она также решается на МТ. Обратное верно.
ну я же говорю: сначала делаем сумматор, который умеет инкремент и декремент. Потом считаем нули этим сумматором. Потом пишем нули и делаем декремент. Потом забиваем остаток единицами. Когда-то давно я это уже реализовал на МТ.
Многовато состояний придется писать тогда, если лента очень длинная либо бесконечная, то легче уж сортировку применить...
Но в принципе осуществимо, это уже на любителя :)
бесконечная. Как и размер программы на C.Многовато состояний придется писать тогда, если лента очень длинная либо бесконечная
то легче уж сортировку применить...
фишка в том, что для МТ можно строго доказать сходимость и скорость алгоритма, а для программы на другом ЯП это сделать сложнее.
бесконечная. Как и размер программы на C.
Ну дык... :)
фишка в том, что для МТ можно строго доказать сходимость и скорость алгоритма, а для программы на другом ЯП это сделать сложнее.
Я не сильно доверяю таким раскладам, если какая либо функция реализована на аппаратном уровне и исполняется за один такт, тогда меняется условие определения скорости.
Так же с языком программирования, когда говорят что qsort не требователен к памяти. В высокоуровневом ЯП может так и кажется, но если посмотреть с другой стороны, сколько памяти тратит данный алгоритм на сохранение промежуточных состояний при рекурсии, то становится ясно что еще и как требователен. Это особенно можно почувствовать при 16 битной адресации, когда прога улетает из за переполнения стека при обработке очень больших массивов. Когда пирамидальная сортировка его проходит без вылетов, но работает медленнее.
ЗЫ: просто думаю что надо еще все условия учитывать...
не меняется. Могу доказать вам на любом примере.Я не сильно доверяю таким раскладам, если какая либо функция реализована на аппаратном уровне и исполняется за один такт, тогда меняется условие определения скорости.
ровно O(log(n)) в бесконечности. На практике, для четырёх миллиардов эл-тов затрачивается не более 32х ячеек.сколько памяти тратит данный алгоритм на сохранение промежуточных состояний при рекурсии
диванный теоретик детектед.то становится ясно что еще и как требователен.
driver ruki.sys подключён?Это особенно можно почувствовать при 16 битной адресации, когда прога улетает из за переполнения стека при обработке очень больших массивов.
надо, только вы не туда думаете.просто думаю что надо еще все условия учитывать...
Няня я у них поелDOSBox tasm - как раз 16 бит...
Заполнение массива из файла, достаточно отсортировать ASCI коды.
Описание вызова процедуры тыц
как обычно.Зы: А что при рекурсии?
Войдите или зарегистрируйтесь, чтобы ответить.
