Форум программистов, компьютерный форум CyberForum.ru

Машина Тьюринга. Перенос нуля. Реализировать на С++ - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 25, средняя оценка - 4.68
Asuser
0 / 0 / 0
Регистрация: 22.10.2012
Сообщений: 18
22.10.2012, 23:17     Машина Тьюринга. Перенос нуля. Реализировать на С++ #1
Приветствую! Я в С++ очень плохо разбираюсь, но нужна программа... Буду рад всем откликнувшимся.
Миниатюры
Машина Тьюринга. Перенос нуля. Реализировать на С++  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2012, 23:17     Машина Тьюринга. Перенос нуля. Реализировать на С++
Посмотрите здесь:

C++ Машина Тьюринга. (Динамический массив))
Машина Тьюринга C++
Машина Тьюринга C++
C++ Машина тьюринга на с++
C++ Машина Тьюринга
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Asuser
0 / 0 / 0
Регистрация: 22.10.2012
Сообщений: 18
24.10.2012, 22:57  [ТС]     Машина Тьюринга. Перенос нуля. Реализировать на С++ #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <conio.h>
using namespace std;
 
int main()
{
    int q,n,i;
    char a[20];
 
    cout << "Vvedit slovo (alfavit {0,1}): ";
    cin >> a;
    
    i=0;
    q=1;
    
    while(q!=0)
    {
        if (a[i]=='0')
        {
            switch(q)
            {
            case 1: { a[i]='0'; q=2; i++; break; }
            case 2: { cout<<a<<endl; a[i]='1'; q=3; break; }
            case 3: { cout<<a<<endl; a[i]='0'; q=4; i--; break; }
            case 4: { cout<<a<<endl; a[i]='0'; q=6; i--; break; }
            case 5: { cout<<a<<endl; a[i]='0'; q=0; break; }    
            }
        }
        else if (a[i]=='1')
        {
            switch(q)
            {
            case 1: { cout<<a<<endl; a[i]='1'; q=3; i++; break; }
            case 2: { cout<<a<<endl; a[i]='0'; q=5; break;}
            case 3: { cout<<a<<endl; a[i]='1'; q=6; i--; break; }
            }
        }
    }
    cout << "\nVihidne slovo: "<<a;
getch();
}
Машина Тьюринга. Перенос нуля. Реализировать на С++

Не работает, исправьте, кто может...
doctor_lecter
 Аватар для doctor_lecter
279 / 152 / 8
Регистрация: 22.09.2012
Сообщений: 283
24.10.2012, 23:48     Машина Тьюринга. Перенос нуля. Реализировать на С++ #3
Не очень понял что у вас в задании. Могу привести пример примитивной реализации машины Тьюринга, вы для нее можете попробовать задать правила для своего задания. На этом примере я реализовал машину Тьюринга, которая заменяет 0 на 1 и наоборот. Могут быть баги, сделал только что и тестил только на этом примере:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
 
using namespace std;
 
struct rule {
    char input;     // Входной символ '\0' - последний
    char state;     // Состояние. 'S' - начальное. 'Q' - завершение работы
    char output;    // Выходной символ
    char newState;  // Новое состояние
    char dir;       // Направление движения. 'L', 'R' - налево и направо соответственно. 'N' - не двигаться
};
 
bool turing(
    char* arr,      // Входная лента. Для простоты пусть будет конечной длины
    int len,        // Длина ленты
    rule* rules,    // Список правил
    int num         // Количество правил
) {
    int pos = 0;    // Положение ленты
    char st = 'S';  // Текущее состояние
    while (true) {
        char c = arr[pos];
        int i;
        for (i=0; i < num; ++i) {
            if ((rules[i].input==c) && (rules[i].state == st))
                break;
            else
                if (i == num-1) {
                    cout << "Не найдено правила для символа " << c << " при состоянии " << st << endl;
                    return false;
                }
        }
        arr[pos] = rules[i].output;
        st = rules[i].newState;
        switch (rules[i].dir) {
        case 'L':
            --pos;
            if (pos < 0) {
                cout << "Выход за пределы ленты слева" << endl;
                return false;
            }
            break;
        case 'R':
            ++pos;
            if (pos >= len) {
                cout << "Выход за пределы ленты справа" << endl;
                return false;
            }
            break;
        case 'N':
            break;
        default:
            cout << "Неопределенное направление" << endl;
            return false;
        }
        if (st == 'Q')
            return true;
    }
    return false;
}
 
int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 3;
    rule rules[3];
    rules[0].input = '0';
    rules[0].state = 'S';
    rules[0].output = '1';
    rules[0].newState = 'S';
    rules[0].dir = 'R';
    rules[1].input = '1';
    rules[1].state = 'S';
    rules[1].output = '0';
    rules[1].newState = 'S';
    rules[1].dir = 'R';
    rules[2].input = '\0';
    rules[2].state = 'S';
    rules[2].output = '\0';
    rules[2].newState = 'Q';
    rules[2].dir = 'N';
 
    const int size = 6;
    char test[6] = {'1', '0', '0', '1', '1', '\0'};
 
    cout << "Входная лента:";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента: ";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        return 0;
    } else {
        cout << endl << "Ошибка" << endl;
        return 1;
    }
}
Asuser
0 / 0 / 0
Регистрация: 22.10.2012
Сообщений: 18
25.10.2012, 11:03  [ТС]     Машина Тьюринга. Перенос нуля. Реализировать на С++ #4
doctor_lecter, нужен перенос нуля. Например ввели слово 0010, после обработки командами МТ на выходе имеем 0100. Было 0111100, стало 0011110. Вот впринципе и все
Дело в том, что тот набор команд 100% правильный (во втором посте), наверняка закодил неправильно...
doctor_lecter
 Аватар для doctor_lecter
279 / 152 / 8
Регистрация: 22.09.2012
Сообщений: 283
25.10.2012, 11:30     Машина Тьюринга. Перенос нуля. Реализировать на С++ #5
Обычно набор команд МТ имеет вид: Входной символ|состояние -> Выходной символ|Состояние|Направление, а у вас после -> идет Состояние и Либо выходной символ, либо направление. Это в принципе тоже правильно, просто получится менее компактно.

Я правильно понял что входное слово имеет такой вид: 000001..{тут не может быть 0}...10000

Тогда функцию main можно написать так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 7;
    rule rules[ruleNum];
 
    rules[0].input = '0';
    rules[0].state = 'S';
    rules[0].output = '0';
    rules[0].newState = 'A';
    rules[0].dir = 'N';
 
    rules[1].input = '0';
    rules[1].state = 'A';
    rules[1].output = '0';
    rules[1].newState = 'A';
    rules[1].dir = 'R';
 
    rules[2].input = '1';
    rules[2].state = 'A';
    rules[2].output = '1';
    rules[2].newState = 'B';
    rules[2].dir = 'L';
 
    rules[3].input = '0';
    rules[3].state = 'B';
    rules[3].output = '1';
    rules[3].newState = 'C';
    rules[3].dir = 'R';
 
    rules[4].input = '1';
    rules[4].state = 'C';
    rules[4].output = '1';
    rules[4].newState = 'C';
    rules[4].dir = 'R';
 
    rules[5].input = '0';
    rules[5].state = 'C';
    rules[5].output = '0';
    rules[5].newState = 'D';
    rules[5].dir = 'L';
 
    rules[6].input = '1';
    rules[6].state = 'D';
    rules[6].output = '0';
    rules[6].newState = 'Q';
    rules[6].dir = 'N';
 
    const int size = 10;
    char test[size] = {'0', '0', '0', '1', '1', '0', '\0', '\0', '\0', '\0'};
 
    cout << "Входная лента: ";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента:";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        return 0;
    } else {
        cout << "Ошибка" << endl;
        return 1;
    }
}
Это вариант отработает и на входных данных вида 00011010, на выходе будет 00110010, т.е будет перенесен только 0 у первой последовательности 1
kira_1
0 / 0 / 0
Регистрация: 16.11.2013
Сообщений: 59
02.06.2014, 21:26     Машина Тьюринга. Перенос нуля. Реализировать на С++ #6
Подскажите, пожалуйста, в чем ошибка. По этому примеру сделала МТ, которая выполняет умножение 2 чисел в унарной системе. Пишет, что для определенного символа правила, а по алфавиту все правильно введено.

Вот алфавит:

q0*→q0R q4a→q4aR
q01→q0R q4=→q4=R
q0×→q1×R q41→q41R
q11→q2aR q4*→q51R
q21→q21L q5*→q2*L
q2a→q2aL q6a→q61R
q2=→q2=L q6×→q7×R
q2×→q3×L q7a→q7aR
q31 → q4aR q71→q2aR
q3a→q3aL q7=→q8=L
q3*→q6*R q8a→q81L
q4×→q4×R q8×→q9H


А вот код программы:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include <iostream>
 
using namespace std;
#include <conio.h>;
struct rule {
    char input;     // Входной символ '\0' - последний
    char state;     // Состояние. 'S' - начальное. 'Q' - завершение работы
    char output;    // Выходной символ
    char newState;  // Новое состояние
    char dir;       // Направление движения. 'L', 'R' - налево и направо соответственно. 'N' - не двигаться
};
 
bool turing(
    char* arr,      // Входная лента. Для простоты пусть будет конечной длины
    int len,        // Длина ленты
    rule* rules,    // Список правил
    int num         // Количество правил
) {
    int pos = 0;    // Положение ленты
    char st = 'A';  // Текущее состояние
    while (true) {
        char c = arr[pos];
        int i;
        for (i=0; i < num; ++i) {
            if ((rules[i].input==c) && (rules[i].state == st))
                break;
            
            else
                if (i == num-1) {
                    cout << "Не найдено правила для символа " << c << " при состоянии " << st << endl;
                    return false;
                }
 
        }
        arr[pos] = rules[i].output;
        st = rules[i].newState;
        switch (rules[i].dir) {
        case 'L':
            --pos;
            if (pos < 0) {
                cout << "Выход за пределы ленты слева" << endl;
                return false;
            }
            break;
        case 'R':
            ++pos;
            if (pos >= len) {
                cout << "Выход за пределы ленты справа" << endl;
                return false;
            }
            break;
        case 'N':
            break;
        default:
            cout << "Неопределенное направление" << endl;
            return false;
        }
        if (st == 'Q')
            return true;
    }
    return false;
}
int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 24;
    rule rules[ruleNum];
 
    rules[0].input = '*';
    rules[0].state = 'A';
    rules[0].newState = 'A';
    rules[0].dir = 'R';
 
    rules[1].input = '1';
    rules[1].state = 'A';
    rules[1].newState = 'A';
    rules[1].dir = 'R';
 
    rules[2].input = 'x';
    rules[2].state = 'A';
    rules[2].output = 'x';
    rules[2].newState = 'B';
    rules[2].dir = 'R';
 
    rules[3].input = '1';
    rules[3].state = 'B';
    rules[3].output = 'a';
    rules[3].newState = 'C';
    rules[3].dir = 'R';
 
    rules[4].input = '1';
    rules[4].state = 'C';
    rules[4].output = '1';
    rules[4].newState = 'C';
    rules[4].dir = 'L';
 
    rules[5].input = 'a';
    rules[5].state = 'C';
    rules[5].output = 'a';
    rules[5].newState = 'C';
    rules[5].dir = 'L';
 
    rules[6].input = '=';
    rules[6].state = 'C';
    rules[6].output = '=';
    rules[6].newState = 'C';
    rules[6].dir = 'L';
 
    rules[7].input = 'x';
    rules[7].state = 'C';
    rules[7].output = 'x';
    rules[7].newState = 'D';
    rules[7].dir = 'L';
 
    rules[8].input = '1';
    rules[8].state = 'D';
    rules[8].output = 'a';
    rules[8].newState = 'E';
    rules[8].dir = 'R';
 
    rules[9].input = 'a';
    rules[9].state = 'D';
    rules[9].output = 'a';
    rules[9].newState = 'D';
    rules[9].dir = 'L';
 
    rules[10].input = '*';
    rules[10].state = 'D';
    rules[10].output = '*';
    rules[10].newState = 'J';
    rules[10].dir = 'R';
 
    rules[11].input = 'x';
    rules[11].state = 'E';
    rules[11].output = 'x';
    rules[11].newState = 'E';
    rules[11].dir = 'R';
 
    rules[12].input = 'a';
    rules[12].state = 'E';
    rules[12].output = 'a';
    rules[12].newState = 'E';
    rules[12].dir = 'R';
 
    rules[13].input = '=';
    rules[13].state = 'E';
    rules[13].output = '=';
    rules[13].newState = 'E';
    rules[13].dir = 'R';
 
    rules[14].input = '1';
    rules[14].state = 'E';
    rules[14].output = '1';
    rules[14].newState = 'E';
    rules[14].dir = 'R';
 
    rules[15].input = '*';
    rules[15].state = 'E';
    rules[15].output = '1';
    rules[15].newState = 'F';
    rules[15].dir = 'R';
 
    rules[16].input = '*';
    rules[16].state = 'F';
    rules[16].output = '*';
    rules[16].newState = 'C';
    rules[16].dir = 'L';
 
    rules[17].input = 'a';
    rules[17].state = 'J';
    rules[17].output = '1';
    rules[17].newState = 'J';
    rules[17].dir = 'R';
 
    rules[18].input = 'x';
    rules[18].state = 'H';
    rules[18].output = 'x';
    rules[18].newState = 'I';
    rules[18].dir = 'R';
 
    rules[19].input = 'a';
    rules[19].state = 'H';
    rules[19].output = 'a';
    rules[19].newState = 'H';
    rules[19].dir = 'R';
 
    rules[20].input = '1';
    rules[20].state = 'H';
    rules[20].output = 'a';
    rules[20].newState = 'C';
    rules[20].dir = 'R';
 
    rules[21].input = '=';
    rules[21].state = 'H';
    rules[21].output = '=';
    rules[21].newState = 'I';
    rules[21].dir = 'L';
 
    rules[22].input = 'a';
    rules[22].state = 'I';
    rules[22].output = '1';
    rules[22].newState = 'I';
    rules[22].dir = 'L';
 
    rules[23].input = 'x';
    rules[23].state = 'I';  
    rules[23].newState = 'Q';
    rules[23].dir = 'N';
 
 
    const int size = 8;
    char test[size] = {'*', '1', '1', '1', 'x', '1', '1', '*'};
 
    cout << "Входная лента: ";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента:";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        getch();
        return 0;
    } else {
        cout << "Ошибка" << endl;
            getch();
        return 1;
    }
}
Yandex
Объявления
02.06.2014, 21:26     Машина Тьюринга. Перенос нуля. Реализировать на С++
Ответ Создать тему
Опции темы

Текущее время: 09:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru