Examkin

Soru

Zorluk: ZorÖzel Tanımlı İşlemler

Bir ff fonksiyonu, her nn pozitif tam sayısı için

f(1)=1f(1) = 1
f(2n)=f(n)+1f(2n) = f(n) + 1
f(2n+1)=f(n)f(2n+1) = f(n)

eşitliklerini sağlamaktadır.

Buna göre, f(x)=5f(x) = 5 eşitliğini sağlayan en küçük xx pozitif tam sayısı kaçtır?

  1. A
    20
  2. B
    24
  3. 16Cevap
  4. D
    31
  5. E
    32

Cevap

En küçük pozitif tam sayı 16'dır.
Soruda verilen fonksiyon kuralları incelendiğinde, fonksiyonun her adımda sayıyı 2'ye böldüğü (ikilik tabanda bir basamak sola kaydırdığı) görülür. Eğer sayı çift ise (2n2n formundaysa) fonksiyon değeri 1 artmakta, tek ise (2n+12n+1 formundaysa) değişmemektedir. Bu durum, fonksiyonun girdi olarak aldığı sayının ikilik tabandaki yazımındaki '0' rakamlarının sayısının 1 fazlasını verdiğini gösterir. f(x)=5f(x) = 5 olması için sayının ikilik gösteriminde 4 adet sıfır olmalıdır. Bu şartı sağlayan en küçük sayı 100002=1610000_2 = 16 değeridir.

Adım Adım Çözüm

1
Küçük değerler için fonksiyonun sonuçlarını hesaplayarak davranışı gözlemleyelim.
f(1)=1f(1) = 1, f(2)=f(1)+1=2f(2) = f(1) + 1 = 2, f(3)=f(1)=1f(3) = f(1) = 1, f(4)=f(2)+1=3f(4) = f(2) + 1 = 3, f(5)=f(2)=2f(5) = f(2) = 2, f(6)=f(3)+1=2f(6) = f(3) + 1 = 2, f(7)=f(3)=1f(7) = f(3) = 1, f(8)=f(4)+1=4f(8) = f(4) + 1 = 4 olarak bulunur.
Fonksiyonun kurallarındaki örüntüyü tespit etmek.
2
Elde edilen sonuçları, sayıların ikilik tabandaki (2'lik taban) yazımlarıyla karşılaştıralım.
1 sayısı 12  ⟹  f(1)=11_2 \implies f(1) = 1, 2 sayısı 102  ⟹  f(2)=210_2 \implies f(2) = 2, 3 sayısı 112  ⟹  f(3)=111_2 \implies f(3) = 1, 4 sayısı 1002  ⟹  f(4)=3100_2 \implies f(4) = 3, 8 sayısı 10002  ⟹  f(8)=41000_2 \implies f(8) = 4 olur.
İkilik tabandaki yazım ile fonksiyon çıktısı arasındaki ilişkiyi kurmak.
3
Fonksiyonun genel kuralını formüle edelim.
f(x)f(x) fonksiyonunun sonucu, xx sayısının ikilik tabandaki yazımında yer alan '0' rakamlarının sayısının 1 fazlasıdır. Dolayısıyla, f(x)=5f(x) = 5 olması için xx sayısının ikilik yazımında tam olarak 5−1=45 - 1 = 4 tane sıfır bulunmalıdır.
f(x)=5f(x) = 5 denklemini sağlayan koşulu belirlemek.
4
İkilik tabanda 4 adet sıfır içeren en küçük pozitif tam sayıyı bulalım.
En küçük değeri elde etmek için basamak sayısını en az tutmalıyız. İkilik tabanda en sol basamak 1 olmak zorundadır. Bu basamağın yanına 4 adet sıfır koyarak en küçük sayıyı 10000210000_2 olarak elde ederiz. Bu sayının onluk tabandaki karşılığı 24=162^4 = 16'dır.
Koşulu sağlayan en küçük sayının onluk tabandaki karşılığını hesaplamak.

Anahtar Kavram

Özyinelemeli kurallarla tanımlanmış fonksiyonların ikilik taban (binary) analiziyle çözülmesi.

Alternatif Yöntem

Fonksiyonun kuralları tersten gidilerek de analiz edilebilir. f(x)=5f(x) = 5 değerine ulaşmak için bir önceki adımda f(y)=4f(y) = 4 olmalıdır. En küçük sayı hedeflendiği için her adımda sayının 2 katı alınarak (yani çift sayı kuralı işletilerek) ilerlenir. f(1)=1→f(2)=2→f(4)=3→f(8)=4→f(16)=5f(1)=1 \rightarrow f(2)=2 \rightarrow f(4)=3 \rightarrow f(8)=4 \rightarrow f(16)=5 adımlarıyla en küçük sayı 16 olarak bulunur.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

Özel Tanımlı İşlemler

Bu konudan daha fazla soru