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

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

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

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

19.05.2009, 11:07. Просмотров 1642. Ответов 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 то программа во время работы виснет, но если вместо этой переменной ввести конкретное число, то все работает нормально... Пробовал сам решить данную проблему, но увы без успешно.
В чем проблема, как избавиться от нее?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.05.2009, 11:07     Машина Тьюринга. (Динамический массив))
Посмотрите здесь:

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

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

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kazak
3034 / 2355 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
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 происходить не будет.
ReM
3 / 3 / 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 спасибо.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.05.2009, 18:52     Машина Тьюринга. (Динамический массив))
Еще ссылки по теме:

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

Машина Тьюринга. Выводит неправильный ответ - C++
Пишу машину Тьюринга для разных команд, в конце выводит неправильный результат, что не так? Список команд: 0q1-&gt;0q1R 1q1-&gt;0q2R ...

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

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

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

Динамический массив - C++
Народ прошу помочь написать задачу ибо завтра нада сдавать.Вот усливия : Сформировать одномерный динамический массив целых чисел.Из...


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

Или воспользуйтесь поиском по форуму:
ReM
3 / 3 / 0
Регистрация: 18.09.2008
Сообщений: 45
24.05.2009, 18:52  [ТС]     Машина Тьюринга. (Динамический массив)) #4
Возник такой вопрос:
В целом программа работает нормально, но если ввести к примеру все числа равные 100, то программа повисает. Пытался сам разобраться, но увы без успешно. Какие тут могут быть причины и как их можно исправить?
Yandex
Объявления
24.05.2009, 18:52     Машина Тьюринга. (Динамический массив))
Ответ Создать тему
Опции темы

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