Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.58
ReM
4 / 4 / 0
Регистрация: 18.09.2008
Сообщений: 45
#1

Машина Тьюринга. (Динамический массив)) - C++

19.05.2009, 11:07. Просмотров 1681. Ответов 3
Метки нет (Все метки)

Написал машину Тьюринга для умножения трех натуральных чисел:
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
230
231
232
233
234
235
236
237
238
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <dos.h>
#include <alloc.h>
#include <stdlib.h>
char *r;
 
// Начало программы
void main(){
// Исходные данные - 3 числа
int a,b,c,dl_len;
 
// Текущее состояние и текущий просматриваемый символ на ленте
int state,index;
// счетчик цикла
int i,rez;
clrscr();
// Ввод исходных данных
printf("a= ");
scanf("%d",&a);
printf("b= ");
scanf("%d",&b);
printf("c= ");
scanf("%d",&c);
if((a<0)||(b<0)||(c<0))
{
    printf("Одно или несколько чисел отрицательное(ые) - не натуральное(ые)");
}
else
{
if((a!=0)&(b!=0)&(c!=0))
{
    dl_len=a*b*c+a+b+c+7;
    r=(char*)malloc(dl_len*sizeof(char));
    if (r == NULL)
    {
        printf("Маловато памяти!\n");
        getch();
        exit(1);
    }
    //Заполенение ленты
 
    for (i=0;i<dl_len;i++) //елси в место этой строки, допустим, поставить - for (i=0;i<200;i++), то все ok...
        {*(r+i)='_';}
 
    for (i=0;i<a;i++)
        {r[i]='1';}
 
    for (i=a+1;i<a+1+b;i++)
        {r[i]='1';}
 
    for (i=a+b+2;i<a+b+2+c;i++)
        {r[i]='1';}
 
    printf("Исходное состояние ленты: ");
    for (i=0;i<=a+b+2+c;i++)
        {printf("%c",r[i]);}
 
    // Инициализация начальных значений
    state=0;
    index=0;
    rez=0;
    // Главный цикл программы. Выполняется пока не достигнуто конечное состояние
    while (state!=-1){
    switch (state) {
     case 0: {if (r[index]=='1') {r[index]='a';state=1;index++; break;}
          if (r[index]=='_') {r[index]='_';state=13;index++; break;}
      //Отмечаем цифру первого числа для инициализации итерации умножения
          } break;
      case 1: {if (r[index]=='1') {r[index]='1';state=1;index++;break;}
           if (r[index]=='_') {r[index]='_';state=2;index++;break;}
      // ищем второе число
          } break;
      case 2: {if (r[index]=='1') {r[index]='b';state=3;index++;}
      //помечаем начало второго числа
          }  break;
      case 3: {if (r[index]=='1') {r[index]='1';state=3;index++;break;}
           if (r[index]=='b') {r[index]='b';state=3;index++;break;}
           if (r[index]=='_') {r[index]='_';state=4;index++;break;}
      // отмечаем цифру второго числа, для инициализации цикла по второму числу
          } break;
      case 4: {if (r[index]=='1') {r[index]='c';state=5;index++;break;}
           if (r[index]=='c') {r[index]='c';state=5;index++;break;}
      // помечаем третье число
          }  break;
      case 5: {if (r[index]=='1') {r[index]='1';state=5;index++;
              break;}
           if (r[index]=='y') {r[index]='y';state=5;index++;
              break;}
           if (r[index]=='_') {r[index]='y';state=6;index--;}
    //  Дописываем y в конец результата умножения a*b
          }  break;
      case 6: {if (r[index]=='1') {r[index]='1';state=7;index--;
              break;}
           if (r[index]=='c') {r[index]='c';state=8;index--;
              break;}
           if (r[index]=='y') {r[index]='y';state=6;index--;}
    // возврщаемся ко второму числу
          }  break;
      case 7: {if (r[index]=='1') {r[index]='1';state=7;index--;
              break;}
           if (r[index]=='c') {r[index]='c';state=8;index--;}
    // пропускаем третье число
          }  break;
      case 8: {if (r[index]=='_') {r[index]='_';state=9;index--;}
    //промежуток между вторым и третьим числом
          }  break;
      case 9: {if (r[index]=='1') {r[index]='b';state=3;index++;
              break;}
           if (r[index]=='b') {r[index]='b';state=9;index--;
              break;}
           if (r[index]=='_') {r[index]='_';state=10;index++;}
    // отмечаем следующую цифру второго числа
          }  break;
      case 10: {if (r[index]=='b') {r[index]='1';state=10;index++;
         break;}
            if (r[index]=='_') {r[index]='_';state=11;index--;}
    // снимаем отметки со второо числа
          }  break;
      case 11: {if (r[index]=='1') {r[index]='1';state=11;index--;
               break;}
            if (r[index]=='_') {r[index]='_';state=12;index--;}
            // идем к первосму числу
          }  break;
      case 12: {if (r[index]=='1') {r[index]='1';state=12;index--;
               break;}
            if (r[index]=='a') {r[index]='a';state=0;index++;}
    // отмечаем следующую цифру второго числа и стартуем новую итерацию по числу a
          }  break;
      case 13: {if (r[index]=='1') {r[index]='1';state=13;index++;
               break;}
            if (r[index]=='_') {r[index]='_';state=14;index++;}
    // в первом числе кончились цифры
          }  break;
      case 14: {if (r[index]=='c') {r[index]='c';state=15;index++;}
    // начало третьего числа
          }  break;
      case 15: {if (r[index]=='1') {r[index]='1';state=15;index++;
               break;}
            if (r[index]=='y') {r[index]='_';state=16;index++;}
    // вставляем побел между c и a*b
          }  break;
      case 16: {if (r[index]=='y') {r[index]='y';state=16;index++;
               break;}
            if (r[index]=='_') {r[index]='1';state=17;index--;}
    //ищем конец a*b
          }  break;
      case 17: {if (r[index]=='y') {r[index]='1';state=17;index--;
               break;}
            if (r[index]=='_') {r[index]='_';state=18;index--;}
    // дописывем y в конец a*b взамен удаленного в состоянии 15
          }  break;
      case 18: {if (r[index]=='1') {r[index]='1';state=18;index--;
               break;}
            if (r[index]=='c') {r[index]='1';state=19;index--;}
    //в начало третьего числа ставим 1
          }  break;
      case 19: {if (r[index]=='_') {r[index]='_';state=20;index++;}
    //пробел между вторым и третьим числом
          }  break;
      case 20: {if (r[index]=='1') {r[index]='a';state=21;index++;
               break;}
            if (r[index]=='_') {r[index]='_';state=28;index++;}
    // старт умножения с на a*b
          }  break;
      case 21: {if (r[index]=='1') {r[index]='1';state=21;index++;
               break;}
            if (r[index]=='_') {r[index]='_';state=22;index++;}
    //проходим к a*b
          }  break;
      case 22: {if (r[index]=='1') {r[index]='b';state=23;index++;}
    // помечаем первую цифру a*b
          }  break;
      case 23: {if (r[index]=='1') {r[index]='1';state=23;index++;
              break;}
           if (r[index]=='b') {r[index]='b';state=23;index++;
              break;}
           if (r[index]=='y') {r[index]='y';state=23;index++;
              break;}
           if (r[index]=='_') {r[index]='y';state=24;index--;}
    // последовательно помечаем цифры числа a*b
          }  break;
      case 24: {if (r[index]=='1') {r[index]='b';state=23;index++;
              break;}
           if (r[index]=='b') {r[index]='b';state=24;index--;
              break;}
           if (r[index]=='y') {r[index]='y';state=24;index--;
              break;}
           if (r[index]=='_') {r[index]='_';state=25;index++;}
    // формируем результат a*b*c
          }  break;
      case 25: {if (r[index]=='b') {r[index]='1';state=25;index++;
               break;}
            if (r[index]=='y') {r[index]='y';state=26;index--;}
    // в числе a*b помечены все цифры
          }  break;
      case 26: {if (r[index]=='1') {r[index]='1';state=26;index--;
               break;}
            if (r[index]=='_') {r[index]='_';state=27;index--;}
    // заменяем все b на 1
          }  break;
      case 27: {if (r[index]=='1') {r[index]='1';state=27;index--;
               break;}
            if (r[index]=='a') {r[index]='a';state=20;index++;}
    // старт новой итерации по числу c
          }  break;
      case 28: {if (r[index]=='1') {r[index]='1';state=28;index++;
               break;}
            if (r[index]=='y') {rez=index; r[index]='_';state=29;index++;}
    //вставляем пробел между a*b и a*b*c
          }  break;
      case 29: {if (r[index]=='y') {r[index]='y';state=29;index++;
               break;}
            if (r[index]=='_') {r[index]='y';state=30;index--;}
          }  break;
    //записываем y в конец резуьтата и останов.
      case 30: {if (r[index]=='y') {r[index]='y'; state=30;index--;}
            if (r[index]=='_') {r[index]='_'; state=31;index++;}
          }  break;
      case 31: {if (r[index]=='y') {r[index]='1'; state=31;index++;}
            if (r[index]=='_') {r[index]='_'; state=-1;}
          }  break;
 
      default:         printf("Ошибка!\n");
    }
    }
    printf("\nРезультат умножения трехчисел: ");
    for (i=rez+1;i<=index-1;i++)
    {printf("%c",r[i]);}
}
else
{
    printf("\n Одно или несколько чисел =0, результат будет = 0!!!");
}
}
getch();
}
Если в строке 44 указана переменная dl_len то программа во время работы виснет, но если вместо этой переменной ввести конкретное число, то все работает нормально... Пробовал сам решить данную проблему, но увы без успешно.
В чем проблема, как избавиться от нее?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2009, 11:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Машина Тьюринга. (Динамический массив)) (C++):

Машина Тьюринга - C++
Помогите пожалуйста с задачей на машине Тьюринга: дано три числа в двоичной системе а, в,с , нужно проверить можно ли составить триугольник...

Машина Тьюринга - C++
Доброго времени суток. У меня возникла проблема с выводом после = строки. #include &quot;stdafx.h&quot; #include &lt;string&gt; #include...

Машина тьюринга на с++ - C++
Мне нужно реализовать на С++ машину Тьюринга, которая выполняет деление целых чисел m и n. Подскажите, пожалуйста, любые примеры реализации...

Машина Тьюринга - C++
Дана последовательность символов двух видов a, b. Построить машину Тьюринга, которая заменяет символ a на символ c и подсчитывает число...

Машина Тьюринга - C++
Всем доброго времен суток! Ребятки, паника.. На 1 курсе препод дал работу на С++ - смоделировать универсальную машину Тьюринга, с...

Машина Тьюринга - C++
Построить МТ, удваивающую число на ленте (п-р 01110 --&gt; 01111110) (не программу, а просто таблицу:)) ответ должен быть в таком виде...

3
kazak
3048 / 2369 / 160
Регистрация: 11.03.2009
Сообщений: 5,436
Завершенные тесты: 1
19.05.2009, 13:31 #2
Поставь бряк на эту строку и посмотри каке значение имеет dl_len.

Добавлено через 1 час 20 минут 43 секунды
Смотри цикл while, зацикливание в нем происходит.

Добавлено через 39 минут 20 секунд
Смотрел при a = 2, b = 2, c = 2 - в итоге зацикливается на case 29: state = 29, index = 21?!(хотя при этом dl_len =21, те допустимые значения index для r[index] 0 - 20) в итоге маловероятно, что r[21] будет содержать 'y' или '_', а значит изменение state и index происходить не будет.
1
ReM
4 / 4 / 0
Регистрация: 18.09.2008
Сообщений: 45
19.05.2009, 16:39  [ТС] #3
Да, действительно... Проблема оказалась в 34 строке (dl_len=a*b*c+a+b+c+7, длина ленты должна задаваться - dl_len=a*b*c+a*b+c+5.
Попутно возник еще вопрос... Чему будет равна максимальна длинна массива? как проверить?
ЗЫ: 2kazak спасибо.
0
ReM
4 / 4 / 0
Регистрация: 18.09.2008
Сообщений: 45
24.05.2009, 18:52  [ТС] #4
Возник такой вопрос:
В целом программа работает нормально, но если ввести к примеру все числа равные 100, то программа повисает. Пытался сам разобраться, но увы без успешно. Какие тут могут быть причины и как их можно исправить?
0
24.05.2009, 18:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2009, 18:52
Привет! Вот еще темы с ответами:

Реализовать код машина Тьюринга - C++
Ребят, нужна помощь/консультация нужно написать код машины тьюринга, должна вводиться строка из 0 или 1, вводиться команды и выдавать...

Расшифровка алгоритмов в коде(Машина Тьюринга) - C++
Всем привет! Есть код программы, имитирующий машину Тьюринга. Помогите разобраться в ней. Можете подсказать для чего здесь используемые в...

Машина Тьюринга. Перенос нуля. Реализировать на С++ - C++
Приветствую! Я в С++ очень плохо разбираюсь, но нужна программа... Буду рад всем откликнувшимся.

Машина Тьюринга: не хватает одного IF в программе - C++
Добрый день. Программа считывает вводимый мной файл (1.txt, 2.txt, 3.txt, 4.txt). Считываются положение головки, самой полосы данных и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru