再帰を伴う系列を見つける

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 - リターンステートメントでも同じことが言えます。ポインタをreturingしていても、関数がintをrと期待しているそう、eturned：これに

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

：このから

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

5 - あなたは最長のシリーズを必要とするので、あなたのcount変数があるため、0、1でない起動する必要があります数字列の可能な最低系列は1であり、0ではありません。

希望します。

Answer 2

@MarcLaurentで指摘されているように、投稿されたコードには多くの問題があります。しかし、根本的に、このアプローチには欠陥があるようです。再帰関数を書くのは、物事を困難にすることではなく、物事を単純化することです。再帰に役立つ問題は、より小さなサブ問題に分解することができます。

配列の中で最も長い配列の長さの長さを見つけると、1つの再帰的アプローチは、この長さが繰り返し数の最初のシーケンスの長さか、最長の長さのどちらかであることを認識します配列の残りの部分に反復された数字のシーケンス。コードでは、これは次のようになります。ここでは

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はここでは簡単に定義できるマクロであり、最初のシーケンスの長さを見つける関数を書くだけです。これは再帰的に行うこともできますが、必ずしもそうである必要はありません。

初期シーケンスの長さは次のように見える可能性が見つかった再帰関数：配列が要素（ベースケース）が含まれない場合、長さがそうでなければ戻り、明らか0であり、ここで

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); 
} 

値は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); 
}