Examkin

Soru

Zorluk: ZorSayı Dizileri ve Örüntüler

Bir bilgisayarın güvenlik protokolü, şifreleme anahtarı oluşturmak için özel bir sayı dizisi algoritması kullanmaktadır. Algoritma, sisteme girilen iki başlangıç sayısını alır ve üçüncü terimden itibaren her yeni terimi, kendinden önceki iki terimin farkının mutlak değeri olarak hesaplar.

Sisteme başlangıç değerleri olarak:
1. terim=181. \text{ terim} = 18
2. terim=302. \text{ terim} = 30
sayıları girilmiştir.

Buna göre, bu algoritmanın üreteceği dizinin 95. terimi aşağıdakilerden hangisidir?

  1. A
    0
  2. 6Cevap
  3. C
    12
  4. D
    18
  5. E
    24

Cevap

Dizinin 95. terimi 6 sayısıdır.
Dizinin terimleri hesaplandığında 7. terimden itibaren {6, 6, 0} şeklinde 3'lü bir periyoda girdiği görülür. İlk 6 terim bu döngünün dışındadır. 95. terimi bulmak için öncelikle döngü dışı 6 terim çıkarılır (95−6=8995-6=89). Kalan 89 sayısı döngü uzunluğu olan 3'e bölündüğünde kalan 2 olur. Döngünün 2. elemanı ise 6 sayısıdır.

Adım Adım Çözüm

1
Dizinin ilk terimlerini kurala (an=∣an−1−an−2∣a_n = |a_{n-1} - a_{n-2}|) göre hesapla.
18, 30, 12, 18, 6, 12, 6, 6, 0, 6, 6, 0...
Örüntünün tekrar ettiği noktayı (periyodu) bulmak için dizi ilerletilmelidir.
2
Dizideki tekrar eden döngüyü (periyot) ve döngünün başladığı yeri tespit et.
Dizi: [18, 30, 12, 18, 6, 12] (ilk 6 terim düzensiz), ardından [6, 6, 0] şeklinde sürekli tekrar eden 3 elemanlı bir döngü başlar.
Dizinin 7. teriminden itibaren (6, 6, 0) bloğu sonsuza kadar tekrarlanmaktadır.
3
95. terimin döngü içinde hangi sıraya denk geldiğini modüler aritmetik ile hesapla.
Toplam terim - Düzensiz kısım = 95−6=8995 - 6 = 89. Kalan terim sayısı 89'dur. Döngü uzunluğu 3 olduğundan, 89(mod3)89 \pmod 3 işlemi yapılır. 89=29×3+289 = 29 \times 3 + 2.
Düzensiz kısmı çıkardıktan sonra kalan sayının 3'e bölümünden kalan, döngüdeki sırayı verir.
4
Kalan sayıya karşılık gelen döngü elemanını bul.
Kalan 2 olduğu için, (6, 6, 0) döngüsünün 2. elemanı cevaptır. Bu da 6 sayısıdır.
Döngünün 1. elemanı 6, 2. elemanı 6, 3. elemanı (tam bölünen) 0'dır.

Anahtar Kavram

Periyodik Sayı Dizileri ve Modüler Aritmetik

İpuçları

1
Dizinin ilk 10-12 terimini tek tek yazarak tekrar eden bir grup sayı (döngü) olup olmadığını kontrol ediniz.
2
Dizi belirli bir yerden sonra [6, 6, 0] şeklinde sürekli tekrar etmektedir. Tekrarın kaçıncı terimden sonra başladığına dikkat ediniz.
3
İlk 6 terim döngüye dahil değildir. 95'ten 6 çıkarıp, kalanı döngü uzunluğuna (3) bölerek kalana bakınız.

Alternatif Yöntem

Tüm terimlerin 6'nın katı olduğu görülür. Sayıları 6'ya bölüp (3, 5) ile başlayan [3, 5, 2, 3, 1, 2, 1, 1, 0, 1, 1, 0...] dizisini analiz etmek işlemi sadeleştirebilir.
Tahmini Süre:2m 30s
Bu soruyu puanla

Konular

Sayı Dizileri ve Örüntüler

Bu konudan daha fazla soru