2010-08-06 105 views
4

出於好奇,寫了一個遞歸字符串反轉函數,但在XOR有一點問題。這個函數的全部重點是不使用迭代器,這就是爲什麼它是一個遞歸函數。這不是家庭作業,只是好奇心。遞歸字符串反轉函數

private static char[] ReverseNL(char[] arr, int index) 
    { 
     var len = arr.Length; 
     if (index > 0) 
      arr[len - index] ^= arr[index - 1]; 
     return index-- < 1 ? arr : ReverseNL(arr, index); 
    } 

似乎jamble我的字符串

的第一部分 「嘿那裏堆!」變成「我♫→A←E↨reht星爺」

它始終是被搞亂這句話的前半部分......

UPDATE ..

我想XOR是不是真的需要這裏..所以用基本的任務,也擺脫了回報。

private static void ReverseNL(char[] arr, int index) { 
     var len = arr.Length; 
     if (index > 0 && index > len/2) { 
      var c = arr[len - index]; 
      arr[len - index] = arr[index - 1]; 
      arr[index - 1] = c; 
      index--; 
      ReverseNL(arr, index); 
     } 
    } 
+5

你幾歲? – NullUserException 2010-08-06 14:10:28

+3

@NullUserException - 顯然已經夠老了,以至於在一個問題中引用South Park類的歌曲(不管它是否合適是另一個問題)。 – 2010-08-06 14:12:51

+1

我建議將您的字符串更改爲更標準的短語,例如:「快速棕色狐狸跳過懶惰狗」 – 2010-08-06 14:13:28

回答

4

如果您想要使用XOR和遞歸的解決方案,請嘗試此操作:

private static void ReverseNL(char[] arr, int index) 
{ 
    if (index <arr.Length/2) 
    { 
     arr[index] ^= arr[arr.Length - index-1]; 
     arr[arr.Length - index-1] ^= arr[index ]; 
     arr[index] ^= arr[arr.Length - index-1]; 
     ReverseNL(arr,++index); 
    } 
} 

你不需要返回任何東西,因爲一切都在數組中完成。當然,你可以刪除異或部分,只是交換元素,但這是更冷卻。 ;)

(編輯:指數應該從0開始)

+0

當然這不能正確地扭轉字符串「abba」。 – strager 2010-08-06 15:26:46

+0

我猜你在我編輯之前評論說: – 2010-08-06 18:16:49

0

在這個特殊的例子,我寧願這樣做:

return arr.Reverse(); 
+0

謝謝,但我沒有要求的最佳辦法扭轉一個字符串..這只是一個好奇的鍛鍊 – 2010-08-06 14:15:02

+5

你真的錯過了功課標籤 – 2010-08-06 14:15:36

+0

當然一門功課成績應要求最簡潔的答案可能... – 2010-08-06 14:17:07

1

一個觀察:你所操作和返回一個數組。總是相同的數組。數組始終是一個參考。

這意味着您的退貨聲明過於複雜且具有誤導性。只要在所有情況下都以return arr;結束。

考慮一般提示的一部分:使其更簡單,並且您會看到更容易的錯誤。那--單獨在回報聲明中應該引起一個紅旗。


// untested, simplified return 
private static char[] ReverseNL(char[] arr, int index) 
{ 
    var len = arr.Length; 
    if (index > 0) 
     arr[len - index] ^= arr[index - 1]; 

    // return index-- < 1 ? arr : ReverseNL(arr, index); 

    if (index >= 1) 
     ReverseNL(arr, index-1); 

    return arr;  
} 
+0

我不明白我的退貨聲明有什麼問題。我可以將其分解成幾行,但它會做同樣的事情。它是返回arr如果索引是0,否則它遞歸。該部件經過測試並正常工作。 – 2010-08-06 14:30:28

+0

@Sonic:你正在倒轉。根本不需要回報。如果您確實使用return,則它與遞歸yes/no無關。 – 2010-08-06 14:38:58

7

遞歸幾乎總是用來做簡單的問題。遞歸算法在本質上通常是功能性的(儘管它們不一定是)。

在倒車的字符串(或char[])的情況下,「簡單」的意思是「一個較小的陣列上操作的」。

例如,可以減少如下:

"test" 
"est" 't' 
"st" 'e' 
"t"  's' 
""  't' 

(在左邊的是進行了數據壓縮;右側是切割數據)。

char[] reverse(char[] data) { 
    if (data.Count() == 0) { 
     return new char[] { }; 
    } 

    char cut = data.First(); 
    char[] rest = data.Skip(1); 

    char [] restReversed = reverse(rest); 

    // ??? 
} 

我把它留給你找出需要與你有數據下一步該做什麼:

僞代碼,你可以按照如下步驟進行還原。

0

異或具有被調用兩次交換的一對元件。它只在數組的前半部分被調用一次。 (在編輯中:嚴格來說,每次分配只調用一次,所以淨效應就像在陣列的一半上進行雙XOR交換。)

+0

哦,這是有創意的,我不會想出這樣做.. – 2010-08-06 14:40:43

6

可能不會是最有效的,但是這應該給你如何讓遞歸工作的一些想法......

static string ReverseNL (string s) 
    { 
     if ((s == null) || (s.Length <= 1)) 
     { 
      return s; 
     } 
     return ReverseNL(s.Substring(1)) + s[0]; 
    } 

    static void Main(string[] args) 
    { 
     string src = "The quick brown fox"; 
     Console.WriteLine(src); 
     src = ReverseNL(src); 
     Console.WriteLine(src); 
    } 
+0

,它的作品太好了,非常好,謝謝 – 2010-08-06 15:20:29

+0

其實我認爲這是我最喜歡的解決方案,因爲它只有3行。簡單而優雅。 – 2010-08-06 15:26:22