JonyRock 28 янв 2009 в 10:54

Немного логики…

2 мин

2.6K

Занимательные задачки

+12

Комментарии 41

НЛО прилетело и опубликовало эту надпись здесь

JonyRock 28 янв 2009 в 11:11

угу, у вас зоркий глаз :)

НЛО прилетело и опубликовало эту надпись здесь

JonyRock 28 янв 2009 в 11:24

у нас в регистре r0 лежит x, если выполнить s(s0), то к значению r0 прибавится 1. Т.е. это просто инкремент.
P.S. в этом решении есть ошибка, нужно найти какая.

Ayay 28 янв 2009 в 11:25

Нужно сделать Z(r2) т.е. обнулить вначале к2… Или я не прав?

JonyRock 28 янв 2009 в 11:31

Вообще у нас все регистры находятся в нуле с самого начала. Здесь что-то другое надо сделать.

НЛО прилетело и опубликовало эту надпись здесь

JonyRock 28 янв 2009 в 11:47

Подсказка: 0 — это тоже натуральное число. Все ли у нас будет хорошо при таком раскладе?

НЛО прилетело и опубликовало эту надпись здесь

JonyRock 28 янв 2009 в 12:01

Да, но мы программисты и счет начинается с нуля.
P.S. меня в школе тоже учили, в инсте дело обстоит не так.

JonyRock 28 янв 2009 в 12:07

а вообще натуральные числа можно оставить в покое и обратиться к условия задачи: «r0, r1 >= 0 „

Ayay 28 янв 2009 в 11:51

Вроде так должно быть в первой задаче
с1) j(r0,0,c5);
с2) s(r0); x = x+1
c3) s(r2); r2 = r2+1
c4) j(r2,r1,c2); если r2=r1, тогда прыгнуть на с2.
с5)

JonyRock 28 янв 2009 в 12:10

все равно ошибки.

Ayay 28 янв 2009 в 12:21

Исправленная первая задачка… В этот раз должно заработать :)
с1) j(r2,r1,c5);
с2) s(r0); x = x+1
c3) s(r2); r2 = r2+1
c4) j(1,1,c1)
с5)

JonyRock 28 янв 2009 в 12:32

********************************
*--------------------------------------*
* Первая задача решена. *
*--------------------------------------*
********************************

alt0172 28 янв 2009 в 11:49

Написано может быть неграмотно, т.к. асм я не учил как положено

задача 2
AX — первое число, BX — второе число. Первое число больше по условию:
1) XOR CX, CX
2) INC CX
3) INC BX
4) CMP AX,BX
5) JNZ 2
6) MOV AX,CX

улучшение (неизвестно, что больше):
AX — первое число, BX — второе. DX,EX — вспомогательные (наверняка есть и без них решение, но с ними почти сразу в голову пришло)

1) XOR CX,CX
2) MOV DX,AX
3) MOV EX,BX
4) INC CX
5) INC DX
6) INC EX
7) CMP AX,EX
8) JE С
9) CMP BX,DX
A) JE С
B) JMP 4
C) MOV AX,CX

над 3ей пока думаю.

alt0172 28 янв 2009 в 11:52

«улучшение» это решение задачи |x-y|

JonyRock 28 янв 2009 в 11:59

1) у вас ошибка в обоих решениях, поймете какая, если решите первую задачу.
2) хоть вы и используете xor для обнуления, соблюдайте пожалуйста правила: нельзя использовать бинарные операции, нельзя использовать «JNZ»
4) если вам не очень нравится ассемблер (или по другим причинам), можно использовать форму МНР (мне так даже будет легче проверять)

P.S. но думаете вы в верном направлении.

alt0172 28 янв 2009 в 12:19

1) ошибку я нашел (не знаю правда, единственную ли)
2) хорошо, но это мелочи, которые исправлять недолго

Ayay 28 янв 2009 в 12:07

Задача № 2.
c1) j(r1,0,c6);
c2) s(r1)
c3) s(r2)
c4) j(r0,r1,c2)
c5) T(r0,r2)
c6)

Ayay 28 янв 2009 в 12:35

Исправленная вторая задача… Вот и подошел я наконец к третьей задачке :)
c1) j(r0,r1,c5);
c2) s(r1)
c3) s(r2)
c4) j(1,1,c1)
c5) T(r0,r2)
c6)

JonyRock 28 янв 2009 в 12:44

********************************
*--------------------------------------*
* Вторая задача решена. *
*--------------------------------------*
********************************

JonyRock 28 янв 2009 в 13:33

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

iv_s 28 янв 2009 в 12:10

Помню как-то от скуки сделал интерпретатор МНР машины:)
Только вот в ваших условиях не понял про отрицательные числа.
Вы расширяете возможности машины и вводите отрицательные числа? Или предлагаете кодирование, например если число в третьем регистре, то оно отрицательное?

JonyRock 28 янв 2009 в 12:11

На этот вопрос я ответил в «P.P.P.S»

Antikiller 28 янв 2009 в 12:11

Хехе, у нас преп в инсте любил такие задачки давать. Мне было лень на бумажке считать, написал интерпретатор кода МНР. Естественно, сработал закон подлости, и задачек уже больше не было.
Сейчас уже, конечно, мозги не те.

sysprg 28 янв 2009 в 12:26

К реальной жизни гораздо ближе обратная задача — вычислить что-то подобное без использования сравнений и команд перехода (на арифметике, сдвигах и логических операциях).

alt0172 28 янв 2009 в 12:57

а можно пояснить вот этот момент:

>Ограничения:
>— класть в регистры отрицательные числа
и
>X, Y — любые целые ( и отрицательные тоже )
>r0 — x; r1-y

если х меньше нуля, то в каком виде он будет в r0?

JonyRock 28 янв 2009 в 13:33

Единственно, что я могу вам сказать точно: у всех задач есть решение.

alt0172 28 янв 2009 в 13:42

Здорово, но ведь это не ответ.

JonyRock 28 янв 2009 в 13:47

Если я отвечу, это будет подсказкой.

JonyRock 28 янв 2009 в 17:20

Ну так как задача уже решена. то вот вам ответ:
Область значения функции f(x,y) >= 0, так как
f(x,y) = |x — |y||

Следовательно, нам и не нужно класть в регистры отрицательные числа для ответа. нам вообще не надо вычитать. А то, как это делается блестяще продемонстрировал Ayay.

Ayay 28 янв 2009 в 14:53

Задачка № 3.
; найдем модуль «у»

c1) T(r3,r1)
c2) J(r2,r1,c7)
c3) J(r3,0,c7)
c4) S(r2)
c5) S(r3)
c6) J(1,1,c1)

; получаем значение модуля «у» в регистре r2

c7) T(r1,r2); записываю модуль «у» в r1
c8) Z(r3); обнуляем третий регистр
c9) T(r3,r0); записываю в r3 значение r0

; дальше идет расчет модуля разности

c10) J(r3,0,c17); увеличиваем копию r0(r3) пока r0 не станет =0, тогда ответ х+у = r2 ( если x=r0<0 )
c11) J(r2,r0,c19); увеличиваем копию r1(r2) пока r2 не станет =r0, тогда ответ х-у = r4 ( если x=r0>0 и x>y )
c12) J(r3,r1,c19); увеличиваем r3 пока r3 не станет =r1, тогда ответ y-x = r2 ( если x=r0>0 и x<y )
c13) S(r2)
c14) S(r3)
c15) S(r4)
c16) J(1,1,c10)

c17) T(r0,r2)
c18) J(1,1,c43); выход из программы

c19) T(r0,r4)
c20); выход из программы

JonyRock 28 янв 2009 в 17:14

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

JonyRock 28 янв 2009 в 17:17

P.S. его можно сделать еще меньше, если убрать строчку c8.

Ayay 28 янв 2009 в 17:34

На счет с8 вы правы… А слона то я и не заметли:) Спасибо за задачку. Было интресно поломать над ней голову.

JonyRock 28 янв 2009 в 17:28

Теперь решение на ASM: (полностью программа, можно сразу транслировать)

; — .MODEL small
.STACK 256
; — .DATA
r0 dw 0
r1 dw 0
r2 dw 0
r3 dw 0
r4 dw 0
r5 dw 0
r6 dw 0
r7 dw 0
r8 dw 0
r9 dw 0
r10 dw 0
; — .CODE
Start:
mov ax,@data
mov ds,ax
mov es,ax
; —
mov ax,{num1}; первое число
mov r1,{num2}; второе число
mov r0, ax
mov r3, ax

x2: mov ax,r5
cmp r3,ax
je ex1
mov ax,r0
cmp r4,ax
je ex2
inc r4
inc r3
jmp x2
ex1:
mov r3,0
inc r3
jmp y1
ex2:
mov r3,0
y1:
mov ax,r1
mov r6,ax
y2: mov ax,r7
cmp r6,ax
je eSum
mov ax,r1
cmp r5,ax
je eSum
inc r6
inc r5
jmp y2
eSum:
mov ax,1
cmp r3,ax
je ePlus
mov r0,0
mov ax,r4
mov r1,ax
mov ax,r5
mov r2,ax
em1:mov ax,r5
cmp r1,ax
je anv
mov ax,r4
cmp r2,ax
je anv
inc r1
inc r2
inc r0
jmp em1
ePlus:
mov r3,0
ep1:mov ax,r5
cmp r3,ax
je anvx
inc r4
inc r3
jmp ep1
anvx:
mov ax,r4
mov r0,ax
anv:
; процедура вывода r0

; — mov ah,08h
int 21h
mov ax,4C00h
int 21h
END Start

JonyRock 28 янв 2009 в 17:30


   ; --------------------------------------
   .MODEL small        
   .STACK 256   
      
       
   ; --------------------------------------
   .DATA            
    	    	
    	r0 dw 0
    	r1 dw 0
    	r2 dw 0
    	r3 dw 0
    	r4 dw 0
    	r5 dw 0
    	r6 dw 0 
    	r7 dw 0 
    	r8 dw 0 
    	r9 dw 0 
    	r10 dw 0 
      
   ; --------------------------------------
   .CODE                
    Start:                             
       	mov ax,@data      
       	mov ds,ax
       	mov es,ax                         
       	; --------
	
		mov ax,{num1} ; ïåðâîå ÷èñëî
		mov r1,{num2} ; âòîðîå ÷èñëî
		
		mov r0, ax
		mov r3, ax
		

		x2:	mov ax,r5
			cmp r3,ax
			je ex1
			mov ax,r0
			cmp r4,ax
			je ex2
			inc r4
			inc r3
			jmp x2
		
		
			
		
		
		ex1:
			mov r3,0
			inc r3
			jmp y1
		ex2:
			mov r3,0
			
		y1:
			mov ax,r1
			mov r6,ax
			
		y2:	mov ax,r7
			cmp r6,ax
			je eSum
			mov ax,r1
			cmp r5,ax
			je eSum
			inc r6
			inc r5
			jmp y2
		
		
					
		eSum:		
			
			mov ax,1
			cmp r3,ax
			je ePlus
			
			mov r0,0
			mov ax,r4
			mov r1,ax
			mov ax,r5
			mov r2,ax
			
		em1:mov ax,r5
			cmp r1,ax
			je anv
			mov ax,r4
			cmp r2,ax
			je anv
			inc r1
			inc r2
			inc r0
			jmp em1 
			
			
		ePlus:
			mov r3,0
		ep1:mov ax,r5
			cmp r3,ax
			je anvx
			inc r4
			inc r3
			jmp ep1 
				
		anvx:
			mov ax,r4
			mov r0,ax
			
		anv:
			; ïðîöåäóðà âûâîäà r0							

		; --------
       	mov ah,08h        
       	int 21h           
       	mov ax,4C00h      
       	int 21h           
   END Start

LDEV 28 янв 2009 в 23:40

Это жесть была. Преподавали в университете. Хотя развивает логику и дает некоторые понятия, как работает процессор. А на лекциях по микропроцессорам — сидели еще в дебагере и строили ёлочки и мирамидки из значений в регистрах :)

vastvision 29 янв 2009 в 06:32

Простите за оффтоп!
Мне надо написать программу на МНР, вычисляющую значения некоторой функции. Кто мне может помочь, пишите в личку.
$$

MVM 29 янв 2009 в 12:49

Обожаю мнр. В универе по матлогике проходили. Там даже самописная программа была, для интерпритации и визуализации кода. ))

Зарегистрируйтесь на Хабре, чтобы оставить комментарий