查找一個遞歸序列

Question

我試圖寫一個遞歸函數，它通過指針和它的大小獲取數組，並返回數組中最長的一系列相同的相鄰數字的長度（假設有一個系列），

例如：

array: {1 2 3 3 4 5 6 6 6 6 7 8} 
returns-->: 4 

，但我不知道這有什麼錯我的功能;我想我錯了。

關於如何解決它的任何想法？

#include <stdio.h> 
#include <stdlib.h> 

int LongestSeries(int* arr, int size, int* count, int* maxcount); 


int main() 
{ 
    int i, size, *arr, count=0, maxcount=0; 

    // allocation an array (unknow size) 
    { 
     printf("Enter Size of the Array-->:"); 
     scanf("%d", &size); 

     arr = (int*)malloc(size * sizeof(int)); 
     if (arr == NULL) 
     { 
      printf("Error!!"); 
      exit(1); 
     } 
     printf("Enter Numbers for the Array:\n"); 
     for (i = 0; i < size; i++) 
     { 
      printf("Enter a Number-->:"); 
      scanf("%d", &arr[i]); 
     } 
    } 
    for (i = 0; i < size; i++) 
     printf(" %d ", arr[i]); 
    printf("\n"); 

    printf(" %d \n", LongestSeries(arr, size, count, maxcount)); 

    free(arr); 
    return 0; 
} 


int LongestSeries(int* arr, int size, int* count, int* maxcount) 
{ 
    if (arr[size-1] == arr[size-2]) 
     count++; 
    if (maxcount<count) 
     maxcount = count; 

    LongestSeries(arr, size - 1, count, maxcount); 

    if (*arr==arr[0]) 
     return maxcount; 
} 

Answer 1

裏有一些問題，在您的代碼：

1 - 功能LongestSeries預計在count和maxcount參數的指針，但你傳遞的變量的值來代替。您需要更改函數調用以發送地址引用，如下所示：printf(" %d \n", LongestSeries(arr, size, &count, &maxcount));

2 - 您的遞歸終止條件放在遞歸調用下方，導致遞歸永不結束。您需要將它放在遞歸調用上方，最好是遞歸函數中的第一條語句。

3 - 由於您的count和maxcount參數爲指針，你必須使用引用操作與價值，而不是它的地址有效：

從這個：

if (arr[size-1] == arr[size-2]) 
     count++; 
    if (maxcount<count) 
     maxcount = count; 

這樣：

if (arr[size-1] == arr[size-2]) 
     ++*count; 
    if (*maxcount < *count) 
     *maxcount = *count; 

4 - 在你的return語句中同樣適用：你在迴盪指針，但你的函數期望int是r eturned，所以：

從這個：

if (*arr==arr[0]) 
     return maxcount; 

這樣：

if (*arr==arr[0]) 
     return *maxcount; 

5 - 由於需要最長的系列，您count變量需要在1，不0啓動，因爲數字序列中可能的最低系列是1，而不是0.

希望它有幫助。

Answer 2

正如@MarcLaurent指出的，發佈的代碼有很多問題。但從根本上說，這種方法似乎有缺陷。編寫遞歸函數的目的不是爲了讓事情變得困難，而是爲了簡單起見。適用於遞歸的問題可以分解爲更小的子問題。

對於手頭的問題，找到數組中重複數的最長序列的長度，一個遞歸方法會承認這個長度是重複數的初始序列的長度或最長的長度數組其餘部分中重複數字的序列。在代碼中，這可能看起來像：

size_t longest_seq(size_t sz, int *a) 
{ 
    if (sz == 0) { 
     return 0; 
    } 
    size_t count = init_seq(sz, a); 
    return MAX(count, longest_seq(sz - count, a + count)); 
} 

在此，如果該陣列不包含元素（基礎情況），則返回0。否則，返回初始序列長度的較大者或數組其餘部分中最長的序列。 MAX這裏是一個宏，很容易定義，我們只需編寫一個函數來查找初始序列的長度。這也可以是遞歸的，儘管它不需要。

用於查找的初始序列的長度

遞歸函數可能看起來像：

size_t init_seq(size_t sz, int *a) 
{ 
    if (sz == 0) { 
     return 0; 
    } 
    return 1 + ((sz > 1 && a[0] == a[1]) ? init_seq(sz - 1, a + 1) : 0); 
} 

在此，如果該陣列不包含元素（基礎情況），則長度是明顯0，否則返回值爲1添加到數組其餘部分的初始序列的長度（如果存在下一個元素，且該元素與第一個元素相同）或0。

通過這種方式解決問題，解決方案簡單易懂。這是一個完整的程序來實現上述思路：

#include <stdio.h> 

#define MAX(X, Y) (X) > (Y) ? (X) : (Y) 

size_t longest_seq(size_t, int *); 
size_t init_seq(size_t, int *); 

int main(void) 
{ 
    size_t arr_sz; 
    printf("Enter number of elements: "); 
    scanf("%zu", &arr_sz); 

    int arr[arr_sz]; 

    printf("Enter array values:\n"); 
    for (size_t i = 0; i < arr_sz; i++) { 
     scanf("%d", &arr[i]); 
    } 

    printf("Longest sequence of repeats: %zu\n", longest_seq(arr_sz, arr)); 

    return 0; 
} 

size_t longest_seq(size_t sz, int *a) 
{ 
    if (sz == 0) { 
     return 0; 
    } 
    size_t count = init_seq(sz, a); 
    return MAX(count, longest_seq(sz - count, a + count)); 
} 

size_t init_seq(size_t sz, int *a) 
{ 
    if (sz == 0) { 
     return 0; 
    } 
    return 1 + ((sz > 1 && a[0] == a[1]) ? init_seq(sz - 1, a + 1) : 0); 
} 

示例程序的交互：

Enter number of elements: 12 
Enter array values: 
1 2 3 3 4 5 6 6 6 6 7 8 
Longest sequence of repeats: 4 

Answer 3

int LongestSeries(int* arr, int size, int count, int maxcount){ 
    if(size == 0) 
     return maxcount < count ? count : maxcount; 

    if(count == 0){ 
     return LongestSeries(arr + 1, size - 1, 1, maxcount); 
    } else { 
     if(arr[-1] == *arr){ 
      return LongestSeries(arr + 1, size - 1, count + 1, maxcount); 
     } else { 
      if(count > maxcount) 
       maxcount = count; 
      return LongestSeries(arr + 1, size - 1, 1, maxcount); 
     } 
    } 
} 

int main(void){ 
    int arr[] = {1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 7, 8}; 
    int size = sizeof(arr)/sizeof(*arr); 
    printf("%d\n", LongestSeries(arr, size, 0, 0)); 
} 

---

減少代碼：

int LongestSeries(int* arr, int size, int count, int maxcount){ 
    if(size == 0) 
     return maxcount < count ? count : maxcount; 

    if(count == 0 || arr[-1] != *arr){ 
     if(count > maxcount) 
      maxcount = count; 
     return LongestSeries(arr + 1, size - 1, 1, maxcount); 
    } 
    return LongestSeries(arr + 1, size - 1, count + 1, maxcount); 
}