Блог

Я изучаю C с помощью набора задач курса CS50 2, используя функцию crypt для подбора пароля методом перебора. В настоящее время пишется функция, которая выводит все возможные строки определенной длины, например:

 aa
ab
...
az
ba
...
zy
zz
  

Для этого я написал довольно простую рекурсивную функцию:

 #include <cs50.h>
#include <stdio.h>
#include <crypt.h>
#include <string.h>

void stringcycler(int n, int passLength, char *pass)
// Scrolls through all lowercase letter combinations for a string of length passLength
// Expects an integer value of the length of the strng as both n and passLength
// Also expects a char* array of length passLength with all chars set to 'a' (and a null character)
{
    if(n != 0)
    {
        for(pass[passLength - n] = 'a'; pass[passLength - n] < 'z'; pass[passLength - n]  )
        {            
            stringcycler(n-1, passLength, pass);
            printf("%sn", pass);
            // return 0;
        }
    }
}


int main()
{    
    // Initialise char *c, and scroll through letters
    int passLength = 2; // The number of characters you want to brute force guess
    char pass[passLength   1]; //  Add 1 for the null character
    int i;

    for(i = 0; i < passLength; i  ) pass[i] = 'a'; // Set every char in pass to 'a'
    pass[passLength] = ''; // Set null character at the end of string

    stringcycler(passLength, passLength, pass);

    return 0;
}
  

По большей части это работает, но переходит только в yz. Всякий раз, когда он видит z, он в основном пропускает, поэтому переходит к yz, а затем никогда не переходит от za к zz. Если я добавлю = в строку цикла for:

 pass[passLength - n] < 'z';
  

ie.

 pass[passLength - n] <= 'z';
  

Затем он печатает символы ‘{‘ в миксе. Любая помощь? И еще один вопрос, как я могу изменить это, чтобы оно работало и для всех комбинаций верхнего и нижнего регистра, есть ли аккуратный способ сделать это?

Вы печатаете после возврата из вашей рекурсии, но вы должны печатать, когда рекурсия достигла конца (или начала, в вашем случае) строки. Другими словами, печать должна быть альтернативной ветвью рекурсии:

 void stringcycler(int n, int len, char *pass)
{
    if (n != 0) {
        for (pass[len - n] = 'a'; pass[len - n] <= 'z'; pass[len - n]  ) {            
            stringcycler(n - 1, len, pass);
        }
    } else {
        printf("%s ", pass);
    }
}
  

if Часть создает строки по мере дальнейшего рекурсии вниз. else Часть что-то делает со сконструированной строкой. (Конечно, вы должны включить 'z' в свой цикл. Ваш исходный код печатает z только в последнюю очередь, потому что он печатает после возврата рекурсии, что означает, что буфер символов находится в состоянии, при котором он не будет (повторно) входить в цикл.)

Ниже приведен общий алгоритм обратного отслеживания для генерации пароля. Идея здесь в том, чтобы представить заполнение ячеек для данного массива символов a . Мы будем генерировать возможных кандидатов на заданную позицию k для массива a . Я выбрал кандидатов в виде строчных букв ascii a-z и прописных букв ASCII A-Z . Если вы хотите включить другие символы ASCII, просто соответствующим образом измените функцию construct_candidates. Как только массив заполнен, т.е. k становится PASS_LEN , мы знаем, что сгенерировали пароль, мы можем обрабатывать его так, как нам нравится, я только что напечатал пароль здесь. Значение макроса PASS_LEN можно настроить для генерации пароля любой желаемой длины.

 #include <stdio.h>
#include <stdlib.h>
#define PASS_LEN 2

static char* construct_candidates (char a[], int k, int *count)
{
    /* Lower case ASCII */
    int min1 = 97; 
    int max1 = 122; 

    /* Upper case ASCII */
    int min2 = 65; 
    int max2 = 90; 

    *count = (max1 - min1   1)   (max2 - min2   1); 
    char *cand = calloc(*count, sizeof(char));
    if (cand == NULL) {
        printf("malloc failedn");
        return NULL;
    }   
    int idx = 0;
    for (int i = min1; i <= max1; i  ) {
        cand[idx] = i;
        idx  ;
    }   
    for (int i = min2; i <= max2; i  ) {
        cand[idx] = i;
        idx  ;
    }   

    return cand;
}

static void backtrack(char a[], int k)
{
    int i;
    if (k == PASS_LEN) {
        for (i = 0; i < PASS_LEN; i  ) {
            printf("%c", a[i]);
        }   
        printf("n");
        return;
    }   

    int cand_count = 0;
    char *cand = construct_candidates(a, k, amp;cand_count);
    if (cand == NULL) {
        printf("Failed to get candidatesn");
        return;
    }   
    for (i = 0; i < cand_count; i  ) {
        a[k] = cand[i];
        backtrack(a, k   1); 
    }
    free(cand);
}

int main()
{
    char a[PASS_LEN] = {''};
    backtrack(a, 0); 
}