Anonymous user
Minimal steps down to 1: Difference between revisions
→{{header|Phix}}
(Added C#) |
|||
Line 734:
There are 1 with 24 steps for start between 1 and 20000: [19681]
There are 1 with 26 steps for start between 1 and 50000: [45925]
</pre>
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Minimal_steps_down_to_1
use warnings;
no warnings 'recursion';
use List::Util qw( first );
use Data::Dump 'dd';
for ( [ 2000, [2, 3], [1] ], [ 2000, [2, 3], [2] ] )
{
my ( $n, $div, $sub ) = @$_;
print "\n", '-' x 40, " divisors @$div subtractors @$sub\n";
my ($solve, $max) = minimal( @$_ );
printf "%4d takes %s step(s): %s\n",
$_, $solve->[$_] =~ tr/ // - 1, $solve->[$_] for 1 .. 10;
print "\n";
printf "%d number(s) below %d that take $#$max steps: %s\n",
$max->[-1] =~ tr/ //, $n, $max->[-1];
($solve, $max) = minimal( 20000, $div, $sub );
printf "%d number(s) below %d that take $#$max steps: %s\n",
$max->[-1] =~ tr/ //, 20000, $max->[-1];
}
sub minimal
{
my ($top, $div, $sub) = @_;
my @solve = (0, ' ');
my @maximal;
for my $n ( 2 .. $top )
{
my @pick;
for my $d ( @$div )
{
$n % $d and next;
my $ans = "/$d $solve[$n / $d]";
$pick[$ans =~ tr/ //] //= $ans;
}
for my $s ( @$sub )
{
$n > $s or next;
my $ans = "-$s $solve[$n - $s]";
$pick[$ans =~ tr/ //] //= $ans;
}
$solve[$n] = first { defined } @pick;
$maximal[$solve[$n] =~ tr/ // - 1] .= " $n";
}
return \@solve, \@maximal;
}</lang>
{{out}}
<pre>
---------------------------------------- divisors 2 3 subtractors 1
1 takes 0 step(s):
2 takes 1 step(s): /2
3 takes 1 step(s): /3
4 takes 2 step(s): /2 /2
5 takes 3 step(s): -1 /2 /2
6 takes 2 step(s): /2 /3
7 takes 3 step(s): -1 /2 /3
8 takes 3 step(s): /2 /2 /2
9 takes 2 step(s): /3 /3
10 takes 3 step(s): -1 /3 /3
16 number(s) below 2000 that take 14 steps: 863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943
5 number(s) below 20000 that take 20 steps: 12959 15551 17279 18143 19439
---------------------------------------- divisors 2 3 subtractors 2
1 takes 0 step(s):
2 takes 1 step(s): /2
3 takes 1 step(s): /3
4 takes 2 step(s): /2 /2
5 takes 2 step(s): -2 /3
6 takes 2 step(s): /2 /3
7 takes 3 step(s): -2 -2 /3
8 takes 3 step(s): /2 /2 /2
9 takes 2 step(s): /3 /3
10 takes 3 step(s): /2 -2 /3
1 number(s) below 2000 that take 17 steps: 1699
1 number(s) below 20000 that take 24 steps: 19681
</pre>
| |||