ohp10.dvi

Size: px

Start display at page:

Download "ohp10.dvi"

もりよりおえづか
5 years ago
Views:

2 ( ) 2

3 2 : def delete if at then (1) EOF (2)@cur 1 (3)@prev 1 : def exch if then return a b c d a.next = b; b.next = c; c.next = = b 4 ( 2 ) a b c 1 : def backward then return a top; a do forward 3

4 2 ( ) : def invert top; if at then return a b a.next while do c = b.next; b.next = a; a = b; b = c = a; (@head ) 1 0 4

5 invert top 1 Buffer class Buffer Cell = Struct.new(:data, :next) def = Cell.new("EOF", = 1 def getlineno def goto(n) top; (n-1).times do forward def at 5

6 4 def = = = 1 def forward if at then = = + 1 def @lineno + 1 def print puts(" " # delete exch backward def backward goto(@lineno - 1) def invert top; if at then return a b a.next while do c = b.next; b.next = a; a = b; b = = a; top 6

7 4 def subst(str) if at then return a = str.split( / = a[2] def read(file) open(file, "r") do f f.each do s insert(s) def save(file) top open(file, "w") do f while not at do f.puts(@cur.data); forward 7

8 4 ( ): def edit e = Buffer.new while true do printf(">") line = gets; c = line[0..0]; s = line[1..-2] if c == "q" then return elsif c == "t" then e.top; e.print elsif c == "p" then e.print; l = e.getlineno; s.to_i.times do e.forward; e.print ; e.goto(l) elsif c == "i" then e.insert(s) elsif c == "r" then e.read(s) elsif c == "w" then e.save(s) elsif c == "s" then e.subst(s); e.print elsif c == "d" then e.delete elsif c == "x" then e.exch elsif c == "b" then e.backward elsif c == "v" then e.invert elsif c == "a" then e.forward; e.insert(s); e.backward elsif c == "c" then e.delete; e.insert(s); e.backward elsif c == "g" then e.goto(s.to_i) else e.forward; e.print 8

9 8 Node Le(<=) if while read print read print class Le < Node def initialize(l, r) = <= def exec() return then 1 else 0 e # Lt(<), Gt(>), Ge(>=), Eq(==), Ne(!=) class If < Node def initialize(l, r) = I def exec() 0 class While < Node def initialize(l, r) = W def exec() 0 class Read < Node def initialize() = R def exec() print > ; return gets.to_i class Print < Node def initialize(l) = P def exec() puts(@left.exec) 9

10 8 def test2 e = Seq.new( Assign.new(Var.new( n ), Read.new), Seq.new( Assign.new(Var.new( i ), Lit.new(2)), While.new( Le.new(Var.new( i ), Var.new( n )), Seq.new( puts(e) Assign.new(Var.new( k ), Lit.new(2)), Seq.new( Assign.new(Var.new( sosu ), Lit.new(1)), Seq.new( While.new( Lt.new(Var.new( k ), Var.new( i )), Seq.new( If.new(Eq.new(Mod.new(Var.new( i ), Var.new( k )), Li Assign.new( sosu, Lit.new(0))), Assign.new(Var.new( k ), Add.new(Var.new( k ), Lit.ne Seq.new( return e.exec If.new(Ne.new(Var.new( sosu ), Lit.new(0)), Print.new( Assign.new(Var.new( i ), Add.new(Var.new( i ), Lit.new 10

11 8 irb> test2 ((n=(r));((i=2);((i<=n)w((k=2);((sosu=1);(((k<i)w((((i%k)==0)i( (k=(k+1))));(((sosu!=0)i(ip));(i=(i+1))))))))) > => nil irb> 11

12 8? Ruby ( ) ( ) ( ) ( 1) 1 def p(x) x* : 1 12

13 (abstract data type ADT) (Ruby ) (stack) LIFO(last-in, first-out) ( ) ( ) / push/pop ( 2 ) push pop top array A B C C B A top: C B A 2: 1 push ( 2 ) top push top pop 1 13

14 Ruby push/pop 1 ( 2 ) : class Stack1 def = = -1 def isempty() < 0 def += = x def pop() -= 1; return x 14

15 : irb> s = Stack1.new... irb> s.push(1) => 1 irb> s.push(2) => 2 irb> s.push(3) => 3 irb> s.isempty => false irb> s.pop => 3 irb> s.pop => 2 irb> s.push(4) => 4 irb> s.push(5) => 5 irb> s.pop => 5 irb> s.pop => 4 irb> s.pop => 1 irb> s.isempty => true 15

16 (queue) ( ) FIFO(fist-in, first-out) ( ) / enq/deq (3 ) enqueue dequeue C D E enq deq array optr top: D E C E D C iptr J I H iptr optr K last top: E D F last 3: iptr optr 2 ( 3 ) (circular buffer) (ring buffer) 16

17 / ipt opt 1 2 last ( 3 ) (top null last ( 1 ) : class Queue1 def = def isempty() <= 0 def = = += 1 def deq() = -= 1; 2 17

18 : irb> q = Queue1.new... irb> q.enq(1) => 1 irb> q.enq(2) => 2 irb> q.isempty => false irb> q.deq => 1 irb> q.enq(3) => 2 irb> q.enq(4) => 3 irb> q.deq => 2 irb> q.deq => 3 irb> q.deq => 4 irb> q.isempty => true 1 18

19 (table) (key) 0 N a[99] = abc... # a[99]... # 99 0 N key kuno saito... val : 2 put get Ruby ( ) def []=(k,v)... k v... def [](k)... k 19

20 (entry) ( 5) ( ) kuno saito hata okano : TableEntry1 = Struct.new(:key, :val) class Table1 def = [] def do e if e.key == k then return e.val return nil def []= do e if e.key == k then e.val = v; v)) 20

21 irb> t1 = Table1.new => irb> t1[ kuno ] = 20 => 20 irb> t1[ okano ] = 44 => 44 irb> t1[ kuno ] => 20 irb> require pp => true irb> pp t1 # pp [#<struct TableEntry1 key="kuno", val=20>, #<struct TableEntry1 key="okano", val=44>]> => nil ( ) (search) (linear search) n O(n) 21

22 2 3 2 (binary search tree) 2 (2 ) ( 6) : 2 ( ) ( ) O(logn) 3 total order 22

23 2 TableEntry2 = Struct.new(:key, :val, :left, :right) class Table2 def = nil def [](k) == nil then return nil == k then > k then else def []=(k,v) == = TableEntry2.new(k,v) == = v > k == nil = = v else == nil = = v nil 23

24 2 nil N 1 N N bench 0 N 1 t = Table1.new # Table2.new Array.new(10000) bench(10000) do x = rand(10000); t[x] = x #1 3 2 ( ) 24

25 Ruby Hash (associative array) Perl JavaScript Python Ruby Perl (hash table) Ruby ( ) Hash.new( ) ( nil) { =>, =>,... } ( ) h = {1 => "abc", 8 => "xyz", 3 => "a"} h = {"abc" => 3, "def" => "u"} h = { } # Hash.new(nil) O(1) 25

26 0 N 1 i = hash( ) hash ( ) 0 N ( 7) hash hash ( ) O(1) saito 30 kuno hash saito hash kuno 20 7: 4 26

27 1 hash ( ) 2 hash (collision) 2 5 ( 50%) 4 ( ) Ruby 5 1 d = hash2( ) d d 27

28 ? ( ) 1 (2 ) 8: ( )

29 Ruby def prepare $graph = Hash.new() cn(" ", " "); cn(" ", " "); cn(" ", " ") cn(" ", " "); cn(" ", " "); cn(" ", " ") cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " ") cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " "); cn(" ", " ") Node1 = Struct.new(:name, :arr, :path) def cn(name1, name2) if $graph[name1] == nil then $graph[name1] = Node1.new(name1, if $graph[name2] == nil then $graph[name2] = Node1.new(name2, $graph[name1].arr.push($graph[name2]) $graph[name2].arr.push($graph[name1]) prepare $graph cn arr( ) path nil 29

30 A B ( ) 1 def traverse1(start, goal) s = Stack1.new; n = $graph[start]; n.path = [start]; s.push(n puts("start: #{start}") while!s.isempty do n = s.pop n.arr.each do m if m.path == nil m.path = n.path.dup; m.path.push(m.name) puts("#{m.name}: #{m.path.join(, )}") if m.name == goal then return else s.push(m) 0 1 (path nil ) 7 7 dup join 30

31 def test1 prepare; traverse1(, ) irb> test1 START: :, :, :, :, :,, :,,, => nil 4 ( push/pop enq/deq ) irb> test2 START: :, :, :, :,, :,, :,, :,,, => nil 31

32 ? LIFO 9 (depth first search) FIFO ( ) 9: ( )

33 7 2 A B B 1 B 1 pop A push 1 A 1 pop B push B 1 pop A 1 push 33

34 (context) (state) x + 1 x (state transition) ( ) 34

35 (game) (puzzle) 1 ( ) ( / ) 1 ( ) ( ) (state space search) 35

36 10: ( ) 10 ( ) 9 (1) (2) (3) = / / 2 36

37 ( ): s = ; s.mark; stack.push(s) while!stack.isempty do s = stack.pop (s ) do s1 if s1.isgoal then! elsif!s.ismarked then s1.mark; stack.push(s1)! ( ) mark ismarked 37

38 : 11 11: ( 1 ) (0 9 ) 1 ( ) : $hmax = 3; $vmax = 4; $goalx = 1; $goaly = 3 $hsize = [2, 1, 1, 1, 1, 2, 1, 1, 1, 1] $vsize = [2, 2, 2, 2, 2, 1, 1, 1, 1, 1] $names = Mvvvvwssss. 38

39 : 9 (X Y 9 ) 2 makeboard : def makeboard(x, y) b = Array.new($vmax+1) do Array.new($hmax+1, -1) $hsize.length.times do i $hsize[i].times do j return b $vsize[i].times do k b[y[i]+k][x[i]+j] = i -1( ) 2 39

40 : b i x,y dx,dy movable : def movable(b, i, x, y, dx, dy) if x+dx < 0 x+$hsize[i]-1+dx > $hmax y+dy < 0 y+$vsize[i]-1+dy > $vmax then return false $hsize[i].times do j $vsize[i].times do k p = b[y+dy+k][x+dx+j]; if p!= -1 && p!= i then return false return true NO -1( ) NO OK 1 State 9 XY 1 initailze dup 40

41 : getx gety isgoal 0 move i dx,dy (self ) ( dup ): class State def initialize(x, @prev = p def getx() def gety() def isgoal() == $goalx == $goaly def move(i, dx, dy; s = dy; return s def to_s() s = do a a.each do i s = s + $names[i..i] ; s = s + "\n" return s def output(f) nil f.puts(to_s); f.puts( ) 41

42 : to s makeboard 1 1 output main Ruby x y visited 1 ( ) ( ) : 42

43 : def main x = [1,0,3,0,3,1,0,1,2,3]; y = [0,0,0,2,2,2,4,3,3,4] stack = [State.new(x,y)]; visited = {stack[0].to_s => true} while true do if stack.length == 0 then puts("impossible."); return false s = stack.pop puts(s.to_s); puts( ---- ) if s.isgoal then break # or s = stack.shift x = s.getx; y = s.gety; b = makeboard(x, y) $hsize.length.times do i [[1,0],[-1,0],[0,1],[0,-1]].each do a if movable(b, i, x[i], y[i], a[0], a[1]) s1 = s.move(i, a[0], a[1]); k1 = s1.to_s if visited[k1] == nil then stack.push(s1); visited[k1 File.open( out.data, w ) do f s.output(f) return true out.data : 43

44 : irb> main vmmv vmmv vwwv vssv s..s ---- vmmv vmmv vwwv vssv s.s vmmv vmmv vwwv vssv ss ( ) vvvv vvvv ssww MM.s MM.s ---- vvvv vvvv ssww 44

45 .MMs.MMs ---- => true stack.pop stack.shift ( stack )

46 10A 1. Subject: Report 10A Q1. Q2. Q3. 46

47 10B + Report 10B 47

r10.dvi

r10.dvi 2015 10 2015.12.7 1 ( ) 2 2.1 2 : def delete if at then return @cur = @prev.next = @cur.next (1) EOF (2)@cur 1 (3)@prev 1 : def exch if at @cur.next == @tail then return a = @prev; b = @cur.next; c = @cur;