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 回答