codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
;;;お題 ;;;与えられた文字列中の文字F,GをそれぞれF-F-F-GG,GG ;;;に変換するとして ;;;初期文字列を"F"とする時,n回の置換で得られる ;:;文字列を求めよ ;;; 0回置換 ->"F" ;;; 1回置換 ->"F-F-F-GG" ;;; 2回置換 ->"F-F-F-GG-F-F-F-GG-F-F-F-GG-GGGG" ;;;解答例 (define foo (lambda (s n) (list->string (goo (string->list s) n)))) (define goo (lambda (l n) (if (zero? n) l (goo (change-fg l (lambda (x) x)) (1- n))))) ;;;補助関数 ;;;とても巨大な結果になるので末尾再帰でないと ;;;時間がかかって論外.ここではcollectorを用いて ;;;末尾再帰定義としている (define change-fg (lambda (l col) (cond ((null? l) (col '())) ((eq? (car l) #\F) (change-fg (cdr l) (lambda (x) (col (append (string->list "F-F-F-GG") x))))) ((eq? (car l) #\G) (change-fg (cdr l) (lambda (x) (col (append (string->list "GG") x))))) (else (change-fg (cdr l) (lambda (x) (col (cons (car l) x)))))))) ;;;適用例 (foo "F" 0) "F" (foo "F" 1) "F-F-F-GG" (foo "F" 2) "F-F-F-GG-F-F-F-GG-F-F-F-GG-GGGG" ;;;(foo "F" 8)はとても長い文字列(29011文字)になる ;;;ので結果文字列の表示は省略 ;;;参考:(foo "F" 8)の長さを求める (length (string->list (foo "F" 8))) 29011
Private
[
?
]
Run code
Submit