Anonymous user
Minimal steps down to 1: Difference between revisions
Add swift
(Add swift) |
|||
Line 1,613:
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|Swift}}==
{{trans|Python}}
<lang swift>func minToOne(divs: [Int], subs: [Int], upTo n: Int) -> ([Int], [[String]]) {
var table = Array(repeating: n + 2, count: n + 1)
var how = Array(repeating: [""], count: n + 2)
table[1] = 0
how[1] = ["="]
for t in 1..<n {
let thisPlus1 = table[t] + 1
for div in divs {
let dt = div * t
if dt <= n && thisPlus1 < table[dt] {
table[dt] = thisPlus1
how[dt] = how[t] + ["/\(div)=> \(t)"]
}
}
for sub in subs {
let st = sub + t
if st <= n && thisPlus1 < table[st] {
table[st] = thisPlus1
how[st] = how[t] + ["-\(sub)=> \(t)"]
}
}
}
return (table, how.map({ $0.reversed().dropLast() }))
}
for (divs, subs) in [([2, 3], [1]), ([2, 3], [2])] {
print("\nMINIMUM STEPS TO 1:")
print(" Possible divisors: \(divs)")
print(" Possible decrements: \(subs)")
let (table, hows) = minToOne(divs: divs, subs: subs, upTo: 10)
for n in 1...10 {
print(" mintab( \(n)) in { \(table[n])} by: ", hows[n].joined(separator: ", "))
}
for upTo in [2_000, 50_000] {
print("\n Those numbers up to \(upTo) that take the maximum, \"minimal steps down to 1\":")
let (table, _) = minToOne(divs: divs, subs: subs, upTo: upTo)
let max = table.dropFirst().max()!
let maxNs = table.enumerated().filter({ $0.element == max })
print(
" Taking", max, "steps are the \(maxNs.count) numbers:",
maxNs.map({ String($0.offset) }).joined(separator: ", ")
)
}
}</lang>
{{out}}
<pre>MINIMUM STEPS TO 1:
Possible divisors: [2, 3]
Possible decrements: [1]
mintab( 1) in { 0} by:
mintab( 2) in { 1} by: /2=> 1
mintab( 3) in { 1} by: /3=> 1
mintab( 4) in { 2} by: /2=> 2, /2=> 1
mintab( 5) in { 3} by: -1=> 4, /2=> 2, /2=> 1
mintab( 6) in { 2} by: /3=> 2, /2=> 1
mintab( 7) in { 3} by: -1=> 6, /3=> 2, /2=> 1
mintab( 8) in { 3} by: /2=> 4, /2=> 2, /2=> 1
mintab( 9) in { 2} by: /3=> 3, /3=> 1
mintab( 10) in { 3} by: -1=> 9, /3=> 3, /3=> 1
Those numbers up to 2000 that take the maximum, "minimal steps down to 1":
Taking 14 steps are the 16 numbers: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943
Those numbers up to 50000 that take the maximum, "minimal steps down to 1":
Taking 22 steps are the 3 numbers: 25919, 31103, 38879
MINIMUM STEPS TO 1:
Possible divisors: [2, 3]
Possible decrements: [2]
mintab( 1) in { 0} by:
mintab( 2) in { 1} by: /2=> 1
mintab( 3) in { 1} by: /3=> 1
mintab( 4) in { 2} by: /2=> 2, /2=> 1
mintab( 5) in { 2} by: -2=> 3, /3=> 1
mintab( 6) in { 2} by: /3=> 2, /2=> 1
mintab( 7) in { 3} by: -2=> 5, -2=> 3, /3=> 1
mintab( 8) in { 3} by: /2=> 4, /2=> 2, /2=> 1
mintab( 9) in { 2} by: /3=> 3, /3=> 1
mintab( 10) in { 3} by: /2=> 5, -2=> 3, /3=> 1
Those numbers up to 2000 that take the maximum, "minimal steps down to 1":
Taking 17 steps are the 1 numbers: 1699
Those numbers up to 50000 that take the maximum, "minimal steps down to 1":
Taking 26 steps are the 1 numbers: 45925</pre>
=={{header|Wren}}==
| |||