Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Пт мар 29, 2024 00:30

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: Задача про зашифрованную черепашку
СообщениеДобавлено: Ср июн 13, 2018 21:42 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
Программа «черепашка» использует односимвольные команды для перемещения вперед на одну клетку, поворота направо на 90° и поворота налево на 90°. Дано начальное положение «черепашки» и конечное положение, задаваемые целыми числами в двумерных координатах. Начальное направление – вдоль оси X. Коды для каждой команды неизвестны. Составить программу, которая, принимая начальные и конечные координаты, а также строку с командами, определит коды каждой команды.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про зашифрованную черепашку
СообщениеДобавлено: Чт июн 14, 2018 23:20 
Не в сети

Зарегистрирован: Пт июн 06, 2008 14:21
Сообщения: 128
Откуда: Карелия
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Hishnik писал(а):
а также строку с командами

Не понятно, чем заканчиваются команды? Конец строки?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про зашифрованную черепашку
СообщениеДобавлено: Чт июн 14, 2018 23:46 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 7960
Благодарил (а): 25 раз.
Поблагодарили: 144 раз.
F-MAP писал(а):
Не понятно, чем заканчиваются команды? Конец строки?

Да чем удобнее. Это лишнее условие, на практике-то всегда можно преобразовать.


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про зашифрованную черепашку
СообщениеДобавлено: Чт июн 14, 2018 23:58 
Не в сети

Зарегистрирован: Пт июн 06, 2008 14:21
Сообщения: 128
Откуда: Карелия
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Hishnik писал(а):
F-MAP писал(а):
Не понятно, чем заканчиваются команды? Конец строки?

Да чем удобнее. Это лишнее условие, на практике-то всегда можно преобразовать.

Это в смысле защиты от "дурака", вдруг исполнение команд строки не достигнут или переедут конечное положение... или это не рассматривается?


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про зашифрованную черепашку
СообщениеДобавлено: Вс июн 24, 2018 01:55 
Не в сети

Зарегистрирован: Сб июл 23, 2016 23:15
Сообщения: 11
Благодарил (а): 0 раз.
Поблагодарили: 0 раз.
Код:
CREATE COMMANDS C" 1222223222221223222221222333" ",
0 VALUE START-X
0 VALUE START-Y
0 VALUE START-DIR
10 VALUE END-X
10 VALUE END-Y

: TOSS, ( XM .. XN .. X0 X N -- XM .. X .. X0 )  \  PUT X TO N-TH PLACE IN STACK
  0x8B C, 0x4D C, 0x00 C,          \ MOV ECX, [EBP]
  0xFF C, 0xC0 C,                  \ INC ECX
  0x89 C, 0x4C C, 0x85 C, 0x00 C,  \ MOV [EAX*4+EBP], ECX
  0x8B C, 0x45 C, 0x04 C,          \ MOV EAX, [EBP+4]
  0x8D C, 0x6D C, 0x08 C,          \ LEA EBP, [EBP+8]
; IMMEDIATE

(
http://fforum.winglion.ru/viewtopic.php?p=45524#p45524

LEA EBP, 4 [EAX*4] [EBP]
MOV EAX, -4 [EBP]
)

: DROPN, ( X1 .. X[i] N -- X1 .. X[i-N] )  \  DROP N CELLS FROM DATA STACK
  0x8D C, 0x6C C, 0x85 C, 0x04 C,  \ LEA EBP, EAX*4 + EBP + 4
  0x8B C, 0x45 C, 0xFC C,          \ MOV EAX, EBP - 4
; IMMEDIATE

: TURN-LEFT ( DIR -- DIR' )
  DUP 0   = IF 90  ELSE
    DUP 90  = IF 180 ELSE
      DUP 180 = IF 270 ELSE
        DUP 270 = IF 0   
  THEN THEN THEN THEN
  NIP
;

: TURN-RIGHT ( DIR -- DIR' )
  DUP 0   = IF 270 ELSE
    DUP 90  = IF 0   ELSE
      DUP 180 = IF 90  ELSE
        DUP 270 = IF 180
  THEN THEN THEN THEN
  NIP
;

: FORWARD ( POS-X POS-Y DIR -- POS-X' POS-Y' DIR )
  DUP 0   = IF 2 PICK 1+ 2 TOSS, ELSE
    DUP 90  = IF 1 PICK 1+ 1 TOSS, ELSE
      DUP 180 = IF 2 PICK 1- 2 TOSS, ELSE
        DUP 270 = IF 1 PICK 1- 1 TOSS,
  THEN THEN THEN THEN
;

: SIMULATE-SINGLE-STEP ( START-X START-Y DIR LRF -- END-X END-Y DIR )
  DUP [CHAR] L = IF OVER TURN-LEFT 1 TOSS, ELSE
    DUP [CHAR] R = IF OVER TURN-RIGHT 1 TOSS, ELSE
                        3 PICK 3 PICK 3 PICK FORWARD
                        DROP 3 TOSS, 3 TOSS,
  THEN THEN
  DROP
;

: EXPAND-CODE ( CODE -- CODE-L CODE-R CODE-F )
  DUP 255 AND SWAP
  DUP 8 RSHIFT 255 AND SWAP
  16 RSHIFT 255 AND
;

: COMPRESS-CODE ( CODE-L CODE-R CODE-F -- CODE )
  16 LSHIFT 1 PICK 8 LSHIFT OR
  2 PICK OR
  NIP NIP
;

: DECODE-COMMAND ( COMMAND CODE -- LRF )
  EXPAND-CODE
  3 PICK 3 PICK = IF [CHAR] L ELSE
    3 PICK 2 PICK = IF [CHAR] R ELSE
                         [CHAR] F
  THEN THEN                            \ COMMAND CODE-L CODE-R CODE-F LRF
  3 TOSS, 3 DROPN,                     \ LRF
;

: SIMULATE ( START-X START-Y DIR COMMANDS CODE -- END-X END-Y DIR )
  SWAP COUNT ROT                       \ START-X START-Y DIR COMMANDS U CODE
  0                                    \ START-X START-Y DIR COMMANDS U CODE I=0
  BEGIN
    2 PICK OVER >                      \ WHILE U > I
  WHILE                                \ X Y DIR COMMANDS U CODE I
    6 PICK 6 PICK 6 PICK 6 PICK 4 PICK \ X Y DIR COMMANDS U CODE I X Y DIR COMMANDS I
    + C@ 5 PICK DECODE-COMMAND         \ X Y DIR COMMANDS U CODE I X Y DIR LRF
    SIMULATE-SINGLE-STEP               ( START-X START-Y DIR LRF -- END-X END-Y DIR )
    6 TOSS, 6 TOSS, 6 TOSS,            \ X Y DIR COMMANDS U CODE I
    1+
  REPEAT
  4 DROPN,
;

: ENUM-COMMANDS ( COMMANDS -- CODE )
  COUNT
  0 0 0 0                               \ COMMANDS U L R F I
  BEGIN
    DUP 5 PICK <                        \ COMMANDS U L R F I I<U?
    4 PICK 0 <> 4 PICK 0 <> 4 PICK 0 <> \ COMMANDS U L R F I I<U? L<>0 R<>0 F<>0
    OVER AND -ROT AND AND NOT AND       \ COMMANDS U L R F I I<U&!(L,R,F<>0)
  WHILE                                 \ COMMANDS U L R F I
    5 PICK OVER + C@                    \ COMMANDS U L R F I COMMAND
    4 PICK 0 = IF
      DUP 4 TOSS,
    ELSE
      4 PICK OVER <> IF                 \ COMMANDS U L R F I COMMAND
       
        3 PICK 0 = IF
          DUP 3 TOSS,
        ELSE
          3 PICK OVER <> IF             \ COMMANDS U L R F I COMMAND

            DUP 2 TOSS,
          THEN
        THEN
      THEN
    THEN
    DROP
    1+
  REPEAT                                \ COMMANDS U L R F I
  DROP COMPRESS-CODE NIP NIP
;

(
code permutations:
code swap step
123  12   1
132       6
213  23   2
312  12   5
231  12   3
321  23   4
)

\ I = 0 | 1
: SWAP-CODE ( CODE I -- CODE )
  SWAP EXPAND-CODE                     \ I CODE0 CODE1 CODE2
  3 PICK 0 = IF
    ROT SWAP                           \ I 1 0 2
  ELSE
    SWAP                               \ I 0 2 1
  THEN
  COMPRESS-CODE NIP
;

: PERMUTATE-CODE ( CODE PERMUTATION-NUMBER -- CODE )
  2 MOD SWAP-CODE
;

: MAIN ( START-X START-Y START-DIR END-X END-Y COMMANDS --  )
  DUP ENUM-COMMANDS
  0                                        \ X Y DIR EX EY COMMANDS CODE PERMUTATION-NUMBER=0
  BEGIN
    DUP 6 <
  WHILE                                    \ X Y DIR EX EY COMMANDS CODE PN
    DUP
    ." Permutation number: " . CR
   
    OVER EXPAND-CODE -ROT SWAP
    ." Simulation code: " EMIT SPACE EMIT SPACE EMIT CR
   
    7 PICK 7 PICK 7 PICK 5 PICK 5 PICK
    SIMULATE DROP                          \ X Y DIR EX EY COMMANDS CODE PN SIM-X SIM-Y
   
    2DUP SWAP
    ." Simulation end coordinates: " . ." , " . CR

    5 PICK = SWAP 6 PICK = AND IF          \ X Y DIR EX EY COMMANDS CODE PN
      DROP EXPAND-CODE -ROT SWAP
      ."  Code for 'left' is:    " EMIT CR
      ."  Code for 'right' is:   " EMIT CR
      ."  Code for 'forward' is: " EMIT CR
      2DROP 2DROP 2DROP EXIT
    THEN

    CR
    SWAP OVER PERMUTATE-CODE SWAP
    1+
  REPEAT
  2DROP 2DROP 2DROP 2DROP
  ." Simulation failed!" CR
;

START-X START-Y START-DIR END-X END-Y COMMANDS MAIN


Код:
Permutation number: 0
Simulation code: 1 2 3
Simulation end coordinates: 0 , -3

Permutation number: 1
Simulation code: 2 1 3
Simulation end coordinates: 0 , 3

Permutation number: 2
Simulation code: 2 3 1
Simulation end coordinates: 1 , 0

Permutation number: 3
Simulation code: 3 2 1
Simulation end coordinates: 1 , 0

Permutation number: 4
Simulation code: 3 1 2
Simulation end coordinates: 10 , -10

Permutation number: 5
Simulation code: 1 3 2
Simulation end coordinates: 10 , 10
Code for 'left' is:    1
Code for 'right' is:   3
Code for 'forward' is: 2
Ok


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Задача про зашифрованную черепашку
СообщениеДобавлено: Вс июн 24, 2018 11:29 
Не в сети

Зарегистрирован: Пт июн 06, 2008 14:21
Сообщения: 128
Откуда: Карелия
Благодарил (а): 1 раз.
Поблагодарили: 4 раз.
Еще вариант, забыл отправить
Код:
0 VALUE Xbeg \ исходное положение
0 VALUE Ybeg \ исходное положение
0 VALUE Xend \ конечное положение
0 VALUE Yend \ конечное положение

0 VALUE Xd \ положение до выполнения команды
0 VALUE Yd \ положение до выполнения команды
0 VALUE Xt \ положение после выполнения команды
0 VALUE Yt \ положение после выполнения команды

: Команда ( Xt Yt  -- X Y )
\ неизвестная команда изменяет текущее положение
NOOP \ заглушка, исполняет строку команды
;

: Анализ ( -- ) \ определим команду, команды вниз по условию нет
\ !! Система координат - ось Y вверх ось X вправо
\ иначе поменять местами X Y
Yt Yd = IF \ влево или вправо
Xt Xd - 0>  IF \ команда вправо на 90
." команда вправо  Xt 1+ "
            ELSE  \ команда влево на 90  ( 0= не рассматривается )
." команда влево  Xt 1- "
            THEN
        ELSE \ команда вверх
." команда вверх  Yt 1+ "
        THEN
CR
;

: ОпределитьКоманды  ( Xbeg Ybeg Xend Yend -- )
TO Yend
TO Xend
TO Ybeg
TO Xbeg
Xbeg TO Xt
Ybeg TO Yt
BEGIN
Xt Yt 2DUP TO Yd TO Xd
Команда  TO Yt TO Xt
Анализ
Xt Yt  Xend Yend D= \ или ROT = >R = R> AND
UNTIL


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB