ЛАБОРАТОРНАЯ РАБОТА №3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ
ИМЕНИ АКАДЕМИКА С.П. КОРОЛЕВА
(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ)» (СГАУ)
Факультет информатики
Кафедра программных систем
ОТЧЕТ
По лабораторным работам по дисциплине
«Практикум на ЭВМ»
Вариант № 25
| Выполнил студент группы 6212 Уланов Р.Н. Проверил доцент каф. ПС Дубина С.М. Дата сдачи: 15.12.14 Оценка: |
Самара
2014 г.
СОДЕРЖАНИЕ
1 Лабораторная работа №1 «Булева алгебра». 3
1.1 Задание. 3
1.2 Алгоритм решения. 3
1.3 Код программы.. 3
2 Лабораторная работа №2 «Машина Тьюринга». 4
2.1 Задание. 4
2.2 Алгоритм решения. 4
2.3 Код программы.. 4
3 Лабораторная работа №3 «Исчисление предикатов». 9
3.1 Задание. 9
3.2 Алгоритм решения. 9
3.3 Код программы.. 9
4 Лабораторная работа №4 «Теория алгоритмов». 10
4.1 Задание. 10
4.2 Алгоритм решения. 10
4.3 Код программы.. 10
5 Лабораторная работа №5 «Автоматизация вывода». 11
5.1 Задание. 11
5.2 Алгоритм решения. 11
5.3 Код программы.. 11
ЛАБОРАТОРНАЯ РАБОТА №1
«Булева алгебра»
Задание
Данную КНФ преобразовать в эквивалентную СКНФ: X 
Z V 
X Y Z V X Z Y.
Алгоритм решения
Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение :Z Z = 0 (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:
Код программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Text.RegularExpressions;
namespace матлог
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
string s = "X OR Z OR V AND NOT X OR Y OR NOT Z OR V AND X OR NOT Z OR Y";
string[] kon = Regex.Split(s, "OR");
MessageBox.Show("Пребразованная СКНФ: \n (X OR Y OR Z OR V) AND (X OR NOT Y OR Z OR V) AND (NOT X OR Y OR NOT Z OR V) AND (X OR Y OR NOT Z OR V) AND (X OR Y OR NOT Z OR NOT V)");
}
private void Form1_Load(object sender, EventArgs e)
{
}
private void label1_Click(object sender, EventArgs e)
{
}
}
}
ЛАБОРАТОРНАЯ РАБОТА №2
«Машина Тьюринга»
Задание
Разработать МТ, осуществляющую проверку "больше" с пошаговой демонстрацией её работы.
Алгоритм решения
По предоставленному алфавиту пользователь вводит для сравнения два числа в разные окна для работы программы. После проверки алгоритма, МТ выводит на экран “1” в случае, когда число a>b, и “λ”, если a<b.
Код программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ЭВМ_Лаба_2
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
dg1rows();
dg2rows();
dg3rows();
Text = "Лабораторная работа №2";
name.Text = "Выполнил: Овсянников Валентин 6213Б Вариант 41";
label1.Text = "Алфавит: _ 0 1";
tabpage1.Text = "МТ1";
TextS1.HeaderText = "s10";
TextS2.HeaderText = "s11";
TextS3.HeaderText = "s12";
TextS4.HeaderText = "s13";
TextS5.HeaderText = "s14";
tabpage2.Text = "МТ2";
TextS6.HeaderText = "s18";
TextS7.HeaderText = "s19";
TextS8.HeaderText = "s20";
TextS9.HeaderText = "s21";
TextS10.HeaderText = "s22";
tabpage3.Text = "МТ3";
TextS11.HeaderText = "s23";
TextS12.HeaderText = "s24";
TextS13.HeaderText = "s25";
TextS14.HeaderText = "s26";
TextS15.HeaderText = "s27";
butinprog.Text = "Ввести программы";
textBox1.Text = "Введите ваше слово";
inword.Text = "Ввести слово";
step.Text = "Сделать шаг";
s1.HeaderText = "s1";
s2.HeaderText = "s2";
s3.HeaderText = "s3";
s4.HeaderText = "s4";
s5.HeaderText = "s5";
s6.HeaderText = "s6";
s7.HeaderText = "s7";
s8.HeaderText = "s8";
s9.HeaderText = "s9";
s10.HeaderText = "s10";
s11.HeaderText = "s11";
s12.HeaderText = "s12";
s13.HeaderText = "s13";
s14.HeaderText = "s14";
s15.HeaderText = "s15";
s16.HeaderText = "s16";
s17.HeaderText = "s17";
s18.HeaderText = "s18";
s19.HeaderText = "s19";
s20.HeaderText = "s20";
s21.HeaderText = "s21";
s22.HeaderText = "s22";
s23.HeaderText = "s23";
s24.HeaderText = "s24";
s25.HeaderText = "s25";
s26.HeaderText = "s26";
s27.HeaderText = "s27";
exit.Text = "Выход";
}
int cur = 3;
StringBuilder str = new StringBuilder (50);
int lenstr = 0;
int i = 0; int ii = 0;
int j = 0; int jj = 0;
private void exit_Click(object sender, EventArgs e)
{
Close();
}
private int provdg1()
{
int o = 0;
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg1[i, j].Value == null) o=1;
}
o = 1;
}
return o;
}
private int provdg2()
{
int o = 0;
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg2[i, j].Value == null) o=1;
}
o = 1;
}
return o;
}
private int provdg3()
{
int o = 0;
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg3[i, j].Value == null) o=1;
}
o = 1;
}
return o;
}
private void dataGridViewCopy()
{
dataGridView1[0, 0].Value = "_10R";
dataGridView1[0, 1].Value = "25R";
dataGridView1[0, 2].Value = "32R";
dataGridView1[0, 3].Value = "*1L";
dataGridView1[0, 4].Value = "01L";
dataGridView1[0, 5].Value = "11L";
dataGridView1[1, 0].Value = "*3R";
dataGridView1[1, 1].Value = "02R";
dataGridView1[1, 2].Value = "12R";
dataGridView1[1, 3].Value = "*3R";
dataGridView1[2, 0].Value = "14L";
dataGridView1[2, 1].Value = "03R";
dataGridView1[2, 2].Value = "13R";
dataGridView1[3, 1].Value = "04L";
dataGridView1[3, 2].Value = "14L";
dataGridView1[3, 3].Value = "*4L";
dataGridView1[3, 4].Value = "21R";
dataGridView1[3, 5].Value = "31R";
dataGridView1[4, 0].Value = "*6R";
dataGridView1[4, 1].Value = "05R";
dataGridView1[4, 2].Value = "15R";
dataGridView1[4, 3].Value = "*6R";
dataGridView1[5, 0].Value = "07L";
dataGridView1[5, 1].Value = "06R";
dataGridView1[5, 2].Value = "16R";
dataGridView1[6, 1].Value = "07L";
dataGridView1[6, 2].Value = "17L";
dataGridView1[6, 3].Value = "*7L";
dataGridView1[6, 4].Value = "21R";
dataGridView1[6, 5].Value = "31R";
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg1[i, j].Value != null) { dataGridView1[i+9, j].Value = dg1[i, j].Value; dataGridView1[i+9, 3].Value = "*15L"; }
}
}
dataGridView1[14, 0].Value = "_16R";
dataGridView1[14, 1].Value = "015L";
dataGridView1[14, 2].Value = "115L";
dataGridView1[14, 3].Value = "_15L";
dataGridView1[15, 0].Value = "_16R";
dataGridView1[15, 1].Value = "_17R";
dataGridView1[15, 2].Value = "_17R";
dataGridView1[15, 3].Value = "_18R";
dataGridView1[16, 1].Value = "_17R";
dataGridView1[16, 2].Value = "_17R";
dataGridView1[16, 3].Value = "_23R";
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg2[i, j].Value != null) dataGridView1[i+17, j].Value = dg2[i, j].Value;
}
}
for (int i = 0; i <= 4; i++)
{
for (int j = 0; j <= 2; j++)
{
if (dg3[i, j].Value != null) dataGridView1[i+22, j].Value = dg3[i, j].Value;
}
}
}
private void butinprog_Click(object sender, EventArgs e)
{
if ((provdg2() == 0) || (provdg3() == 0))
{
if ((provdg3() == 0) && (provdg2() == 0)) MessageBox.Show("В программах МТ2 и МТ3 нет состояния покоя");
if ((provdg2() == 0) && (provdg3() == 1)) MessageBox.Show("В программе МТ2 нет состояния покоя");
if ((provdg3() == 0) && (provdg2() == 1)) MessageBox.Show("В программе МТ3 нет состояния покоя");
}
else
{
dataGridView1.Visible = true;
dataGridView1.Enabled = true;
butinprog.Enabled = false;
textBox1.Enabled = true;
inword.Enabled = true;
dataGridView1.Rows.Clear();
dataGridView1rows();
dataGridViewCopy();
}
}
private void dataGridView1rows()
{
dataGridView1.Rows.Add(6);
dataGridView1.Rows[0].HeaderCell.Value = "_";
dataGridView1.Rows[1].HeaderCell.Value = "0";
dataGridView1.Rows[2].HeaderCell.Value = "1";
dataGridView1.Rows[3].HeaderCell.Value = "*";
dataGridView1.Rows[4].HeaderCell.Value = "2";
dataGridView1.Rows[5].HeaderCell.Value = "3";
}
private void dg1rows()
{
dg1.Rows.Add(3);
dg1.Rows[0].HeaderCell.Value = "_";
dg1.Rows[1].HeaderCell.Value = "0";
dg1.Rows[2].HeaderCell.Value = "1";
}
private void dg2rows()
{
dg2.Rows.Add(3);
dg2.Rows[0].HeaderCell.Value = "_";
dg2.Rows[1].HeaderCell.Value = "0";
dg2.Rows[2].HeaderCell.Value = "1";
}
private void dg3rows()
{
dg3.Rows.Add(3);
dg3.Rows[0].HeaderCell.Value = "_";
dg3.Rows[1].HeaderCell.Value = "0";
dg3.Rows[2].HeaderCell.Value = "1";
}
private void textBox1_Click(object sender, EventArgs e)
{
if (this.textBox1.Text == "Введите ваше слово") this.textBox1.Text = "";
}
private void inword_Click(object sender, EventArgs e)
{
str = new StringBuilder(textBox1.Text);
lenstr = str.Length;
textBox1.Enabled = false;
inword.Enabled = false;
step.Visible = true;
textBox2.Visible = true;
if (str.ToString() == "Введите ваше слово") str = new StringBuilder("");
textBox2.Text = "___" + str;
for (int t = 0; t <= str.Length+3; t++)
{
textBox2.Text = textBox2.Text + "_";
}
step.Enabled = true;
i = 0; ii = 0;
j = 0;
cur = 3;
}
private void step_Click(object sender, EventArgs e)
{
StringBuilder word = new StringBuilder(textBox2.Text);
if (i < 9)
{
if (textBox2.Text[cur].ToString() == "_") j = 0;
if (textBox2.Text[cur].ToString() == "0") j = 1;
if (textBox2.Text[cur].ToString() == "1") j = 2;
if (textBox2.Text[cur].ToString() == "*") j = 3;
if (textBox2.Text[cur].ToString() == "2") j = 4;
if (textBox2.Text[cur].ToString() == "3") j = 5;
dataGridView1[ii, jj].Style.BackColor = Color.White;
if ((dataGridView1[i, j].Value != null) || ((i != 0) && (j != 0)) || (dataGridView1[ii, j].Value.ToString()[3].ToString() != "S"))
{
word[cur] = Convert.ToChar(dataGridView1[i, j].Value.ToString()[0].ToString());
textBox2.Text = word.ToString();
ii = i; jj = j;
dataGridView1[i, j].Style.BackColor = Color.LightSkyBlue;
if (cur == 2) { i = Convert.ToInt32(dataGridView1[ii, j].Value.ToString()[1].ToString() + dataGridView1[ii, j].Value.ToString()[2].ToString()) - 1; }
else { i = Convert.ToInt32(dataGridView1[ii, j].Value.ToString()[1].ToString()) - 1; }
if (dataGridView1[ii, j].Value.ToString()[2].ToString() == "R") { cur++; }
if (dataGridView1[ii, j].Value.ToString()[2].ToString() == "L") { cur--; }
}
if (cur == 2)
{
word[cur] = '_';
textBox2.Text = word.ToString();
cur++;
i = 9;
}
}
if (i>=9)
{
if (textBox2.Text[cur].ToString() == "_") j = 0;
if (textBox2.Text[cur].ToString() == "0") j = 1;
if (textBox2.Text[cur].ToString() == "1") j = 2;
if (textBox2.Text[cur].ToString() == "*") j = 3;
if (textBox2.Text[cur].ToString() == "2") j = 4;
if (textBox2.Text[cur].ToString() == "3") j = 5;
dataGridView1[ii, jj].Style.BackColor = Color.White;
if ((dataGridView1[i, j].Value != null) || (dataGridView1[ii, j].Value.ToString()[3].ToString() != "S"))
{
word[cur] = Convert.ToChar(dataGridView1[i, j].Value.ToString()[0].ToString());
textBox2.Text = word.ToString();
ii = i; jj = j;
dataGridView1[i, j].Style.BackColor = Color.LightSkyBlue;
i = Convert.ToInt32(dataGridView1[ii, j].Value.ToString()[1].ToString() + dataGridView1[i, j].Value.ToString()[2].ToString()) - 1;
if (dataGridView1[ii, j].Value.ToString()[3].ToString() == "R") { cur++; }
if (dataGridView1[ii, j].Value.ToString()[3].ToString() == "L") { cur--; }
}
else
{
if (dataGridView1[ii, j].Value.ToString()[3].ToString() == "S")
{
word[cur] = Convert.ToChar(dataGridView1[ii, j].Value.ToString()[0].ToString());
}
textBox2.Text = word.ToString();
MessageBox.Show("Результат: "+word.ToString());
step.Enabled = false;
inword.Enabled = true;
textBox1.Enabled = true;
}
}
}
}
}
ЛАБОРАТОРНАЯ РАБОТА №3
«Исчисление предикатов»
Задание
Преобразовать формулу ∀X ∀Y ((A1² (X,Y) A2² (X,Y)) V A3² (X,Y)) в нормальную форму Сколема.
Алгоритм решения
Для решения задачи воспользуемся эквивалентным преобразованием в нормальную форму Сколема.
Код программы
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Text.RegularExpressions;
namespace матлог
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
string s = "∀X ∀Y ((A1^2 (X,Y) OR A2^2 (X,Y)) AND NOT A3^2 (X,Y))";
string[] kon = Regex.Split(s, "OR");
MessageBox.Show("Нормальная форма Сколема для ∀X ∀Y ((A1^2 (X,Y) OR A2^2 (X,Y)) AND NOT A3^2 (X,Y)): \n((A1^2 (X,Y) OR A2^2 (X,Y)) AND NOT A3^2 (X,Y))");