Member 14004777 Ответов: 3

Не знаю, как перевести идею на язык C++


Привет, ребята. Моя программа нуждается в модификации.

На самом деле это универсальная машина Тьюринга, и моя цель-сделать ее параллельной.

Параллельная машина Тьюринга выполняет инструкции от 1.txt к своей ленте и печатает ее только с одним шагом изменений (это важно!), позже он делает то же самое с 2.txt, 3.txt и еще 4.txt-да. После этого машина повторяет эти операции с условием, что если одна лента сделана (остановлена), то другие не остановятся, пока не будет сказано в инструкции.
Итак, параллельная машина печатает шаг за шагом измененные по выполненным инструкциям ленты:
1.txt 1-е изменение
2.txt 1-е изменение
3.txt 1-е изменение
4.txt 1-е изменение
1.txt 2-е изменение
2.txt 2-е изменение
...
У меня есть несколько идей, но я не знаю, как перевести их на C++:
Создайте вектор класса машины, по одному для каждого входа, а затем на каждом шаге пройдите через весь список машин и, если не end_of_tape, вызовите execute.

Не мог бы кто-нибудь помочь мне и перевести его?

Что я уже пробовал:

#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iterator>
using namespace std;
struct instruction {
    string current_state;
    char current_char;
    char next_char;
    int move;
    string next_state;
};
 
    istream& operator>>(istream& is, instruction& i) {
    is >> i.current_state >> i.current_char >> i.next_char;
    char move_ch; is >> move_ch;
    if(move_ch == 'R') i.move = 1;
    else if(move_ch == 'L') i.move = -1;
    else i.move = 0;
    return is >> i.next_state;
}
 
struct machine {
    int position;
    string state;
    string tape;
    bool execute(const instruction &i);
    bool end_of_tape() const {
        return position < 0 || position > tape.size();
    }
};
 
bool machine::execute(const instruction &i) {
    if(i.current_state != state || tape[position] != i.current_char) return false;
    state = i.next_state;
    tape[position] = i.next_char;
    position += i.move;
    return true;
}
 
    istream & operator>>(istream &is, machine &m) {
    m.state = "0";
    is >> m.position;
    return is >> m.tape;
}
 
int main() {
    string filename;
    cout << "Enter filename: ";
    cin >> filename;
    ifstream ifs(filename, ifstream::in);
    machine m;
    ifs >> m;
    vector<instruction> program;
    copy(istream_iterator<instruction>(ifs),
        istream_iterator<instruction>(),
        back_inserter(program));
    for(size_t i = 0; !m.end_of_tape() && i < program.size();) {
        if (m.execute(program[i])) i = 0;
        else i++;
        cout << m.tape << endl;
    }
        cout << "HALT!";
 
    return 0;
}

3 Ответов

Рейтинг:
1

CPallini

Что не так с функцией

execute( int machine, int instruction)

и петля вроде
for (i=0; i<max_program_size; ++i)
  for (m=0; m<machines; ++m)
     execute(m,i);
?


Рейтинг:
0

KarstenK

Ваша концепция-это не верхушка вашей задачи.

Вам нужен только класс машины с флагом выполнения, буфером инструкций (вектором) и командой выполнения.

class Machine
{
 bool running;
 vector <instruction> instructions;
 bool loadInstructions(string file);
 bool execute();//pop or you need a counter
};

Эти машины могут быть добавлены после создания в вектор, который затем зацикливается для выполнения.

Сделайте некоторые выходные данные и используйте отладчик.


Rick York

Судя по всему, унивотер сегодня просто взбесился. По-видимому, у них очень низкая репутация, так как мои 5 Теперь набрали 4,56 балла. :)

Рейтинг:
0

Rick York

Чтобы сделать алгоритм параллельным, я бы изучил использование OpenMP. Он очень прост в использовании, так как требуется всего несколько прагм, чтобы сделать код параллельным. Вам просто нужно решить, какие переменные являются общими и частными для каждого потока, и "пометить" их соответствующим образом в прагме.

Вот полезное введение в OpenMP : OpenMP Hands-on[^]