in reply to Triangle Numbers
i suggest using a bit vector for storage (see vec.) use one bit per number
to store whether it's triangular or not. i'll leave it as an excersize to figure out the details of my implementation.
Update: changes as per YuckFoo (below)#!/usr/bin/perl -w use strict; $|++; my $number = $ARGV[0] || die("Usage: trivec.pl number$/"); my $vecTri; $vecTri = createTriVec( $number ); print $/, findTriCombo( $vecTri, $number ); sub createTriVec { my $upper = $_[0] || 99; my $vec = "\0"; my $guess = 0; for( my $num = 1; $guess+$num <= $upper; $num++ ) { $guess+=$num; vec( $vec, $guess, 1 ) = 1; } return $vec; } sub findTriCombo { my $vec = $_[0] || return undef; my $num = $_[1] || return undef; my @tris; my $sum = 0; push(@tris, $num, 0, 0), return "@tris" if( vec( $vec, $num, 1 ) ) +; my $i = $num-1; while( $i > 0 ) { # print "<i $i>\t<s $sum>\t<t @tris>$/"; # UNCOMMENT TO SEE WHAT'S GOI +NG ON... if( scalar @tris >= 3 ) { $i = $tris[0] - 1; @tris = (); $sum = 0; } if( vec( $vec, $i, 1 ) ) { push @tris, $i; $sum += $i; $i = $num - $sum; next; } else { $i--; } } if( $sum == $num ) { push(@tris, 0) while @tris < 3; return "@tris"; } return "not found!"; }
Update 2: always returns an array of length three (below)
~Particle ;Þ
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Re: Triangle Numbers
by YuckFoo (Abbot) on Apr 24, 2002 at 19:36 UTC | |
by particle (Vicar) on Apr 24, 2002 at 19:48 UTC | |
by Anonymous Monk on Sep 26, 2002 at 03:45 UTC | |
by Anonymous Monk on Dec 08, 2005 at 04:15 UTC |
In Section
Cool Uses for Perl