Отправляет email-рассылки с помощью сервиса Sendsay

Задачи по ассемблеру

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 882 RSS
←   Сентябрь 2003   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://codeclimber.com
Открыта: 09-11-2002

Автор
Igoryk

Статистика

882 подписчиков
0 за неделю
←   Все выпуски   →

Задачи по ассемблеру


Информационный Канал Subscribe.Ru

Задачи по ассемблеру.

Выпуск #31.

Добрый день, уважаемые читатели! Хочу ознакомить Вас с нововведением в Правилах: нельзя использовать условное компилирование, т.е. при одних условиях, команды попадают в программу, при других нет - так нельзя. Дело в том, что таким образом программа будет менять свой размер в зависимости от входных условий, и подбор "лучших" входных условий увеличивает шансы на победу! Нас же интересует чистый код, т.е. нужно чтобы было видно как на ассемблере выполняется тот или иной алгоритм.

Новость: По предложению G3 будет создан сезонный рейтинг!

 

Сегодня в выпуске:

1. Решение задачи #30.

2. Задача #31.

 

Решение задачи #30.

Таблица рекордов:

  Участник

Размер решения
1. Shur 33 байта
2. G3 37 байт
3. Beeblebrox 38 байт
4. Edward Samokhvalov 51 байт
5. Alex 52 байта
6. Ayl 54 байта
7. Vzub Pnukem 58 байт

 

Условие задачи.

Вывести на экран выражение, значение которого равно Value.

 

Решения.

Решение by Shur:

;by Shur
;33 bytes
;fasmw

value equ -3
;  ch=00
;  bp=09xx

   mov bl,value
   mov dh,'-' xor '+'
   mov di,dx
   mov ax,'9+'+1
   mov cl,9
_next:
   dec ax
   sub bl,cl
   jg _1
   xor ah,dh
   neg bl
_1:
   stosw
   loop _next
   jnz _end
   mov byte [di-1],'$'
   xchg ax,bp
   int 21h
_end:
   ret

Решение by G3:

;Task #30 by G3(tgm80@mail.ru), 37 bytes
;tasm /m task.asm
;tlink /x /3 /t task.obj
 .model tiny
 .386
 .code
org 100h

Value equ -3

Start:
 mov bl,Value-9
 mov cl,8
 mov dx,'$1'  ;dx = смещение строки в памяти
 mov di,dx
L10:    ;рекурсивная процедура
 mov ax,'+1'
 add ax,cx

 pusha
 sub bl,cl
 call L20  
 popa
 
 mov ah,'-'
 add bl,cl
L20:
 stosw   ;записать число и знак в строку
 loop L10  
 jnz L30  ;перейти если bl<>0

 mov [di],dx  ;дописать '1$' в конец строки
 xchg ax,bp  ;ah=9
 int 21h  ;вывести строку
 push cx  ;push 0000h для выхода из программы
L30:
 ret   ;выйти из процедуры или из программы
end Start

Решение by Beeblebrox:

; evaluator by Beeblebrox / TMA
; 38 bytes
; tasm /m9 task30.asm
; tlink /t/x task30.obj
 
VALUE           equ     -27      ; -27...45
 
 .model tiny
 .586
 .code
                org     100h
start:
; bl=sum, cl=digits 9..1, al= '+' | '-'
                mov     bl,VALUE  
                mov     di,bp
                mov     dx,bp
                inc     dx
                mov     cl,9
m0:             mov     ax,'0+'
                js      m1
                add     ah,cl
                sub     bl,cl
stsw:           stosw
                loop    m0
                jne     quit
                mov     byte ptr [di],'$'
                xchg    ax,bp
                int     21h
quit:           retn
m1:
                mov     al,'-'
                add     ah,cl
                add     bl,cl
                jmp     stsw
 
                end     start

Решение by Edward Samokhvalov:

;By Sam0khvalov Edward & Lev Blaivas (идейн0)
;компилить fasmом над0
;51 БАЙТa

Chisl0  equ   -19

;  stack: 1+2+3+4+5+6+7+8+9$

  ;в CX 0x00ff по дефолту стоит уж0
  inc cx  ;cx становится 0
brutef0rc3: cwd  ;dx=0
  push  "$" ;билдим строку в стэке, готовимся в 9 функ 21 прер
  mov   bl, 9 ;counter слагаемых
@@stuff: mov   al, "+" ; +
  mov   ah, bl
  ror   cl, 1 ;тестим самый правый бит (луп на 8 итераций
      ;не изменит в итоге cx)
  jnc   plus
  inc   ax ; -
  inc   ax
  sub   dl, ah ;минусуем
  jmp   Nastya
  plus:  add   dl, ah ;плюсуем
  Nastya: add   ah, 30h ;переводим число в ascii
  push  ax ;пихаем в стэк: ah=число al=знак
  dec   bx ;слагаемые от 9 до 1
  cmp   bl, 1
  ja    @@stuff

  push  0x3100 ;последнюю цифирьку надо запихнуть туды
  inc   sp ;это разкоментировать
     ;чтобы убрать пробел перед выводящейся строкой

  xor   dl, Chisl0-1 ; 0H0 ИЛИ НЕ ОНО???
  jnz   nifiga
  mov   ah, 9
  mov   dx, sp
  int   21h
  nifiga: loopnz brutef0rc3
  int 20h

Решение by Alex:

;tasm /m2 task30.asm
;tlink /t task30
;52 байта
;by Alex

CSEG segment
assume cs:CSEG, ds:CSEG, ss:CSEG, es:CSEG
org 100h
 .586
Value equ -15
main:
;debug:
;mov bp,0915h
;mov cx,00ffh
;mov si,100h
;ch=0
con:
mov di,bp;bp=09??h, адрес для буфера
mov bx,si;bh=1,bl=0

mov al,31h
stosb

cicl:
inc bx
rol ch,1;ch содержит массив '+' и '-',исли бит равен 0, то + , иначе -
jnc added

not_added:
mov al,'-'

sub bh,bl;bh содержит сумму
jmp end_cicl

added:
add bh,bl
mov al,'+'

end_cicl:
mov ah,bl
add ah,31h
stosw;заношу в буфер знак и цифру
cmp bl,8
jne cicl

cmp bh,value;сравниваю значение суммы с value
je Ok


inc ch
jnz con

ret

ok:
mov ax,0924h;ah=номер ф-ции DOS, 24h='$'
stosb

mov dx,bp;адрес строки для вывода
int 21h
quit:
ret
cseg ends
end main

Решение by Ayl:

Всем бы так решения оформлять :)

Алгоритм решения:
 
Так как у нас всего 9 цифр, причем первая всегда положительная,
то имеем всего 8 знаков. Эти 8 знаков очень удобно кодируются с
помощью 1-го байта (1 бит на знак, 0 = плюс, 1 = минус).
Всего нужно перебрать 256 вариантов.
Слагаемые лучше всего располагать по-порядку. Мне удобнее считать
от 1 до 9, хотя можно было сделать и наоборот - от 9 до 1.
Нетрудно доказать, что результат может быть только нечетным числом
(т.к. у нас 5 нечетных слагаемых) при любом расположении чисел.
Причем диапазон решений равен [-45;45]
Решение ищется следующим образом:
1. В регистре BL будем накапливать сумму (сразу же пишем туда 1),
в регистре AX храним маску для выделения знаков (AH) и текущее слагаемое.
Регистр BH - рабочий, регистр CL содержит очередной вариант расположения
знаков.
2. Для текущего варианта расположения знаков вычисляем значение выражения,
причем для вычитания используем сложение с дополнительным значением
слагаемого (для этого используем регистр BH)
3. Повторяем шаг 2 до момента получения результата или перебора всех 256 вариантов
4. Выводим результат при успехе или просто молча выходим (типа, обиделись :-) ).
 
; Assembler Tasks COMPO #30
; tasm task30.asm
; tlink /x /t task30.obj
; task30.com
; by Ayl
; size: 54 bytes
;
 
 .Model TINY
 .386
 
VALUE EQU 25
 
 .Code
 .Startup
                   ; пpи стаpте пpогpаммы pегистp CL = 0ffh (см.пpавила)!
@@Start:
  mov  ax, 8002h   ; начинаем с 2, маска знаков - 80
  mov  bl, 1       ; вначале сумма = 1
 
@@Crt_Frml:
  mov  bh, al      ; копиpуем текущее слагаемое в pегистp для pаботы
 
  test cl, ah      ; пpовеpяем очеpедной знак (1 - минус, 0 - плюс)
  jz @@Plus        ; если знак - "плюс", то пpосто суммиpуем
  
@@Minus:
  neg  bh          ; a - b = a + (-b)! Изменяем знак текущего слагаемого
 
@@Plus:
  add  bl, bh      ; аpифметическое сложение. В pегистpе BL накапливаем сумму
                   ; Комментаpий.
                   ; Общая длина блока суммиpования очеpедного слагаемого
                   ; pавна 2 (копиpование) + 2 (пpовеpка знака) + 2 (пеpеход) +
                   ; 2 (инвеpсия) + 2 (сложение) = 10 байт.
                   ; То же самое можно сделать по-отдельности для сложения и
                   ; вычитания:
                   ;   test cl, ah      ; (2)
                   ;   jz @@Plus        ; (2)
                   ; @@Minus:
                   ;   sub  bl, al      ; (2)
                   ;   jmp short @@Cont ; (2)
                   ; @@Plus:
                   ;   add  bl, al      ; (2)
                   ; @@Cont:
                   ;   ...
                   ; То есть получаем те же 10 байт. Hо используем лишний
                   ; пеpеход. ИМХО, ваpиант, испольхованный в пpогpамме
                   ; выглядит получше с точки зpения пpоизводительности.
 
  inc  ax          ; пеpеходим к следующему слагаемому. Команду inc ax
                   ; можно использовать, т.к. AL < 10 => пеpеноса в AH не будет
  shr  ah, 1       ; изменяем маску для выделения знака
  jnz  @@Crt_Frml  ; если пеpебpали не все ваpианты - пpодолжаем счет
 
  cmp  bl, VALUE   ; сpавниваем полученный pезультат с эталоном
  je @@End         ; если сумма совпала - выводим выpажение
 
  dec  cx          ; пеpеходим к следующей гpуппе знаков
  jns  @@Start     ; именно такое условие, т.к. надо пеpебpать не 255,
                   ; а 256 ваpиантов
 
  ret              ; если ничего не нашли - пpосто выходим
 
@@End:
  mov  ax, 8031h   ; вывод pезультата. AH = маска для знаков, AL = ASCII код 1
 
@@Rep_Out:
  int  29h         ; выводим слагаемое
  push ax          ; сохpаняем AX, чтобы использовать AL для вывода знака
 
  mov  al, '+'     ; считаем, что знак "плюс"
  test cl, ah      ; но пpовеpяем, что это так
  jz @@Out_Plus    ; все-таки "плюс" :-)
 
  mov  al, '-'     ; нет - "минус"
 
@@Out_Plus:
  int 29h          ; выводим знак
  pop  ax          ; восстановим AX
  inc  ax          ; пеpейдем к следующему слагаемому
  shr  ah, 1       ; и следующему знаку
  jnz @@Rep_Out    ; пока знаки не закончатся
 
  int 29h          ; выведем последнюю цифpу
 
  ret              ; выйдем из пpоги
end

Решение by Vzub Pnukem:

;by Vzub Pnukem
;tasm /m2 *.asm, tlink /t *.asm
;58 bytes

 .model tiny
 .code
 .286
org 100h

Start:
 mov ah, 00000000b  ;Расположение знаков: 0=+, 1=-
Again:
 mov bh, 9   ;Начальная сумма
 mov cx, 8   ;Следующая цифра
Calc:
 rol ah, 1
 jc Minus
 add bh, cl
 add bh, cl
Minus:
 sub bh, cl
 loop Calc

 cmp bh, Value
 jz Found
 inc ah
 jnz Again
 ret 

Found:
 mov al, '9'
 int 29h
Print:
 rol ah, 1
 jc Minus1
 mov bl, '+'
 jmp Putsign
Minus1:
 mov bl, '-'
Putsign:
 xchg al, bl
 int 29h
 mov al, bl
 dec al
 int 29h
 cmp al, '1'
 jnz Print

 ret

Value EQU 43

end start

 

Задача #31.

 

Задание:

 Сегодня Вашему вниманию представляется новое COMPO. Условия придумал G3, за что ему большое спасибо. С тестированием помог Shur, ему тоже большое спасибо. (Кто был на форуме, тот знает).

 

Все COMPO #31 расположено на сайте в одном zip-файле. Он содержит правила этого COMPO, тест и пример решения. Все запускаемые файлы в архиве распространяются AS IS (как есть), т.е. мы не можем нести ответственность за то, как они будут запускаться у Вас, но мы всегда тщательно все проверяем, т.е. бояться Вам в принципе нечего!

 

В форуме открыта тема COMPO #31, в которую можно будет посылать вопросы, и, естественно, получать ответы. Здесь же будут выкладываться все уточнения. Решения сюда посылать не надо!!! Они должны посылаться мне, как обычно.

 

Тематика COMPO: графический фильтр Emboss. Как его сделать смотрите в архиве (ссылка дана в форуме). Оптимизировать можно и по размеру, и по скорости. Только указывайте в теле письма какую именно оптимизацию Вы делали.

 

Размер моего решения: 62 байта.

Количество тактов на Intel Pentium Celeron 566MHz: 000C30E5h tics.

 

В общем все сюда: COMPO #31

 

Отправить решение до 17.09.2003

 

В заключение...

На главной странице "Задач" [http://codeclimber.com/asmtasks.html] будут даны размеры программ лидеров, как только таковые появятся. И так будет с каждой задачей. Узнав, эту информацию каждый может прислать более оптимизированное решение.

Любые предложения по улучшению рассылки, Ваши задачи, вопросы прошу присылать мне на почту, указанную внизу рассылки. 

 

(с) CodeClimber - Все права защищены! 
URL: http://codeclimber.com  E-Mail: compo@codeclimber.com
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное