Şu Algoritmanın Neresi Hatalı?

7 yıl

Binbaşı

Konu Sahibi

1000 kişinin bir yuvarlak masada oturduğunu düşünün. 1. kişi yanındakini öldürüp bıçağı canlı kalan kişiye veriyor. O da aynı şeyi yapıyor. En sonunda masadaki kaçıncı kişi sağ kalır. Mesela, birinci kişi ikinciyi öldürüyor ve bıçağı üçüncü kişiye veriyor. Üçüncü kişi de dördüncüyü öldürüyor ve bıçağı beşinciye veriyor. Bunun çözümünü programlama ile çözmek istedim ve aşağıdaki mantığı kurdum ama anlamadığım bir nedenden ötürü hata veriyor.

Kod:

visitors = range(1, 1001)

i = 1

while(len(visitors) > 1):
    del visitors[i]
    i = i + 1 

print visitors

Hata:



Traceback (most recent call last):
  File "main.py", line 6, in <module>
    del visitors[i]
IndexError: list assignment index out of range

A

AI Engineer

7 yıl

Binbaşı

Konu Sahibi

Sorunu çözdüm galiba: 1000 tane elaman var kümemde. İlk başlarda "i = i + 1" çalışıyor çünkü sayılar küçük ama sayı büyüdükçe kümem küçülüyor. Sonra Index'e karşılık sayı gelmiyor. Misal i oldu 700 ama visitors[700] karşılık elaman yok.

 
  
 visitors = range(1, 1001) 
  
 i = 1 
  
 while(len(visitors) > 1): 
     del visitors[i] 
     i = (i + 1) % len(visitors)  
  
 print visitors

Bu şekilde çalıştı.

M

mr.yilanci

7 yıl

Teğmen

Bu algoritmayla neyi hedefliyorsun ? Nasıl bir liste oluşturmak istiyorsun ?

S

STR Priest

7 yıl

Yüzbaşı

Cevabi buldugumu dusunuyorum konu disindaki konunuzuda attim cevap ama silinmesi ve sadece burayi takip edenlerde varsa diye burayada atiyorum

< Resime gitmek için tıklayın >

< Bu mesaj bu kişi tarafından değiştirildi STR Priest -- 22 Temmuz 2018; 6:48:21 >

M

Mephalay

7 yıl

Yarbay

Eger herhangi bir anda, masada 2^n kadar insan varsa, o sirada bicagi elinde tutan kisi son kalan kimse olacaktir. Bu ipucu ile bakarsan algoritmaya loop yapmana gerek kalmaz, O(1) zamanda cozebilirsin.

< Bu ileti tablet sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

S

seyfi84

7 yıl

Yüzbaşı

python 2 kullanıyorsun, onu kullanma artık bitti python 2. bu yazdığın şey python 3'te çalışmaz çünkü range nesnesi immutable oldu, del yapamazsın.

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

S

STR Priest

7 yıl

Yüzbaşı

quote:

Orijinalden alıntı: seyfi84

python 2 kullanıyorsun, onu kullanma artık bitti python 2. bu yazdığın şey python 3'te çalışmaz çünkü range nesnesi immutable oldu, del yapamazsın.

Haklisiniz fakat yukarda yazdigim koda bakarsaniz ufak tricklerle onu atlatabilmek mumkun. Ama python3 candir

Bu mesaja 1 cevap geldi.

S

seyfi84

7 yıl

Yüzbaşı

sana degil soru sorana cevap verdim, yoksa zaten ayni kisi misin?

yaptigin seyin trick denecek bir tarafi yok, range nesnesini list yapiyorsun hepsi bu

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @STR Priest

T

Tuğkan-0153

7 yıl

Yarbay

masayı temsilen array[n] olsa. 1000 kişi varsa n = 999 olacak ; array 0 dan başlayacak. ilk turda tek sayı endeksler ikinci turda çift sayı böyle azalarak sonuçta en sondan bir önceki yani başlangıçta array[n-1] deki kişi kalır gibi yani döngü döndürmeye ve delete ile array elemanlarını silerek hesaplamaya gerek olmadan sonuç belli gibi.

< Bu ileti mini sürüm kullanılarak atıldı >

G

Guest-D639AD061

7 yıl

Teğmen

quote:

Orijinalden alıntı: Mephalay

Eger herhangi bir anda, masada 2^n kadar insan varsa, o sirada bicagi elinde tutan kisi son kalan kimse olacaktir. Bu ipucu ile bakarsan algoritmaya loop yapmana gerek kalmaz, O(1) zamanda cozebilirsin.

Mephalay hocamın dediği gibi boşu boşuna döngü kurmanın anlamı yok.
İnternette araştırın, bu tür sorulara matematikçiler çok zekice çözümler üretmişler.
Başlangıç içinhttps://www.geeksforgeeks.org/puzzle-100-people-in-a-circle-with-gun-puzzle/.

Bu mesaja 1 cevap geldi.

A

AI Engineer

7 yıl

Binbaşı

Konu Sahibi

quote:

Orijinalden alıntı: Guest-D639AD061

Mephalay hocamın dediği gibi boşu boşuna döngü kurmanın anlamı yok.
İnternette araştırın, bu tür sorulara matematikçiler çok zekice çözümler üretmişler.
Başlangıç içinhttps://www.geeksforgeeks.org/puzzle-100-people-in-a-circle-with-gun-puzzle/.

Alıntıları Göster

Bu sonuca nasıl ulaştınız? Sıfırdan kendiniz mi düşündünüz? Çünkü bunu düşünmek kolay değil. GeekforGeek'te kanıtı yok. Direkt formül vermiş.

Bu mesaja 1 cevap geldi.

G

Guest-D639AD061

7 yıl

Teğmen

quote:

Orijinalden alıntı: AI Engineer

Bu sonuca nasıl ulaştınız? Sıfırdan kendiniz mi düşündünüz? Çünkü bunu düşünmek kolay değil. GeekforGeek'te kanıtı yok. Direkt formül vermiş.

Alıntıları Göster

Hayır ben bulmadım, araştırabilmeniz için linki vermiştim, sorunun orijinal adı Josephus problem.
Şuradan okuyabilirsiniz, hızlıca göz gezdirdim, güzel anlatmış gibi göründü.
Vazgeçtim o siteye bir daha baktım, ama Ali Nesin'in çözümü daha güzel.https://matematikkoyu.org/docs/sayma.pdf buradan josephus diye aratın bu daha iyi.

< Bu mesaj bu kişi tarafından değiştirildi Guest-D639AD061 -- 23 Temmuz 2018; 22:21:53 >
Bu mesaja 1 cevap geldi.

T

Tuğkan-0153

7 yıl

Yarbay

Verdiğin linkten sonra probleme şimdi yeniden baktım. Kod yazmadan sadece matematik formul ile de bulunabilir belki fakat kodla çözünce sonuç garanti. Nitekimhttps://rosettacode.org/wiki/Josephus_problem#Perl 'da bu problemin Perl ile çözümünü buldum, kodu biraz sadeleştirerek ve Türkçe yorum ekleyerek yazdım. 0 .. 999 arası endeksli 1000 kişi içinde endeksi 976 olan kişi hayatta kaldı.

< Resime gitmek için tıklayın >

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @soii

A

AI Engineer

7 yıl

Binbaşı

Konu Sahibi

Cevap 977. kişi olmalı ama.

Edit: Endeks demişsin pardon.

< Bu mesaj bu kişi tarafından değiştirildi AI Engineer -- 24 Temmuz 2018; 1:23:28 >
Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @revivo72

T

Tuğkan-0153

7 yıl

Yarbay

Rosettacode.org 'a baktın mı? Python ile masadan gidenlerin tek tek listesini vererek çözmüş. endeks 0 dan başladığı için onda da 976. endeks kalıyor

< Resime gitmek için tıklayın >

< Bu ileti mini sürüm kullanılarak atıldı >

Bu mesajda bahsedilenler: @AI Engineer

G

Guest-D639AD061

7 yıl

Teğmen

Hayır bin kişisiniz zaten, tükürseniz boğarsınız karşınızdakileri, niye birbirinizi öldürüyonuz demi

G

Glitch

7 yıl

Teğmen

Problemin adı Josephus Circle matematik veya programlama ile çözülebilir.Adım adım çözen bir program yazmıştım ama java ile.İstersen koyayım.

Bu mesaja 2 cevap geldi.

T

Tuğkan-0153

7 yıl

Yarbay

Rosetta.org 'a baktın mı?http://rosettacode.org/wiki/Josephus_problem#Java 'da Java çözümünü de yazmışlar cunku her bir dilde çözümünü yazmışlar. (linki tıklayınca DH Forum kampanya linki eklediği için # etiketinden dolayı açmayabilir; DH linkini silerek açın)

< Bu ileti mini sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @Glitch

G

Glitch

7 yıl

Teğmen

Ben ödev icabi circular linked list ile yazmistim.Bir de insan sayisini ve kac kisi araliklarla oldurcegini input aliyor.Ordakinden biraz farkli yani.Arkadas farkli bir algoritma ister belki diye yazdim.

< Bu ileti mobil sürüm kullanılarak atıldı > Bu mesaja 1 cevap geldi.

Bu mesajda bahsedilenler: @revivo72