sonraki »

[wizofwor]

Bir algoritma sorusu. Aslında matematik sorusuydu ama ben bunu çözen bir algoritma yazmanın güzel bir egsersiz olacağını düşündüm. Biraz vBasic'te uğraştım mamafih başarılı olamadım. Her hangi bir dilde yapabilecek olan var mı?

Örneğin n=8 olsun. Bir kağıda bir'den 8'e kadar sayıları yazıyoruz.

1,2,3,4,5,6,7,8

1'den başlayarak ikinci sayıyı iptal ediyoruz.

1,2,3,4,5,6,7,8

Sonra başa dönüyoruz ve aynı işlemi kalan diziyle yapıyoruz.

1,2,3,4,5,6,7,8

Sonra tekrar başa dönüyoruz
1,2,3,4,5,6,7,8

ve f(8) = 1'dir diyoruz.



İkinci bir örnek de 9 için yapalım.

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

İşte karışıklık yaratan kısım burası. En son 9'u saydığımız için bu sefer 1'i iptal ederek başlıyoruz.

1,2,3,4,5,6,7,8,9

1,2,3,4,5,6,7,8,9

ve f(9)=3'tür diyoruz.


Amaç her n değeri için aynı mantıkla sonuç veren bir f(n) fonksiyonu yazmak.

[Mathman]

9 u saydığından dolayı 1 i neden iptal ediyorsun .. oradaki mantığı anlamadım

[Atacan]

Ben komple anlamadım

[wizofwor]

Eleme yaparken son rakama geldiğinde başa geri dönüyor.

Aslında resimle daha kolay anlaşılıyor. Aşağıda n=5 için resimli anlatım var.

1'i atlayarak başlıyoruz. 2 iptal. 3 kalıyor, 4 iptal. 5 kalıyor, 1 iptal. 3 kalıyor, 5 iptal. Mantık bu şekilde. Elimizde en son 1 rakam kalana kadar bir atlayarak iptal ediyoruz.

[Mathman]

n=10 için cevap 5 mi mesela?

[nightlord]

sanirim soyle bisey. biraz aceleye geldi. su an lineer cozumden iyisini goremedim. belki sabit zamanli bir cozum de matematiksel olarak cikarilabilir (hatta ihtimalen oyle).

Kod:

int SonrakiDaireselIndex(int i, int n){
  return ((i + 1) % n));
}

int SorulanF(int n){
  // henuz silinmemisleri bir dizide tutalim
  bool* henuzSilinmedi = new bool[n];
  for(int i = 0; i < n; ++i)
    henuzSilinmedi[i] = true;

  // n-1 kere bir eleman cikaralim
  int s = 0;
  for (int i = 0; i < (n - 1); ++i){
    //su an bulundugumuz yerden itibaren ilk silinmemis ogeyi bul
    while (!henuzSilinmedi[s])
      s = SonrakiDaireselIndex(s, n);

    // bu ogeyi atliyoruz
    s = SonrakiDaireselIndex(s, n);

    //su an bulundugumuz yerden itibaren ilk silinmemis ogeyi bul
    while (!henuzSilinmedi[s])
      s = SonrakiDaireselIndex(s, n);

    // bu ogeyi siliyoruz
    henuzSilinmedi[s] = false;
  }

  // n - 1 elemani sildik kalan elemani dondur
  for (int i = 0; i < n; ++i){
    if (henuzSilinmedi[i]){
      return (i + 1);
    }
  }

  // bu noktaya vardiysak kodda bug var
  assert(false);
}

[wizofwor]

Aslında matematik sorusu zaten. Yani matematiksel bir çözümü var. Ben bu şekilde uğraşmak istedim ama dizinin sonundaki sayıyı tutup 1'i iptal ettiği yerde takıldım. Sanıyorum C ile çözmüşsün. Bunu vbasic'e adapte edip excel'e ekleyebilecek miyim bakalım.

@mathman evet f( 10) = 5 oluyor.

[wizofwor]

@nightlord:

Senin kodu vbasic'e tercüme ettim. Excel dosyasını ilgilenen arkadaşlar için bu yazının ekine koydum. Çok süper oldu. Olay dairesel index fikrinde. Bunu akıl edebilseydim gerisi kolaymış. Tecrübe de bu demek oluyor herhalde.

Kodu ise şöyle

Kod:

Function nightlordF(n As Integer) As Integer

    Dim i As Integer 'counter
    
    'n boyunda bir dizi tanımlayalım
    've her bir elemanın değerini "true" yapalım.
    Dim numbers() As Boolean
    ReDim numbers(n - 1)
    For i = 0 To n - 1 Step 1
        numbers(i) = True
        Next i
        
    'n-1 kere eleman çıkaralım
    Dim s As Integer 'su an bulunduğumuz yer
    s = 0
    
    For i = 1 To n - 1 Step 1
        
        'ilk silinmemiş öğeyi bul
        While numbers(s) = False
            s = sonrakiDaireselIndex(s, n)
        Wend
        
        'ilk silinmemiş öğeyi atla
        s = sonrakiDaireselIndex(s, n)
    
        'bir sonraki silinmemiş öğeyi bul
        While numbers(s) = False
            s = sonrakiDaireselIndex(s, n)
        Wend
    
        'bu öğeyi sil
        numbers(s) = False
    
    Next i
    
    'son kalan elemanı döndür
    For i = 0 To n - 1 Step 1
        If (numbers(i) = True) Then
            nightlordF = i + 1
        End If
        Next i
        
End Function

Function sonrakiDaireselIndex(s As Integer, n As Integer)
    s = s + 1
    sonrakiDaireselIndex = s Mod n
End Function

[nightlord]

dairesel index fikri de zaten senin verdigin problem tanimindan geliyor aslinda. Ama cok da kolay bir soru sayilmaz bu. Guzel bir yazilim muhendisi interview sorusu olur.

Sorunun orjinalini nerede buldugunu sorabilir miyim?

[wizofwor]

Bu bir iş arkadaşımın sorduğu bir matematik sorusuydu. Matematiksel çözümü de excel formulü olarak "=2*X-(2^(INT(LOG(X;2))+1)-1)" imiş.

[kaptan akgun]

İlginç bir soruymuş

[AmigaMan]

Algoritma Sorusunu çözdüm java,python, c# ve VBA dillerinde kodları hazırladığımda foruma göndereceğim

[wizofwor]

Aynı mantıkla mı yoksa farklı bir yoldan mı çözdün?

[AmigaMan]

Dizi Mantığıyla ama C kodunu incelemedim.