Minimal steps down to 1: Difference between revisions
Added Wren
(Added XPL0 example.) |
(Added Wren) |
||
Line 1,224:
Up to 50,000 found 1 number that requires at least 26 steps.
(45925) 26 steps: -2=>45923, -2=>45921, /3=>15307, -2=>15305, -2=>15303, /3=>5101, -2=>5099, -2=>5097, /3=>1699, -2=>1697, -2=>1695, /3=>565, -2=>563, -2=>561, /3=>187, -2=>185, -2=>183, /3=>61, -2=>59, -2=>57, /3=>19, -2=>17, -2=>15, /3=>5, -2=>3, /3=>1</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
<lang ecmascript>import "/fmt" for Fmt
var limit = 50000
var divs = []
var subs = []
var mins = []
// Assumes the numbers are presented in order up to 'limit'.
var minsteps = Fn.new { |n|
if (n == 1) {
mins[1] = []
return
}
var min = limit
var p = 0
var q = 0
var op = ""
for (div in divs) {
if (n%div == 0) {
var d = (n/div).floor
var steps = mins[d].count + 1
if (steps < min) {
min = steps
p = d
q = div
op = "/"
}
}
}
for (sub in subs) {
var d = n - sub
if (d >= 1) {
var steps = mins[d].count + 1
if (steps < min) {
min = steps
p = d
q = sub
op = "-"
}
}
}
mins[n].add("%(op)%(q) -> %(p)")
mins[n].addAll(mins[p])
}
for (r in 0..1) {
divs = [2, 3]
subs = (r == 0) ? [1] : [2]
mins = List.filled(limit+1, null)
for (i in 0..limit) mins[i] = []
Fmt.print("With: Divisors: $n, Subtractors: $n =>", divs, subs)
System.print(" Minimum number of steps to diminish the following numbers down to 1 is:")
for (i in 1..limit) {
minsteps.call(i)
if (i <= 10) {
var steps = mins[i].count
var plural = (steps == 1) ? " " : "s"
var mi = Fmt.v("s", 0, mins[i], 0, ", ", "")
Fmt.print(" $2d: $d step$s: $s", i, steps, plural, mi)
}
}
for (lim in [2000, 20000, 50000]) {
var max = 0
for (min in mins[0..lim]) {
var m = min.count
if (m > max) max = m
}
var maxs = []
var i = 0
for (min in mins[0..lim]) {
if (min.count == max) maxs.add(i)
i = i + 1
}
var nums = maxs.count
var verb = (nums == 1) ? "is" : "are"
var verb2 = (nums == 1) ? "has" : "have"
var plural = (nums == 1) ? "": "s"
Fmt.write(" There $s $d number$s in the range 1-$d ", verb, nums, plural, lim)
Fmt.print("that $s maximum 'minimal steps' of $d:", verb2, max)
System.print(" %(maxs)")
}
System.print()
}</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|XPL0}}==
| |||