Boyuttaki bitişik alt dizilerin sayısını nasıl bulursunuz? $k$ belirli bir dizide?

Question

Örneğin: Dizi verildiğinde $[1,2,3,4,5,6,7,8,9]$ nerede $N$ dizinin uzunluğu ve $k$alt dizi boyutudur. Buraya$N = 9$ ve verilen $k = 5$, onu bulduk $N-k+1$ bitişik boyut alt dizileri $k$bulunabilir. Nasıl kanıtlayabiliriz$N-k+1$ boyutun bitişik alt dizilerinin sayısı olarak $k$? Eminim sezgiseldir, ama kafamı dolanamıyorum.

Answer 1

Genel bir değer için cevaba bakmak yerine $k$hadi belirli örneklere bakalım.

Her şeyden önce, kaç tane uzunlukta alt dizi vardır? Bu sorunun cevabı$n$. Neden? Çünkü şunlardan herhangi birini seçebiliriz$n$ dizimizdeki öğeler.

Sonra, iki uzunluğunda kaç tane alt dizi var? Bu sorunun cevabı$n - 1$. Neden? Çünkü şunlardan herhangi birini seçebiliriz$n$dizinin "başlangıcı" olan son öğe haricindeki öğeler (ve hemen ardından gelen öğe de dahil edilecektir). Daha sonra eklenecek bir öğe olmadığından diziyi son öğeden "başlatamayacağımızı" unutmayın.

Aynı mantıkla devam edersek, uzunluk alt dizileri için cevabın $k$ olmalıdır $n - (k - 1) = n - k + 1$ diziyi sonuncusu dışında herhangi bir yerde "başlatabildiğimiz" için $k - 1$ pozisyonlar.