Блог

Я кодирую алгоритм рекурсивного транспонирующего шифрования, чтобы освежить некоторые из моих простых навыков C. Поскольку вы, возможно, лучше знакомы с столбчатым шифром транспонирования, рекурсивный работает таким образом, предполагая некоторый открытый текст str в качестве входных данных:

• If strlen(str) <=2 : encrypt(str) == str
• else : encrypt(str) == encrypt(reversed_first_half_of_str) encrypt(reversed_second_half_of_str)

Вот моя попытка зашифровать открытый текст любой длины с помощью этого алгоритма.

 void encrypt(char string[], size_t length) {
    int i, rs_bound;
    int mid = floor((double)length / 2.0);
    char left_substr[mid], right_substr[length - mid];

    if (length <= 2) {
        if (length > 0) {
            write_ciphertext(string);
        }
        return;
    }

    // Reverse the first half of the string
    for (i = 0; i < mid;   i) {
        left_substr[i] = string[mid - i - 1];
    }
    encrypt(left_substr, mid);

    // Reverse the second half of the string
    if ((length - mid) % 2 == 0) {
        rs_bound = mid;
    }
    else {
        rs_bound = mid   1;
    }
    for (i = 0; i < rs_bound;   i) {
        right_substr[i] = string[length - i -1];
    }
    encrypt(right_substr, length - mid);

}
 

Учитывая открытый текст 123456789 , он выдает вывод 3412¬ºþ89575¬ºþ вместо правильного, 341289576 . Кроме того, учитывая открытый текст 12345678 , он выдает вывод 412ÿ7856ÿ вместо правильного 341289576 . Когда я заменяю rs_bound на mid , я получаю правильные выходные данные для входов четной длины (например, the 12345678 ), а когда я заменяю его на mid 1 , я получаю правильный вывод для нечетных четных строк (например, the 123456789 ).

Обратите внимание, что по очевидным причинам left_substr всегда имеет четную длину. Единственной подстрокой, которая должна обрабатывать входные данные произвольной длины, является right_substr .

Может кто-нибудь помочь мне обобщить способ right_substr правильной обработки входных данных как нечетной, так и четной длины?

РЕДАКТИРОВАТЬ: вот моя реализация reverse_string , согласно предложению Джонни.

 char* reverse_string(char *str, size_t length)
{
    if (!str) {
        return NULL;
    }

    char *revsubstr = malloc(length);
    // Get the substring to be reversed from the whole string.
    memcpy(revsubstr, str, length);

    // "Mark" the two ends of the substring to be reversed.
    char* start = revsubstr;
    char* end = revsubstr   length - 1;
    // Reverse it
    for( ; start < end;   start, --end) {
        char s = *start, e = *end;
        *start = e;
        *end = s;
    }

    return revsubstr;
}
 

Я думаю, вы слишком много думаете о поиске средней точки. Это просто:

 int mid = length / 2;
 

Ваш код может быть проще для понимания, если вы создадите вспомогательную функцию для обратного преобразования строки:

 // Do an in-place reversal of the string. Returns the input string.
char * reverse_string(char *string, size_t length)
{
     for (int l = 0, r = length - 1; l < r; l  , r--) {
        char tmp = string[l];
        string[l] = string[r];
        string[r] = tmp;
     }
     return string;
}
 

Кроме того, я не вижу необходимости в каких-либо дополнительных массивах, если вы выполняете реверсирование на месте. Тогда ваш код становится точно таким, как описано в описании проблемы.

 void encrypt(char string[], size_t length)
{
    if (length <= 2) {
        return;
    }

    int mid = length / 2;
    
    // Reverse then encrypt first half
    encrypt(reverse_string(string, mid), mid);
    // Reverse then encrypt second half
    encrypt(reverse_string(amp;string[mid], length - mid), length - mid);
}
 

Я проверил это с:

 int main(void) {
    char num[] = "123456789";
    encrypt(num, strlen(num));
    printf("%sn", num);
    return 0;
}
 

И результат

 341289576