Обучающая программа по информатике
k1 = 1 + 0 + 1 = 0 – нет ошибки;
k2 = 0 + 0 =0 – нет ошибки;
k3 = 0 + 1 = 1 – ошибка.
Полученное двоичное число 100 дает номер ошибочного разряда, т.е. 4.
1.5. Машина Поста
«Внешний вид» машины Поста
Машина Поста не есть реально существующее, сделанное кем-то устройство; поэтому слова «внешний вид» и взяты в кавычки. Машина Поста, как и ее близкий родственник - машина Тьюринга, - представляет собой мысленную конструкцию, существующую лишь в нашем воображении (хотя ее в принципе и можно было бы изготовить «в металле»). Именно это имеют в виду, когда говорят о машинах Поста и Тьюринга, что они суть «абстрактные» вычислительные машины. И подобно тому, как можно выучиться считать на счетах или на логарифмической линейке, не имея перед собой этих приборов, а, пользуясь лишь их описаниями и представляя их себе мысленно, так же и мы научимся вычислять на машине Поста.
Машина Поста состоит из ленты и каретки (называемой также считывающей и записывающей головкой).
Лента бесконечна и разделена на секции одинакового размера: для наглядности ленту будем считать расположенной горизонтально (рис. 13).
Бесконечность ленты находится в противоречии со сделанным выше утверждением, что машину Поста можно было бы в принципе построить. Дело в том, что мы объявили ленту бесконечной лишь для простоты изложения. С тем же успехом можно было бы предположить, что лента не бесконечная, а лишь неограниченно растущая в обе стороны: например, можно было бы считать, что лента наращивается на одну секцию, как только каретка доходит до конца ленты и должна двигаться дальше, или считать, что за каждую единицу времени слева и справа нарастает по одной секции. Однако будет удобнее считать, что все секции слева и справа уже наросли, и тем самым, хотя и в ущерб реальности, полагать ленту бесконечной в обе стороны.
Порядок, в котором расположены секции ленты, подобен порядку, в котором расположены все целые числа. Поэтому естественно ввести на ленте «целочисленную систему координат», занумеровав секции целыми числами ..., -3,-2,-1,0,1, 2,3, ... (рис. 14).
Мы будем считать, что система координат жестко сопоставлена с лентой, и получим, таким образом, возможность указывать какую-либо секцию ленты, называя ее порядковый номер, или координату. (Иногда, впрочем, бывает удобно наряду с основной, «постоянной» системой координат, ввести еще вспомогательную, «временную», сдвинутую по отношению к первоначальной)
В каждой секции ленты может быть либо ничего не записано (такая секция называется пустой), либо записана метка V (тогда секция называется отмеченной) (рис. 15).
Информация о том, какие секции пусты, а какие отмечены, образует состояние ленты. Иными словами, состояние ленты — это распределение меток по ее секциям. Как мы далее увидим, состояние ленты меняется в процессе работы машины.
Каретка может передвигаться вдоль ленты влево и вправо. Когда она неподвижна, она стоит против ровно одной секции ленты на этом и следующих чертежах каретка изображена в виде зачерненного квадрата); говорят, что каретка обозревает эту секцию, или держит ее в поле зрения.
Информация о том, какие секции пусты, а какие отмечены и где стоит каретка, образует состояние машины Поста.
Таким образом, состояние машины слагается из состояния ленты и указания номера той секции, которую обозревает каретка. За единицу времени (которую мы будем называть шагом) каретка может сдвинуться на одну секцию влево или вправо. Кроме того, каретка может поставить (напечатать) или уничтожить (стереть) метку на той секции, против которой она стоит, а также распознать, стоит или нет метка в обозреваемой ею секцией[2].
Программа машины Поста
Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Эта работа происходит по инструкции определенного вида, называемой программой. Для машины Поста возможно составление различных программ. Посмотрим, как устроена программа.
Каждая программа машины Поста состоит из команд. Командой машины Поста будем называть выражение, имеющее один из следующих шести видов (буквы i, j, j1, j2 означают всюду натуральные числа 1, 2, 3, 4, 5, …):
Первый вид. Команды движения вправо.
![]()
Второй вид. Команды движения влево.
![]()
Третий вид. Команды печатания метки.
![]()
Четвертый вид. Команды стирания метки.
![]()
Пятый вид. Команды передачи управления.

Шестой вид. Команды остановки.
![]()
Например,
![]()
является командой движения вправо,

- командой передачи управления, а
![]()
-командой остановки.
Число i, стоящее в начале команды, называется номером команды. Так, у приведенных только что команд номера соответственно 137, 25 и 6386. Число j, стоящее в конце команды (а у команд передачи управления - каждое из чисел j1, и j2), будем называть отсылкой (при этом в команде передачи управления j1—верхней, а j2 — нижней отсылкой). У команд остановки нет отсылки. Так, у приведенных только что команд отсылками служат числа 1, 32, 25, причем 32 —верхняя отсылка, а 25 — нижняя отсылка.
Программой машины Поста будем называть конечный непустой (т. е. содержащий хотя бы одну команду) список команд машины Поста, обладающий следующими двумя свойствами:
1) На первом месте в этом списке стоит команда с номером 1, на втором месте (если оно есть) – команда с номером 2 и т. д.; вообще на k-м месте стоит команда с номером k.
2) Отсылка любой из команд списка совпадает с номером некоторой (другой или той же самой) команды списка (более точно: для каждой отсылки каждой команды списка найдется в.списке такая команда, номер которой равен рассматриваемой отсылке).
Например, следующий список будет программой машины Поста:
А эти два списка не будут программами машины Поста, хотя и составлены из команд машины Поста:
Для наглядности программы машины Поста мы будем записывать столбиком. Число команд программы называется длиной программы[1].
Работа машины Поста
Чтобы машина Поста начала работать, надо задать, во-первых, некоторую программу, а во-вторых, некоторое ее (машины) состояние, т. е. как-то расставить метки по секциям ленты (в частности, можно все секции оставить пустыми) и поставить каретку против одной из секций. Как правило, мы будем предполагать, что в начальном (т.е. в задаваемом вначале) состоянии машины каретка ставится всегда против секции с номером (координатой) нуль. При таком соглашении начальное состояние машины полностью определено состоянием ленты.
Как уже говорилось, программа является той инструкцией, на основании которой работает машина. Работа машины на основании заданной программы (и при заданном начальном состоянии) происходит следующим образом. Машина приводится в начальное состояние и приступает к выполнению первой команды программы. Эта команда выполняется за один шаг, после чего машина приступает к выполнению той команды, номер которой (назовем его а) равен отсылке (одной из отсылок, если их две) первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение команды, номер которой равен отсылке команды с номером а. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k-м шаге выполнялась команда с номером i, тогда, если эта команда имеет единственную отсылку j, то на k+1-м шаге выполняется команда с номером j; если эта команда имеет две отсылки j1 и j2, то на k+1-м шаге выполняется одна из двух команд – с номером j1 или с номером; если, наконец, выполняющаяся на k-м шаге команда вовсе не имеет отсылки, то на k + 1-м шаге и на всех последующих шагах не выполняется никакая команда: машина останавливается. Осталось объяснить, что значит выполнить команду и какая из отсылок - при наличии двух - выбирается в качестве номера следующей команды.
Выполнение команды движения вправо состоит а том, что каретка сдвигается на одну секцию вправо. Выполнение команды движения влево состоит в том, что каретка сдвигается на одну секцию влево. Выполнение команды печатания метки состоит в том, что каретка ставит метку на обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая перед началом выполнения команды секция пуста; если же на обозреваемой секции уже стоит метка, команда считается невыполнимой. Выполнение команды стирания метки состоит в том, что каретка уничтожает метку в обозреваемой секции; выполнение этой команды возможно лишь в том случае, если обозреваемая секция отмечена; если же на обозреваемой секции и так нет метки, команда считается невыполнимой. Выполнение команды передачи управления с верхней отсылкой j1 и нижней отсылкой j2 никак не изменяет состояния машины: ни одна из меток не уничтожается и не ставится, и каретка также остается неподвижной (машина делает, так сказать, «шаг на месте»); однако если секция, обозреваемая перед началом выполнения этой команды, была пуста, то следующей должна выполняться команда с номером j1, если же эта секция была отмечена, следующей должна выполняться команда с номером j2 (роль команды передачи управления сводится, следовательно, к тому, что каретка во время выполнения этой команды как бы «распознает», стоит ли перед ней метка). Выполнение команды остановки тоже никак не меняет состояния машины и состоит в том, что машина останавливается.
Если теперь, задавшись программой и каким-либо начальным состоянием, пустить машину в ход, то осуществится один из следующих трех вариантов:
1) В ходе выполнения программы машина дойдет до выполнения невыполнимой команды (печатания метки в непустой секции или стирания метки в пустой секции); выполнение программы тогда прекращается, машина останавливается; происходит так называемая безрезультатная остановка.
2) В ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается; происходит так называемая результативная остановка.
3) В ходе выполнения программы машина не дойдет до выполнения ни одной из команд, указанных в первых двух вариантах; выполнение программы при этом никогда не прекращается, машина никогда не останавливается; процесс работы машины происходит бесконечно[5].
Глава 2. Инструкция программиста
Данная учебная программа должна запускаться на IBM и совместимых компьютерах. Минимальные системные требования: процессор Pentium и выше, объем оперативной памяти 16MB, видеокарта с расширением 800x600, 256 цветов, операционная система семейства Windows 95 и выше, на компьютере также должен быть установлен .NET Framework.
Основную ценность представляют файлы расширением *.cs (в них содержится весь код программы).
Опишем основные файлы, содержащиеся в этой папке:
Even_ueven.cs – файл, в котором содержится код, отвечающий за работу алгоритма «Кодирование по методу четностинечетности»;
Even_ueven.resx – файл, в котором содержится информация о графическом представлении формы «Кодирование по методу четностинечетности»;
Hemming.cs - файл, в котором содержится код, отвечающий за работу алгоритма «Кодирование по методу Хэмминга»;
Hemming.resx – файл, в котором содержится информация о графическом представлении формы «Кодирование по методу Хэмминга»;
Post.cs - файл, в котором содержится код, отвечающий за работу алгоритма «Программирование машины Поста»;
Post.resx – файл, в котором содержится информация о графическом представлении формы «Программирование машины Поста»;
Error.cs - файл, в котором содержится код, отвечающий за работу формы Error;
Error.resx – файл, в котором содержится информация о графическом представлении формы Error;
Help.cs - файл, в котором содержится код, отвечающий за работу формы Справка;
Help.resx – файл, в котором содержится информация о графическом представлении формы Справка;
Start.cs - файл, в котором содержится код, отвечающий за работу формы Start;
Start.resx – файл, в котором содержится информация о графическом представлении формы Start;
AssemblyInfo.cs - файл, в котором содержится информация о версии файла, внутреннем и исходном имени файла, производителе;
StudyProgram.exe - закомпилированный файл программы, находящийся в папке debug, которая находится в папке bin.
Для изменения программы необходимо изменить ее исходный код. Это можно сделать, используя любой текстовый редактор. Пример кода представлен на Рис.2.
Изменение кода при помощи текстового редактора не очень удобно, для этого лучше использовать Visual Studio .Net, специально для этого разработанный.
На Рис.3 можно увидеть внешний облик Visual Studio .Net. Для его запуска необходимо кликнуть кнопку Пуск, выбрать в пункте Все программы Microsoft Visual Studio .NET 2003Microsoft Visual Studio .NET 2003. Далее в запустившемся приложении кликнуть кнопку Open Project и используя проводник, выбрать файл Study_Programs.sln. Программа откроет приложение. Для изменения внешнего вида программы необходимо воспользоваться ярлыком Design. Можно добавить новые элементы формы, перетащив их из выезжающего окна Toolbox. Исходный код программы см. в Приложении.
В самом начале программы задаются поля, так называемые член- переменные, содержащие некоторое значение: int Prav; int ch; int ChVoprosov=1 (в ООП поля иногда называют данными объекта).Где Prav-это количество правильных ответов, ch – это сумма всех разрядов генерируемого числа и контрольного разряда, а ChVoprosov-число вопросов заданных пользователю (нумерация начинается с 1) Перед идентификаторами полей указываются их типы.
При запуске формы Even_ueven во время работы программы сразу срабатывает метод Generation(); .Суть данного метода состоит в том, чтобы сгенерировать произвольное семизначное двоичное число, которое появится в окне textBox1 и контрольный разряд(который также является двоичным числом), который появится в окне textBox2. Для этого создается генератор случайных чисел, который записывает в переменную d либо 0, либо 1( d=r.Next(0,2); ), данная операция повторяется 7 раз с помощью цикла с параметром for( for (int i=0; i<7; i++) ). В результате, последовательно добавив каждую из сгенерированных цифр, мы получаем требуемое семизначное число. Контрольный разряд создается тоже с помощью генератора случайных чисел ( g=r.Next(0,2); ).Также в этом методе сразу подсчитывается сумма всех разрядов генерируемого числа и контрольного разряда ch: сначала складываются разряды числа все в том же цикле for (ch+=d; - 7 раз), а затем прибавляется контрольный разряд g (ch+=g;).
При нажатии кнопки button1 (Код числа правильный) вначале запускается метод ChangeChVoposov(); который увеличивает номер вопроса на одну единицу в окне textBox3. Затем в поле Prav(количество правильных ответов) считывается значение из окна textBox4( при первом запуске оно равняется 0), Далее с помощью управляющей конструкции if (ch==0 || ch==2 || ch==4 || ch==6) определяется правильно ли пользователь ответил : ch - сумма всех разрядов генерируемого числа и контрольного разряда должна быть четной или равной 0. В случае верного выбора количество правильных ответов увеличивается на 1 ( Prav++; ). Затем запускается метод ChangePrav();, который устанавливает число правильных ответов в окне textBox4. После чего ch обнуляется ( ch=0; ) , и запускается метод Generation();.
При нажатии кнопки button2 (Код числа неправильный) алгоритм программы является практически аналогичным за исключением того, что в управляющей конструкции if (ch==1 || ch==3 || ch==5 || ch==7) правильность ответа пользователя заключается в том, чтобы сумма ch являлась нечетным числом.
Также следует обратить внимание на то, что при работе с дизайном формы нужно заблокировать окна от пользователя, чтобы он не смог перепечатать значение генерируемых семиразрядного числа и контрольного разряда, а также количество заданных вопросов и данных правильных ответов. Исходный код программы представлен в Приложении.
Кодирование по методу Хэмминга
В самом начале программы задаются поля: int ChVoprosov=1,
int X; int Nomer; int [] x=new int[10] .Где X – это переменная значение которой не позволяет в определенных случаях нажиманием на одну и ту же кнопку увеличивать число правильных ответов, Nomer – это получаемый номер разряда, который подлежит замене на противоположный, int [] x=new int[10] – это массив, состоящий из значений, которые являются разрядами генерируемого двоичного числа, а ChVoprosov-число вопросов заданных пользователю (нумерация начинается с 1). Перед идентификаторами полей указываются их типы.
При запуске формы Hemming во время работы программы сразу срабатывает метод Generation(); и метод Number(); .Суть первого метода состоит в том, чтобы сгенерировать произвольное девятизначное двоичное число, которое появится в окне textBox1. Суть второго метода заключается в том, чтобы подсчитать номер разряда, в котором есть ошибка (если конечно такова вообще имеется). Следует учесть, что номер подсчитывается в двоичном виде.
Для формирования произвольного девятизначного двоичного числа создается генератор случайных чисел, который записывает в переменную d либо 0, либо 1( d=r.Next(0,2); ), данная операция повторяется 9 раз с помощью цикла с параметром for( for (int i=1; i<10; i++) ). В результате, последовательно добавив каждую из сгенерированных цифр, мы получаем требуемое девятизначное число. Также на каждом шаге цикла с параметром считываются значения в массив int [] x ( x[i]=d; ), т.е. получается , что каждый элемент массива равен соответствующему по номеру разряду сгенерированного числа. В данном методе переменная X приравнивается к 1, что означает, что число только что сгенерированно и пользователь еще не пробовал дать свой ответ.
В методе Number() подсчитываются суммы контрольных разрядов сгенерируемого по числа, соответствующие определенным группам проверки. В нашем случае количество групп проверки для девятизначного числа равно 4, следовательно, мы получаем четыре суммы x1, x2, x3, x4.
Затем подсчитывается номер ошибочного разряда (Nomer=x4*1000+x3*100+x2*10+x1;)
При нажатии кнопки button1 (Ошибки нет) в начале исчезает все то, что пользователь успел ввести в окно «Исправленный вариант» (textBox2.Text="";), т.к. нажав эту кнопку пользователь показывает то, что он уже не находит ошибок в числе. Потом с помощью управляющей конструкции if проверяется не записан ли уже ответ в окне «Правильный ответ»( if(textBox1.Text.Length!=textBox3.Text.Length) ели не записан, то тогда X приравнивается к единице: X=1;) Затем с помощью управляющей конструкции if проверяется, равен ли X единице (if (X==1) – если это выполнено, то значит, что пользователь еще не пробовал дать свой ответ). Дальнейшее выполнение действий возможно только если X=1. Затем, используя снова if, Nomer сравнивается с нулем (if (Nomer==0)). В случае выполнения данного условия (т.е. номер ошибочного разряда равняется нулю, что означает отсутствие ошибки) число правильных ответов увеличивается на одну единицу ( Prav++; ), и запускается метод Otvet(); . Данный метод записывает в окно textBox3 (Правильный ответ) ответ, получаемый путем записи всех элементов массива int [] x в порядке возрастания:
textBox3.Text=x[1]+""+x[2]+""+x[3]+""+x[4]+""+x[5]+""+[6]+""+x[7]+""+x[8]+""+x[9];
В данном случае ошибка отсутствует и все элементы запишутся без изменения, т.е. в окне textBox3 появится число, аналогичное тому, которое находится в окне textBox1 (Число, возможно содержащее ошибку).
Если Nomer не равняется нулю, то тогда запускается метод Sravnenie();. Этот метод вначале проверяет не дали ли вы уже свой окончательный ответ (не равно ли уже X нулю) и только в случае равенства X единице (if (X==1)) выполняется вся остальная часть метода: переменную i приравнивают т к нулю (int i=0;). Затем происходит сравнение числа Nomer с двоичными цифрами, которые при переводе в десятичную систему счисления соответствуют числам от 0 до 9 (например: if (Nomer == 101) – число Nomer сравнивается с двоичным числом 101, которому в десятичной системе счисления соответствует 5). Если Nomer равняется какому-то из предложенных двоичных чисел, то тогда переменной i присваивается значение соответствующего десятичного числа (Например в случае равенства номера числу 101, переменной i присвоится значение 5 (i = 5;)). Если переменная i меняет свое значение с нуля на какое-то от 1 до 9, то тогда выполняется условие следующей за этим управляющей конструкции if (i!=0) (i отлично от нуля) и осуществляется следующие операции: x[i] сравнивается с 0, если это выполняется, то тогда x[i] меняет свое значение на противоположное, т.е. на 1, и затем запускается уже упомянутый выше метод Otvet(); (только теперь в окне textBox3 появится число, аналогичное тому, которое находится в окне textBox1 (Число, возможно содержащее ошибку), но уже с замененным на противоположный разрядом, номер которого равен i.). Если x[i] не равняется 0(следовательно равняется 1), то тогда выполняется ветка else с аналогичными действиями, только для x [i] противоположным значением будет являться 0.
Если в ходе выполнения метода Sravnenie(); не было произведено никаких замен (не выполнялся метод Otvet();), то это означает, что числу Nomer соответствует какое-то двоичное число, которое при переводе в десятичную систему счисления дает цифру большую 9. Это означает, что в сгенерированном девятиразрядном числе отсутствуют ошибки. Тогда с помощью сравнения длины строки в окне textBox3 с нулем (if(textBox3.Text.Length==0)) мы получаем в случае выполнения данного условия, что ошибки отсутствуют. Следовательно, мы можем увеличить число правильных ответов на 1 и запустить метод Otvet();,который запишет в окно textBox3 число, равное тому, которое находится в окне textBox1 (Число, возможно содержащее ошибку).
В итоге мы меняем число правильных ответов в окне textBox5, а также приравниваем X к нулю, это означает, что мы сделали свой окончательный выбор того, содержит ли сгенерированное число ошибки.
При нажатии кнопки button2 (Ошибка есть) в начале запускается метод Proverka();. Смысл этого метода заключается в том, чтобы проверить ввел ли пользователь достаточное количество разрядов в окно «Исправленный вариант» и являются ли они двоичными числами (0 и 1). Вначале с помощью управляющей конструкции if проверяется, записал ли пользователь строку в окно «Исправленный вариант» требуемой длины и нет ли уже появившегося ответа в окне textBox3 (Правильный ответ): if(textBox2.Text.Length! =textBox1.Text.Length && textBox1.Text.Length! = textBox3.Text.Length)
Если это условие выполняется, то это означает, что пользователь ввел в окно «Исправленный вариант» строку меньшую по своей длине 9 или то, что уже был получен ответ и, следовательно, выполняется действие, заключенное в фигурных скобках: запуск формы об ошибке, содержащее пояснение того, в чем заключается ошибка ввода (A5=new Error("Исправленный вариант должен содержать 9-ти разрядное число"); A5.ShowDialog(); )
Если это условие не выполняется, то работа алгоритма программы продолжается по ветке else. Вначале снова проверяется отсутствие ответа if(textBox1.Text.Length!=textBox3.Text.Length) и только когда это условие выполнено запускается цикл с параметром (for(int i=0; i<textBox2.Text.Length; i++)) , который сравнивает все разряды введенного пользователем числа с 0 или 1.Для этого используется заложенный в языке C# метод работы со строками Substring(i,1) (string d=textBox2.Text.Substring(i,1); - в строку d записывается один символ введенного пользователем числа , начиная с i-ой позиции (а i меняется от 0 до длины введенной строки, т.е. до 9 )). В ходе работы цикла d 9 раз сравнивается с 0 или 1 (if(d!=b && d!=a)) ,и при первом же случая, когда d не является 1 или 0 появляется форма ошибки, содержащее пояснение того, в чем заключается ошибка ввода (A5=new Error("Исправленный вариант должен содержать 9-ти разрядное двоичное число"); A5.ShowDialog(); ), а цикл прекращается, т.к. переменной i присваивается значение равное textBox2.Text.Length. Также в случае появления ошибки переменная X приравнивается к 0. В случае отсутствии ошибки ввода переменная X приравнивается к 1.На этом метод Proverka(); заканчивается. Если X=1, то возможны дальнейшие операции заключенные в фигурных скобках условия if (X==1). Используя условную конструкцию if, Nomer сравнивается с нулем (if (Nomer==0)). Если данное условие выполняется (т.е. номер ошибочного разряда равняется нулю, что означает отсутствие ошибки), то пользователь ответил неправильно, неверно предположив, что содержится ошибка. Затем запускается метод Otvet(), который выведет число в окне textBox3, равное сгенерированному числу.
После этого запускается метод Sravnenie(); (его запуск требуется, если не выполняется условие Nomer==0). Если Nomer не равен нулю и метод Sravnenie(); не дает правильного ответа в окне textBox3,, то, следовательно, Nomer при переводе в десятичную систему счисления дает число, большее, чем 9. Это означает, что сгенерированное число не содержит неправильных разрядов и в окно textBox3 нужно записать заданное число без изменений. Для этого используется условная конструкция, которая проверяет, записан ли ответ в textBox3: if (textBox3.Text.Length==0) Otvet();. Затем в переменную Moe считывается число, которое пользователь ввел в окно textBox2, а в переменную Pravilnoe считывается ответ из textBox3. После чего эти две переменные сравниваются между собой и в случае равенства количество правильных ответов увеличивается на 1: if (Moe==Pravilnoe) Prav++; . Затем переменная X приравнивается к нулю, что означает, что пользователь уже сделал свой окончательный выбор.
Кнопка button3 служит для того чтобы сгенерировать следующее число, когда работа с предыдущим закончена. При нажатии