我寫了這段代碼解決了河內的塔。經過32453次迭代我的代碼停止工作

-2

import java.util.*; 
class towers{ 
    public static void main(String args[]) 
    { 
     honoi('A','B','C',(long)1,n); 
    } 
    static int disk_no(long i,int n) // to find the next disk to move 
    { 
     if(i%2!=0) 
      return 1; 
     else 
     { 
      int j; 
     long k; 
     for(j=2;j<=n;j++) 
      for(k=0;k<Math.pow(2,n-j);k++) 
        if(i==(long)Math.pow(2,(long)j-1)*((2*k)+1)) 
        { 
        System.out.println("returning :"+j); 
        return j; 
        } 
     return 0; 
     } 
     } 
     static void honoi(char x,char y,char z,long i,int n) 
     { 
      if(i<Math.pow(2,n)) 
      { 
      switch((int)i%2) 
       { 
       case 0:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+z+" to "+y); 
          honoi(x,y,z,++i,n);break; 
       default:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+x+" to "+y); 
           honoi(y,z,x,++i,n); 
       } 
      } 
     }}

我從用戶讀取n值作爲磁盤數量ofcourse我跳過在這裏我認爲這個問題是 disk_no（）功能，如果不提在代碼中的邏輯錯誤如果有的話我寫了這段代碼解決了河內的塔。經過32453次迭代我的代碼停止工作

來源

2015-11-22 ram914

究竟是什麼問題？ – Seelenvirtuose

嘗試詳細解釋問題。例如，在32453次迭代之後，局部變量的值是什麼？等等.. – OhadM

問題是你的代碼拋出一個StackOverflowError。

本質上，你的honoi方法打印出所有必要的步驟來解決河內拼圖的n磁盤步驟i以上。它通過計算移動i然後調用自己i替換爲i + 1並且可選地與x,y和z切換。

問題出現是因爲您的方法自行調用。 Java每次調用方法honoi時，都需要在執行方法結束時存儲返回的位置。它將這些返回位置存儲在「堆棧」中。當一個方法返回時，Java從堆棧頂部刪除這些位置中的最後一個，然後繼續從這個位置運行程序。這些退貨地點所用的'堆棧'只有有限的空間。如果這個堆棧變得太大，Java會拋出一個StackOverflowError。

如果用大量磁盤運行程序，代碼將需要太多空間來存儲返回位置，因爲您的方法在返回之前調用自己的次數太多。只有在所有動作都顯示後，您的honoi方法纔會返回。

爲了避免堆棧溢出，我將您的honoi方法修改爲如下，它使用循環而不是自行調用。 i現在是一個循環變量，所以我刪除了i作爲方法參數。你將需要從你的電話中刪除(long)1到honoi在main()：

static void honoi(char x,char y,char z,int n) 
    { 
     for (long i = 1; i < Math.pow(2,n); ++i) 
     { 
     switch((int)i%2) 
      { 
      case 0:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+z+" to "+y); 
       break; 
      default:System.out.println("STEP "+i+" :\tMove disk "+(long)disk_no(i,n)+" from pole "+x+" to "+y); 
       char temp = x; 
       x = y; 
       y = z; 
       z = temp; 
      } 
     } 
    }

從char temp = x;四線起掉周圍x，y，並且z，因爲你的這種方法的遞歸版本稱自己與x， y和z參數在default的情況下切換。

我不知道，如果你原來在支持尾遞歸優化另一種語言（例如功能性語言，比如哈斯克爾）寫了這個程序。如果一種語言支持這種優化，那麼它將能夠檢測一個方法是否以對同一方法的調用結束，如果是，則使用一種'goto'跳回到該方法的開始。您的代碼似乎會從這種優化中受益：如果在Java中支持尾遞歸優化，您的代碼很可能無誤地運行。但是，that's not likely to happen in Java。

來源

2015-11-22 13:03:58

我寫了這段代碼解決了河內的塔。經過32453次迭代我的代碼停止工作

回答

相關問題