Mülakat Sorusu: M1 Merdivenleri

M1'in yürüyen merdivenlerinde hafifçe yükselirken aklınıza bir soru geliyor:

Acaba n basamaklı bir merdiveni her seferinde 1 veya 2 basamak çıkarak kaç farklı biçimde çıkabilirim?

DİLEDİĞİNİZ DİLDE KOD YAZARAK ÇÖZEBİLİRSİNİZ.

Kaynak: imlec.io

Örnekler

Girdi (Input)

n = 2

Çıktı (Output)

2

Açıklama

2 basamaklı bir merdiven 2 farklı biçimde çıkılabildiğinden çıktı 2 olur.

• 1 Adım + 1 Adım
• 2 Adım

Girdi

n = 3

Çıktı

3

Açıklama

3 basamaklı bir merdiven 3 farklı biçimde çıkılabildiğinden çıktı 3 olur.

• 1 Adım + 1 Adım + 1 Adım
• 1 Adım + 2 Adım
• 2 Adım + 1 Adım

n=100 için yanıt kaç olur?

Dikkat arkadaşlar, kod yazarak çözmelisiniz. :)

İstediğiniz dili seçebilirsiniz.

KAYNAK

https://imlec.io

Dynamic programming konusunun giriş seviyesi problemlerinden.

#include <iostream>

using namespace std;

int count(int x) {

  int dp[x + 1];

  dp[0] = 1;

  dp[1] = 1;   

  for(int i = 2; i <=x; i++){

    dp[i] = dp[i - 1] + dp[i - 2];

  }

  return dp[x];

}

int main() {

  int x;

  cin >> x;

  int ans = count(x);

  cout << ans << '\n';

return 0;

}

Sonuç da fibonacci serisi çıkıyor bu problem için.

Edit : 100. sayı için 64 bit int de yetmiyor, 128 bit int veri tipine bakmak lazım.

Veya sayıların basamaklarını linked listte tutup toplama yapılabilir.