2

この文字列生成アルゴリズムを、先頭ではなく指定された文字列で開始する方法を見つける必要があります。たとえば、「aaaa」ではなく「baxi」で始まり、残りの文字列スペースを通過します。

    private static String Charset = "abcdefghijklmnopqrstuvwxyz";

    /// <summary>
    /// Start Brute Force.
    /// </summary>
    /// <param name="length">Words length.</param>
    public static void StartBruteForce(int length)
    {
        StringBuilder sb = new StringBuilder(length);
        char currentChar = Charset[0];

        for (int i = 1; i <= length; i++)
        {
            sb.Append(currentChar);
        }

        int counter = 0;
        ChangeCharacters(0, sb, length, ref counter);
        Console.WriteLine(counter);
    }

    private static void ChangeCharacters(int pos, StringBuilder sb, int length, ref int counter)
    {
        for (int i = 0; i <= Charset.Length - 1; i++)
        {                
            sb[pos] = Charset[i];
            if (pos == length - 1)
            {
                counter++;
                Console.WriteLine(sb.ToString());
            }
            else
            {
                ChangeCharacters(pos + 1, sb, length, ref counter);
            }
        }
    }
4

2 に答える 2

2

あなたが持っているものはかなり近いですが、問題の根本は、ChangeCharacters常に最初の可能な文字列から始まるように書かれているようです。たとえば、各位置の文字は常にアルファベットの最初の文字から始まります('a'あなたの例では)。開始文字列の各位置で最初のパスを実行して、既に配置されている文字から開始する必要があります。その後のパスは、生成するアルファベットの最初の文字から開始します。

したがって、既にあるコードを使用して、次の変更を行う必要があります。

  1. これが最初のパスであることを示すフラグを渡します。
  2. 最初のパス フラグに基づいて、ループの開始点を選択します。
  3. その最初のパス フラグを再帰呼び出しに渡します。
  4. 各位置での最初のパスの後、フラグをリセットします。
  5. StringBuilder現在のデフォルトの開始点ではなく、開始文字列で を初期化します。

わかりやすくするために変更する価値のある項目が他にもいくつかあります。これらはいずれも正確性のために厳密に必要なものではありませんが、コードを読みやすく理解しやすくします。

  1. lengthと常に同じなので、を渡す必要はありませんsb.Length。情報が重複していると、せいぜい読者はより多くの情報を追跡する必要があり、最悪の場合、後でコードを変更して関係が壊れた場合にバグが発生する可能性があります。

  2. ゼロベースのインデックス付けを使用する言語でのインデックス ループの標準的なイディオムは、境界でのオーバーフロー エラーを回避するため、「より小さい」(または「等しくない」) コンパレータを使用する「エンドポイント専用」形式です。i < lengthの代わりにi <= length - 1。ほとんどのコード リーダーはこのイディオムを本能的に理解しますが、エンドポイントを含む形式では通常、アンチ イディオムが必要な理由を考える必要があります。

  3. 参照によってカウンターを渡すのではなく、生成された文字列の数を返すだけです。外部状態を変化させないメソッドは、「純粋」または「機能的」と呼ばれることが多く、一般的に理解しやすいものです。(ただし、StringBuilder渡される状態にも注意してください。)

    • さらに改良するためにIEnumerable<string>、 を返すことをお勧めします。これにより、カウントを追跡する必要がなくなるだけでなく、呼び出し元がその決定を行うのではなく、文字列をどうするかを決定できるようになります (たとえばConsole.WriteLine、カウンターの呼び出しとインクリメント) ）あなたの方法の内部。

すべてをまとめると、コードは次のようになります (どの変更または提案が行われているかを示すコメントで注釈が付けられています)。

public static void StartBruteForce(string start)
{
   /*change 5*/ StringBuilder sb = new StringBuilder(start);
   /*sugg 3*/ int counter = ChangeCharacters(0, /*change 1*/ true, sb);
   Console.WriteLine(counter);
}

private static int ChangeCharacters(int pos, /*change 1*/ bool firstPass , StringBuilder sb)
{
    /*sugg 3*/ int counter = 0;
    for (int i = /*change 2*/ firstPass ? Charset.IndexOf(sb[pos]) : 0; /*sugg 2*/ i < Charset.Length; i++)
    {                
        sb[pos] = Charset[i];
        if (pos == /*sugg 1*/ sb.Length - 1)
        {
            counter++;
            Console.WriteLine(sb.ToString());
        }
        else
        {
            /*sugg 3*/ counter += ChangeCharacters(pos + 1, /*change 3*/ firstPass, sb);
            /*change 4*/ firstPass = false;
        }
    }
    /*sugg 3*/ return counter;
}
于 2013-01-25T18:01:41.180 に答える
0

再帰アルゴリズムは、再開できるようにステップに分割する必要があります。

この階乗アルゴリズムをステップに分割して、再開できるようにします。

または、再開ポイント [いずれの場合でも必要になります] を知る必要がありますが、そのポイントに到達する前にすべての値を無視します。

これは (より悪い) 素朴な実装であり、CPU に関しては、計算を再開するという考え全体を無効にします。実際には再開しないため、以前の値をキャプチャ/出力しないだけです。

private static String Charset = "abcdefghijklmnopqrstuvwxyz";

/// <summary>
/// Start Brute Force.
/// </summary>
/// <param name="length">Words length.</param>
public static void StartBruteForce(int length)
{
    StringBuilder sb = new StringBuilder(length);
    char currentChar = Charset[0];

    for (int i = 1; i <= length; i++)
    {
        sb.Append(currentChar);
    }

    int counter = 0;

    var resumePoint = 60975;

    ChangeCharacters(0, sb, length, ref counter, resumePoint);

    Console.WriteLine(counter);
}

private static void ChangeCharacters(int pos, StringBuilder sb, int length, ref int counter, int resumePoint)
{
    for (int i = 0; i <= Charset.Length - 1; i++)
    {
        sb[pos] = Charset[i];
        if (pos == length - 1)
        {
            counter++;
            if (counter >= resumePoint)
            {
                Console.WriteLine(string.Format("{0} : {1}", counter, sb.ToString()));
            }
        }
        else
        {
            ChangeCharacters(pos + 1, sb, length, ref counter, resumePoint);
        }
    }
}
于 2013-01-25T16:07:46.827 に答える