Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

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

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

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://399335]
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
Find Nodes?
    Voting Booth?
    On a regular basis, I'm most likely to spy upon:

    Results (104 votes). Check out past polls.