6

再帰を含む次の問題をどのように解決しますか?

入力文字列 s のn回の繰り返しchar *repeat(char *s, int n) からなる文字列を作成して返すように、prototype を使用して関数を実装します。例: 入力が「Hello」で 3 の場合、出力は「HelloHelloHello」です。再帰構造のみを使用してください。

私の解決策は私にはかなり醜いようで、もっときれいなものを探しています。これが私のコードです:

char *repeat(char *s, int n) {
  if(n==0) {
     char *ris = malloc(1);
     ris[0] = '\0';
     return ris;
  }
  int a = strlen(s);
  char *ris = malloc(n*a+1);
  char *ris_pre = repeat(s,n-1);
  strcpy(ris,ris_pre);
  strcpy(ris+(n-1)*a,s);
  free(ris_pre);
  return ris;
}
4

5 に答える 5

9

より整然としたエレガントなソリューション (これをBasic Solutionと呼んでいます) は次のとおりです。

基本的な解決策

char *internalRepeat(char *s, int n, size_t total)
{
    return (n > 0)
        ? strcat(internalRepeat(s, n - 1, total + strlen(s)), s)
        : strcpy(malloc(total + 1), "");
}

char *repeat(char *s, int n)
{
    return internalRepeat(s, n, 0);
}

これが再帰の美しさです。このソリューションの鍵は、再帰を使用して結果の長さを段階的に構築することです。パラメーターtotalはこれを行います (NUL ターミネーターは含みません)。再帰が終了すると、結果バッファーが 1 回 (NUL ターミネーターを含めて) 割り当てられ、再帰の巻き戻しを使用して、 の各コピーをs結果に追加します。基本的なソリューションは次のように動作します。

  1. 空の文字列が何回繰り返されても、長さ 0 の文字列を返します。
  2. 空でない文字列の 0 回または負の繰り返しに対して、長さ 0 の文字列を返します。
  3. 空でない文字列のゼロ以外の正数の繰り返しに対して、長さがゼロでない文字列を返します。

上記の関数に基づいてプログラムを作成すると、次のステートメントが実行されます。

printf("Repeat \"\" 0 times: [%s]\n", repeat("", 0));
printf("Repeat \"\" 3 times: [%s]\n", repeat("", 3));
printf("Repeat \"abcde\" 0 times: [%s]\n", repeat("abcde", 0));
printf("Repeat \"abcde\" 1 times: [%s]\n", repeat("abcde", 1));
printf("Repeat \"abcde\" 4 times: [%s]\n", repeat("abcde", 4));

次の出力が生成されます。

Repeat "" 0 times: []
Repeat "" 3 times: []
Repeat "abcde" 0 times: []
Repeat "abcde" 1 times: [abcde]
Repeat "abcde" 4 times: [abcdeabcdeabcdeabcde]



編集:最適化されたソリューションが続きます。最適化手法に興味がある場合は、読み進めてください。



ここでの他のすべての提案は、原則としてO( n^2 )で実行され、反復ごとにメモリが割り当てられます。Basic Solution はエレガントで、単一malloc()の のみを使用し、2 つのステートメントしか必要としませんが、驚くべきことにBasic Solution の実行時間も O( n^2 )です。文字列が長い場合、これは非常に非効率的でsあり、基本的な解決策はここでの他のどの提案よりも効率的ではないことを意味します.

最適化されたソリューション

以下は、実際にO( n )で実行されるこの問題の最適な解決策です。

char *internalRepeat(char *s, int n, size_t total, size_t len)
{
    return (n > 0)
        ? strcpy(internalRepeat(s, n - 1, total, len), s) + len
        : strcpy(malloc(total + 1), "");
}

char *repeat(char *s, int n)
{
    int len = strlen(s);

    return internalRepeat(s, n, n * len, len) - (n * len);
}

ご覧のとおり、3 つのステートメントがあり、もう 1 つのパラメーター を使用しlenて の長さをキャッシュしていsます。の' 番目のコピーが配置されるlen結果バッファー内の位置を計算するために再帰的に使用されるため、結果に追加されるたびにforに置き換えることができます。これにより、 O( n^2 )ではなく、O( n ) の実際の実行時間が得られます。nsstrcat()strcpy()s

基本ソリューションと最適化ソリューションの違いは何ですか?

他のすべてのソリューションでは、結果にコピーを追加するために文字列をstrcat()少なくとも 1n回使用しています。の実装は非効率性を隠しているため、ここに問題があります。内部的には、次のように考えることができます。snsstrcat()strcat()

strcat = strlen + strcpy

つまり、追加するときは、追加自体を行う前に、まず追加先の文字列の末尾を見つける必要があります。この隠れたオーバーヘッドは、実際、n文字列のコピーを作成するには、n長さのチェックとn物理的なコピー操作が必要であることを意味します。ただし、本当の問題は、追加するコピーごとsに、結果が長くなることです。これはstrcat()結果内の連続する各長さチェックも長くなっていることを意味します。「スキャンまたはコピーしなければならない回数s」を比較基準として 2 つのソリューションを比較すると、2 つのソリューションの違いがどこにあるのかがわかります。

n文字列 のコピーの場合s、基本的なソリューションは次のように実行されます。

strlen's/iteration: 2
strcpy's/iteration: 1

Iteration | Init | 1 | 2 | 3 | 4 | ... | n |   Total    |
----------+------+---+---+---+---+-----+---+------------+
Scan "s"  |   0  | 1 | 2 | 3 | 4 | ... | n | (n+1)(n/2) |
Copy "s"  |   0  | 1 | 1 | 1 | 1 | ... | 1 |     n      |

一方、最適化されたソリューションは次のように実行されます。

strlen's/iteration: 0
strcpy's/iteration: 1

Iteration | Init | 1 | 2 | 3 | 4 | ... | n |    Total   |
----------+------+---+---+---+---+-----+---+------------+
Scan "s"  |   1  | 0 | 0 | 0 | 0 | ... | 0 |      1     |
Copy "s"  |   0  | 1 | 1 | 1 | 1 | ... | 1 |      n     |

表からわかるように、基本的なソリューションは、組み込みの長さチェックインにより、文字列の( n^2 + n)/2 回strcat()のスキャンを実行しますが、最適化されたソリューションは常に(n + 1)のスキャンを実行します。これが、基本的なソリューション (および に依存する他のすべてのソリューションstrcat()) がO(n^2)で実行されるのに対し、最適化されたソリューションはO(n)で実行される理由です。

O( n ) と O( n^2 ) を比較すると、実数はどうなりますか?

大きな文字列が使用されている場合、実行時間は大きな違いになります。s例として、 1,000 個のコピー (== 1GB) を作成したい 1MBの文字列を考えてみましょう。1 バイト/クロック サイクルでスキャンまたはコピーできる 1 GHz の CPU がある場合、次のように のコピーが 1,000 個生成sます

Basic:  (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
                              = (10^3 ^ 2) / 2 + (3 * 10^3) / 2
                              = (5 * 10^5) + (1.5 * 10^2)
                              = ~(5 * 10^5) (scans of "s")
                              = ~(5 * 10^5 * 10^6) (bytes scanned/copied)
                              = ~500 seconds (@1GHz, 8 mins 20 secs).

Optimised: (n + 1)            = 10^3 + 1
                              = ~10^3 (scans of "s")
                              = ~10^3 * 10^6 (bytes scanned/copied)
                              = 1 second (@1Ghz)

ご覧のとおり、ほぼ瞬時に完了する最適化されたソリューションは、完了するまでに約 10 分かかる基本的なソリューションを解体します。ただし、文字列をs小さくすることが役立つと考える場合、次の結果は恐ろしいことです。ここでも、1 バイト/クロック サイクルを処理する 1 GHz マシンでは、s1 KB (1000 分の 1) として、1,000,000 のコピーを作成します (合計 == 1 GB、前と同じ)。これは与える:

Basic:  (n + 1) * (n / 2) + n = (n ^ 2) / 2 + (3n / 2)
                              = (10^6 ^ 2) / 2 + (3 * 10^6) / 2
                              = (5 * 10^11) + (1.5 * 10^5)
                              = ~(5 * 10^11) (scans of "s")
                              = ~(5 * 10^11 * 10^3) (bytes scanned/copied)
                              = ~50,000 seconds (@1GHz, 833 mins)
                              = 13hrs, 53mins, 20 secs

Optimised: (n + 1)            = 10^6 + 1
                              = ~10^6 (scans of "s")
                              = ~10^6 * 10^3 (bytes scanned/copied)
                              = 1 second (@1Ghz)

これは本当に衝撃的な違いです。書き込まれたデータの合計量が同じであるため、Optimized Solution は以前と同じ時間で実行されます。ただし、基本的なソリューションは、結果を構築するのに半日以上かかります。これは、O( n ) と O( n^2 )の実行時間の差です。

于 2012-07-02T08:46:43.273 に答える
3

文字列を一度だけ割り当てるこのアプローチを試してください。

char *repeat(char *s, int n) {
   int srcLength = strlen(s);
   int destLength = srcLength * n + 1;      
   char *result = malloc(destLength);
   result[0] = '\0'; // This is for strcat calls to work properly

   return repeatInternal(s, result, n);
}

char *repeatInternal(char *s, char *result, int n) {
  if(n==0) {
     return result;
  }

  strcat(s, result);  
  return repeat(result, s, n-1);
}

2 番目の繰り返し方法は、最初の方法でのみ使用する必要があります。(最初のものはプロトタイプメソッドです)

注:コンパイル/テストはしていませんが、これは機能するはずです。

于 2012-07-01T11:45:01.390 に答える
2

これは1つです:

char *repeat (char *str, int n)
{
  char *ret_str, *new_str;

  if (n == 0)
  {
    ret_str = strdup ("");
    return ret_str;
  }
  ret_str = repeat (str, n-1);
  new_str = malloc (sizeof (char) * strlen (str) * (n + 1));
  new_str[0] = '\0';
  strcpy (new_str, ret_str);
  strcat (new_str, str);
  free (ret_str);
  return new_str;
}

私たちは誰かをきれいに見せるコードを得ることができますrealloc ()

char *repeat (char *str, int n)
{
  char *ret_str;

  if (n == 0)
  {
    ret_str = strdup ("");
    return ret_str;
  }
  ret_str = repeat (str, n-1);
  ret_str = realloc (ret_str, sizeof (char) * strlen (str) * (n + 1));
  strcat (ret_str, str);
  return ret_str;
}

編集1

わかりました、これはよりコンパクトです。

char *repeat (char *str, int n)
{
  static char *ret_str;
  static int n_top = -1;

  if (n >= n_top)
    ret_str = calloc (sizeof (char), strlen (str) * n + 1);
  if (n <= 0)
    return ret_str;

  n_top = n;

  return strcat (repeat (str, n-1), str);
}

最終的な文字列を保持するために静的バッファーを使用するため、再帰のすべてのレベルで 1 つのバッファーが使用されます。

は、再帰呼び出しからstatic int n_topの以前の値の値を保持します。nこれは、 で-1呼び出されたときのケースを処理するためにによって初期化されるn = 0ため、空の文字列が返されます (および はcalloc0 で初期化するために使用されます)。したがって、最初の再帰呼び出しでは、値は-1最上位レベルでのみn > n_toptrue になります (n常に減少するため)。この場合、バッファー全体が割り当てられret_strます。それ以外の場合は、0 になるときの一番下の条件を見つけますn。この時点n = 0で、事前に割り当てられた静的バッファーのアドレスをret_str再帰ツリーの親呼び出し元に返します。この単一のバッファは、再帰の各レベルで使用され、strに達するまで、前のレベルに引き渡されmainます。

編集2

さらにコンパクトですが、醜い

char *repeat (char *str, int n)
{
  static int n_top;
  n_top = (n_top == 0)? n: n_top;
  return (n <= 0)?(n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1)):strcat (repeat (str, n-1), str);
}

で call を使用すると、最後のコンパクトなコードに問題がありましたrepeat (str, n); repeat (str, 0);。この実装はその問題を克服し、1 つの関数のみを使用するさらにコンパクトな実装です。

醜いがあることに注意してください(n=n_top,n_top=0,calloc (sizeof (char), strlen (str) * n + 1))。ここでは、ロールバック中に の値を使用してn_topメモリを割り当て、次に にリセットn_topして、または他のメインの呼び出し元 (再帰的ではない)からの次の呼び出しで0関数がn_top設定されるようにします。これはもっと読みやすい方法で行うことができますが、これはクールに見えます。より読みやすいものに固執することをお勧めします。0main ()

編集3

狂人バージョン

これにより、繰り返しstrlen ()の呼び出しが解消されます。は 1 回だけ呼び出され、現在の深さstrlen ()の値とともに文字列の長さの値を使用して、返される最終的な文字列の末尾を示す値を見つけます (そのアドレスは中間変数に格納されません。戻って合格)。文字列を に渡すときに、オフセットを追加し、すぐ次の深さから返された応答文字列に追加することで、ソース メモリの場所を指定します。これは実際には文字列の末尾の直後に位置を提供し、その後lengthのものをコピーします。ご了承くださいnoffsetmemcpymemcpyoffsetmemcpymemcpystrstr_lenmemcpy渡された宛先アドレス、つまりこの深さの応答文字列の終了アドレスをoffset返しますが、この返された値から戻ることによって達成される実際の開始が必要offsetです。

これはまだ単一の機能を使用していることに注意してください:D

char *repeat (char *str, int n)
{
  static int n_top, str_len;
  int offset = 0;

  (n_top == 0)?(n_top = n,str_len = strlen (str)):(offset = str_len * (n_top-n));
  return (n <= 0)?(n=n_top,n_top=0,malloc (str_len * n + 1)):(memcpy (repeat (str, n-1) + offset, str, str_len) - offset);
}

いくつかのメモ:

  • offset = str_len * (n-1)最初の深さではstrオフセット 0 にコピーされ、その後の再帰的な深さから文字列が逆方向から応答文字列にコピーされる場合があります。

  • 実行するときは、バイトmemcpyをコピーするように指示しnますが、これには は含まれません\0。しかしcalloc、終端の `'\0' 文字のためのスペースで最終宛先メモリを割り当てるために使用するので、それは 0 に初期化されます。したがって、最終的な文字列は '\0' で終端されます。

  • sizeof (char) は常に 1 です

  • よりコンパクトで不可解に見えるようにするにoffsetは、計算を削除し、最後の式でオフセットを直接計算しreturnます。

  • このコードを実際に使用しないでください。

于 2012-07-01T11:55:58.317 に答える
0

これはもう少しコードを必要とするソリューションですが、O(n)ではなくO(log n)時間で実行されます。

// Return a string containing 'n' copies of 's'
char *repeat(int n, char *s) {
  return concat((n-1) * strlen(s), strdup(s));
}

// Append 'charsToAdd' characters from 's' to 's', charsToAdd >= 0
char *concat(int charsToAdd, char *s) {
  int oldLen = strlen(s);
  if (charsToAdd <= n) {  // Copy only part of the original string.
    char *longerString = malloc((oldLen + charsToAdd + 1) * sizeof(char));
    strcpy(longerString, s);
    strncat(longerString, s, charsToAdd);
    return longerString;
  } else { // Duplicate s and recurse.
    char *longerString = malloc((2 * oldLen + 1) * sizeof(char));
    strcpy(longerString, s);
    strcat(longerString, s);
    free(s);  // Free the old string; the recusion will allocate a new one.
    return concat(charsToAdd - oldLen, longerString);
  }
}
于 2012-07-01T13:02:14.403 に答える
0

考えられる解決策:

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


char *repeat(char *s, int n)
{
    static char *sret=NULL;
    static int isnew=1;

    if (!s || !s[0])
    {
        if (sret) { free(sret); sret=NULL; }
        return "";
    }

    if (n<=0) return "";

    if (isnew)
    {
        int nbuf = strlen(s)*n + 1;
        sret = (char*)realloc(sret, nbuf);
        memset(sret, 0, nbuf);
        isnew=0;
    }

    strcat(sret,s);
    repeat(s, n-1);
    isnew = 1;
    return sret;
}

int main()
{
    char *s = repeat("Hello",50);
    printf("%s\n", s);

    s = repeat("Bye",50);
    printf("%s\n", s);

    repeat(NULL,0); /* this free's the static buffer in repeat() */

    s = repeat("so long and farewell",50);
    printf("%s\n", s);

    return 0;
}

[編集]
単一の関数を使用する aps2012 のソリューションのバリエーションですが、静的 int を使用します。

char *repeat(char *s, int n)
{
    static int t=0;
    return (n > 0) 
        ? (t += strlen(s),strcat(repeat(s, n - 1), s)) 
        : strcpy(malloc(t + 1), "");
}

呼び出し元はfree()、メモリ リークを回避するために、返された文字列を取得する必要があります。

于 2012-07-02T08:44:10.703 に答える