Çoğu durumda, numaralandırma sorunları özyinelemeli numaralandırma ile çözülür. Ne yazık ki, genel bir yaklaşım yoktur, çünkü genellikle, yineleme yöntemleri büyük ölçüde görevin kendisine bağlıdır.
Bununla birlikte, çeşitli kombinatoryal nesnelerin numaralandırılması yöntemleri arasında bazı benzerlikler görülebilir. Bu nedenle, açıklayıcı bir örnek olarak, n'den k'ye kadar tüm kombinasyonları oluşturan bir kodu ele alalım.
int n, k;
// Kombinasyon öneklerini destekleyen bir dizi.
//
// Bu durumda önek, kombinasyonda bazı nesneleri seçtiğimiz anlamına gelir.
//
// Daha sonra, ya doğru kombinasyonda tamamlanacaklar,
// veya özyineleme, böyle bir önekin doğru şekilde tamamlanamayacağını anladığında dalı kesecektir.
vektör dizi;
// özyinelemeli yineleme işlevinin kendisi
//
// konum - şu anda belirleyeceğimiz kombinasyondaki nesnenin sayısı (0'dan k - 1'e)
//
// önceki - önceki adımda alınan nesnenin değeri
//
// Kombinasyonlarda nesnelerin sırası önemli değildir ([1, 2] ve [2, 1] aynı ve benzer kabul edilir),
// yani sadece nesne değerlerinin artan sırada olduğu kümeler oluşturmak istiyoruz.
//
// [1, 2] ve [2, 1] gibi aynı seçeneklerin yalnızca bir kez yinelenmesi için bu gereklidir
// (bizim durumumuzda, yalnızca [1, 2]'yi dikkate alacağız, ancak sıralı bir küme olmadığı için [2, 1]'i dikkate almayacağız).
//
// Bu yüzden yineleme sayısını azaltmak için prev değişkenini tutuyoruz
geçersiz kayıt(int konum, int önceki) {
// seçilen elemanın sayısı k'ye eşitse, o zaman zaten tüm elemanları seçmişiz demektir
// Çünkü sayıları 0 ile k - 1 arasındadır
eğer (konum == k) {
// koşul sağlanıyorsa, doğru kombinasyon artık arr dizisindedir
// ve onu bir şekilde işleyebiliriz (bu durumda konsola yazdırmanız yeterli)
için (int i = 0; i < k; i++)
cout n - önceki - 1)
geri dönmek;
// index pos ile pozisyona koyduğumuz nesneyi yineliyoruz
// ama çünkü sıralı bir küme istiyoruz, o zaman mümkün olan minimum değer önceki + 1'dir.
for (int i = önceki + 1; i < n; i++) {
arr.push_back(i); // Global diziye bir eleman ekleyin. Şimdi onu seçmiş görünüyoruz.
rec(konum + 1, i); // aşağıdaki öğeleri ayarlamak için yinelemeli olarak çalıştırın
arr.pop_back(); // özyinelemeden döndükten sonra, şu anda seçili olan öğemiz artık alakalı değil,
// Çünkü özyineleme içinde, böyle bir önekle tüm seçenekleri gözden geçirdik,
// yani bu elemanın kaldırılması gerekiyor
}
}
int ana()
{
cin>> n>> k;
// başlangıçta elemanı 0. konuma ayarlayacağız
// -1 öğesinin daha önce seçildiğini varsayıyoruz, böylece yineleme başlangıçta boş bir nesneden başlıyor
rec(0, -1);
0 dönüşü;
}
Aynı kod, ancak yorumsuz:
int n, k;
vektör dizi;
geçersiz kayıt(int konum, int önceki) {
eğer (konum == k) {
için (int i = 0; i < k; i++)
cout n - önceki - 1)
geri dönmek;
for (int i = önceki + 1; i < n; i++) {
arr.push_back(i);
rec(konum + 1, i);
arr.pop_back();
}
}
int ana() {
cin>> n>> k;
rec(0, -1);
0 dönüşü;
}
Özyinelemeli yinelemelerde, özyineleme kesintilerine her zaman özel dikkat gösterilmelidir. Uygulamada, programı büyük ölçüde hızlandırabilirler.
|