Bir bulmaca

Geleceğin zehir programcılarından öğrencim Bade Özgüle bana bir matematiksel oyun gösterdi, programını nasıl yazabileceğini sordu. Matematik bulmacalarını hiç beceremem, ama sonunda işbirliğiyle hallettik.

Elinizde tombala kartları gibi, üzeri numaralı beş tane kart olsun:

Karşınızdaki kafasından 1 ile 31 arasında bir sayı tutsun. Sonra kartları gösterin ve tuttuğu sayının hangi kartlarda mevcut olduğunu göstermesini isteyin. Tutulan sayı, seçilen kartlardaki en küçük sayıların toplamıdır. Sözgelişi, birinci, üçüncü, ve dördüncü kartları gösterdiyse, tutulan sayı 1+4+8=13’dür.

Yöntem nasıl çalışıyor? Kartları üretirken, hangi kartın üzerinde hangi sayıların bulunacağına nasıl karar veriyoruz? 31’e kadar değil, daha yüksek bir sayıya kadar çıkmak istesek kaç kart kullanmamız gerekir? Bu kartları üretecek bir program nasıl yazarız?

Cevabı haftaya. İpucu: İkili tabanda düşünün.

Ek: Çözümü aşağıya yorum olarak ekledim.

Reklamlar

Kaan Öztürk hakkında

Kaan Öztürk İstanbul’da doğdu. İstanbul Lisesi ve Boğaziçi Fizik mezunu. Rice Üniversitesi‘nde uzay fiziği alanında doktora yaptı. Işık ve Yeditepe üniversitelerinde ders verdi. 2015-2016 döneminde Rice'da ziyaretçi araştırmacı olarak çalıştı. Bugünlerde Sabancı Üniversitesi'nde optimizasyon ve yapay öğrenme konularında doktoraüstü araştırmacı olarak çalışıyor.

13 Mart 2012 tarihinde İlginç Şeyler içinde yayınlandı ve , , olarak etiketlendi. Kalıcı bağlantıyı yer imlerinize ekleyin. 8 Yorum.

  1. Güzel soruymuş.
    Her bir karttaki en küçük sayı: 1,2,4,8 ve 16. Öncelikle bu 5 sayı farklı şekillerde toplanarak 31 tane sayı edilebilir ( kombinasyon(5,5)+komb(5,4)+…+komb(5,1)=31). 6 kart olsaydı aynı mantıkla 63 sayı elde edilebilirdi.

    Yönteme gelince; kartlardaki en küçük sayılar ikili tabandaki basamak değerlerini gösterdiğinden, 2^0,2^1,2^2,2^3 ve 2^4, sayıları ikili tabanda yazarsak hangi kartta hangi sayı yazılmalı bulabilirz. Örneğin 31 ikili tabanda: 11111 yani 5 kartta da yazmalı. Benzer şekilde 19: 10011, ilk 2 karta ve son karta yazılmalı gibi.

    Programda ise input olarak kartlara yazılacak sayılar verilmeli. Bu sayılar ikili sistemde donusturuldukten sonra basit if-else komutlarıyla hangi basamak 1’se o karta (matrise) rakamı yazmalı.

    Devamı da öğrencilere kalsın ;).

  2. İkili tabanda düşünün fazla büyük bir ipucu olmuş hocam =)

    Çözümü en kısa şekilde özetlersek (hala çözenler bakmasın)
    Sayılar ikilik tabanda yazıldığında X’inci basamağı 1 ise X’inci kartta yer alıyor. En küçük sayılar da basamak değerleri.

  3. http://guvenatbakan.com/kart/

    Kısıtlı C++ bilgimizle programı yazdık. Çağatay Dağıstan’dan çok büyük kopya çektik 🙂

    Seçilecek kart sayısını girdiriyoruz, ona göre kartları gösteriyoruz. Yalnız 9 kart girince Segmantation Fault hatası alıyoruz. Acaba Array’in limiti mi var anladım?

  4. Arrayi statik olarak tanımlamışsınız. int kart[9][512]; şeklinde ama aslında bu büyüklükte de 9un çalışması lazım.

    int** kart;

    ….

    kart = (int **) malloc( sizeof(int *)*(kartsayi));
    for(int i = 0; i<kartsayi; i++){
    kart[i]= (int *) malloc(sizeof(int) * aralik/2);
    }

    (olayın nasıl olduğunu anlamak isterseniz: http://www.eumus.edu.uy/eme/c/c-notes_summit/intermediate/sx9.html Biraz karışık noktalarındandır aslında C'nin)

    şeklinde yapınca dinamik daha büyük sayılarla çalışan bir array elde edilebilir. Düzeltip yollayayım dedim ama convert fonksiyonun nasıl çalıştğını tam anlayamadım ayrıntılı inceleyemedim de. Erişmemesi gereken yerlere erişmeye çalışıyor. Yorum olarak fonksiyonun ne yaptığını yazarsanız yardımcı olabilirim. Düzeltip yollayayabilirim hatta.

    Kolay gelsin.

  5. Ben malloc filan anlamam hocam ne kadar anlatsanız da, temel seviyede biliyorum sadece 🙂

    Kartları anlayacağınız üzre matriste şu şekilde tutuyorum: kart[kaçıncıkart][kartın_elemanı]. kart değişkeni benim deyimimle global tanımlı, fonksiyondan nasıl müdahale edeceğimi bilmediğim için global tanımladım.

    convert fonksiyonuna sayıyı gönderiyorum, klasik ikiye bölme işlemini yapıyorum. kalana bakıyorum, eğer 1 ise i. karta yazıyorum.(i ilk olarak 1 değerini alıyor) (oradaki for da, kartın_elemanı değerini bulmak ,üstüne yazmamak için öyle bir işlem yaptım. türk usulü :))

    Daha sonra i++ yapıyorum ve 2 ye bölünmüş sayıyı tekrar convert fonksiyonuna gönderiyorum.

    Böyle Türk usulü bir program yazdık onda da hata çıktı iyi mi 🙂

    Bu arada kaç seferdir deniyorum wordpress hesabımla yorumu gönderemedim. Sıkıntı çıkardı.

  6. Reblogged this on guvenatbakan and commented:
    Güzel bir matematik sorusu.

  7. Katkıda bulunan herkese teşekkürler. Benim çözümüm şöyle:

    Tuttuğumuz sayıyı ikilik tabana çevirelim. 0-31 arası bütün sayılar beş basamaklı bir ikilik sayıyla gösterilebilir. Birinci kartta, ikilik gösterimde birler basamağında 1 olan sayılar (onluk tabanda) yazılı. İkinci kartta ikiler basamağında 1 olan sayılar, üçüncü kartta dörtler basamağında 1 olan sayılar, ve saire.

    Onüç sayısı ikili olarak 01101 şeklinde gösterilir. O zaman birinci, üçüncü, ve dördüncü kartlarda 13 yazılı olmalı, diğerlerinde olmamalı.

    Tuttuğumuz sayının k numaralı kartta mevcut söylediğimizde, sayının ikilik gösteriminde sağdan k-inci basamağın 1 olduğunu söylüyoruz. Böylece sayıyı ikili tabanda tam olarak söylüyoruz zaten. O basamağın onluk tabandaki sayısal değeri ise, karttaki en küçük sayıya eşittir. Böylece gösterilen kartları toplayınca hangi sayının tutulduğunu buluruz.

    Birinci kartta, 2’ye bölümünden 1 kalan sayılar, yani tek sayılar bulunmalı.

    İkinci kartta: 1’den 31’e kadar olan sayıları önce ikiye bölüp küsüratını atın. Sonuç tekse, sayı ikinci kartta yazılı olmalı. Sözgelişi 11/2 -> 5 ikinci kartta.

    Üçüncü kartta: Yine 1’den 31’e kadar sayıları önce dörde bölün ve küsuratı atın. Sonuç tekse sayı üçüncü kartta yazılı olmalı. Sözgelişi 13/4 -> 3 üçüncü kartta.

    Genel olarak n sayısını 2(k-1)‘e bölüp küsuratını attığınızda elinizde tek sayı varsa, n sayısı k kartına yazılı olmalı.

    Bu işi yapacak bir C programı şöyle olabilir:

    #include <stdio.h>
    main()
    {
    	int i,k;
    	int payda=1;
    	int K=5; // kartlarin sayisi
    	int N=1; // sayilarin ust siniri, 2^K - 1 olacak.
    	
    	for(i=1; i<=K; i++)
    		N *= 2;
    	N--;  // N = 2^K - 1
    
    	// Kartlari bas:	
    	for(k=1; k<=K; k++){
    		printf("%d.kart: ",k);
    		for(i=1; i<=N; i++){
    			if( (i/payda) % 2 == 1)
    				printf("%d ", i);
    		}
    		payda *= 2;
    		printf("\n");
    	}
    
    }
    

    C’ye özgü bit kaydırma operatörleri << ve >> ile bunu biraz daha kısa yazabiliriz. i>>(k-1) ifadesi, i sayısının bitlerini k-1 kadar sağa kaydırır, yani i sayısını 2(k-1)‘e bölüp küsuratını atmakla aynı değeri verir. Benzer şekilde 1<<K ifadesi 1’i K bit kadar sola kaydırır, yani 2K değerini verir.

    #include <stdio.h>
    main()
    {
    	int i,k;
    	int K=5; // kartlarin sayisi
    	int N=(1<<K) - 1; // sayilarin ust siniri, 2^K - 1.
    	
    	// Kartlari bas:	
    	for(k=1; k<=K; k++){
    		printf("%d.kart: ",k);
    		for(i=1; i>=N; i++){
                            if( (i>>(k-1)) % 2 == 1)
    				printf("%d ", i);
    		}
    		printf("\n");
    	}
    
    }
    
    • anadoluhayvani

      Okuldayken (toplama, çarpma gibi) belli başlı matematik konularında oldukça zayıf olduğum için ikili sistem deyince bir türlü akıl erdiremedim meseleye. Arkasından matematik bu deyip, kulağımı tersten kaşıyarak kartlarda kural aramaya koyuldum. Haliyle nasıl çalıştığını yorumları okuyana kadar anlayamadığım bir çözüme ulaşmış oldum, çeşit olsun diye paylaşayım:

      Kartların ilk hanesinin 2^0, 2^1, 2^2, 2^3, 2^4 olduğu görülüyor hemen. İlk kart tek sayılardan devam ediyor, diğer kartlar ise her hanede 1 artarak giderken aralarda o kartın ilk hanesinin değeri kadar atlamalar yapıyor. Böyle düşününce aslında ilk kartın da her basamakta 2^0 değerinde atlamalar yaptığı ortaya çıkıyor (yani bu yüzden ikişer ikişer gidiyor). Bunu göz önünde bulundurarak biraz dikkatli bakınca tek tek olan artışlarında yine o kartın ilk hanesi miktarında bloklar halinde olduğunu görebiliyoruz (bir başka deyişle ilk kartta 2^0 yani 1’li bloklar var, 1’den 2’ye geçince 1 daha atladığımız için 3’e varıyoruz). Yani:

      3. kart için; ilk rakam 4 (2^2), ardından 3 kere bir önceki rakam 1 artıyor; 5, 6, 7 ve 4,5,6,7 şekilde 4’lü bir blok elde ediyoruz. Ne zaman bir sonraki rakam 8, 16 veya 32 (yani yine 4’ün katları) oluyor 4 hanelik bir bloğu atlıyoruz. Kısaca 4,5,6,7 yazdıktan sonra 8’e gelince bir atlamak yerine 4 atlayıp 12’den 4 saymaya devam etmemiz gerek. 4. kart için ilk rakam 8 olduğu için 8 bloklar yazıp, 8’in katlarına geldiğimizde 8 rakamlık blokları çıkartıyoruz. Python kullanarak buna uygun en kaba program şöyle yazılabilir:

      from numpy import *
      N = 5

      m = zeros((N,2**(N-1)))
      for i in range(N):
      m[i,0] = 2**i
      for j in range(1,2**(N-1)):
      if j%(2**i) == 0:
      m[i,j] = m[i,j-1] + 1 + 2**i
      else:
      m[i,j] = m[i,j-1] + 1
      print m

      Sonuçta, yaklaşık 20 sene gecikmekye ikili sistemin ne olduğunu anladığımda sonuç şaşırtıcı değil. k kartındaki n sayısı, 2^k’ye bölünebilir ise (mesela k.m) ikili sistemde k+m basamağına geçtiğimiz için n sayısı ve arkasından gelen k-1 sayının değeri 0 olacak; geriye kalanlar ise aslında ilk hane dışında 2^k’ye bölünemeyen sayılar oluyor. Bir başka deyişle yapılan şey Kaan’ın çözümünün tersten uygulanmasından ibaret.

Bir Yanıt Bırakın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s

%d blogcu bunu beğendi: