Dinamik programlamada çekirdek döküm hatası

Question

Belirli bir değişim miktarı için gereken en az sayıda jetonu belirleyen bir programı değiştiriyorum. Bu bozuk para sisteminde sadece üç para var: 0,01 $, 0,06 $, 0,10 $. Yani 13 sent için, paralar 3 ise minimum sayıdır. 56 sent için, minimum sayı 6'dır. Program bu kısmı yapar, benim kullandığım her jetonun numarasını belirlemek için not tablosunu takip etmektir. Örneğin, 13 sent için asgari 3 jeton ve bu paralar 2 6-cent sikke ve 1 1-cent sikke olur. biz her zaman sağ alttaki başlamak böyle bir şey için

1cent 0 1 2 3 4 5 6 7 8 9 10 11 12 13 
6cent 0 1 - 3 - - - 2 - - - - - 3 
10cent 0 - - 3 - - - - - - - - - 3 

:

Aşağıda oluşturulan not tablo gibi görünür. Bunu yinelemeli olarak yapmaya çalışıyorum. Bir desen fark ettim. Bir numaramız varsa ve bunun üzerindeki sayı aynı sayı değilse, aynı satırın cent boşluklarının soluna "atlar". Alt satırda, 10 cent satırında, sonunda 13 ile 3 arasında 10 boşluk olan bir sıçrama görüyoruz. Eğer bir sayı ve yukarıdaki sayı aynı ise, bu, madeni paraların birçok kez kullanılmasından sonra bir satır yukarı doğru hareket ettiğimiz anlamına gelir. Yukarıdaki tabloda, sağ alt köşede, 3 başlıyoruz. Yukarıdaki sayı da 3 olup, 0 "atlamalı" olduğundan, kullanılan 10 sentlik jetonun sayısı 0'dır ve bir sonraki satıra, 6 cent satırına geçiyoruz.

Şimdi 3 ve 13'u karşılaştırıyoruz. Bu iki sayı eşit değildir, dolayısıyla 6 boşlukları üzerinde hareket ediyoruz. Böylece şu an itibariyle 1 "atlama" var. Şimdi 2 ve 7'a bakıyoruz. Bu ikisi de eşit değil, bu yüzden 6 daha fazla alan üzerinde hareket ediyoruz ve şimdi 2 "atlar" var. Şimdi 1 ve 1'u karşılaştırıyoruz ve bunlar eşittir, böylece bir satır yukarı çıkıp o noktadan başlarız. Geçmişte bu satırda 2 "atlar" olduğundan, kullanılan 6 cent madeni para sayısı 2'dur. Bu son kısım için kafa karıştırıcı oluyor. Bir satır yukarı hareket ettiğimizde, bulunduğumuz sütunda başlıyoruz. 1 ve 1'u karşılaştırdığımızdan, o sütundan devam edeceğiz. Bu, son satır olan satır 0 olduğundan, kalan değişim miktarı her zaman en üstteki sayı olacaktır. Örneğimde, bir satır yukarı çıktık ve 1'da başladık, böylece 1 cent paralarının sayısı 1'dur. Bu, kullanılan toplam sikke sayısı:

1 cent: 1 
6 cent: 2 
10 cent: 0 

Bunun çok kafa karıştırıcı bir şekilde ifade edildiğini biliyorum. Umarım benim kodum bunu daha iyi gösterir. İşte bu uygulamaya çalışmıştır nasıl:

void countCoins(uint i, uint a, uint coinVal, 
       const vector<uint> & denom, 
       Matrix<uint> & memo) 
{ 
    uint numCoins = 0; 

    // Check the current value with the value above it 
    if(memo.at(i, a) != memo.at(i - 1, a)) 
    { 
     if(denom.at(i) == coinVal) 
     { 
     numCoins++; 
     } 

     countCoins(i, a - denom.at(i), coinVal, denom, memo); // If not equal, "jump" over 
    } 
    else 
    { 
     if(i > 0) 
     { 
     countCoins(i - 1, a, coinVal, denom, memo); // If equal, move up a row 
     } 
     else 
     { 
     numCoins += a; // If equal and the row number is 0 
     } 
    } 
} 

Bu kod derler, ama onu çalıştırdığınızda ben "diye bir mesaj almak matrix.h: 48: Nesne & Matris :: En (uint, uint) [with object = unsigned int; uint = unsigned int]: Assertion `satırı: & satır col < cols 'başarısız oldu İptal edildi (çekirdek dökülmüş)" ve nedenini bilmiyorum. Bu çekirdek terk edilmiş mesajı neden alacağımı bilen var mı?

Answer 1

Sen memo ve/veya denom erişmeye çalışmadan önce i ve a az 0 olup olmadığını kontrol etmek gerekir.

void countCoins(uint i, uint a, uint coinVal, 
       const vector<uint> & denom, 
       Matrix<uint> & memo) 
{ 
    if (i < 0) { 
     // handle edge case and return 
    } 

    if (a < 0) { 
     // handle edge case and return 
    } 

    uint numCoins = 0; 

    ... 
    ... 

} 

Not: i ve a siz de kontrol gerekir memo boyutlarına ve denom daha yüksek değerlere sahip olabilir edin. Ama senin kodunda her zaman onları azaltıyor gibi görünüyor, bu yüzden büyük olasılıkla değil.