遞歸函數中的分段錯誤

我正在實現Strassen's matrix multiplication algorithm作爲賦值的一部分。我已經正確編碼了，但我不知道它爲什麼給出分段錯誤。我叫strassen（）爲strassen（0，n，0，n）;主要是。 n是由用戶給出的數字，它是2的冪，它是矩陣（2D陣列）的最大尺寸。它沒有給n = 4的段錯誤，但是對於n = 8,16,32，它給出段錯誤。代碼如下所示。遞歸函數中的分段錯誤

void strassen(int p, int q, int r, int s) 
    { 
     int p1,p2,p3,p4,p5,p6,p7; 
     if(((q-p) == 2)&&((s-r) == 2)) 
     { 
      p1 = ((a[p][r] + a[p+1][r+1])*(b[p][r] + b[p+1][r+1])); 
      p2 = ((a[p+1][r] + a[p+1][r+1])*b[p][r]); 
      p3 = (a[p][r]*(b[p][r+1] - b[p+1][r+1])); 
      p4 = (a[p+1][r+1]*(b[p+1][r] - b[p][r])); 
      p5 = ((a[p][r] + a[p][r+1])*b[p+1][r+1]); 
      p6 = ((a[p+1][r] - a[p][r])*(b[p][r] +b[p][r+1])); 
      p7 = ((a[p][r+1] - a[p+1][r+1])*(b[p+1][r] + b[p+1][r+1])); 
      c[p][r] = p1 + p4 - p5 + p7; 
      c[p][r+1] = p3 + p5; 
      c[p+1][r] = p2 + p4; 
      c[p+1][r+1] = p1 + p3 - p2 + p6; 
     } 
     else 
     { 
      strassen(p, q/2, r, s/2); 
      strassen(p, q/2, s/2, s); 
      strassen(q/2, q, r, s/2); 
      strassen(q/2, q, s/2, s); 
     } 
    }

來源

2013-03-16 Shreyas Kale

最有可能的終止條件不正確，並且函數遞歸直到它溢出堆棧。您至少應該檢查在調試器中運行時會發生什麼。如果調試器停止在'c'數組的任何一個賦值處，請檢查這些索引以使它們不超出範圍。 – 2013-03-16 16:22:06

不要讓我們猜測。段錯誤的原因是什麼，堆棧溢出或溢出數組邊界？在gdb中敲擊它並提供更多信息。 – 2013-03-16 16:24:03

您也可以嘗試將'int'聲明放在第一個if中。雖然我覺得約阿希姆是正確的。你確定條件是'=='而不是'<='？說'p'和'q'是10和10.然後我們有（10,10）（10,5）（10,2）（10,1）（10,0）... – 2013-03-16 16:25:55

一些在你的else塊的條件是無限遞歸（至少第二和第四，沒有檢查等）。這可以用筆和紙很容易地證明：例如：
strassen(p, q/2, s/2, s)爲`0,8,0,8將產生在每個迭代：

1) 0, 4, 4, 8 

2) 0, 2, 4, 8 

3) 0, 1, 4, 8 

4) 0, 0, 4, 8 

5) 0, 0, 4, 8

...

，並因爲沒有這些結果的傳遞你

if(((q-p) == 2)&&((s-r) == 2))

測試中，函數將運行（我懷疑分支，因爲第4個函數有同樣的問題...），直到堆棧結束時，導致分段錯誤。

無論如何，如果你正在嘗試在else塊做的是遞歸平分矩陣，更好的企圖都將是這樣的：

strassen(p, (q+p)/2, r, (r+s)/2);            
strassen(p, (q+p)/2, (r+s)/2, s);            
strassen((q+p)/2,q, (r+s)/2, s);             
strassen((q+p)/2,q, r, (r+s)/2);

（記住，我沒有檢查這個代碼，雖然）

來源

2013-03-16 16:39:37 Rick77

謝謝，我會再次嘗試，並期待在它與筆ñ紙和gdb了。 – 2013-03-16 16:43:37

請問，如果我的回答滿足您的問題，請不要忘記標記爲解決方案;-) – Rick77 2013-03-17 10:36:54

void strassen(int p, int q, int r, int s) 
{ 
    int p1,p2,p3,p4,p5,p6,p7; 
    if(q-p == 2 && s-r == 2) 
    { 
     p1 = (a[p][r] + a[p+1][r+1]) * (b[p][r] + b[p+1][r+1]); 
     p2 = (a[p+1][r] + a[p+1][r+1]) * b[p][r]; 
     p3 = a[p][r]     * (b[p][r+1] - b[p+1][r+1]); 
     p4 = a[p+1][r+1]    * (b[p+1][r] - b[p][r]); 
     p5 = (a[p][r] + a[p][r+1])  * b[p+1][r+1]; 
     p6 = (a[p+1][r] - a[p][r])  * (b[p][r] +b[p][r+1]); 
     p7 = (a[p][r+1] - a[p+1][r+1]) * (b[p+1][r] + b[p+1][r+1]); 
     c[p][r] = p1 + p4 - p5 + p7; 
     c[p][r+1] = p3 + p5; 
     c[p+1][r] = p2 + p4; 
     c[p+1][r+1] = p1 + p3 - p2 + p6; 
    } 
    else 
    { 
     if (q/2-p >= 2 && s/2-r >= 2) strassen(p, q/2, r, s/2); 
     if (q/2-p >= 2 && s-s/2 >= 2) strassen(p, q/2, s/2, s); 
     if (q-q/2 >= 2 && s/2-r >= 2) strassen(q/2, q, r, s/2); 
     if (q-q/2 >= 2 && s-s/2 >= 2) strassen(q/2, q, s/2, s); 
    } 
}

但更簡單的遞歸塞將在函數的開頭，如：

{ 
    int p1,p2,p3,p4,p5,p6,p7; 
    if(q-p < 2 || s-r < 2) return; 
    if(q-p == 2 && s-r == 2) 
    { ...

來源

2013-03-16 16:48:45 wildplasser

遞歸函數中的分段錯誤

回答

相關問題