Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
kanbodows
1

Олимпиадная задачка. Если есть идеи то помогите. Вместе решим

07.11.2011, 22:39. Просмотров 869. Ответов 1
Метки нет (Все метки)

B. Время исполнения
Time Limit: 1000 ms
Memory Limit: 1024 kb

При проектировании программы на языке низкого уровня иногда требуется оценить время исполнения программы. Каждая команда при выполнении занимает некоторое количество времени в тактах процессора.

Дан фиксированный набор команд и регистров:

Регистры:
A,B,C,D
Каждый регистр может хранить целое число в диапазоне от 0 до 2011 включительно.

Команды:
MOV reg_dst,number - поместить целое число (number) в регистр (reg_dst)
MOV reg_dst,reg_src - поместить знaчение регистра источника(reg_src) в регистр приемник(reg_dst)
XCHG reg1,reg2 - обменять местами значения двух регистров - reg1 и reg2
LOOP label - выполняется цикл с метки label до LOOP.
LOOP проверяет, если регистр С > 0, то совершается переход на метку и уменьшается C на единицу, иначе цикл заканчивается и выполняется следующая команда за командой LOOP.
Метка всегда является отдельной строкой и начинается со знака ":". Например - :label1.
NOP - ничего не делать
EXIT - окончание выполнения.
Требуется оценить общее время исполнения данной программы в тактах процессора.


Input
Первые 5 строк содержат количество тактов процессора (числа 0 < N < 1000), требуемые для исполнения каждой из пяти приведенных выше команд в следующем порядке:
MOV
XCHG
LOOP
NOP
EXIT
Далее идет программа, время выполнения которой требуется оценить.
На каждой строке - точно одна команда или метка. Все операторы в программе корректны и записаны латинскими буквами.
Метка всегда находятся выше соответствующей команды LOOP.Допускаются вложенные и пересекающиеся циклы
Параметры команд MOV и XCHG записываются через запятую.
Общий размер программы не превышает 7000 строк.
Программа гарантировано завершается командой EXIT не более чем через 14000 исполнений команд.


Output
В выходном файле вывести одно число 0 < N < 1 000 000, время исполнения программы в тактах процессора.


Sample Input
1
2
3
4
5
MOV A,2
MOV C,3
XCHG A,C
:label1
NOP
LOOP label1
EXIT


Sample Output

30
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.11.2011, 22:39
Ответы с готовыми решениями:

Подсуммы (олимпиадная задачка), нужны идеи
64 megabytes / 1 seconds / stdin / stdout Не все числа одинаково полезны. Если, например, вам...

Разработка и маркетинг если есть интересные идеи
Готов взятся за исполнение и маркетинг интересных идей за долю в проекте Сам был в такой...

Программа, которая считает площадь круглой заготовки, если с неё вырезать три прямоугольника разного размера. Есть идеи?
Нужна программа с использованием функций

методом неопред. коэфф. не получается, а если делать так(картинка ниже), так же не выходит. есть идеи?
∫(3x-1)dx/(x2+4)(x2+9); Сразу методом неопред. коэфф. не получается, а если делать так(картинка...

1
odip
Эксперт С++
7170 / 3228 / 77
Регистрация: 17.06.2009
Сообщений: 14,166
08.11.2011, 11:26 2
Ну и что ты уже написал ?
Насколько я понимаю проблемы могут быть только со временем выполнения

Добавлено через 15 минут
Для решения задачи нужно выполнить код
При это требуется выполнять все команды и вести состояние 4 регистров
попутно считать число тактов

Можно построить двупроходный компилятор
1 проход
Заносим программу в массив PROG ( хватит 7000 структур )
Заносим все метки в отдельный ассоциативный массив LABELS
При этом запоминаем на какой строке программы находится метка
Все операторы GOTO вместе с метками переходов заносим в программу

2 проход
В массиве PROG во всех операторах GOTO заменяем строчные метки на номер строки
Номер определим по массиву LABELS

3 проход
Выполняем программу
0
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2011, 11:26

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

олимпиадная задачка
На доске наклеено несколько листов объявлений. Все они прямоугольной формы. Некоторые письма...

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

Олимпиадная задачка
cut Помогите пожалуйста, напишите программу на C++. Входной файл: input.txt Выходной файл:...

Олимпиадная задачка
Мальчик Вася, чтобы попасть к себе домой на 10-й этаж, сначала поднимается до 7-го, а потом идет 3...


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

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

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