### Exercises -- finish as many of these as you can during class. # Write a function f(x,y) which # returns 0 if x is negative and less than y; or # returns 1 if x is non-negative and greater than y; or # returns 2 if x is equal to y; or # returns 3 otherwise def f(x,y) case when (x < 0 && x < y) then 0 when (x >= 0 && x > y) then 1 when (x == y) then 2 else 3 end end # Write function pow(x,y) which returns the number that is x to the y # power. Don't cheat and use a built-in function! def pow(x,y) if y == 0 then 1 else x*pow(x,y-1) end end # Write function filter(a,x) which removes all occurences of x from array a. # Try writing the functon without using Array.delete. # Try writing the function so it returns a new array instead of operating # in-place. def filter(a, x) idx = 0 while(a[idx]) do if a[idx] == x then a.delete_at idx else idx += 1 end end end # Write a program that prints the numbers from 1 to 100. But for multiples of # three print “Fizz” instead of the number and for the multiples of five print # “Buzz”. For numbers which are multiples of both three and five print # “FizzBuzz”. def fizzbuzz (1..100).each { |i| if i % 3 == 0 && i % 5 == 0 then puts "FizzBuzz" elsif i % 3 == 0 then puts "Fizz" elsif i % 5 == 0 then puts "Buzz" else puts i end } end def fizzbuzz1 (1..100).each { |i| case when i % 3 == 0 && i % 5 == 0 then puts "FizzBuzz" when i % 3 == 0 then puts "Fizz" when i % 5 == 0 then puts "Buzz" else puts i end } end # Write function fact(n) which returns n! (factorial). Try to make a # version using a for loop, a while loop, and as a recursive function. def fact(n) res = 1 for i in (1..n) res = res * i end return res end def fact1(n) result = 1 for i in (1..n) result *= i end result end def fact2(n) result = 1 while n >= 1 do result *= n n -= 1 end result end def fact3(n) if (n <= 1) then return 1 else return n*fact3(n-1) end end # Implement the square root function using Newton's method by repeatedly # applying the formula z = z - (z^2 - x) / 2z. Ie. initialize z to some value # (eg. 1.0), compute z - (z^2 - x) / 2z, and then compute it again with the # resulting value. Repeat this process "precision" times. def sqrt(x, precision) z = 1.5 while (precision > 0) z = z - (z*z - x) / (2*z) precision -= 1 end return z end def sqrt1(x, precision) z = 1.5 prev = 0 cutoff = 0.00000000001 total = precision while (precision > 0 && (prev - z).abs > cutoff) prev = z z = z - (z*z - x) / (2*z) precision -= 1 end puts "Total iterations: #{total - precision}" return z end #--------------------------------------------------------------------- # In all of the functions that follow, the argument es is a list # (array) of edges, where an edge is itself an array of size two. The # arguments n and m are nodes, which are simply natural numbers # (integers starting at 0). We interpret the edges as directed, so # that [0,1] is an edge going from (source node) 0 to (target node) # 1. # Write a function countsource(es,n) that returns an integer, counting # how often n is the source node (the first element of the pair) of # any edge appearing in es. For example: # countsource([[1,2],[2,3],[1,4],[4,5]], 1) returns 2 # countsource([[1,2],[2,3],[1,4],[4,5]], 2) returns 1 # countsource([[1,2],[2,3],[1,4],[4,5]], 6) returns 0 def countsource(es, n) res = 0 for i in (0...es.size) if es[i][0] == n then res = res + 1 end end return res end def countsource1(es, n) count = 0 es.each { |edge| count += 1 if edge[0] == n } count end # Write a function istarget(es,n) that returns a boolean indicating # whether n is the target node (the second element of the pair) of # any edge appearing in es. For example: # istarget([[1,2],[2,3],[1,4],[4,5]], 1) returns false # istarget([[1,2],[2,3],[1,4],[4,5]], 2) returns true # istarget([[1,2],[2,3],[1,4],[4,5]], 6) returns false def istarget(es,n) for i in (0...es.size) if es[i][1] == n then return true end end return false end def istarget1(es,n) es.each { |edge| return true if edge[1] == n } return false end # Write a function sourceedges(es,n) that returns an array of those # edges in es for which node n is the source node. For example: # sourceedges([[1,2],[2,3],[1,4],[4,5]], 1) returns [[1,2],[1,4]] # sourceedges([[1,2],[2,3],[1,4],[4,5]], 2) returns [[2,3]] # sourceedges([[1,2],[2,3],[1,4],[4,5]], 6) returns [] def sourceedges(es, n) res = [] for i in (0...es.size) if es[i][0] == n then res.push(es[i]) end end return res end def sourceedges1(es,n) source_arr = [] es.each { |edge| source_arr.push edge if edge[0] == n } source_arr end # Write a function reachable(es,n,m) that returns a boolean indicating # whether node m is reachable from node n, using the given list of # edges. As examples: # # reachable([[1,2],[2,3],[1,4],[4,5]], 4, 5) returns true # reachable([[1,2],[2,3],[1,4],[4,5]], 1, 3) returns true # reachable([[1,2],[2,3],[1,4],[4,5]], 1, 5) returns true # reachable([[1,2],[2,3],[1,4],[4,5]], 2, 5) returns false # reachable([], 1, 5) returns false # reachable(0, 1, 5) is a type error # # Don't worry about performance -- you haven't learned enough about Ruby # data structures to do a great job yet def reachable(es, n, m) esn = sourceedges(es,n) if esn == [] then return false else if istarget(esn,m) then return true else esrest = es - esn # to avoid cycles for i in (0...esn.size) if reachable(esrest,esn[i][1],m) then return true end end return false end end end def reachable1(es,n,m) edges = sourceedges1(es,n) visited = [] while (!edges.empty?) curr_edge = edges.shift if curr_edge[1] == m then return true end visited.push curr_edge sourceedges1(es,curr_edge[1]).each { |edge| if !(visited.include? edge) then edges.push edge end } end return false end def reachable2(es,n,m) return false if es.empty? edges = sourceedges1(es,n) return true if istarget(edges,m) remaining = es - edges edges.each { |edge| return true if reachable2(remaining,edge[1],m) } return false end