TSPL 학습 노트 (4): 배열 관련 연습
11317 단어 학습 노트
scheme 에는 배열 이라는 데이터 구조 가 없 기 때문에 list 로 배열 과 유사 한 조작 을 실현 해 야 합 니 다. 다음은 먼저 일부 보조 그룹 함수 가 배열 을 조작 하고 표시 하 는 데 사용 되 는 것 을 정의 합 니 다.
(define (gen-matrix width hight f)
(define (gen-row x y row matrix)
(if (>= x width) (cons (reverse row) matrix)
(gen-row (+ x 1) y (cons (f x y) row) matrix)))
(define (gen y matrix)
(if (>= y hight) matrix
(gen (+ y 1) (gen-row 0 y '() matrix))))
(reverse (gen 0 '())))
(define (show-matrix matrix)
(define (show-row row)
(if (not (null? row)) (begin (display (car row))(display "
")(show-row (cdr row)))))
(show-row matrix))
(define (get-matrix-size matrix)
(if (null? matrix) '()
(if (null? (car matrix)) '()
(list (length (car matrix)) (length matrix)))))
gen-matrix 하나의 width X hight 행렬 을 만 드 는 데 사용 되 고 f 는 (lambda (x y)) 와 같은 함수 로 x y 위 치 를 출력 하 는 데 사용 된다. 예 를 들 어:(gen-matrix 4 4 (lambda (x y) (if (and (= x 2) (= y 2)) 1 0)하나의 (22) 위 치 를 1 로 만 들 고 나머지 위 치 는 0 인 4X4 행렬 을 만 듭 니 다.
show-matrix 목록 형식의 행렬 을 사각형 으로 화면 에 출력 하 는 데 사용 합 니 다. 예 를 들 어:(show-matrix (gen-matrix 4 4 (lambda (x y) (if (and (= x 2) (= y 2)) 1 0))))출력
(0 0 0 0)
(0 0 0 0)
(0 0 1 0)
(0 0 0 0)get-matrix-size 행렬 의 width 와 hight 를 얻 는 데 사용 되 는 반환 값 은 list 입 니 다. (car list) = width (cadr list) = hight(define (member? xs x)
(cond
[(null? xs) #f]
[else (if (equal? x (car xs)) #t (member? (cdr xs) x))]))
member?함 수 는 x 가 xs 에 존재 하 는 지 여 부 를 판단 하 는 데 사 용 됩 니 다. 이 함 수 는 아래 의 몇 가지 예제 에서 사 용 됩 니 다.
미궁
미궁 지 도 를 지정 하고 시작 점 과 목표 점 을 입력 하 며 시작 점 에서 목표 점 까지 의 경 로 를 출력 합 니 다. 먼저 scheme 코드 를 보 겠 습 니 다.
(define maze1 '((1 1 1 1 1 1 1 1 1)
(1 0 1 0 0 0 1 0 1)
(1 0 1 0 1 0 1 0 1)
(1 0 1 0 1 0 1 0 1)
(1 0 0 0 0 0 0 0 1)
(1 1 1 1 1 1 1 1 1)))
;
(define (findpath-one maze from to)(define (findpath-one maze from to)
(letrec* ( [direction '((0 -1) (0 1) (-1 0) (1 0))]
[arrive? (lambda (cur) (and (= (car cur) (car to)) (= (cadr cur) (cadr to))))]
[moveable? (lambda (x y)
(cond
[(> y (length maze)) #f]
[else (let ([line (list-ref maze y)])
(if (> x (length line)) #f (= (list-ref line x) 0)))]))]
[foreach-dir (lambda (dirs pos path close)
(cond
[(null? dirs) '()]
[else (let* ([dir (car dirs)]
[dirx (car dir)]
[diry (cadr dir)]
[nextpos (list (+ (car pos) dirx) (+ (cadr pos) diry))]
[ret (move nextpos path close)])
(if (not (null? ret)) ret (foreach-dir (cdr dirs) pos path close)))]))]
[move (lambda (pos path close)
(if (arrive? pos) (reverse (cons pos path))
(if (or (not (moveable? (car pos) (cadr pos))) (member? close pos)) '()
(foreach-dir direction pos (cons pos path) (cons pos close)))))])
(cond
[(arrive? from) (list from)]
[(or (not (moveable? (car from) (cadr from))) (not (moveable? (car to) (cadr to)))) '()]
[else (foreach-dir direction from (list from) (list from))])))
전형 적 인 역 추적 알고리즘 을 사용 하여 현재 점 에서 출발 하여
direction 중의 네 가지 방향 을 옮 겨 다 니 며 한 방향 으로 전진 할 때 막 히 면 윗 층 으로 거 슬러 올 라 가 다음 방향 을 시도 합 니 다.방향 이 다 떨 어 지면 현재 점 에서 목표 에 도달 할 수 없 음 을 나타 내 고 계속 윗 층 으로 거 슬러 올 라 갑 니 다. 만약 에 1 층 으로 거 슬러 올 라 가 고 방향 이 다 떨 어 지면 출발점 에서 목표 점 에 도달 하지 못 한 경 로 를 나타 냅 니 다. 여 기 는 보조 적 인 데이터 구조 close 표를 사용 하여 이미 지나 간 경 로 를 저장 하고 경 로 를 탐지 할 때 되 돌아 가 는 길 로 인해 순환 하지 않도록 합 니 다.결 과 를 화면 에 표시 하려 면 다음 함 수 를 정의 할 수 있 습 니 다.
(define (showmaze maze path)
(let ([matrix-size (get-matrix-size maze)])
(define matrix (gen-matrix (car matrix-size) (cadr matrix-size) (lambda (x y)
(if (member? path (list x y)) '*
(list-ref (list-ref maze y) x)))))
(show-matrix matrix))
)지도 와 경 로 를 입력 하면 길 찾기 결 과 를 화면 에 표시 할 수 있 습 니 다. 예 를 들 어:
(showmaze maze1 (findpath-one maze1 '(1 1) '(3 3)))출력
(1 1 1 1 1 1 1 1 1)
(1 * 1 0 0 0 0 0 1)
(1 * 1 0 1 0 1 0 1)
(1 * 1 * 1 0 1 0 1)
(1 * * * 0 0 1 0 1)
(1 1 1 1 1 1 1 1 1)이어서 haskell 버 전 을 보 겠 습 니 다.
import qualified Data.Set as Set
--
--module Maze
--(
-- FindOne
--) where
--
elemat :: [maybe] -> Int -> maybe
elemat xs idx =
if idx >= length xs then error "index out of range"
else fetch xs 0
where fetch (x:xs) acc =
if acc == idx then x
else fetch xs (acc+1)
--
movable ::[[Int]] -> (Int,Int) -> Bool
movable maze (x,y) =
if y < length maze then
let line = elemat maze y
in if x < length line then
elemat line x == 0
else False
else False
--
findonepath :: [[Int]] -> (Int,Int) -> (Int,Int) -> [(Int,Int)]
findonepath maze from to
| not (movable maze from) || not (movable maze to) = []
| otherwise = foreachdir direction from [from] $ Set.fromList []
where
direction = [(0,-1),(0,1),(-1,0),(1,0)] -- 4
foreachdir dirs (x,y) path close
| null dirs = []
| otherwise =
let
(dirx,diry) = head dirs
nextpos = (x+dirx,y+diry)
ret = move path close nextpos
in
if null ret then
foreachdir (tail dirs) (x,y) path close
else ret
move path close (x,y)
| (x,y) == to = reverse ((x,y):path) --
| otherwise =
if Set.member (x,y) close || not (movable maze (x,y)) then []
else foreachdir direction (x,y) ((x,y):path) $ Set.insert (x,y) close
scheme 버 전과 다른 점 은 두 가지 가 있 습 니 다.
8 황후 문제 도 전형 적 인 역 추적 알고리즘 문제 로 문제 풀이 방법 은 미로 문제 와 유사 하 다.
(define (puzzle size)
(define (vaild? queen pos);
(define (check xs)
(if (null? xs) #t
(let ([x (car (car xs))]
[y (cadr (car xs))])
(cond [(= x (car pos)) #f]
[(= (abs (- x (car pos))) (abs (- y (cadr pos)))) #f]
[else (check (cdr xs))]))))
(check queen))
(define (foreach-row x y queen result)
(cond
[(>= x size) result]
[(>= y size) (cons queen result)]
[else (let ([newresult (if (vaild? queen (list x y))
(foreach-row 0 (+ y 1) (cons (list x y) queen) result)
result)])
(foreach-row (+ x 1) y queen newresult))]))
(let ([result (foreach-row 0 0 '() '())])
(define (show xs)
(if (not (null? xs))
(begin (display "------result-------
")
(show-matrix (gen-matrix size size (lambda (x y) (if (member? (car xs) (list x y)) '* " "))))
(show (cdr xs)))))
(show result)
(display "total solution:")(display (length result))(display "
")))haskell 의 실현
--
vaild :: [(Int,Int)] -> (Int,Int) -> Bool
vaild [] _ = True
vaild xs (x,y) = foldr (\q acc -> if (x == (fst q)) || (abs (x - fst q)) == (abs (y - snd q)) then False else acc) True xs
foreachrow :: (Int,Int) -> Int -> [(Int,Int)] -> [[(Int,Int)]] -> [[(Int,Int)]]
foreachrow (x,y) size queen result
| x >= size = result
| y >= size = (queen:result)
| otherwise = let newresult = if vaild queen (x,y) then foreachrow (0,y+1) size ((x,y):queen) result
else result
in foreachrow (x+1,y) size queen newresult
puzzle :: Int -> Int
puzzle 0 = 0
puzzle size = length $ foreachrow (0,0) size [] []뱀 모양 행렬
입력 2, 출력:
1 2
4 3입력 3, 출력:
1 2 3
8 9 4
7 6 5 이에 따라 유추 하 다.
먼저 알고리즘 을 간단하게 설명 합 니 다. 초기 에 행렬 은 모두 0 이 고 왼쪽으로 이동 하 며 계수 값 1 을 시작 위치 (0 0) 까지 기록 하고 현재 방향 으로 이동 합 니 다. 충돌 할 때 까지 이동 방향 을 전환 합 니 다. 충돌 하 는 조건 은 x y 좌표 가 행렬 범위 나 x y 위 치 를 초과 하 는 값 이 0 이 아 닙 니 다.
2 차원 배열 을 처리 하기 위해 다음 과 같은 보조 함 수 를 추가 합 니 다.
;1 ,2
; 0
(define (make-array n init) (rep init n))
(define (array-at array n) (element-at array (+ n 1)))
(define (array-replace-at array n new) (replace array new (+ n 1)))
(define (make-array2d width hight init) (make-array hight (make-array width init)))
(define (array2d-at array2d c r)
(let ([row (if (> (length array2d) r) (array-at array2d r) '())])
(if (null? row) "idx out of range"
(if (> c (length row)) "idx out of range"
(array-at row c)))))
(define (array2d-replace-at array2d c r new)
(let ([row (if (> (length array2d) r) (array-at array2d r) '())])
(if (null? row) "idx out of range"
(if (> c (length row)) "idx out of range"
(array-replace-at array2d r (array-replace-at row c new))))))
다음은 주 함수 입 니 다.
(define (snake size)
(define maxc (* size size))
(define (snake-imp c matrix cur direction)
(if (> c maxc) matrix
(let* ([curx (car cur)]
[cury (cadr cur)]
[tmpx (+ curx (caar direction))]
[tmpy (+ cury (cadar direction))]
[newmatrix (array2d-replace-at matrix curx cury c)]
[newdirection (if (or ;
(> 0 tmpx)
(>= tmpx size)
(> 0 tmpy)
(>= tmpy size)
(not (= 0 (array2d-at newmatrix tmpx tmpy)))) (lshift direction 1)
direction)]
[newx (+ curx (caar newdirection))]
[newy (+ cury (cadar newdirection))])
(snake-imp (+ c 1) newmatrix (list newx newy) newdirection))))
(snake-imp 1 (make-array2d size size 0) '(0 0) '((1 0) (0 1) (-1 0) (0 -1))))이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STL 학습노트(6) 함수 객체모방 함수는 모두pass-by-value이다 함수 대상은 값에 따라 전달되고 값에 따라 되돌아오기 때문에 함수 대상은 가능한 한 작아야 한다(대상 복사 비용이 크다) 함수 f와 대상 x, x 대상에서 f를 호출하면:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
