Emrehan Halıcı'nın Sorusunun Çözümü

[tujix]

merhaba arkadaslar
Emrehan Halıcı'dan super bir soru ve ayni guzellikte iki cozum
Soru:
18xx lerde acimasiz bir kral su sekilde bir meraka girmisitir:
10 tane koleyi daire seklinde dizip iclerinden birnin eline bir kilic versem ve ve saat yonunde olmak sartiyla elinde kılıc olan yanındaki ilk sağ kisiyi oldurup ondan sonraki ilk sağ kisiye kilici verse ve bu sekilde 1 kisi kalincaya kadar devam etse kacinci kisi kurtulur der ve dener.5.kole kurtulmustur fakat kralin meraki yine depresmistir 10000kiside kacinci kole kurtulur?


Bununlada yetinmeyip acaba x kole olsa kacincisi kurtulur diyen acimasiz arkadaslar icin kac kisi arasindan kacincinin kurtulcagini hesaplatan opsiyenel sekilde yazilmis iki tane cevap program.
herkese iyi oldurmeler




#!/usr/bin/python
try:
----kisi=int(raw_input("Gebertmek istediginiz mahkum sayisini giriniz : "))
----if kisi<>0:
--------A,B=[],[0]
--------for i in range(1,kisi+1,1):
------------ A.append(1)
--------x,a=0,0

--------while A.count(1)<>1:
------------while x<kisi:
----------------if A[x]==1:
-------------------- a=a+1
--------------------if a==2:
------------------------ A[x]=B[0]
------------------------ a=0
------------------------ x=x+1
--------------------else:
--------------------x=x+1
----------------else:
-------------------- x=x+1
------------else:
----------------if a==1:
--------------------x=0
--------------------if A[x]==1:
------------------------ A[x]=B[0]
------------------------ a=0
--------------------else:
------------------------ x=x+1
--------------------if a==0:
------------------------ x=0

--------for i in range(kisi):
------------ if A[i]==1:
---------------- print "Bugun %d'inci koleniz hayatta kalmayi basardi"%(i+1)
---------------- pass
----else:
-------- print "Hic kole oldurmek istemiyor musunuz? "
except:
---- print "Lutfen bir rakam giriniz !!!"
################################################## #


#ayni isi yapan ikinci program

#!/usr/bin/python
ke=int(raw_input("kac eleman öldurmek istiyorsunuz :"))#ke=>kac eleman
oleceklistesi=[]
for i in range(1,ke+1,1):
---- oleceklistesi.append(i)
sagkalanlarinsayisi=len(oleceklistesi)
i=0
while(i<sagkalanlarinsayisi+1):
----if(oleceklistesi[i]==oleceklistesi[-2]):
-------- oleceklistesi.remove(oleceklistesi[i+1])
-------- i=0
-------- sagkalanlarinsayisi=len(oleceklistesi)
--------if(sagkalanlarinsayisi==1):
------------ break
-------- else:
------------ continue
--------if(oleceklistesi[i]==oleceklistesi[-1]):
------------ oleceklistesi.remove(oleceklistesi[0])
------------ i=0
------------ sagkalanlarinsayisi=len(oleceklistesi)
------------ if(sagkalanlarinsayisi==1):
---------------- break
------------ else:
---------------- continue
------------ sagkalanlarinsayisi=len(oleceklistesi)
-------- oleceklistesi.remove(oleceklistesi[i+1])
-------- i=i+1
print oleceklistesi[0],".köle sansliymis "
##########################################
hey bir +rep elinemi yapisti

[tujix]

kodlar hakkinda biraz yorum yaparsaniz sevinirm arkadaslar
neresine mudahale edersek daha hizli calisir veya bunlardan daha hizlisi varsa paylasirsaniz memnun olurum
ilk kod ikincisine fark atiyo mesela acaba ne yaparsak kodlarimiz daha hizli calisir

[samil]

Problemin çok daha farklı bir çözümü var, ama algoritmik değil, matematiksel.
Bu soruyu 1'den 20 ye kadar elemanları bir kağıtta yazarsan bir formül ortaya çıkartacaksın. Asal sayılarda 1. eleman çıkıyordu heralde.
Hatırlarsam şöyle birşey keşfetmiştim:
Girilen sayıdan küçük ona en yakın asal sayıyı buluyordum.
sonra girilen sayının asal sayıdan farkına n deyip, 2n+1 ile kaçıncı eleman olduğunu buluyordum ayakta kalanın.
İstersen ilk 100 asal sayıyı bir dizide tut onlarla karşılaştır sürekli, böylece en yakın asal sayıyı hesaplamak için bir fonksiyondan kurtulursun...
Hadi kolay gelsin, ama bunun senin yöntemden hızlı çalışacağı kesin
başarılar.

[scripter]

kilic her zaman 1.ci kole'de mi olcak?

[myavuzselim]

@samil, ornek verebilir misin? Soyledigin yontemle 5 eleman icin sonuc (5-3)*2+1 = 5 cikiyor, ama (saymaya 1'den basliyorsak) sonuc 3.

@tujix, ne yazik ki programlarini calistiramadim, sonsuz donguye giriyor.

Bu da benim cozumum:

def kalan(n):
    next = range(2, n+2)
    next[-1] = 1
    i = 1
    while not next[i] == i:
        next[i] = next[next[i]]
        i = next[i]
    return i

Once linkedlist kullanarak yapmistim, sonra buna gerek olmadigini anladim. Bu da bir cesit linkedlist sayilir zaten.

[myavuzselim]

0 yerine 1'den baslayalim diyerek bir hata yapmisim. Dogrusu:

def kalan(n):
    next = range(1, n+1)
    next[-1] = 0
    i = 0
    while not next[i] == i:
        next[i] = next[next[i]]
        i = next[i]
    return i+1

Ayrica bu da logaritmik bir cozum, en hizlisi bu :

def k(n):
    if n == 1:
        return 0
    elif n % 2 == 0:
        return 2 * k(n/2)
    else:
        return 2 * k(n/2) + 2

[samil]

1- 1

2- 1
3- 3

4- 1
5- 3
6- 5
7- 7

8- 1
9- 3
10- 5
11- 7
12- 9
13- 11
14- 13
15- 15


16- 1
17- 3
18- 5
19- 7
20- 9
21- 11
22- 13
23- 15
24- 17
25- 19
26- 21
27- 23
28- 25
29- 27
30- 29
31- 31

Bunu çözümlemek lazım...

[mr1yh1]

devamı da @samil 'in gösterdiği gibi gidiyorsa :

n kişi için,
2^i < n <2^(i+1) olacak şekilde i bulunabilir.
(n-2^i) * 2 + 1 istediğimiz sayıyı verir.

test :
n = 3
2^1 < 3 < 2^2
(3-2^1)*2+1 = 3

n=12
2^3<12<2^4
(12-2^3)*2+1 = 9

n=10000
2^13<10000<2^14
(10000-2^13)*2+1 = 3617
...

[myavuzselim]

samil ve mr1yh1, sahane oldu. Tebrikler!
Koda dokelim:

def k(n):
    xi = 1
    while 2 * xi <= n:
        xi *= 2
    
    return (n-xi) * 2 + 1

Scripting dilleri icin log fonksiyonu daha hizliymis. Biraz obfuscated ama daha hizli olani:

from math import log
log2 = log(2)
def f(n):
    return ((n-(1<<int(log(n)/log2)))<<1) + 1

Yavas yavas algoritmanin iyilestirildigi konular eglenceli oluyor

not: ikinci kodu (ben ekleme yaparken) mr1yh1 ile ayni anda yazmisiz, karisiklik olmasin.

[mr1yh1]

2^i <= n <2^(i+1) olacaktı, @myavuzselim kodda düzeltmiş.

bu arada i'yi bulmak için logartima kullanılabilir.
log(n)/log(2) nin tam kısmı i'yi verir.

binlerce kişinin hayatını kurtardık.