Как считать простые пути, ограниченные ± 1 или ± 2 шага?
Я предполагаю, что если вы восстанавливаете db, вам не нужны никакие существующие транзакции на этом db. Правильно? Если это так, это должно сработать для вас:
USE master
GO
ALTER DATABASE AdventureWorksDW
SET SINGLE_USER
--This rolls back all uncommitted transactions in the db.
WITH ROLLBACK IMMEDIATE
GO
RESTORE DATABASE AdventureWorksDW
FROM ...
...
GO
Теперь вам нужно запомнить еще один предмет. После того, как вы установите db в однопользовательский режим, кто-то другой может попытаться подключиться к db. Если они преуспеют, вы не сможете продолжить восстановление. Это гонка! Мое предложение состоит в том, чтобы сразу запускать все три заявления.
1 ответ
Рассмотрим используемые пробелы.
0 1 2 3 4 5 6
^
Чтобы получить число справа, необходимо использовать ячейку перед ее использованием. Следовательно, все способы заканчиваться x, идущими слева, не могут включать числа справа. И все способы заканчиваться x, идущими справа, использовали x-1 и набор движений справа от x не пересекаются с левой стороны.
Пусть f(A, x) = l(A, x) + r(A, x), где l(A, x) представляет все пути окончания в точке x, идущие слева; r(A, x), идущий справа.
Чтобы получить l(A, x), нам нужно:
(1) all ways to reach (x-1)
= l(A, x-1)
(there are no numbers used to
the right of x, and since
x is used last, we could not
have reached x-1 from the right.)
(2) all ways to reach (x-2):
cleary we need l(A, x-2). Now
to reach (x-2) from the right,
the only valid path would have
been ...(x-3)->(x-1)->(x-2)
which equals the number of ways
to reach (x-3) from the left.
= l(A, x-2) + l(A, x-3)
Чтобы получить r(A, x), нам нужно:
(1) all ways to reach (x+1) so as
to directly go from there to x
= l(A, x-1)
(We can only reach (x+1) from (x-1).)
(2) all ways to reach (x+2) after
starting at (x+1)
= l(A, x-1) * f(A[x+1...], 1)
(To get to the starting point in
A[x+1...], we must first get to
(x-1).)
Так что, похоже,
f(A, x) = l(A, x) + r(A, x)
l(A, x) =
l(A, x-1) + l(A, x-2) + l(A, x-3)
r(A, x) =
l(A, x-1) + l(A, x-1) * f(A[x+1...], 1)
f(_, 1), обратите внимание, что l(_, 1) = 1).
function f(A, x){
if (x < 0 || x > A.length - 1)
return 0
return l(A, x) + r(A, x)
function l(A, x){
if (x < 0 || x > A.length - 1)
return 0
if (x == 0)
return 1
let result = l(A, x-1)
if (A[x-2] && A[x-2] == 2){
result += l(A, x-2)
if (A[x-3] && A[x-3] == 2)
result += l(A, x-3)
}
return result
}
function r(A, x){
if (x < 0 || x >= A.length - 1 || !(A[x-1] && A[x-1] == 2))
return 0
let result = l(A, x-1)
if (A[x+2] && A[x+2] == 2)
result += l(A, x-1) * f(A.slice(x+1), 1)
return result
}
}
function validate(A){
let n = A.length
function g(i, s){
if (debug)
console.log(s)
let result = 1
let [a, b] = [i+1, i-1]
if (a < n && !s.includes(a))
result += g(a, s.slice().concat(a))
if (b >= 0 && !s.includes(b))
result += g(b, s.slice().concat(b))
if (A[i] == 2){
[a, b] = [i+2, i-2]
if (a < n && !s.includes(a))
result += g(a, s.slice().concat(a))
if (b >= 0 && !s.includes(b))
result += g(b, s.slice().concat(b))
}
return result
}
return g(0, [0])
}
let debug = false
let arr = []
let n = 7
for (let i=0; i<n; i++)
arr[i] = Math.ceil(Math.random() * 2)
console.log(JSON.stringify(arr))
console.log('')
let res = 0
for (let x=0; x<arr.length; x++){
let c = f(arr, x)
if (debug)
console.log([x, c])
res += c
}
if (debug)
console.log('')
let v = validate(arr)
if (debug)
console.log('')
console.log(v)
console.log(res)