We don't bite newbies here... much PerlMonks

### Re: Triangle Numbers Revisited

by Limbic~Region (Chancellor)
 on Oct 14, 2004 at 20:49 UTC ( #399335=note: print w/replies, xml ) Need Help??

in reply to Triangle Numbers Revisited

All,
I was having a conversation with blokhead in the CB concerning the most efficient solution to this problem. Not having any idea how to determine the big O notation, I ran a few tests to see how well my solution scaled.

The first thing I noticed was the average number of guesses doubled every time I increased the search group by a factor of 10. Then I noticed something really cool - it also corresponded to a power of 2. This allowed me to calculate the average case scenario for any number

```#!/usr/bin/perl
use strict;
use warnings;

my \$num       = \$ARGV[0] || 47;
my \$length    = length \$num;
my \$base      = 10 ** (\$length - 1);
my \$base_ave  = 2  ** (\$length - 1);
my \$next      = 10 ** \$length;
my \$next_ave  = 2  ** \$length;
my \$ave_diff  = \$next_ave - \$base_ave;
my \$tot_diff  = \$next     - \$base;
my \$distance  = \$num - \$base;
my \$guess     = \$base_ave + (\$distance * \$ave_diff) / \$tot_diff;
print "\$guess\n";

So for 12_345 you can expect 16.42, and for 123_456_789 you can expect 262.67 As you can see this scales quite well. While this is the average case, the worst case scenario should still scale reasonably well.

Cheers - L~R

Create A New User
Node Status?
node history
Node Type: note [id://399335]
help
Chatterbox?
 choroba waits [thepkd]: \$aohoaoh ->{'foo'} has to be dereferenced to access its contents right? [thepkd]: sorry. i mean \$aohoaoh[0] [GotToBTru]: \$aohoaoh is an array reference tho [thepkd]: some guy was suggesting \$aohoaoh[0]->{'foo '}[0]->{}. This wouldnt work. [GotToBTru]: you're mixing notation there I think [GotToBTru]: \$aohoaoh->[0] is a hash reference, so \$aohoaoh->[0]->{ key1} would work

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (11)
As of 2016-12-06 13:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
On a regular basis, I'm most likely to spy upon:

Results (104 votes). Check out past polls.