Minimal steps down to 1: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Less verbose output) |
(Added Go) |
||
Line 48: | Line 48: | ||
* [https://www.youtube.com/watch?v=f2xi3c1S95M Learn Dynamic Programming (Memoization & Tabulation)] Video of similar task. |
* [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}}== |
=={{header|Perl 6}}== |