1

この関数を実装する方法が本当にわかりません。関数は、整数へのポインター、文字列の配列へのポインター、およびプロセス用の文字列を受け取る必要があります。関数は、交換' ch 'の組み合わせのすべてのバリエーションを' @ 'シンボルに書き込み、整数をこの配列のサイズに変更する必要があります。処理の例があります：

choker => {"choker","@oker"}

chocho => {"chocho","@ocho","cho@o","@o@o"}

chachacha => {"chachacha","@achacha","cha@acha","chacha@a","@a@acha","cha@a@a","@acha@a","@a@a@a"}

私はこれをc標準99で書いています。これはスケッチです：

int n;
char **arr;
char *string = "chacha";
func(&n,&arr,string);

そして関数スケッチ：

int func(int *n,char ***arr, char *string) {

}

したがって、「ch」の組み合わせの数をカウントし、この関数にメモリを割り当てる別の関数を作成する必要があると思います。このアルゴリズムについてのアイデアを聞いてうれしいです。前もって感謝します。

4

4 に答える 4

0

元の問題を解決するために必要な2つのサブ問題があります。

  • バリエーションの配列にスペースを割り当てる
  • 変動の計算

f最初の問題では、入力文字列内の「ch」の出現回数を取得し、全変動の数を返す数学関数を見つける必要があります。あなたの例に基づいて：f(1) = 1、、。これにより、どこから始めればよいかがわかりますが、関数が正しいことを証明することが重要です。誘導はその証拠を作る良い方法です。f(2) = 4f(3) = 8

置換プロセスにより、結果の長さが元の長さよりも短くなることが保証されるため、元の長さに等しい個々の結果にスペースを割り当てることができます。

2番目の問題に関しては、最も簡単な方法は、nightlytrailsによって提供される例のように、再帰を使用することです。

count結果、結果、文字列の現在の状態、および現在の文字列に割り当てた配列を取得する別の関数が必要になりindexます。

呼び出されたときに、それ以降に「ch」が出現しない場合はindex、結果を配列の位置countと増分に保存しますcount（したがって、次回は前の結果を上書きしません）。

それ以降に「ch」がある場合は、indexこの関数を2回呼び出します（繰り返し部分）。index呼び出しの1つは、現在の文字列のコピーを使用し、「ch」のすぐ先までだけインクリメントします。もう1つの呼び出しは、「ch」が「@」に置き換えられた現在の文字列のコピーを使用し、「@」indexを超えてtoをインクリメントします。

メモリリークがないことを確認してください。malloc一致するものがなければいいえfree。このソリューションを機能させると、メモリが不足していることに気付くかもしれません。必要以上に使用しています。アルゴリズムの改善は、読者の練習問題です。

于 2012-12-03T00:49:01.777 に答える
0

組み合わせの数を簡単に数えることができます。

char * tmp = string;
int i;
for(i = 0; *tmp != '\0'; i++){
    if(!(tmp = strstr(tmp, "ch")))
        break;
    tmp += 2; // Skip past the 2 characters "ch"
}

// i contains the number of times ch appears in the string.

int num_combinations = 1 << i;

// num_combinations contains the number of combinations. Since this is 2 to the power of the number of occurrences of "ch"
于 2012-12-03T00:25:17.240 に答える
0

まず、文字列を反復処理して「ch」の数を返す countChs などのヘルパー関数を作成します。文字列の重複がないため、これは簡単なはずです。

出現回数がある場合、長さstrlen(original) - 1の各文字列 (元の文字列を除く) で、 2^count 文字列にスペースを割り当てる必要があります。また、n 変数をその 2^count に等しくなるように変更します。

スペースを割り当てたら、新しいテーブルのすべてのインデックスを反復処理し、元の文字列のコピー (strcpy() または strncpy() をコピー) で埋めてから、それらの 'ch' を '@' に置き換えます (ある「C string replace」を探してください)。

最後に、arr ポインターが新しいテーブルを指すようにします。ただし、注意してください。以前に他のデータを指していた場合は、それを解放することを検討する必要があります。そうしないと、メモリ リークが発生します。

于 2012-12-03T00:30:16.933 に答える
0

置換された文字列のすべてのバリエーションが必要な場合は、配列サイズに2^n要素が含まれます。Where n- "ch" 部分文字列の数。したがって、これを計算すると次のようになります。

int i = 0;
int n = 0;
while(string[i] != '\0')
{
    if(string[i] == 'c' && string[i + 1] == 'h')
        n++;

    i++;
}

次に、数値のバイナリ表現を使用できます。整数を から にインクリメントすると、i 番目の数値の 2 進数表現が、どの「ch」オカレンスを変更するかを教えてくれることに注意して0ください2^n。そう：

for(long long unsigned int i = 0; i < (1 << n); i++)
{
    long long unsigned int number = i;
    int k = 0;

    while(number > 0)
    {
        if(number % 2 == 1)
            // Replace k-th occurence of "ch"

        number /= 2;
        k++;
    }

    // Add replaced string to array
}

このコードは のバイナリ表現のすべてのビットをチェックしnumber、k 番目のビットが 1 の場合は k 番目のオカレンスを変更します。k 番目の「ch」の変更は非常に簡単です。

long long intunsigned は値しか保持できないため、このコードは 64 回以下のオカレンスに対してのみ有効2^64です。

于 2012-12-03T00:30:53.400 に答える