Matrix chain multiplication: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (→{{header|Perl 6}}: simplified code to directly address the task specifications) |
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: show cost, as per task spec) |
||
| Line 543: | Line 543: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Perl 6}} |
{{trans|Perl 6}} |
||
<lang perl> |
<lang perl>use strict; |
||
use feature 'say'; |
|||
sub matrix_mult_chaining { |
|||
my(@dimensions) = @_; |
my(@dimensions) = @_; |
||
my(@cp,@path); |
my(@cp,@path); |
||
| Line 557: | Line 560: | ||
for my $step ($start .. $end - 1) { |
for my $step ($start .. $end - 1) { |
||
my $new_cost = $cp[$step][$start] |
my $new_cost = $cp[$step][$start] |
||
+ $cp[$end][$step + 1] |
|||
+ $dimensions[$start] * $dimensions[$step+1] * $dimensions[$end+1]; |
|||
if ($new_cost < $cp[$end][$start]) { |
if ($new_cost < $cp[$end][$start]) { |
||
$cp[$end][$start] = $new_cost; # cost |
$cp[$end][$start] = $new_cost; # cost |
||
| Line 567: | Line 570: | ||
} |
} |
||
find_path(0, $n-1, @cp); |
$cp[$n-1][0] . ' ' . find_path(0, $n-1, @cp); |
||
} |
} |
||
| Line 585: | Line 588: | ||
} |
} |
||
say matrix_mult_chaining(<1 5 25 30 100 70 2 1 100 250 1 1000 2>); |
|||
say matrix_mult_chaining(<1000 1 500 12 1 700 2500 3 2 5 14 10>);</lang> |
|||
{{out}} |
{{out}} |
||
<pre>((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12)) |
<pre>38120 ((((((((A1A2)A3)A4)A5)A6)A7)(A8(A9A10)))(A11A12)) |
||
(A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11))</pre> |
1773740 (A1((((((A2A3)A4)(((A5A6)A7)A8))A9)A10)A11))</pre> |
||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||