Re: Recursion
DB James wrote:
>
> Al Getz wrote:
> >
> > Al Getz wrote:
> > >
> > > DB James wrote:
> > > >
> <SNIP>
> > > > --Quark
> > >
> > >
> > > When i was around 12 or 13 years old i found a way to solve the 8 queens
> > > problem in my head. This might sound like a big deal to some people,
> > > but actually it wasnt that hard because i found a quick way to do it
> > > using another number base system. Anyone can do it using this method.
> > > Of course i still think it's a good way to show how computer algos
> > > work though, any way you decide to solve it.
> > >
> > > Here's a hint...
> > > The number base system is base 8, and each board column is thought of as
> > > a power of 8.
>
> Al, are you trying to cause insomnia due to chess boards dancing in
> programmer's heads with that "hint? 
>
> > > > - Sometimes it is almost spooky in its effectiveness.
> > >
> > > Spooky you say?
> > > With the algorithm i was talking about in my previous post (the one
> > > that had to calculate something to high accuracy) it was perhaps the
> > > first time i saw something that actually resembled emergence on the
> > > computer! The solution set seemed to 'emerge' from the input data,
> > > and it's so darn accurate it is almost impossible to believe without
> > > seeing; really almost spookie.
> > > One little function that can call itself...so little code, such a
> > > big problem solved!
> > >
> That is just the kind of thing I meant -- where a small amount of code gives
> big and often complex results. Some 8 queens solvers show the "backing out"
> of unproductive paths and going on to other possibilities.
>
> > > Al
> >
> > Hello again,
> >
> >
> > I guess i should have also mentioned that for many chess players
> > the 8 queens problem isnt that hard for them to solve given 8
> > queens and a regular chess board. But this is not my main
> > reason for posting again...
> >
> > > Spooky you say?
> > The algo i was talking about achieved quite a bit of extra functionality
> > from being able to call itself, and only a few tests were required
> > within the function to make the decisions to either call itself again
> > or call the long calculation routine again or exit. Just doing this
> > meant that the algo could follow the solution and break it into
> > smaller and smaller pieces if necessary, and the way this occurs makes
> > it seem as if it almost 'knows' what to do. It is able to 'adapt'
> > quite well to the input data, doing the same thing over and over
> > possibly going deeper and deeper into the problem until a solution is
> > found.
> >
> > The beginnings of some sort of A.I. perhaps...
> > "I Recursion": Think about what you are thinking about when you
> > think about something--same thing. We solve problems by thinking
> > about something over and over until a solution emerges.
> >
>
> I have an old programming notion that has been helpful to me of the "blind
> bloodhound" who can't see, but he always knows where he's been...
>
> > And adaptability...
> > I had begun to think about the Eu sequence as a bit of an evil, because
> > of the problems it can bring, not only to the programmer, but to the
> > operating system that has to deal with a complex data structure like
> > that when there is a lot of data. It's the data equivalent of the
> > 'goto' statement, where it works just fine with a small (or medium)
> > data set, but as soon as the data becomes large problems pop up,
> > just as a large program with many goto's presents a program maintenance
> > problem.
>
> Poo.
>
> > But then there is the counter point,
> > in that the sequence is the ultimate adaptable data structure, so there
> > may be a place in the future for it after all.
> >
> >
> > Al
> >
> This may be a place to stick something that I (and many others) read of
> long ago and I'm not sure if I translated it from C or if I just got the
> idea from one of Nelson Dewdney's writings... It is the binary search tree.
> Some of the comment lately was on linked lists which reminded me of good old
> recursion, so I cobbled together the following from memory. I haven't tested
> it, so it could well have mistakes:
>
> }}}
<eucode>
> -- binary search tree in Euphoria
> -- the data sequence will expand as it needs to
> -- can be used to create a dictionary of words
>
> constant WORD=1,NUM=2,LEFT=3,RIGHT=4
> constant UNIT={"",0,0,0}
>
> global sequence data
> data={{"mean",0,0,0}} --to start, provide one "mid" word, but NUM is 0
>
> procedure StoreTree(sequence word,integer loc)
> integer cmpr,link
> cmpr=compare(word,data[loc][WORD])
> if cmpr=0 then --word exists, add to count
> data[loc][NUM]+=1
> elsif cmpr=-1 then --if word is less
> if not data[loc][LEFT] then -- create new node
> data=append(data,UNIT)
> link=length(data)
> data[loc][LEFT]=link
> data[link][WORD]=word
> data[link][NUM]+=1
> else -- recursively follow the tree
> Store(word,data[loc][LEFT])
> end if
> else -- if word is greater
> if not data[loc][RIGHT] then -- create new node
> data=append(data,UNIT)
> link=length(data)
> data[loc][RIGHT]=link
> data[link][WORD]=word
> data[link][NUM]+=1
> else -- recursively follow the tree
> Store(word,data[loc][RIGHT])
> end if
> end if
> end procedure
>
> --from a stream of words, call Store():
> --word=NextFromStream()
> --StoreTree(word,1)
> </eucode>
{{{
>
> Anyway, it is something like that, and it does use recursion to "follow its
> nose" and the algorithm is quite happy to use sequences...
>
> --Quark
Hi DB,
Im not saying you shouldnt use them, just pointing out a few
things about them. I use them all the time
Take care,
Al
E boa sorte com sua programacao Euphoria!
My bumper sticker: "I brake for LED's"
From "Black Knight":
"I can live with losing the good fight,
but i can not live without fighting it".
"Well on second thought, maybe not."
|
Not Categorized, Please Help
|
|
