Правильно ли мое решение LC3 для нахождения длины возрастающей последовательности?

Меня просят создать программу на LC3, которая распознает максимальную длину возрастающей подпоследовательности в последовательности чисел.

Ex. {1,2,3,5,2,2,4,5,6,8,3,4}

решение: максимальная возрастающая подпоследовательность: {2,2,4,5,6,8} , максимальная длина возрастающей подпоследовательности: 6

Для этого меня попросили создать подпрограмму с именем MAX_LEN, которая вычисляет max(x,y) двух чисел x,y и имеет входные данные x,y в R2,R5 и должна выдавать результат: max(x,y) в Р5. Также я должен использовать другой INC_SUB_LEN, который вычисляет длину первой возрастающей подпоследовательности с заданного адреса. Входной адрес — R0, а выходная длина должна быть в R2. Максимальная длина пока в R5. Я также должен использовать подпрограмму MAX_LEN. Большая последовательность, из которой мы будем находить подпоследовательности, хранится в адресе DATA, а ее длина — в адресе LENGTH. Мне также даются команды в конце LENGTH .FILL x5000 и DATA .FILL x5001.

Я новичок в программировании LC3, поэтому я написал свою программу на бумаге. Может ли кто-нибудь найти какие-либо ошибки в моем решении? если да, то как я могу их исправить??

Мое решение:

.ORIG x3000
LD R0,DATA
LD R1,DATA
LOOP1 JSR INC_SUB_LEN
ADD R1,R1,#1
LD R4,LENGTH
NOT R4,R4
ADD R4,R4,#1
ADD R3,R1,R4
BRn LOOP1

INC_SUB_LEN 
LOOP ADD R2,R2,#1 
ADD R4,R0,#0
LDR R6,R0,#1
LDR R0,R0,#1
NOT R6,R6
ADD R6,R6,#1
ADD R7,R4,R6
BRnz LOOP
JSR MAX_LEN
RET

MAX_LEN 
NOT R5, R5
ADD R5, R5, #1
ADD R3,R2,R5
BRnz ELSE
ADD R5,R2,#0
NOT R5,R5
ADD R5,R5,#1
ELSE NOT R5,R5
ADD R5,R5,#1
RET


LENGTH .FILL x5000
DATA .FILL x5001
.END

person Community    schedule 21.08.2018    source источник
comment
скопируйте/вставьте свой код в блок форматирования кода. Вы написали это на бумаге? Так что введите его и запустите в симуляторе LC3, и посмотрите, работает ли он! Выполните один шаг, чтобы убедиться, что он работает так, как вы ожидаете. (Может быть, вы также разделите свой большой абзац на несколько абзацев или маркеров. Описывать код на английском — это очень хорошо, поэтому я на самом деле не голосовал против, но см. idownvotedbecau.se/imagesofcode.)   -  person Peter Cordes    schedule 21.08.2018
comment
@PeterCordes У меня действительно были проблемы с вводом кода в симуляторе LC3, потому что меня просят хранить ответы в регистрах, и я точно не знаю, как их распечатать. Я также получил много ошибок, из которых я не знал, что было виновато. Так что проще было написать это на бумаге как какой-нибудь псевдокод. Всё равно спасибо :D   -  person    schedule 21.08.2018
comment
Должна ли возрастающая последовательность начинаться с первого элемента (так что вам просто нужно найти первый невозрастающий шаг) или вам нужно найти самую длинную возрастающую последовательность из всего массива?   -  person Peter Cordes    schedule 21.08.2018
comment
Не пишите код для печати регистров, просто посмотрите на них с помощью отладчика. В этом смысл наличия отладчика, а не простого эмулятора, который может запускать только вашу программу.   -  person Peter Cordes    schedule 21.08.2018
comment
@PeterCordes нет, не обязательно начинать с первого элемента. В примере, который я привел вначале, ответ начинается с 5-го элемента.   -  person    schedule 21.08.2018
comment
Ok. Я думал, что это будет намного сложнее, но кандидаты не могут пересекаться, так что нет необходимости в серьезных отступлениях. Просто сравнивайте и обновляйте самый длинный регистр каждый раз, когда вы доходите до конца возрастающей последовательности. (Но это означает, что вы также должны проверять конец массива в качестве дополнительного условия завершения цикла.)   -  person Peter Cordes    schedule 21.08.2018
comment
@PeterCordes, если бы я написал это на С++, я мог бы заставить его работать довольно быстро. Просто с LC3 сложнее заставить работать логику, поэтому я беспокоюсь, что у меня много ошибок в коде. Я знаю, что это трудно увидеть на бумаге, но если бы вы могли взглянуть на это, это было бы здорово :D.   -  person    schedule 21.08.2018
comment
Я не думаю, что разумно просить других людей отладить ваш код, если вы даже не пытались запустить его самостоятельно. Если у вас возникли проблемы с синтаксическими ошибками или что-то в этом роде, погуглите сообщения об ошибках и (если вы застряли) задайте вопрос об этом, потому что вам придется разобраться с этим в какой-то момент. Затем вы можете вернуться к этому вопросу и обновить его с помощью действительного действительного кода LC3, который вы пробовали. И вы либо думаете, что это работает для ваших тестовых случаев, либо вы застряли на какой-то конкретной ошибке, которую вы не знаете, как решить.   -  person Peter Cordes    schedule 21.08.2018
comment
В настоящее время это похоже на вопрос codereview.stackexchange.com (который не относится к теме SO, см. Как спросить; это слишком широко), за исключением того, что вы не выполнили их минимальный стандарт наличия программы, которую вы тестировали и считаете без ошибок.   -  person Peter Cordes    schedule 21.08.2018
comment
И кстати, если вы знаете, как написать это на C++, вы можете сделать это и скомпилировать (с включенной оптимизацией) для ARM или что-то в этом роде, на godbolt.org и посмотрите на получившийся ассемблер, чтобы увидеть, как компилятор реализует логику. Может быть, MIPS, если вы используете -O3 -fno-delayed-branch, чтобы ориентироваться на простую ISA с простыми режимами адресации, такими как LC3. Или, может быть, MSP430, 16-битный ISA. Кроме того, код в вашем вопросе довольно легкий для комментариев. Обычно вы хотите хотя бы описать, для чего используется каждый регистр.   -  person Peter Cordes    schedule 21.08.2018
comment
@PeterCordes Я написал код на симуляторе и протестировал подпрограмму, которая находит максимальное значение . Однако я не могу проверить остальную часть кода, потому что не знаю, как вставить начальную последовательность чисел. Я собираюсь отредактировать сообщение, чтобы добавить код. Не могли бы вы помочь мне?   -  person    schedule 21.08.2018
comment
Согласно cs.colostate.edu/~fsieker/misc/CtoLC3.html, псевдоинструкция LC3 для инициализированных данных — .fill. Я не знаю, можете ли вы написать .fill 1, 2, 3 ... или вам придется использовать отдельный .fill для каждой записи массива, например .fill 1 / .fill 2 / .fill 3 в отдельных строках. (Возможно, вы захотите использовать имя метки, отличное от data, для начала массива, если это специально для LC3, например, раздел данных или что-то в этом роде.)   -  person Peter Cordes    schedule 21.08.2018
comment
@PeterCordes Что мне нужно написать перед .fill? Я знаю только то, что числа начинаются с x5001. При сборке я также получаю ошибку Unrecognized opcode или синтаксическую ошибку в LOOP или перед ним.   -  person    schedule 21.08.2018
comment
В первой строке просто метка, такая как my_array:, чтобы вы могли ссылаться на это место с помощью символического имени, а не по адресу. Насколько я знаю, вы можете размещать данные где угодно, они не обязательно должны начинаться с .org 0x5001. Данные и код — всего лишь байты в памяти. Что-то вроде my_array .FILL #1, затем на следующей строке .fill #2. (вам может понадобиться # перед числовыми литералами, которые я пропустил. Во всяком случае, это то, что показал первый поиск в Google. Я не знаю всех деталей синтаксиса LC3; это всего лишь одна из многих архитектур, о которых я смутно знаю. Это лучше, чем большинство игрушечных арок.   -  person Peter Cordes    schedule 21.08.2018


Ответы (1)


Существует веб-симулятор: https://wchargin.github.io/lc3web/ Используя это симулятор, вы можете вручную вводить данные в карту памяти, поэтому, даже если вы не можете заполнить пространство памяти в коде, вы можете сделать это в графическом интерфейсе.

Кроме того, документация кода очень важна при сборке, потому что она плохо поддается самодокументированию. Убедитесь, что метки имеют смысл, и у вас должен быть комментарий к блоку, указывающий «стратегию» использования регистров (т. е. какие из них являются временными, а какие используются в более длительной области и должны быть сохранены в стеке перед их перезаписью). У вас также должен быть комментарий к блоку, указывающий назначение каждого логического блока, и эти блоки могут иметь тенденцию быть довольно маленькими, потому что даже простая арифметика может занимать 10-20 строк.

Во второй строке "LD R0, DATA" берутся фактические данные с метки; по вашему описанию вы хотите вместо данных загрузить адрес, для этого вы используете "LEA" а не "LD". Это потребуется для правильной работы вашего LDR в дальнейшем.

Я не понимаю, почему вы инициализируете LENGTH равным 0x5000 или почему DATA является .FILL, если он предназначен для последовательности. Чтобы заблокировать память для больших (более одного слова) данных, вы должны использовать .BLKW и количество байтов. Это резервирует место, и вы можете вручную вставлять данные в симулятор (в стиле «указанный щелчок»), если хотите, или использовать какой-либо другой метод для записи данных программно.

person aqua    schedule 28.08.2018
comment
Спасибо, попробую использовать симулятор :D - person ; 29.08.2018