Read sections 3.1-3.8 in chapter 3 and sections 4.1-4.2 in chapter 4 of the textbook Explorations in Computing.
def lcm(x,y) p = x * y while y != 0 do temp = y y = x % y x = temp q = p / x end return q end
Show how this function computes lcm(45,60) by creating a table that shows the values of each variable at the end of each iteration of the loop. We have started the table for you with the initial values of the variables before the first iteration of the loop:
===================================== x y temp p q ===================================== 45 60 --- 2700 --- =====================================
def lcm(x, y) return lcm2(x, y, x, y) end def lcm2(x, y, a, b) if (a == b) then return a end if (a < b) then return lcm2(x, y, a+x, b) else # otherwise, a > b return lcm2(x, y, a, b+y) end end
Show how lcm(45,60) is computed recursively here by showing the chain of recursive calls that are made until an answer is found. We have started the chain for you below:
lcm(45, 60) --> lcm2(45, 60, 45, 60) --> lcm2(45, 60, 90, 60) -->
def findmax(list) max_so_far = list[0] for i in (1..list.length-1) do if list[i] > max_so_far then max_so_far = list[i] end end return max_so_far end
HINT: Instead of keeping track of the maximum so far, keep track of the index of the maximum so far.
list.delete_if { |item| item == findmax(list) }
What is wrong with this computation? Explain with an example.
scores.each{ |x| if x / 10 == 7 then print x print "\n" end }
scores.delete_if { |x| x / 10 == x % 10 }
def sieve(n) numlist = Array(2..n) primes = [] while numlist.length > 0 do primes << numlist.first numlist.delete_if { |x| x % primes.last == 0 } end return primes end
def sieve2(n) numlist = Array(2..n) primes = [] while numlist.first < Math.sqrt(n) do primes << numlist.first numlist.delete_if { |x| x % primes.last == 0 } end return primes + numlist end
The return statement returns an array containing the values in primes followed by the values in numlist. Briefly explain why we need to do this.
def search(list, key) index = 0 while index < list.length do if list[index] == key then return index end index = index + 1 end return nil end
Suppose that we know the additional fact that the list is sorted in non-decreasing order (this means that list[i] ≤ list[i+1], for 0 ≤ i < list.length-1). For example, if our list has the values:
[25, 37, 45, 61, 73, 79, 82, 94]
then if we want to search for the key 50 using linear search, we can stop when we reach 61 and return nil (assuming that the list is sorted).
def sorted?(list) end
HINT: Set up a loop to compare list[i] with list[i+1]. If you ever get two neighboring elements that are not in non-decreasing order, then the whole list cannot be sorted. Be careful with the range you use for i.