Как лучше всего следовать функции, чтобы понять, что она делает?

Question

Этот вопрос является общим, но я приведу конкретный пример.

Общая проблема, которая должна быть решена, объясняется here. Описание длинное, поэтому я не буду вырезать и вставлять, но основная идея заключается в строках ввода S и T (как они вызывают в приведенном ниже коде), найдите минимальное количество изменений, которые необходимо выполнить для S, чтобы создать T. Одно изменение может быть:

• Вставьте одну букву в любой конец строки.
• Удалить одну букву с любого конца строки.
• Измените одну букву на другую.

Ниже представлено решение, которое я пытаюсь отслеживать. То, что я ищу, - это советы о том, как наилучшим образом решить проблему. Каковы некоторые методы, которые я могу использовать для чтения и понимания кода (давайте отбросим шаг через отладчик).

#include<iostream> 
#include<cstring> 
#include<stdio.h> 
using namespace std; 
char S[2010]; 
char T[2010]; 
int lens,lent; 
int main() 
{ 
    int i,j,ma,p; 

    while(scanf("%s%s",S,T)!=EOF) 
    { 
     lens=strlen(S); 
     lent=strlen(T); 
     ma=0;p=0; 
     for(i=0;i<lens;i++) 
     { 
      p=0; 
      for(j=0;j<lent;j++) 
      { 
       if(i+j>=lens) 
        break; 
       if(S[i+j]==T[j]){p++;} 
      } 
      if(ma<p) 
       ma=p; 
      if(ma==lent) 
       break; 
     } 
     for(i=0;i<lent;i++) 
     { 
      p=0; 
      for(j=0;j<lens;j++) 
      { 
       if(i+j>=lent) 
        break; 
       if(T[i+j]==S[j]){p++;} 
      } 
      if(ma<p) 
       ma=p; 
      if(ma==lent) 
       break; 
     } 
     printf("%d\n",lent-ma); 
    } 
    return 0; 
} 

Answer 1

Шаг 1: Объясните себе, что представляют переменные:

S: строка из которой мы хотим извлечь подстроку

T: строку, которую мы хотим достичь в после модификации извлеченной подстроки с максимально возможным количеством операций

lens: длина строки S

lent: длина строки T

i: индекс в S, из которого извлекается подстрока начинается

j: индекс в строке T символа, который мы хотим соответствовать с соответствующим символом в подстроку

p: количество совпадающих символов, найденных в настоящее время исследуемой подстроки

ma: максимальное количество ма ать символы для любого из подстрок

---

Шаг 2: Установив эти значения, это довольно просто, чтобы перевести первый цикл на слова:

for loop 1 : selects a start position of the substring 

    set the match counter to 0, since we start investigation of a new substring 


    for loop 2 : loops through the substring 

     if 1 :  if there is no char left to read string S, stop looping 

     if 2 :  if the current character in the extracted substring matches 
       a character in the "goal" string, increment the match counter (p) 


    if 3 :  now, we finished looping through a substring, 
      if the count of matching characters in the substring and the goal 
      string was higher than for any of the previous counts, 
      then store this value as the max count 

    if 4 :  if the max count of matching characters is equal to the 
      length of the "goal string", dr Moriatry can receive the goal string 
      with 0 substring changes, and hence, we can stop looping 

---

Следующий цикл похож , Роли S и T меняются. Обратите внимание, однако, что роли S и T не были полностью отменены (как говорили некоторые люди). Конечное условие для внешнего цикла for использует длину T в обоих случаях, что имеет смысл.

Здесь мы извлекаем подстроки из строки T (строка цели) и пытаемся сопоставить их со строкой S. Почему мы это делаем?

Я ожидаю, что человек, который написал код хотел, чтобы учесть случаи, как, например, следующее:

S = "b"  T = "abc" 

Если бы мы только извлечь подстроки из S и сопоставляют их всей T строки, начиная в первом индексе (как и в первом цикле) мы сравниваем только «b (в S), совпадение a (первый символ в T), а затем мы продолжим и говорим:« Поскольку никакая подстрока не совпадает, мы нужно три операции смены строки, чтобы получить строку T "(что, очевидно, неверно, поскольку мы можем достичь этого, выбирая« b »в качестве подстроки для извлечения и делая 2 операции изменения в конечном итоге с T)

Answer 2

Я бы начал сначала с некоторых манипуляций с строкой в ​​программе. Первым шагом было бы попытаться дать лучшие имена переменным.

Я бы заменил 'i' на sPos для позиции в строке S. Ну, по крайней мере, это применимо к первому циклу, поскольку второй цикл «i» изменяет значение как позицию в T, d на самом деле тогда решить избавиться от i и вместо этого иметь две переменные, поэтому каждая переменная имеет одну цель, которая соответствует ее имени.

Затем попробуйте то же самое для j, ma и p.

Как только это будет сделано, я подумал бы о том, чтобы попытаться выяснить, что делают две циклы «для». Они кажутся практически идентичными. Возможно, они могут быть разделены на одну функцию, которая вызывается дважды. Опять же, попробуйте выяснить, что делает эта функция, и назовите ее очень осторожно, чтобы имя объясняло ее цель.

Повторяйте шаги, как это, пока у вас не будет кода, который создает определенный человеческий смысл.

Answer 3

Лучшим решением будет переписать код по мере его понимания. Есть несколько вещей:

1. Смотреть дубликат кода. Он делает то же самое с S и T, и роли меняются на противоположные. Вы можете создать функцию foo() с обеими строками в качестве параметра и использовать foo(S,T) и foo(T,S)
2. Попробуйте сломать слишком много глубины. Когда вы видите много вложенных циклов большую часть времени, некоторые из внутренних циклов можно рассматривать как функцию, выполняющую что-то конкретное.
3. переименовывать постепенно переменные, как вы понимаете больше, что происходит
4. И последнее, но не в последнюю очередь, не выбрасывайте пошагового отладчика

Answer 4

1. Извлеките два внешних петель в их собственные функции.
2. Найти общность (подсказка: они только изменяют ma).
3. Извлечь эту общность.
4. Извлеките внутренние петли в их собственную функцию (подсказка: код идентичен).
5. Напишите единичные тесты для каждой функции, чтобы проверить ваше понимание.

Answer 5

Ключом к пониманию кода является понимание значения переменных, которые изменяются наименее, в данном случае ma и p, и распознавать идиомы кодирования.

Два фрагмента кода

if(ma<p) 
    ma=p; 
if(ma==lent) 
    break; 

являются «высоким водяным знаком» идиомами для переменного р (с условием разрыва на максимально возможном значении). p увеличивается при каждом совпадении в символе в позиции j подстроки LHS, начиная с i, с символом j-позиции RHS. Поэтому для петель, индексированных j (внутренние петли), p - это число одинаковых символов, которые находятся в одинаковых j-позициях. Поэтому я бы переименовал p (в моей голове хотя бы!) В «number_of_identical_chars_in_same_pos».

Петли, индексированные по i, находят самую высокую p (сохраненную в ma) для каждой подстроки в LHS, которая заканчивается последним символом LHS (или раньше, если подстрока длинная). Поэтому ma следует переименовать «max_common_chars_in_a_span». Вместе две петли находят максимальное количество общих символов в одном и том же положении любой подстроки, заканчивающейся последним символом любой из сторон.

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