Minimal steps down to 1: Difference between revisions
Added Go
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Less verbose output) |
(Added Go) |
||
Line 48:
* [https://www.youtube.com/watch?v=f2xi3c1S95M Learn Dynamic Programming (Memoization & Tabulation)] Video of similar task.
=={{header|Go}}==
<lang go>package main
import (
"fmt"
"strings"
)
const limit = 50000
var (
divs, subs []int
mins [][]string
)
// Assumes the numbers are presented in order up to 'limit'.
func minsteps(n int) {
if n == 1 {
mins[1] = []string{}
return
}
min := limit
var p, q int
var op byte
for _, div := range divs {
if n%div == 0 {
d := n / div
steps := len(mins[d]) + 1
if steps < min {
min = steps
p, q, op = d, div, '/'
}
}
}
for _, sub := range subs {
if d := n - sub; d >= 1 {
steps := len(mins[d]) + 1
if steps < min {
min = steps
p, q, op = d, sub, '-'
}
}
}
mins[n] = append(mins[n], fmt.Sprintf("%c%d -> %d", op, q, p))
mins[n] = append(mins[n], mins[p]...)
}
func main() {
for r := 0; r < 2; r++ {
divs = []int{2, 3}
if r == 0 {
subs = []int{1}
} else {
subs = []int{2}
}
mins = make([][]string, limit+1)
fmt.Printf("With: Divisors: %v, Subtractors: %v =>\n", divs, subs)
fmt.Println(" Minimum number of steps to diminish the following numbers down to 1 is:")
for i := 1; i <= limit; i++ {
minsteps(i)
if i <= 10 {
steps := len(mins[i])
plural := "s"
if steps == 1 {
plural = " "
}
fmt.Printf(" %2d: %d step%s: %s\n", i, steps, plural, strings.Join(mins[i], ", "))
}
}
for _, lim := range []int{2000, 20000, 50000} {
max := 0
for _, min := range mins[0 : lim+1] {
m := len(min)
if m > max {
max = m
}
}
var maxs []int
for i, min := range mins[0 : lim+1] {
if len(min) == max {
maxs = append(maxs, i)
}
}
nums := len(maxs)
verb, verb2, plural := "are", "have", "s"
if nums == 1 {
verb, verb2, plural = "is", "has", " "
}
fmt.Printf(" There %s %d number%s in the range 1-%d ", verb, nums, plural, lim)
fmt.Printf("that %s maximum 'minimal steps' of %d:\n", verb2, max)
fmt.Println(" ", maxs)
}
fmt.Println()
}
}</lang>
{{out}}
<pre>
With: Divisors: [2 3], Subtractors: [1] =>
Minimum number of steps to diminish the following numbers down to 1 is:
1: 0 steps:
2: 1 step : /2 -> 1
3: 1 step : /3 -> 1
4: 2 steps: /2 -> 2, /2 -> 1
5: 3 steps: -1 -> 4, /2 -> 2, /2 -> 1
6: 2 steps: /2 -> 3, /3 -> 1
7: 3 steps: -1 -> 6, /2 -> 3, /3 -> 1
8: 3 steps: /2 -> 4, /2 -> 2, /2 -> 1
9: 2 steps: /3 -> 3, /3 -> 1
10: 3 steps: -1 -> 9, /3 -> 3, /3 -> 1
There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
[863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943]
There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20:
[12959 15551 17279 18143 19439]
There are 3 numbers in the range 1-50000 that have maximum 'minimal steps' of 22:
[25919 31103 38879]
With: Divisors: [2 3], Subtractors: [2] =>
Minimum number of steps to diminish the following numbers down to 1 is:
1: 0 steps:
2: 1 step : /2 -> 1
3: 1 step : /3 -> 1
4: 2 steps: /2 -> 2, /2 -> 1
5: 2 steps: -2 -> 3, /3 -> 1
6: 2 steps: /2 -> 3, /3 -> 1
7: 3 steps: -2 -> 5, -2 -> 3, /3 -> 1
8: 3 steps: /2 -> 4, /2 -> 2, /2 -> 1
9: 2 steps: /3 -> 3, /3 -> 1
10: 3 steps: /2 -> 5, -2 -> 3, /3 -> 1
There is 1 number in the range 1-2000 that has maximum 'minimal steps' of 17:
[1699]
There is 1 number in the range 1-20000 that has maximum 'minimal steps' of 24:
[19681]
There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26:
[45925]
</pre>
=={{header|Perl 6}}==
| |||