Eccoci.

Modi per salire una scala

In quanti modi si può salire una scala lunga $n$ gradini, potendo salire al massimo 2 scalini per volta? E salendone al massimo $k$ per volta?

Problema ispirato da https://plus.maths.org/content/its-long-way-top.

Soluzione

Partiamo dal caso in cui possiamo fare al massimo due scalini per volta. Chiamando $S(n)$ questo numero di modi in funzione di $n$, risulta che la soluzione è data da

perché moralmente come primo passo dobbiamo sempre fare un passo lungo 1 o lungo 2, indipendentemente da quanto la scala sia alta, e da quei passi poi possiamo osservare di fronte a noi una scala o alta $n-1$ o alta $n-2$ scalini, rispettivamente, e quindi riciclare i calcoli già fatti prima per le altre scale. Quindi è una formula ricorsiva, in cui i calcoli per $n$ più alti si appoggiano ai calcoli fatti per gli $n$ più bassi, dove come casi base abbiamo che una scala alta uno la possiamo salire in un solo modo, e quindi $S(1)=1$, mentre una scala alta due la possiamo salire in due soli modi, e quindi $S(2)=2$.

Mentre generalizzando il calcolo, supponendo cioè di avere un altro parametro $k$ che regola quanti scalini risuciamo a salire al massimo con un solo passo, la soluzione diventa

dove però ora i vari valori $S(n-i)$ si devono trovare in modi a volte meno ovvi. Per capire tutto, insieme ad una semplice idea per convertire il calcolo in codice eseguibile da un computer vi rimando naturalmente al video.

using Plots

function S(n,k)
	n==0 && return 0
	n==1 && return 1
	if n<k 
		return S(n,n)
	elseif n==k
		return S(n,k-1)+1
	else # n>k
		return sum(S(n-i,k) for i in 1:k)
	end
end

scale = 1:14
modi_1 = S.(scale,1)
modi_2 = S.(scale,2)
modi_3 = S.(scale,3)
modi_4 = S.(scale,4)
modi_5 = S.(scale,5)

plot(scale, modi_1, marker=:circle, line=:solid, label="k=1", legend=:left)
plot!(scale, modi_2, marker=:circle, line=:solid, label="k=2")
plot!(scale, modi_3, marker=:circle, line=:solid, label="k=3")
plot!(scale, modi_4, marker=:circle, line=:solid, label="k=4")
plot!(scale, modi_5, marker=:circle, line=:solid, label="k=5")

plot!(xticks=collect(scale))
xlabel!("Gradini")
ylabel!("Modi")
title!("Comparison of S(n, k) for different k values")

La scrittura della funzione in forma ricorsiva è utile, didattica, perché rispecchia la soluzione matematica che abbiamo trovato. Tuttavia, per una implementazione più efficiente c'è un altro modo, che al posto della ricorsione usa una tecnica un po' più avanzata (memoization) appartenente al mondo del "dynamic programming". L'idea è infatti che usando la ricorsione molti calcoli vengono ripetuti; in quest'altra versione invece i calcoli vengono salvati e riutilizzati.

function S_fast(n, k, memo=Dict{Tuple{Int, Int}, Int}())
	# casi base, come prima
	n==0 && return 0
	n==1 && return 1

	# se il risultato è stato già calcolato, ritornalo
	if haskey(memo, (n, k))
		return memo[(n, k)]
	end
	# altrimenti calcolalo...
	result = if n < k
		S(n, n, memo)
	elseif n == k
		S(n, k - 1, memo) + 1
	else
		sum(S(n - i, k, memo) for i in 1:k)
	end
	# ... e salvalo in memo
	memo[(n, k)] = result
	return result
end

julia> @time S(32,5)
 19.574231 seconds
1333610936

julia> @time S_fast(32,5)
  0.000019 seconds (58 allocations: 4.156 KiB)
1333610936