[FreeTalk] Машина Поста
Greetings!
Раз уж у нас разговоры обо всем, не может ли кто-нибудь мне объяснить, как написать
программу для сложения чисел для машины Поста? Или сортировку по убыванию?
Подписаться
Бесплатный дискуссионный лист
Подписчиков 131
За последние 60 дней ни разу не выходила
Сайт листа:
http://svk.sanet.ru
Открыт:
14-03-2004
Пре-модерация: Нет
Адрес для писем в лист: rest.interesting.talk-list@subscribe.ru
Адрес
модератора: rest.interesting.talk-owner@subscribe.ru
Модератор
Статистика
131 подписчиков
0 за неделю
0 за неделю
Ответы:
Greetings, Олег!
Вы писали 16 апреля 2005 г., 21:58:58:
Могу эмулятор заслать, если надо.
Приветствую, Chris!
как
Если небольшой (до метра) то давай. А вообще лучше ссылочку скинь. А
ещё лучше попробуй сам отладить программу что я написал :) Ты ведь
научиться кажется хотел :)
Приветствую, Chris!
написать
Это счас в школе преподают или в институте? Какой у тебя уровень
подготовки? Я вот тут написал программку для сложения чисел. Чисто
теоритически - она должна работать, в правильности её логики я уверен
на 90%, а практически, если ты найдёшь компилятор под машину Поста -
я на 99%уверен что она не запустится с первого раза :) Т.к. это закон!
Если написанная вами программа заработала с первого раза - ищите
ошибки в компиляторе! :)
Короче вот листинг.
Для начала условные обозначения:
2. <= - сдвиг влево.
3. ? - передача управления (первое число - отсылка если ячейка
промаркирована, второе - если не промаркирована).
4. SET - маркировка ячейки.
5. CLR - очистка ячейки.
6. END - конец программы.
В // как обычно комментарии.
Итак, поехали. Т.к. начального состояния машины ты не указал, буду
предпологать самый общий случай (положение коретки относительно цифр
неизвестно). Хорошо хоть известно что цифры всего две...
*************************листинг*************************************
1. ? 14, 2
2. =>, 3
3. ? 14, 4
4. <=, 5
5. SET, 6
6. <=, 7
7. ? 6, 8
8. <=, 9
9. ? 16, 10
10. =>, 11
11. SET, 12
12. =>, 13
13. ? 12, 2
14. =>, 15
15. ? 14, 35
16. =>, 17
17. =>, 18
18. ? 17, 19
19. =>, 20
20. ? 62, 21
21. <= 22
22. SET 23
23. <=, 24
24. ? 23,25
25. <=, 26
26. ? 25, 27
27. <=, 28
28. ? 57, 29
29. =>, 30
30. SET 31
31. =>, 32
32. ? 31, 33
33. =>, 34
34. ? 33, 17
35. =>, 35.5
35.5 <=, 36
/35.5 потому что забыл один сдвиг влево сделать, а адресацию сбивать
не хочется - запутаюсь с циклами/
36. ? 70, 37
37. =>, 38
38. ? 57, 39
39. <=, 40
40. SET 41
41. <=, 42
42. ? 41, 43
43. <=, 44
44. ? 43, 45
45. <=, 46
46. ? 45, 47
47. <=, 48
48. ? 62, 49
49. =>, 50
50. SET 51
51. =>, 52
52. ? 51, 53
53. =>, 54
54. ? 53, 55
55. =>, 56
56. ? 55, 37
57. <=,58
58. <=,59
59. CLR 60
60. <=, 61
61. ? 59, 70
62. =>, 63
63. =>, 64
64. CLR 65
65. =>, 66
66. ? 64, 67
67. <=, 68
68. ? 69, 67
69. =>, 70
70. =>,71
71. ? 72, 70
72. =>, 73
73. ? 74, 81
74. <=, 75
75. CLR 76
76. <=, 77
77. ? 78, 76
78. =>, 79
79. SET 80
80. =>, 70
81. <=, 82
82. CLR 83
83. <=, 84
84. ? 85, 83
85. =>, 86
86. SET 87
87. STOP
*************************конец*************************************
Само сложение сложности не представляет. Это процедура с 70 по 87
строчку. Главное найти где находятся цифры. С принципом поиска
знаком? Будем надеется что Успенского ты читал...
Теперь скажи насколько подробно тебе расписать программу? А то я счас
попытался начать расписывать, если объяснять максимально подробно - на
это уйдёт часа полтора моего времени...
Это пока не пробовал, но чувствую программа будет НАМНОГО сложнее...
P.s.: я привёл всего лишь один из множества вариантов решения
поставленной задачи. Скорее всего не самый рациональный, т.к. я просто
брал и влоб решал. Для оптимизации у меня уже мозги не варят счас...
Greetings, Олег!
Вы писали 17 апреля 2005 г., 6:05:32:
В институте. Я конечно слышал, что это входит в школьный курс, но для меня
это прозвучало как нонсенс.
Вообще - второй курс МехМата. Но в рамках теории алгоритмов и вообще дискретной
математики -> 0.
Ладно, попробую разобраться. Если будут вопросы - обращусь на личку.
Приветствую, Chris!
как
Я тоже очень сильно удевился когда увидел что книжка Успенского
предназначена для _МЛАДШИХ_ классов средней школы... Мы такого даже в
институте не проходили.
Оба на, а чего у нас такого небыло? Странно, к нашей специальности
(Автоматизация Производства) это имеет непосредственное отношение...
Для упрощения разбирательства разобью программу на процедуры:
/поиск первой цифры. Для краткости будет называться п1/
1. ? 14, 2
2. =>, 3
3. ? 14, 4
4. <=, 5
5. SET, 6
6. <=, 7
7. ? 6, 8
8. <=, 9
9. ? 16, 10 /Вход в процедуру поиска второй цифры если первая
цифра найдена слева от коретки (п2.б)/
10. =>, 11
11. SET, 12
12. =>, 13
13. ? 12, 2
14. =>, 15
15. ? 14, 35 /Вход в процедуру поиска второй цифры если первая
цифра найдена справа от коретки (п2.а)/
/процедуры поиска второй цифры отличаются в зависимости от того, где
найдена первая цифра, как сделать в общем виде я пока не придумал.Если
придумаешь - скажи/
/п2.б/
16. =>, 17
17. =>, 18
18. ? 17, 19
19. =>, 20
20. ? 62, 21
Оба на! Только что ошибку нашёл! Это строчка должна выглядеть вот
так:
20. ? 57, 21 /если вторая цифра найдена справа - вход в процедуру
удаления следов поиска слева (пЕ1)/
21. <= 22
22. SET 23
23. <=, 24
24. ? 23,25
25. <=, 26
26. ? 25, 27
27. <=, 28
28. ? 57, 29
Здесь соответственно тоже ошибка:
28: ? 62, 29 /если вторая цифра найдена слева - вход в процедуру
очистки следов справа (пЕ2)/
29. =>, 30
30. SET 31
31. =>, 32
32. ? 31, 33
33. =>, 34
34. ? 33, 17
/2.а/
35. =>, 35.5
35.5 <=, 36
/35.5 потому что забыл один сдвиг влево сделать, а адресацию сбивать
не хочется - запутаюсь с циклами/
36. ? 70, 37 /вход в процедуру сложения, если вторую цифру нашли
сразу справа от первой (п3)/
37. =>, 38
38. ? 57, 39 /вход в Е1/
39. <=, 40
40. SET 41
41. <=, 42
42. ? 41, 43
43. <=, 44
44. ? 43, 45
45. <=, 46
46. ? 45, 47
47. <=, 48
48. ? 62, 49 /вход в пЕ2/
49. =>, 50
50. SET 51
51. =>, 52
52. ? 51, 53
53. =>, 54
54. ? 53, 55
55. =>, 56
56. ? 55, 37
/пЕ1/
57. <=,58
58. <=,59
59. CLR 60
60. <=, 61
61. ? 59, 70 /вход в процедуру сложения/
Кстати, только что обратил внимание, здесь может возникнуть
исключительная ситуация, т.е. безрезультативная остановка, при попытке
очистить пустую ячейку. Это произойдёт если вторая цифра находится в
двух шагах от первой. Чтобы этого не произошло надо сделать цикл с
предусловием, а не с послеусловием как у меня. Но в принципе работать
будет :) Так что если влом (как мне :)) ), можешь и не менять :)
Главное правельно показать работу программы препду ;)
/пЕ2/
62. =>, 63
63. =>, 64
64. CLR 65
65. =>, 66
66. ? 64, 67
67. <=, 68
68. ? 69, 67
69. =>, 70
/п3/
70. =>,71
71. ? 72, 70
72. =>, 73
73. ? 74, 81
74. <=, 75
75. CLR 76
76. <=, 77
77. ? 78, 76
78. =>, 79
79. SET 80
80. =>, 70
81. <=, 82
82. CLR 83
83. <=, 84
84. ? 85, 83
85. =>, 86
86. SET 87
87. STOP
*************************конец*************************************
Уф. Надеюсь ты разберёшься в моих бреднях :)
Greetings, Олег!
Вы писали 18 апреля 2005 г., 23:40:21:
Было то все как надо. Просто другое дело - как преподают. Товарищ лектор имеет
очень
"убаюкивающий" голос. Ему только гипнотизером работать. А практику вел товарищ
аспирант, который в принципе от работы отлынивал, но в конце концов дал нам контрольную
на последнем занятии (зачетную) и свалил. КР была ес-но списана с методичек.
Т.е. материал мы проходим, а в голове ничего не остается.
Так у нас преподается дискретная математика.
Приветствую, Олег!
С каких это пор дискретка имеет отношение к нашей специальности? Вот у
программеров, да, у них 4 вида математики было, а нам она на фик? То, что
Поляков дал нам по ВМСС, должно нам было хватить с головой, а по поводу
алгоритмов - вспомни как назывался курс, который вел Ломакин на 1-ом курсе,
ладно чтобы не парился, сам напишу: "Программирование и основы
алгоритмизации";)))
--
With best regards,
Andrew V.Saprikin. E-mail: m007F***@n*****.ru
*Всему свое время, и время всякой вещи под небом:...время любить, и время
ненавидеть...
Приветствую, Andrew!
Tuesday, April 19, 2005, 12:03:04 PM, you wrote:
Я теорию алгоритмов имел в виду...
Вот машина Поста это самые что ни на есть ОСНОВЫ :) Почему Ломик нам
про неё не рассказывал?
Приветствую, Олег!
Не помню про модель Поста, но Фон Неймановскую модель нам давал Поляков, на
ВМСС, могу тебе напомнить, что пары были по субботам и наверное ты их
благополучно просыпал.. .:P;)
--
With best regards,
Andrew V.Saprikin. E-mail: m007F***@n*****.ru
*Всему свое время, и время всякой вещи под небом:...время любить, и время
ненавидеть...
Приветствую, Andrew!
на
ФонНеймановская модель это несколько не то... Её мне ещё в школе на
информатике давали :) А вот машину Поста я бы с удовольствем изучил,
даже если бы она была по суботам, только не первой парой! :) Это
сильно помогло бы потом разбираться с ассемблером и МикроДАТом...
Greetings, Andrew!
Вы писали 20 апреля 2005 г., 14:36:04:
на
Фон Нейман - основа архитектуры компа, а Пост - основа теории алгоритмов.
Не путай кислое с длинным.
Приветствую, Chris!
написать
Ух! Интересная тема! Только что скачал с инета книжку по Машине Поста,
счас буду разбираться. Часов через несколько расскажу чего достиг :)