LeetCode 1518 numaralı “Su Şişeleri” problemi, ilk bakışta basit görünse de, programlama dünyasında sıkça karşılaşılan döngüsel mantık ve kaynak yönetimi senaryolarına güzel bir örnek teşkil eder. Bu makalede, LeetCode’un bu popüler sorusunu C++ dilinde adım adım nasıl çözeceğimizi, temel iteratif yaklaşımdan matematiksel optimizasyonlara kadar tüm detaylarıyla inceleyeceğiz. Problem, elinizdeki belirli sayıda tam dolu su şişesini tüketip, boş şişeleri belirli bir oranda yeni dolu şişelerle takas ederek toplamda kaç şişe su içebileceğinizi hesaplamanızı istiyor. Peki, bu basit takas işlemi nasıl bir algoritma gerektirir?
Girişimizi biraz daha genişleterek bu problemin aslında ne kadar günlük hayatımıza yakın olduğunu vurgulayalım. Düşünün ki, bir süpermarketin sadakat programına katıldınız ve her 3 boş kutu meyve suyunu iade ettiğinizde size bir tane bedava dolu kutu veriliyor. Ya da bir kahve dükkanında her 5 boş karton bardağı getirdiğinizde bir ücretsiz kahve kazanıyorsunuz. İşte Su Şişeleri problemi de tam olarak bu türden döngüsel bir takas mekanizmasını modellemektedir. İlk başta elinizdeki şişeleri içersiniz, ardından boş şişelerinizi sayar, takas edebilirseniz yeni dolu şişeler elde edersiniz ve bu yeni şişeleri de içersiniz. Bu süreç, elinizde takas edilebilecek kadar boş şişe kalmayana kadar devam eder. Bu problem, hem döngüsel düşünme becerisini geliştirir hem de basit aritmetik işlemlerin doğru sırayla uygulanmasının ne kadar önemli olduğunu gösterir. Amacımız, en optimal ve anlaşılır C++ çözümünü sunarak bu süreci baştan sona kavramanıza yardımcı olmaktır.
Temel Kavramlar ve Iteratif Çözüm Mantığı: Boş Şişeleri Doluya Çevirme Sanatı
Su Şişeleri problemi, iki temel parametreye dayanır: numBottles ve numExchange. numBottles, başlangıçta sahip olduğunuz tam dolu su şişesi sayısını, numExchange ise, bir yeni tam dolu şişe alabilmek için kaç adet boş şişe takas etmeniz gerektiğini belirtir. Hedefimiz, bu döngüsel takas mekanizmasını kullanarak toplamda kaç şişe su içtiğimizi bulmaktır. Bu problemde en doğal ve anlaşılır çözüm yaklaşımlarından biri iteratif (döngüsel) çözümdür.
Iteratif yaklaşımın temel mantığı oldukça basittir: Mevcut dolu şişeleri içeriz, içtiğimiz bu şişeler boş şişeye dönüşür. Ardından, biriktirdiğimiz boş şişelerle takas yapmaya çalışırız. Eğer takas edebilecek kadar boş şişemiz varsa, yeni dolu şişeler alırız ve bu süreci yeni şişeler bitene kadar tekrarlarız. Bu döngü, takas yapamayacak kadar az boş şişemiz kalana kadar devam eder. Bu yaklaşım, problemin doğasını doğrudan yansıttığı için hem kavraması kolay hem de genellikle ilk akla gelen çözümdür.
Bir örnekle somutlaştıralım: Diyelim ki numBottles = 9 ve numExchange = 3. Süreç şöyle işleyecektir:
- Başlangıç: Elimizde 9 dolu şişe var. İçilen toplam şişe sayısı: 0. Boş şişe sayısı: 0.
- Adım 1: 9 dolu şişeyi içeriz. İçilen toplam şişe sayısı: 9. Artık 9 boş şişemiz var.
- Adım 2: 9 boş şişeyle takas yapabiliriz.
9 / 3 = 3yeni dolu şişe alırız. Boş şişe sayımızdan 9’u çıkarırız, 3 yeni şişe için 9 boş şişe kullandığımızdan kalan boş şişe sayımız9 % 3 = 0olur. - Adım 3: Elimizde 3 yeni dolu şişe var. Bu 3 şişeyi de içeriz. İçilen toplam şişe sayısı:
9 + 3 = 12. Artık 3 yeni boş şişemiz var. Kalan boş şişe sayısı:0 + 3 = 3. - Adım 4: 3 boş şişeyle tekrar takas yapabiliriz.
3 / 3 = 1yeni dolu şişe alırız. Kalan boş şişe sayımız3 % 3 = 0olur. - Adım 5: Elimizde 1 yeni dolu şişe var. Bu 1 şişeyi de içeriz. İçilen toplam şişe sayısı:
12 + 1 = 13. Artık 1 yeni boş şişemiz var. Kalan boş şişe sayısı:0 + 1 = 1. - Adım 6: Elimizde 1 boş şişe var. Takas için 3 boş şişeye ihtiyacımız olduğu için başka takas yapamayız.
Sonuç olarak, toplamda 13 şişe su içmiş oluruz. Görüldüğü üzere, bu problem döngüsel bir düşünce yapısı gerektirir ve bu adımları doğru bir şekilde kodlamak, başarılı bir çözüm için anahtardır. Bu iteratif süreç, problemdeki kaynak yönetimi dinamiklerini açıkça ortaya koyar ve her adımda mevcut durumu güncelleyerek ilerler.
C++ ile Adım Adım Implementasyon: Kodu Hayata Geçirmek
Iteratif çözüm mantığını anladığımıza göre, şimdi bu mantığı C++ koduna dökelim. Algoritmamız, toplam içilen şişe sayısını ve mevcut boş şişe sayısını takip ederek ilerleyecektir. İşlem, elimizdeki boş şişelerle yeni dolu şişe takas edemeyecek duruma gelene kadar bir while döngüsü içinde devam edecektir.
Algoritma Adımları:
- Toplam içilen şişe sayısını tutacak bir değişkeni (
totalDrunkBottles) başlangıçta 0 olarak tanımlayın. - Mevcut boş şişe sayısını tutacak bir değişkeni (
emptyBottles) başlangıçta 0 olarak tanımlayın. - Bir
whiledöngüsü başlatın. Bu döngü, mevcut dolu şişelerimiz (numBottles) 0 olana veya takas yapamayacak kadar az boş şişemiz kalana (emptyBottles < numExchange) kadar devam edebilir. Ancak daha basit bir yaklaşım, her adımda mevcut dolu şişeleri içip sonra takas yapmaktır. - Döngü içerisinde:
- İlk olarak, elimizdeki tüm dolu şişeleri (
numBottles) içelim. Bu şişe sayısınıtotalDrunkBottles'a ekleyin. - İçtiğimiz bu şişeler artık boş şişelerdir. Dolayısıyla,
emptyBottlessayısınanumBottlesdeğerini ekleyin. - Elimizdeki dolu şişe sayısı 0 oldu (
numBottles = 0). - Şimdi, elimizdeki
emptyBottlesile kaç tane yeni dolu şişe (newBottles) alabileceğimizi hesaplayın:newBottles = emptyBottles / numExchange. - Eğer
newBottles0 ise, daha fazla takas yapamayız. Döngüyü sonlandırın. - Takas sonucu kalan boş şişe sayısını güncelleyin:
emptyBottles = emptyBottles % numExchange. - Yeni elde ettiğimiz dolu şişeleri (
newBottles) bir sonraki döngüde içmek üzerenumBottlesdeğişkenine atayın.
- İlk olarak, elimizdeki tüm dolu şişeleri (
- Döngü bittikten sonra,
totalDrunkBottlesdeğeri nihai cevabımız olacaktır.
Bu adımları takip ederek aşağıdaki C++ kodunu yazabiliriz:
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
int totalDrunkBottles = 0; // Toplam içilen şişe sayısı
int emptyBottles = 0; // Mevcut boş şişe sayısı
while (numBottles > 0) {
// Mevcut dolu şişeleri iç
totalDrunkBottles += numBottles;
emptyBottles += numBottles;
numBottles = 0; // Şişeler içildikten sonra dolu şişe kalmaz
// Boş şişelerle takas yapabilecek miyiz kontrol et
if (emptyBottles >= numExchange) {
int newBottles = emptyBottles / numExchange; // Kaç yeni şişe alabiliriz
emptyBottles = emptyBottles % numExchange; // Takastan sonra kalan boş şişeler
numBottles = newBottles; // Yeni elde edilen dolu şişeleri ekle
} else {
// Takas yapacak kadar boş şişe yok, döngüyü sonlandır
break;
}
}
return totalDrunkBottles;
}
};
Uygulamalı Örnek ve Değişken Takibi:
Kodumuzu numBottles = 15 ve numExchange = 4 değerleriyle test edelim:
| Adım | numBottles (Başlangıç) | totalDrunkBottles | emptyBottles | newBottles (Hesaplanan) | numBottles (Sonraki Döngü) |
|---|---|---|---|---|---|
| Başlangıç | 15 | 0 | 0 | - | 15 |
| 1. Döngü (İçme) | 15 | 15 | 15 | - | 0 |
| 1. Döngü (Takas) | 0 | 15 | 15 | 15 / 4 = 3 |
3 |
15 % 4 = 3 |
|||||
| 2. Döngü (İçme) | 3 | 15 + 3 = 18 |
3 + 3 = 6 |
- | 0 |
| 2. Döngü (Takas) | 0 | 18 | 6 | 6 / 4 = 1 |
1 |
6 % 4 = 2 |
|||||
| 3. Döngü (İçme) | 1 | 18 + 1 = 19 |
2 + 1 = 3 |
- | 0 |
| 3. Döngü (Takas) | 0 | 19 | 3 | 3 / 4 = 0 |
0 |
Sonuç olarak 19 şişe su içmiş oluruz. Bu tablo, kodumuzun her adımda değişkenlerin nasıl güncellendiğini açıkça göstermektedir. Bu yöntem, problemin akışını anlamak için oldukça faydalıdır. Özellikle, numBottles sıfırlandığında ve newBottles ile tekrar dolduğunda döngünün nasıl devam ettiğini görmek önemlidir.
Mobil Uyumlu Kod Gösterimi İçin İpuçları
Modern web geliştirme pratiklerinde, kod örneklerini mobil cihazlarda da okunabilir tutmak kritik öneme sahiptir. Yukarıdaki CSS içinde @media (max-width: 768px) sorgusunu kullanarak pre etiketlerinin white-space: pre-wrap; özelliği ile kodun otomatik olarak sarılmasını sağladık. Bu, kod bloklarının ekran genişliğini aşmasını engelleyerek yatay kaydırma ihtiyacını ortadan kaldırır. Ek olarak, tablo gibi içeriklerin küçük ekranlarda kaydırılabilir olmasını sağlamak da benzer şekilde kullanıcı deneyimini iyileştirir.
/* Örnek bir mobil uyumlu CSS medya sorgusu */
@media (max-width: 768px) {
pre {
white-space: pre-wrap; /* Kodu yeni satıra sar */
word-wrap: break-word; /* Uzun kelimeleri kır */
}
table {
display: block; /* Tabloyu blok eleman yap */
overflow-x: auto; /* Yatay kaydırma çubuğu ekle */
}
}
Bu tür optimizasyonlar, teknik makalelerin farklı cihazlarda rahatça okunabilmesini garantiler ve okuyucunun içeriğe erişimini kolaylaştırır.
Performans, İleri Düzey Optimizasyon ve Gerçek Dünya Uygulamaları
LeetCode 1518 problemine getirdiğimiz iteratif çözüm, anlaşılırlığı ve doğrudan problem tanımına uygunluğu nedeniyle oldukça güçlüdür. Ancak her zaman olduğu gibi, bir çözümün performansını ve potansiyel ileri düzey yaklaşımları değerlendirmek önemlidir.
Performans Analizi: Zaman ve Uzay Karmaşıklığı
Yukarıdaki iteratif çözümün zaman karmaşıklığı O(numBottles / numExchange) olarak ifade edilebilir. Her döngü adımında, numBottles değeri, takas oranıyla orantılı olarak azalır. Örneğin, her takasta 3 boş şişe karşılığında 1 dolu şişe alıyorsak, efektif olarak numExchange - 1 boş şişe "kaybederiz" veya bir başka deyişle, numExchange - 1 şişe başına bir iterasyon daha yaparız. Dolayısıyla, döngü sayısı başlangıçtaki numBottles değerine bağlıdır ve numExchange ile ters orantılıdır. Özellikle numExchange'in büyük olduğu durumlarda döngü çok hızlı sonlanır. Bu, çoğu pratik senaryo için oldukça verimli bir yaklaşımdır. Uzay karmaşıklığı ise O(1)'dir, çünkü sadece sabit sayıda değişken kullanırız.
İleri Düzey Yaklaşım: Matematiksel Çözüm
Bazı LeetCode problemlerinde iteratif bir çözümün yanı sıra, doğrudan matematiksel bir formül de bulunabilir. "Su Şişeleri" problemi de bu türden bir potansiyele sahiptir. İlk içilen şişe sayısından sonra, her numExchange - 1 adet içilen şişe için fazladan bir şişe kazanma döngüsü oluşur (çünkü numExchange boş şişeden 1 dolu şişe gelirse, net numExchange - 1 boş şişe 'harcanmış' olur). Ancak başlangıçtaki numBottles adet şişe tamamen içildiğinde numBottles adet boş şişemiz olur. Bu boş şişelerle yeni şişeler elde ettiğimizde, her seferinde net numExchange - 1 boş şişe "kaybederiz" (bir dolu şişe için numExchange boş veririz, ama içtiğimiz bu dolu şişe de bize 1 boş şişe olarak geri döner, yani net numExchange - 1 boş şişe harcanmış olur).
Bu döngü, elimizdeki boş şişeler numExchange'den az olana kadar devam eder.
Basit bir formül şu şekilde türetilebilir: totalDrunk = numBottles + (numBottles - 1) / (numExchange - 1). Bu formül, numExchange > 1 ve numBottles >= numExchange olduğu durumlarda geçerlidir. Eğer numBottles < numExchange ise, başlangıçtaki numBottles kadar içebiliriz, fazlası olmaz.
numExchange = 1 gibi durumları (sonsuz döngü olacağı için problem kısıtlamaları genellikle bunu engeller) veya numBottles < numExchange gibi durumları özel olarak ele almalıdır.
Aşağıda, bu matematiksel yaklaşımı kullanan bir C++ çözümü bulunmaktadır:
class Solution {
public:
int numWaterBottles(int numBottles, int numExchange) {
if (numBottles < numExchange) {
return numBottles; // Takas yapamayız, sadece elimizdekileri içeriz.
}
// Başlangıçta içilen şişeler
int totalDrunk = numBottles;
// Her numExchange-1 boş şişe için 1 yeni şişe elde ederiz.
// İlk numBottles şişeyi içtikten sonra numBottles adet boş şişemiz olur.
// Bu boş şişelerle takas yaparak ilerleriz.
// Alternatif olarak, iteratif çözümün basitliğini tercih etmek çoğu zaman daha güvenilirdir.
// Ancak doğrudan formül meraklıları için:
// totalDrunk += (numBottles - numExchange) / (numExchange - 1) + 1; // Bu formül karmaşık köşe durumları içerebilir
// En doğru matematiksel formül, her adımı simüle etmeye dayalıdır.
// Basit iteratif çözüme devam etmek en iyisidir. Ancak bu formül de mümkündür:
// totalDrunk = numBottles + (numBottles - 1) / (numExchange - 1); // Bu da bazı köşe durumlarında farklı sonuç verebilir.
// LeetCode'da genelde iteratif çözüm en anlaşılır ve hataya az açık olandır.
// Yine de bu formülün çalışma mantığı: Her N-1 şişeyi takas ettiğimizde 1 şişe kar ederiz (N şişe verir 1 yeni alırsın, bu 1 yeni de N-1 boş şişe harcanmış gibi bir net etki yaratır).
// Bu da (numBottles - 1) / (numExchange - 1) ek şişe verir.
// totalDrunk += (numBottles - 1) / (numExchange - 1);
// Doğrusu, mevcut boş şişelerin ve yeni doluların birikimli toplamı üzerine kuruludur.
// Basit iteratif çözüm, matematiksel olanın aslında nasıl çalıştığını açıklar.
// Daha iyi bir matematiksel formül şudur:
// int newBottlesFromExchange = (numBottles - 1) / (numExchange - 1);
// return numBottles + newBottlesFromExchange;
// Bu formül sadece numExchange > 1 için ve numBottles >= numExchange için geçerlidir.
// Diğer durumları iteratif çözüm daha doğal ele alır.
// Basitlik ve genellik için iteratif çözüm daha iyidir.
// Matematiksel çözümü uygulamak istersek:
// Eğer numExchange > numBottles ise, sadece numBottles kadar içebiliriz.
// Eğer numExchange == 1 ise, sonsuz döngü (LeetCode kısıtlamaları bunu engeller: numExchange >= 2).
// Bu durumda en güvenli yol iteratif çözüm veya dikkatlice yazılmış bir formüldür.
// İteratif olanın performansı da oldukça iyidir.
// Yine de, matematiksel formülü denemek istersek:
// Toplam içilen şişe sayısı başlangıçtaki numBottles'a ek olarak,
// takaslardan gelen ek şişelerin toplamı olacaktır.
// Her numExchange boş şişeden 1 dolu şişe alırız, bu da 1 şişelik bir "net kazanç" demektir,
// Ancak bu kazanç için numExchange - 1 şişe boş şişeyi "harcarız".
// İlk numBottles şişeyi içtikten sonra numBottles boş şişemiz olur.
// Bu boş şişelerle kaç kere ek şişe alabiliriz?
// (numBottles - 1) / (numExchange - 1)
// Eğer numBottles < numExchange ise bu ifade negatif veya sıfır olabilir.
// Bu yüzden güvenli formül:
int drank = numBottles;
int empty = numBottles;
while (empty >= numExchange) {
int newB = empty / numExchange;
drank += newB;
empty = empty % numExchange + newB;
}
return drank;
// Görüldüğü gibi, matematiksel formül yerine iteratif çözüm hem daha anlaşılır hem de tüm durumları daha doğal kapsıyor.
// LeetCode testlerinde doğrudan matematiksel formül aramak yerine iteratif çözümü tercih etmek daha risksizdir.
// Ancak eğer böyle bir formül olsaydı genellikle şu şekilde olurdu:
// return numBottles + (numBottles - numExchange) / (numExchange - 1) + 1; // bu formülün bazı varsayımları var.
// Daha basit ve güvenli bir matematiksel model:
// total = numBottles;
// empty = numBottles;
// total += (empty - empty % numExchange) / (numExchange -1);
// Bu formül de köşe durumlarında sıkıntı çıkarabilir.
// Sonuç olarak, iteratif çözüm genellikle en sağlamıdır.
}
};
Yukarıdaki matematiksel çözüm kısmında, aslında iteratif çözümün basitliğini ve her durumu kapsama gücünü vurgulamak için bir tartışma başlattık. LeetCode gibi platformlarda, karmaşık matematiksel formüller yerine çoğu zaman doğru işleyen ve anlaşılır iteratif çözümler tercih edilir. Ancak, problemin derinlemesine anlaşılması için farklı bakış açılarını değerlendirmek önemlidir.
Gerçek Dünya Uygulamaları: Kaynak Yönetiminden Sadakat Programlarına
Su Şişeleri problemi, sadece bir LeetCode sorusu olmaktan öte, gerçek dünyadaki birçok senaryoyu modelleyebilir. En belirgin örnekler kaynak yönetimi ve sadakat programlarıdır:
- Geri Dönüşüm ve Üretim Döngüleri: Bir fabrika, belirli miktarda atık malzemeyi geri dönüştürerek yeni bir ürün üretebilir. Örneğin, her 100 kg plastik atıktan 10 kg yeni ürün elde ediliyorsa, başlangıçta eldeki 1000 kg atıkla kaç kg ürün üretilebileceği bu mantıkla hesaplanabilir. Boş şişeler atık malzemeyi, yeni şişeler yeni ürünü temsil eder.
- Müşteri Sadakat Programları: Daha önce bahsettiğimiz gibi, birçok işletme müşteri sadakatini artırmak için programlar sunar. "Her 5 alışverişte bir sonraki ücretsiz" veya "her 10 boş ambalaj getirana bir indirim çeki" gibi kampanyalar, Su Şişeleri problemindeki takas mantığına benzerdir. Burada
numExchange, takas için gereken boş ambalaj/alışveriş sayısıdır. - Enerji Verimliliği ve Yenilenebilir Kaynaklar: Bazı enerji sistemlerinde, üretilen enerjinin bir kısmı sistemin kendi çalışması için harcanırken, bir kısmı da yeni enerji üretimini tetiklemek için kullanılabilir. Bu, sınırlı kaynaklarla sürdürülebilir bir döngü oluşturma prensibine dayanır.
Bu vaka analizleri, basit bir programlama probleminin arkasında yatan evrensel prensiplerin, farklı sektörlerde nasıl uygulanabileceğini göstermektedir. Problemleri soyutlayıp genelleyici çözümler üretmek, bir yazılımcının en değerli becerilerinden biridir.
Sonuç ve Sıkça Sorulan Sorular: Bilgilerinizi Pekiştirin
Bu makalede, LeetCode 1518 numaralı Su Şişeleri problemini C++ dilinde detaylı bir şekilde inceledik. Başlangıçtaki dolu şişeler ve takas oranı gibi temel değişkenlerle yola çıkarak, adım adım iteratif bir çözüm geliştirdik. Bu çözüm, mevcut dolu şişeleri içme, boş şişeleri toplama ve takas etme süreçlerini bir döngü içinde simüle ederek nihai sonuca ulaşır. Ayrıca, çözümümüzün zaman ve uzay karmaşıklığını analiz ettik ve teorik olarak mümkün olabilecek matematiksel bir yaklaşımı da tartıştık. Gerçek dünya senaryolarıyla problemimizin ne kadar geniş bir uygulama alanına sahip olduğunu da görmüş olduk.
Unutmayın ki problem çözme yeteneği, sadece kodu yazmakla sınırlı değildir; aynı zamanda problemin özünü anlamak, farklı yaklaşımları değerlendirmek ve çözümünüzü test etmekle de yakından ilgilidir. Su Şişeleri problemi, bu becerilerin tümünü geliştirmek için harika bir başlangıç noktası sunmaktadır. Şimdi gelin, bu konu hakkında sıkça sorulan bazı sorulara göz atalım:
Sıkça Sorulan Sorular (SSS)
-
S: Su Şişeleri problemi neden önemlidir?
C: Bu problem, döngüsel mantık, kaynak yönetimi ve basit aritmetik işlemlerin programatik olarak nasıl modelleneceğini öğretir. Gerçek dünyada sadakat programları, geri dönüşüm sistemleri veya üretim döngüleri gibi birçok senaryonun temelini oluşturur.
-
S: Problemi çözmek için iteratif yaklaşım mı yoksa matematiksel formül mü daha iyidir?
C: Çoğu durumda, iteratif çözüm hem daha anlaşılır hem de tüm köşe durumlarını daha doğal bir şekilde ele alır. Matematiksel formüller daha kısa kod sağlayabilse de, doğru türetilmesi ve tüm senaryoları kapsadığından emin olunması zordur. Genellikle iteratif çözüm tercih edilir.
-
S:
numExchangedeğeri 1 olsaydı ne olurdu?C: Problem kısıtlamaları genellikle
numExchangedeğerinin en az 2 olmasını garanti eder. Eğer 1 olsaydı, her boş şişe için bir yeni şişe alırdık ve bu da sonsuz bir döngüye yol açardı, çünkü her içtiğimiz şişe bize yeni bir şişe kazandırırdı. -
S: Başlangıçta
numBottlesdeğerinumExchangedeğerinden az olursa çözüm nasıl değişir?C: Eğer
numBottles < numExchangeise, başlangıçtaki tüm şişeleri içeriz ancak takas yapamayız çünkü yeterli boş şişemiz olmaz. Çözüm, sadece başlangıçtakinumBottlesdeğerini döndürür.