[racket] Generative recursion

From: Jos Koot (jos.koot at telefonica.net)
Date: Fri Nov 5 07:05:50 EDT 2010

Actually there is one more way. We only have to check numbers 1 up to the
integer-sqrt of n. For each check whose remainder is 0, we immediately have
two divisors, the checking number and the quotient (except when these two
are equal, giving one divisor only -this happens only when n is a square-))
 
Jos
  _____  

From: users-bounces at racket-lang.org [mailto:users-bounces at racket-lang.org]
On Behalf Of Todd O'Bryan
Sent: 05 November 2010 10:31
To: lukejordan at gmail.com
Cc: users at racket-lang.org
Subject: Re: [racket] Generative recursion



There are really two ways of doing this problem. The way I'd probably use is
to make a list of all the *possible* divisors and then use the filter
function to pull out the actual divisors. 

The way you're probably thinking of requires a helper function for the
recursion, because you need to keep track of where you are in building up
the list. Back in the section on natural numbers, there are exercises to
create lists of numbers of varying types, for example:

; list-from-a-to-b: number number -> list-of-number

(check-expect (list-from-a-to-b 3 7) (list 3 4 5 6 7))

If you can figure out how to write this function, then you just need to
include a conditional to decide whether to add the next number into the list
you're creating or not.

Todd

On Wed, Nov 3, 2010 at 7:18 PM, Luke Jordan <luke.jordan at gmail.com> wrote:


I found implementing this trickier than grasping the solution as well.
Stick with it.  I don't see that you need any functions related prime
numbers.  Perhaps if input is prime that is a trivial case, but try to focus
on what the output is: A list of numbers that can evenly divide the input.
Those numbers are the numbers from 1 to input.  To think about how to get
that list, try solving it by hand.  If input is 3, how do you go about it?
Does 3 divide 3 with no remainder?  Yes, we know that numbers divide
themselves with no remainder.  How about 2? 1?  Try it over with larger
numbers, like 6 and 10.  What process are you using to determine whether the
numbers <= input and > 1 divide input with no remainder, and what happens to
them if do?  What happens if they do not?  When does evaluation cease?  When
it comes to a termination statement, don't forget that list and append are
different. 

Trying not to say too much, but hope I'm still saying something useful.

- Luke


On Wed, Nov 3, 2010 at 17:43, Ken Hegeland <hegek87 at yahoo.com> wrote:


I am trying to do the problem 26.1.1 in the book HTDP and I just feel like
the more I think about it, the more confused I get. I found a post from 2007
with some tips from Jens Axel Søgaard, the link is
http://objectmix.com/scheme/186349-htdp-generative-recursion.html.

I understand whats to be done, but Im just unsure how to accomplish the
task. I believe that trivially solvable in this case is n=1 and n=prime. For
n=1 the solution would be (list 1)
for n=prime Im thinking it should be (list 1 n), my function is similar to
the one on the link with a bit of different organization. When I read jens'
tips near the end I am getting confused.
The closest I can get to an answer is, (=(tabulate-div 20)(list 20 10 5 2
2))

>From the advice supplied, I was able to say that the smaller problems that
you split the program into are, one to get the largest divisor, and one
which gets the smallest divisor using the largest.

As far as template I am using what is supplied in the book. Im simply stuck,
and would love something to help me out, I will continue to run this problem
through my head and see what I can come up with.

Thanks in advance for any help.
	


_________________________________________________
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/users




_________________________________________________
 For list-related administrative tasks:
 http://lists.racket-lang.org/listinfo/users



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20101105/adf11be0/attachment.html>

Posted on the users mailing list.