SonsuzUs

Rekabetçi Programcı Tam Arama (Complete Search)

Tam arama, neredeyse her algoritma probleminde kullanılan bir metottur. Buradaki fikir, kaba kuvvet (brute force) kullanarak bütün olası çözümleri oluşturup sonrasında probleme göre aralarından en iyi çözümü bulmak veya bütün çözümleri saymaktır. Tam arama, bütün çözümler denenebiliyorsa işe yarar bir tekniktir çünkü bu aramayı koda dökmek kolaydır ve aynı zamanda her zaman doğru çözümü bulur. Eğer tam arama soru için çok yavaş kalıyorsa, açgözlü (greedy) algoritmalar veya dinamik programlama gibi başka yöntemler gerekebilir.

5.1 Alt küme Oluşturmak (Generating Subsets)

n elemanlı bir kümenin bütün alt kümelerini oluşturmak için iki yaygın yöntem vardır: özyineleme (recursion) veya bit maskeleme (bitmasking).

Yöntem 1: Özyineleme (Recursion)

Bütün alt kümeleri oluşturmanın şık yollarından biri özyinelemedir. Aşağıdaki search fonksiyonu {0, 1, ..., n-1} kümesinin alt kümelerini oluşturur.

Rekabetçi Programcı Veri Yapıları

Veri yapısı, bilgisayarın hafızasında veri saklamak için bir yoldur. Ele alınan problem için uygun bir veri yapısı seçimi yapmak önemlidir çünkü her veri yapısının kendine göre avantajları ve dezavantajları bulunmaktadır. Bu noktada cevaplanması gereken ana soru, hangi işlemlerin seçtiğimiz veri yapısında verimli olacağıdır.

Bu bölümde C++ standart kütüphanesindeki en önemli veri yapıları tanıtılacaktır. Standart kütüphane zamandan tasarruf sağlayacağı için mümkün olduğunca onu kullanmaya özen gösterilmelidir.

4.1 Dinamik Diziler

Dinamik dizi, programın çalışması sırasında boyutu değiştirilebilen bir dizidir. C++’daki en popüler dinamik dizi vector yapısıdır.

Aşağıdaki kod, boş bir vektör oluşturur ve bu vektöre üç eleman ekler:

Rekabetçi Programcı Sıralama

Sıralama, temel algoritma sorularından biridir. Çoğu algoritmanın içeriğinde, veriyi sıralı halde işlemek daha kolay olduğu için sıralama bulunur. Örneğin “Bu dizide birbiriyle aynı iki eleman var mı?” sorusu sıralamayla çok kolay bir şekilde çözülebilir. Eğer dizi birbiriyle aynı iki eleman içeriyorsa, dizi sıralandıktan sonra bu elemanlar ardışık olacaktır.

Verimli çalışan sıralama algoritmaları $O(n \log n)$ zamanda çalışır ve genelde içeriğinde sıralama bulunan algoritmalar da bu zaman karmaşıklığına sahiptir.

3.1 Sıralama Teorisi

Temel sıralama problemi şöyledir: n elemana sahip bir diziyi artan sırada sıralayın. Örneğin [1, 3, 8, 2, 9, 2, 5, 6] dizisi sıralandıktan sonra [1, 2, 2, 3, 5, 6, 8, 9] haline dönüşür.

$O(n^2)$ Algoritmalar

Basit dizi sıralama algoritmaları $O(n^2)$ zamanda çalışır. Bu algoritmalar kısa olup genelde iki for döngüsüyle çalışır. Çok bilinen $O(n^2)$ algoritmalarından biri olan kabarcık sıralaması (bubble sort), dizideki elemanların değerlerine göre “kabarcık” gibi yer değiştirmesiyle çalışır.

Kabarcık sıralaması n defa tur atar. Her turda, algoritma sıraya uymayan iki ardışık eleman bulduğunda yerlerini değiştirir.

Rekabetçi Programcı Zaman Karmaşıklığı

Rekabetçi programlamada algoritmaların verimliliği önemlidir. Genelde soruyu çözen yavaş bir algoritma oluşturmak kolaydır ama asıl zorluk hızlı bir algoritma oluşturmaktır. Eğer algoritma çok yavaşsa ya sorudan kısmi puan alacaktır ya da hiç almayacaktır.

Zaman karmaşıklığı, bir algoritmanın bir girdi için tahmini olarak ne kadar süre gerektireceğini belirtir. Bunun amacı, girdinin boyutuna göre değişen ve algoritmanın verimliliğini gösteren bir fonksiyon oluşturmaktır. Zaman karmaşıklığını hesaplayarak, algoritmayı koda dökmeden önce yeterince hızlı olup olmadığını anlayabiliriz.

2.1 Hesaplama Kuralları

Bir algoritmanın zaman karmaşıklığı O(...) ile gösterilir. Genelde, girdi büyüklüğü olarak n değişkeni kullanılır. Örneğin sayılardan oluşan bir dizide n dizinin büyüklüğünü, eğer girdi bir yazı ise n yazının uzunluğunu verir.

Döngüler

Algoritmanın yavaşlamasına neden olan genel sebeplerden biri, girdi üzerinde çalışan çok fazla döngü bulundurmasıdır. Bir algoritma ne kadar çok iç içe geçmiş döngü içerirse o kadar yavaşlar. Eğer k tane iç içe geçmiş döngü varsa zaman karmaşıklığı O(n^k) olur.

Örneğin aşağıdaki kodun zaman karmaşıklığı O(n)‘dir:

Rekabetçi Programcı Giriş

Rekabetçi programlama iki konudan oluşur: uygun algoritmayı bulmak (algoritmanın dizaynı) ve uygun algoritmanın koda geçirilmesi (implementasyonu). Uygun algoritmayı bulmak (dizayn) için soru çözmek ve matematiksel düşünme gerekir. Soruların analiz edilip yaratıcı bir şekilde çözülmesi önemlidir. Soruyu çözen algoritmanın hem doğru hem de verimli olması gerekir. Zaten genel olarak soruların temelinde verimli algoritmayı bulmak vardır. Rekabetçi programcıların algoritmalar hakkında teorik bilgiye sahip olması gerekir. Tipik bir soru çözümü genelde bilinen tekniklerle yeni gözlemlerin birleşimidir. Rekabetçi programlamada çıkan teknikler aynı zamanda algoritmaların araştırma bazlı kısmının da temelini oluşturur.

Algoritmaların koda geçirilmesi (implementasyon) içinse iyi kodlama bilgisi gerekir. Rekabetçi programlamada çözümler belirli test caseler kullanılarak puanlanır. Bu yüzden sadece algoritmayı düşünerek bulmak yetmez, aynı zamanda bunun koda doğru bir şekilde geçirilmesi önemlidir.

Yarışmalarda yazılan kodların kısa ama aynı zamanda anlaşılabilir olması gerekir. Yarışmalarda verilen zamanın kısıtlı olması nedeniyle çözümlerin hızlı yazılması gerekir. Klasik yazılım mühendisliğinin aksine, çözümler kısa olup (çoğunlukla en fazla birkaç yüz satır kod) yarışma sonrası geliştirilmesi gerekmemektedir.

1.1 Kodlama Dilleri

Şu anda rekabetçi programlamada en çok kullanılan kodlama dilleri C++, Python ve Java’dır. Örneğin Google Code Jam 2017’de yarışmacıların ilk 3000’ünün 79%’u C++, 16%’sı Python ve 8%’i Java kullanmıştır. Bazı yarışmacılar birden çok kodlama dilini kullandılar.

Çoğu yarışmacı C++ dilini rekabetçi programlama için en iyi dil olarak görüyor ve C++ neredeyse her yarışma sisteminde bulunmaktadır¹. C++11’in yararları arasında çok hızlı ve verimli bir dil olmasıyla beraber çeşitli veri yapıları ile algoritmaları kapsayan bir kütüphaneye sahip olması yer alır.

Yine de birkaç dilde uzmanlaşıp onların yararlarını bilmekte fayda var. Örneğin soruda çok büyük sayılar gerekiyorsa Python, büyük sayılar için işlemleri halihazırda built-in bulundurmasından dolayı uygun bir seçenek olabilir. Neyse ki yarışmalardaki çoğu soru, herhangi bir kodlama dilinin avantajı olmayacak şekilde hazırlanmaktadır.

Bu kitaptaki örnek çözümler C++ ile yazılmış olup standart kütüphanedeki algoritma ve veri yapıları sıklıkla kullanılmıştır. Çözümler C++11 formatında yazılmıştır ki bu format şu anki çoğu yarışmada kullanılabilmektedir.

C++ Kod Örneği

Klasik bir C++ kodu aşağıdaki gibi görünür.

Rekabetçi Programcı Başlangıç

Rekabetçi programlama iki temel konudan oluşur: uygun algoritmayı bulmak (algoritmanın tasarımı) ve bu algoritmayı doğru biçimde koda geçirmek (implementasyonu).

Algoritma tasarımı için soru çözmek ve matematiksel düşünme gerekir. Soruların analiz edilip yaratıcı bir şekilde çözülmesi önemlidir; algoritmanın hem doğru hem de verimli olması beklenir. Rekabetçi programcıların algoritmalar hakkında teorik bilgiye sahip olması gerekir. Tipik bir soru çözümü genelde bilinen tekniklerle yeni gözlemlerin birleşimidir.

İmplementasyon içinse iyi kodlama bilgisi şarttır. Çözümler belirli test durumlarıyla puanlandığından algoritmayı doğru biçimde koda geçirmek kritik önem taşır. Yarışmalarda kodların kısa ama anlaşılabilir olması, aynı zamanda hızlı yazılması gerekir. Klasik yazılım mühendisliğinin aksine, çözümler genellikle birkaç yüz satırı geçmez ve yarışma sonrası geliştirilmesi gerekmez.

1.1 Kodlama Dilleri

Rekabetçi programlamada en çok kullanılan diller C++, Python ve Java‘dır. Google Code Jam 2017’de ilk 3000 yarışmacının %79’u C++, %16’sı Python, %8’i Java kullanmıştır.

Çoğu yarışmacı C++’ı en iyi seçenek olarak görür; neredeyse her yarışma sisteminde bulunur, çok hızlı ve verimlidir, kapsamlı bir standart kütüphanesi vardır. Yine de birkaç dilde uzmanlaşmakta fayda var. Örneğin çok büyük sayılar gerektiren problemlerde Python’ın yerleşik büyük sayı desteği işe yarayabilir.

Not: TÜBİTAK Bilim Olimpiyatları’nda yalnızca C/C++ kullanılabilmektedir.

Bu kitaptaki örnek çözümler C++11 standardıyla yazılmıştır.

C++ Kod Şablonu

Türkçe Sator Kareleri

Sator kareleri meşhur bir kelime dizilimi programıdır. Örneği şu şekildedir.

Kurallardan anlaşılacağa üzere her satır ve sütunda anlamlı kelimeler bulunuyor ve bunlar bazen birbirinin tersi olabiliyor. Anlamlı sator karelerini bulabilmek için öncelikle elimizde bir kelime veri tabanı olması gerekiyor. 60bin anlamlı kelimelerden oluşan veri tabanını indirmek için: Türkçe Sözcük veritabanı na tıklayabilirsiniz. Ben doğrudan import ettiğim için .py dosyası haline getirdim, siz elinizdeki başka veritabanlarını da kullanabilirsiniz.

Bundan sonra kodumuz bir kaç aşamadan geçiyor. Aşağıda kodlarla sator karelerini bulma girişimlerimiz olmuştur.

Pythonda Karmaşık ve İç İçe Listeleri Düzleştirmek (Flatten)

Python’da programlama yaparken, bazen karşımıza iç içe geçmiş listeler, demetler (tuple), kümeler (set) ve hatta sözlükler (dictionary) gibi farklı veri tiplerini bir arada barındıran karmaşık veri yapıları çıkabilir. Bu tür bir yapıyı analiz etmek veya üzerinde işlem yapmak için genellikle onu “düzleştirmek”, yani tek bir liste haline getirmek isteriz.

Bu yazıda, karmaşık bir listedeki tüm sayısal değerleri ayıklayıp tek ve düz bir liste oluşturmanın farklı yollarını inceleyeceğiz.

Zorlu Bir Örnek: Karışık Veri Yapısı

İşe, üzerinde çalışacağımız karmaşık listeyi tanımlayarak başlayalım. Bu liste, içinde tam sayılar, listeler, demetler, kümeler ve sözlükler barındırıyor.

Karıncaların yön bulma yeteneklerini inceleyen program

C# programlama dili ve Unity oyun motoru kullanılarak hazırlanan simülasyon aracılığıyla karıncaların koloni ve besin kaynağı arasında feromon izlerini takip etmesi incelenmiştir.

Giriş

Karıncalar, tek başlarına hayatta kalamayan, basit görevleri üstlenen canlılardır. Ancak pek çok adedi bir araya geldiğinde bir bütün olarak organizma gibi davranırlar. Karıncalar, feromon adı verilen kimyasallar aracılığıyla yönlerini bulurlar. Hem feromon salgılarlar, hem de feromona duyarlı canlılardır.

Karıncalar her an az miktarda feromon salgılarlar ve etrafta rastgele hareket ederek yiyecek ararlar. Karıncalar feromon algılamaları halinde, feromonun yoğunluğuna bağlı olarak feromona yönelebilir veya rastgele gezmeye devam edebilir. Yiyecek bulan bir karıncanın feromon salgılaması artar. Bu durum yiyeceğe ulaşmış karıncaların dönüş yolundayken feromon izini güçlendirmesine ve daha çok karıncanın izi takip ederek yiyeceğe ulaşmasına sebep olur.

Bir iz, en çok karıncanın en kısa sürede geçişiyle en verimli haline ulaşır. Dolayısıyla zaman içerisinde besin kaynağı ve koloni arasındaki yol, iki nokta arasındaki en kısa yol haline gelecektir.

Amaç

Projenin amacı, karıncaların yol bulma yeteneklerini simüle etmek, bu simülasyona bağlı olarak bireylerin, ilaçlama şirketlerinin karınca istilasına karşı uygulayabilecekleri çözümler üzerine kolaylaştırmalar sağlamaktır.

Yöntem

Simülasyon, Unity oyun motoru ve C# dili kullanılarak hazırlanmıştır.

Simülasyon; karınca, besin, feromon objelerinin prefabrikleri ve karınca oluşma noktası, besin oluşma noktası, engel çerçevesinde çalışmaktadır. Feromonun kaybolma süresi simülasyonu kullanan kişi tarafından değiştirilebilmektedir.

Karınca, sonlu durum makinesi (finite-state machine) modeline göre hazırlanmıştır.

Mavi yarıçap : içerisindeki feromonlar karınca tarafından algılanamaz. Kırmızı yarıçap : mesafesindeki feromonlar karınca tarafından algılanabilir. Sarı doğru parçaları arasında kalan açı (yeşil yay) : karıncanın feromon ve besin algılayabileceği açıklığı gösterir. Bu üç parametre de simülasyonu kullanan kişi tarafından değiştirilebilmektedir.

Simülasyon içerisindeki maksimum feromon sayısı, besin sayısı, karınca sayısı belirlenir. Karıncalara ve feromonlara ait parametreler ayarlanır (simülasyon başlangıç halinde referans değerlere sahiptir). Simülasyon başlatılır ve sonuçlar gözlemlenir.

Gözlem ve Sonuç

Karıncalar simülasyonun başlamasıyla rastgele biçimde etrafa yayıldılar. Besine ulaşan ilk karınca koloniye dönerek besin kaynağı-koloni arasındaki feromon izini oluşturdu. Onu takip eden diğer karıncalar izin güçlenmesini sağladı.

Zaman içerisinde, izden saparak besine daha kısa yoldan ulaşan karıncalar oldu. Başka karıncaların da eşlik etmesiyle birlikte kısa olan feromon izi daha da güçlendi. İlk ve uzun olan iz kayboldu.

Farklı bir engel eklenerek oluşturulan başka bir simülasyonda karşılaşılan sonuç

Öneriler

• Karınca kolonisini oluşturan kraliçenin ve erkek karıncanın genetik faktörü eklenebilir.
• Evlerin detaylı modellenebilmesi için tırmanılabilir, altından geçilebilir, geçilemez olacak şekilde mobilya-eşya eklemeleri yapılabilir.
• Simülasyon 3 boyutlu hazırlanabilir.
• Karıncaların karakteristikleri yaşlanmayla beraber değişim göstermektedir. Karıncalar için yaşam döngüsü eklenebilir.
• Karıncalar için tehditler eklenebilir (başka koloniler, zehir madde…)

Kurbağanın Talihsiz Zıplamaları Kırık Basamak ve Olasılıkların Dansı

Bir kurbağa düşünelim: her sıçrayışında ya bir ya da iki basamak yukarı çıkıyor. Amacı 75. basamağa ulaşmak. Ancak ortada bir tehlike var: 38. basamak kırık ve kurbağa o basamağa basarsa düşüyor. Bu yazıda, bu eğlenceli ama çetin problemi hem simülasyonla hem de matematiksel yöntemlerle ele alacağız.

🎯 Problemin Özeti

• Kurbağa 1. basamaktan başlıyor.
• Her adımda %50 olasılıkla 1 veya 2 basamak yukarı çıkıyor.
• Ve 38. basamak kırık: kurbağa oraya basarsa oyun biter.
• Amacı 75. basamağa ulaşmak.

Cevaplamak istediğimiz iki soru:

1. Kurbağanın 38. basamağa basma olasılığı nedir?
2. Kurbağa 38. basamağa hiç basmadan 75. basamağa basabilir mi? Olasılığı nedir?

🎲 Monte Carlo Simülasyonu ile Yaklaşım

Simülasyon yöntemiyle bu soruları yaklaşık olarak cevaplayabiliriz. Aşağıdaki Python kodu bu yaklaşımı uygular:

Kibrit Oyunu Projesi

Seçilen bir p asal sayısı ve n doğal sayısı sonrası sırayla oynanan ve 1.000.000 kibrit çöpünden en son kim yerde kalanları toplayacak şeklinde olan bir programlama oyunu. Oyunumuz bilgisayar veya cep telefonu gibi dijital bir ortamda oynanacaktır. İnsan-insan seçeneği olduğu gibi İnsan-Yapayzeka seçeneği de olacaktır. Oyunumuz sanal olarak 1 milyon kibrit çöpü ile başlayacaktır. Sırası gelen oyuncu p bir asal sayı ve n bir doğal sayı olmak üzere iki sayı girecektir (program ikisini de kontrol edecektir). Bilgisayar ortada kalan kibrit çöplerinden p^n adedini çıkaracaktır. Tam olarak yerdeki kibrit çöplerini bir asalın üssü olarak söyleyen kişi oyunu kazanacaktır. (örneğin yerde 125 kibrit çöpü kaldıysa p = 5 ve n = 3 diyen kişi oyunu kazanacaktır. veya 16 kibrit çöpü kaldıysa 2^4 diyen kişi oyunu kazanır. 4^2 diyemez çünkü 4 bir asal sayı değildir) İki insan oynarken hakemlik yapacak programımızın insana karşı yapay zeka modülü de olacaktır. Program görsel olarak windows ve linux tabanlı sistemlerde sorunsuz çalışacaktır. Python tk kütüphanesi kullanılacaktır.

Projemizin amacı, asal sayılar ve özellikleri hakkında bilgileri bir bilgisayar oyunu aracılığıyla kullanıcıya aktarmaktır. Oyun, kullanıcıların asal sayılarla ilgili işlemleri yapma, problem çözme ve birkaç hamle sonrasını düşünme becerilerini geliştirmeyi hedeflemektedir. Ayrıca, yapay zeka destekli bir modül ile insan ve yapay zeka düşünme biçimlerini karşılaştırma imkanı sunulacaktır. Bu modül, kullanıcıların stratejik düşünme becerilerini analiz ederken, yapay zekanın farklı yaklaşımlarını anlamalarına da olanak tanıyacaktır. Oyun, hem eğitici hem de eğlenceli bir platform sunarak matematiksel düşünme ve teknolojik farkındalık oluşturmayı amaçlar.

Oyunu oynayanların asal sayılar hakkında bilgi edinmesini sağlamak ve asal sayı işlemleri konusunda temel beceri kazandırmak.

Oyunu oynayan kişilerin bir kaç hamle ilerisini hesaplamasını sağlamak ve mantık , düşünme becerilerini arttırmak.

Kodlamaya veya programlamaya meraklı kişilerin “basit bir yapay zeka sistemi nasıl oluşturulur” konusunda ilgisini çekmek.

Büyük asalları bulma ve kullanma konusunda beceriler kazandırmak beklediğimiz sonuçlardandır.

Aynı zamanda oyunla matematikteki asal sayların birleştirilmesi oyunu oynayan kişiler açısından bir farkındalık yaratacağı beklenen sonuçlar arasındadır.

Projenin kodu aşağıdadır.

C++ Programlama Dilinde Vektör Kullanımı

Bu yazıda, C++ Standart Kütüphanesi’nin (STL - Standard Template Library) en güçlü ve sık kullanılan veri yapılarından biri olan vektörleri (vectors) detaylı bir şekilde inceleyeceğiz. Vektörler, C++ programcılarına dinamik boyutlu dizilerle çalışma imkanı sunarak bellek yönetimi ve veri depolama konularında büyük kolaylık sağlar. Gelin, vektörlerin ne olduğuna, nasıl kullanıldığına ve geleneksel C-stili dizilere göre avantajlarına birlikte göz atalım.

Vektör Nedir?

C++’ta std::vector, elemanları aynı türden olan ve dinamik olarak yeniden boyutlandırılabilen bir dizi konteyneridir. Geleneksel C dizilerinin aksine, bir vektörün boyutu çalışma zamanında (runtime) artırılabilir veya azaltılabilir. Bu, programın ihtiyaçlarına göre esnek bir şekilde veri saklamamıza olanak tanır. Vektörler, bellek yönetimini kendileri üstlenirler, bu da programcıyı manuel bellek ayırma ve serbest bırakma zahmetinden kurtarır.

Vektörler, vector başlık dosyası (#include <vector>) altında tanımlanmıştır ve std isim alanı (namespace) içinde bulunurlar.

Neden Vektör Kullanmalıyız?

Geleneksel C-stili dizilere kıyasla vektörlerin birçok avantajı vardır:

Dinamik Boyutlandırma: En önemli avantajıdır. Dizilerin boyutu derleme zamanında sabitken, vektörlerin boyutu çalışma zamanında değişebilir.

Otomatik Bellek Yönetimi: Vektörler, elemanlar eklendikçe veya çıkarıldıkça belleği otomatik olarak yönetir. Bu, new ve delete (veya malloc ve free) ile manuel bellek yönetimi ihtiyacını azaltır ve bellek sızıntıları (memory leaks) gibi hataların önüne geçer.

Zengin Fonksiyon Seti: Vektörler, eleman ekleme, silme, boyut sorgulama, kapasite yönetimi gibi birçok kullanışlı üye fonksiyona sahiptir.

Güvenlik: at() fonksiyonu ile sınırlı erişim kontrolü sağlayarak dizi sınırlarının aşılması (out-of-bounds access) durumunda istisna fırlatır.

STL Algoritmaları ile Uyumluluk: Vektörler, STL’deki sıralama, arama, dönüştürme gibi birçok algoritma ile sorunsuz bir şekilde kullanılabilir.

Vektörlerin Temel Kullanımı

Şimdi vektörlerin C++ kodunda nasıl kullanıldığına dair temel adımlara bakalım.

1. Vektör Kütüphanesini Dahil Etme ve İsim Alanı

Bir vektör kullanmadan önce, programınıza vector başlık dosyasını dahil etmeniz gerekir:

C++ İşaretçiler (Pointers)

İşaretçiler, C++ programlamada bellekteki diğer değişkenlerin adreslerini tutan özel değişkenlerdir. Bellek yönetimi, dinamik veri yapıları oluşturma ve fonksiyonlara argümanları referans yoluyla geçirme gibi birçok güçlü programlama tekniği için temel teşkil ederler.

İşaretçi Nedir?

Bir işaretçi, bir veri türünün bellekteki konumunu (adresini) saklar. Bir değişkenin adresini bir işaretçide sakladığınızda, o işaretçi o değişkene “işaret eder”.

İşaretçi Tanımlama

Bir işaretçi, işaret edeceği veri türü ve ardından bir yıldız işareti (*) ile tanımlanır.

Kaç Tane Var

Elimizde bir problem var. Bir sayı dizisi. Öncelikle bu bir ilişki bulma sorusu. Ama bu soruyu bir programlama veya algoritma sorusuna da çevirebiliriz. Soru aşağıdaki gibi.

• 1
• 11
• 21
• 1211
• 111221

Sırada ki sayı kaçtır?

Permütasyon ve Kombinasyon Örnekleri

Bu belge, permütasyon ve kombinasyon kavramlarını kısaca açıklamakta ve örnek sorularla pekiştirmektedir.

Permütasyon (Sıralama)

Permütasyon, belirli bir kümenin elemanlarının farklı sıralanışlarının sayısını ifade eder. Sıralamanın önemli olduğu durumlarda permütasyon kullanılır.

Segment Ağacı ile Inversion Sayma

Bu kod, bir dizideki inversion sayısını hesaplamak için Segment Ağacı kullanır. Inversion, bir dizideki sıralı olmayan çiftlerin sayısıdır. Bu, dizinin ne kadar “sıralı olmadığı”nın bir ölçüsüdür.

Segment Ağacı, bir dizi üzerinde aralık sorgularını verimli bir şekilde gerçekleştirmek için kullanılan bir veri yapısıdır. Bu kodda, Segment Ağacı, dizideki her bir elemanın “sıkıştırılmış” değerini kullanarak, o elemandan daha büyük elemanların sayısını takip etmek için kullanılır. Bu sayede, her bir eleman için yapılan sorgularla toplam inversion sayısı bulunur.

Aşağıdaki C++ kodu, Segment Ağacı kullanarak bir dizideki inversion sayısını hesaplar:

Segment Ağacı ile Aralık Maksimumu Bulma

Bu kod, bir dizi üzerinde aralık maksimumu sorgularını verimli bir şekilde gerçekleştirmek için bir Segment Ağacı kullanır. Segment Ağacı, bir dizi üzerinde tanımlanmış bir ağaç yapısıdır ve her düğüm, dizinin bir alt aralığını temsil eder. Bu sayede, belirli bir aralıktaki maksimum değeri bulma işlemi, dizinin tamamını taramak yerine ağaç üzerinde daha az sayıda düğümü ziyaret ederek gerçekleştirilebilir.

Bu kodda, Segment Ağacı kullanılarak, verilen bir dizideki belirli bir aralıktaki en büyük elemanı bulmak için query fonksiyonu ve bir elemanın değerini güncellemek için update fonksiyonu uygulanmaktadır. build fonksiyonu ise Segment Ağacını oluşturmak için kullanılır.

Aşağıdaki C++ kodu, Segment Ağacı kullanarak bir dizideki aralık maksimumunu bulmayı sağlar:

Merge Sort ile Inversion Sayma

Bu kod, Merge Sort algoritmasını kullanarak bir dizideki inversion sayısını hesaplar. Inversion, bir dizideki sıralı olmayan çiftlerin sayısıdır. Başka bir deyişle, bir dizideki i ve j indisleri için, eğer i < j ve a[i] > a[j] ise, bu bir inversion’dır. Inversion sayısı, bir dizinin ne kadar “sıralı olmadığı”nın bir ölçüsüdür; sıralı bir dizide inversion sayısı 0’dır.

Merge Sort, böl ve yönet yaklaşımını kullanan, verimli bir sıralama algoritmasıdır. Diziyi ardışık olarak iki alt diziye böler, her bir alt diziyi sıralar ve sonra sıralı alt dizileri birleştirir. Bu birleştirme işlemi sırasında, alt dizilerdeki elemanların göreli sırasını takip ederek inversion sayılarını hesaplayabiliriz. Özellikle, sol alt dizideki bir eleman sağ alt dizideki bir elemandan büyükse, bu bir inversion anlamına gelir ve bu durumdaki inversion sayısı, sol alt dizideki kalan elemanların sayısı kadardır.

Aşağıdaki C++ kodu, Merge Sort algoritmasını kullanarak bir dizideki inversion sayısını hesaplar.

Go Programlama

Go, Google tarafından geliştirilen, açık kaynaklı bir programlama dilidir. Hız, basitlik ve güvenilirlik üzerine odaklanmıştır. Özellikle sistem programlama, ağ programlama ve büyük ölçekli yazılım projeleri için uygundur.

Go’nun Özellikleri

Go’nun bazı temel özellikleri şunlardır:

• Basitlik: Go’nun sözdizimi temiz ve anlaşılırdır, bu da öğrenmeyi ve kod yazmayı kolaylaştırır.
• Hız: Go, derlenen bir dildir ve yüksek performans sunar.
• Eşzamanlılık: Go, goroutine’ler ve kanallar aracılığıyla eşzamanlı programlamayı kolaylaştırır.
• Güvenlik: Go, bellek güvenliği konusunda titizdir ve çöp toplama özelliği sayesinde bellek sızıntılarını önler.
• Statik Tiplendirme: Go, statik tiplendirme ile derleme zamanında hataları yakalar.
• Platform Bağımsızlığı: Go, farklı işletim sistemlerinde (Windows, macOS, Linux) çalışabilir.

Küp şeklinde satranç ve vezirler

Elimizde 8x8x8 lik bir satranç kübü var. Bu tahtaya birbirini yemeyen maksimum kaç vezir yerleştirilir? (Vezirler derinlemesine de hareket edebilmektedir)

Aşağıdaki program vezirlerinizi sırayla koyduktan sonra tahtanızı ve boş yerleri gösterecektir. Bu soru için program yazabilir ve en hızlı çözümü bulmaya çalışabilirsiniz. Tahmin olarak da yazabilirsiniz yorumunuzu.