Hosted by uCoz

Задача № 43. Проверить, начинается ли каждый из членов последовательности с десятичной цифры, на которую оканчивается предыдущий

Формулировка. Дана последовательность натуральных чисел, ограниченная вводом нуля. Проверить, начинается ли каждый из ее членов (со второго) с десятичной цифры, на которую оканчивается предыдущий. Например, таковой последовательностью будет являться 14 47 712 2179 9 9 93 0 (также сохранен ограничивающий ноль).

Решение. Задача решается через цикл с предусловием, что характерно для задач на последовательность с ограничителем. При ее решении мы могли бы не рассматривать «вырожденные варианты», в которых на вход будет подаваться, например, пустая последовательность (то есть состоящая из единственного нуля) или последовательность из одного члена, так как на вопрос о том, удовлетворяют ли такие последовательности заданному критерию, ответить теоретически достаточно трудно. Разумнее всего было бы считать выполнение критерия для таких последовательностей неопределенным, что, однако, в формате даваемого нами ответа не представляется возможным: под «проверкой» характеристического свойства в данном случае понимается ответ на вопрос: либо «да», и последовательность отвечает заданным требованиям, либо «нет», и, соответственно, не отвечает.

Следовательно, нам нужно вместо ответа о «неопределенности» проверяемого свойства дать один из допустимых ответов. Наверное, разумно было бы дать при обработке вырожденных случаев программой ответ «нет». Мы возьмем это на заметку и попытаемся сделать контроль исключений, когда уже будет готово решение задачи для общего случая, чтобы заранее не наделать ошибок. Это необходимо потому, что мы попробуем инициализировать значения переменных при запуске программы таким образом, чтобы обработку вырожденных случаев можно было выполнить с минимальным вложением дополнительного кода – мы уже делали это в задаче 32.

Теперь о переменных. Так как нам необходимо проверять выполнение критерия на двойках (парах) элементов, то и хранить в памяти нужно сразу два элемента (a и b). Первый элемент не имеет предшественника, поэтому после ввода мы не обрабатываем его и можем вводить следующий элемент в одном операторе с ним:

read(a, b);

Имея два элемента, мы уже можем выполнить проверку нашего свойства. Однако уже на этом этапе мы можем догадаться, что в силу необходимости выполнить проверку для всех пар элементов последовательности следует сразу поместить ее в цикл. Мы будем считывать каждый очередной член последовательности в переменную b, и так как последнее вводимое число по условию – 0, то предусловием цикла будет b < > 0 (так как при b = 0 цикл должен прекратиться):

while b <> 0 do begin

    ...

    a := b;

    read(b)

  end;

На месте троеточия будет располагаться код проверки каждой пары, полностью охватывающий определение нашего свойства. Примечание: в «шаблоне» основного цикла мы выделили также оператор a := b, который обеспечивает движение по каждым двум соседним элементам последовательности. Следует обратить внимание на то, что мы должны проверять выполнение нашего свойства для 1-го и 2-го, 2-го и 3-го, 3-го и 4-го и т. д. элементов последовательности.

Когда мы уже выполнили проверку для двух элементов, например, для 1-го (который хранится в переменной a) и 2-го (который хранится в переменной b), то далее мы присваиваем переменной a значение переменной b (в которой у нас хранился 2-ой элемент), затем считываем в b 3-й элемент, чтобы проверить свойство для 2-го и 3-го элементов и т. п.

При этом нужно четко понимать, что мы не можем считывать в цикле сразу две переменные, так как при таком подходе проверка будет выполняться лишь для 1-го и 2-го, 3-го и 4-го и т. д. элементов, что неверно.

Разберем саму проверку. Так как на каждом шаге цикла программе требуется выяснить, начинается ли следующий член последовательности с десятичной цифры данного, то, имея данный член в переменной a и следующий член в b, мы должны сравнить последнюю цифру a (обозначим ее как last) с первой цифрой b (обозначим ее как first). Сделать это можно так:

last := a mod 10;

first := b;

while first > 9 do begin

  first := first div 10

end;

Здесь мы сначала добыли последнюю цифру a (строка 1), затем скопировали в last значение b (переменную b нельзя изменять, так как ее значение понадобится нам на следующем шаге цикла) и во вложенном цикле разделили last на 10 столько раз, чтобы в ней осталась лишь одна цифра, которая является его первой цифрой.

Добыв нужные цифры, мы можем выполнить их сравнение и выйти из цикла в том случае, когда они не равны, так как при этом нарушается наше характеристическое свойство, данное в условии, и после этого дальнейшая проверка бессмысленна:

if last <> first then break;

Когда цикл завершится, нам останется лишь вывести на экран результат сравнения переменных last и first: если цикл завершился, то последовательность отвечает заданному свойству (так как не было выхода через break), они будут равны и будет выведен ответ true; если же был совершен выход через break, то переменные неравны и ответ, соответственно, false.

Теперь попробуем оптимизировать программу для обработки вырожденных случаев для пустой последовательности (когда вводится единственный 0) и для последовательности из одного члена (когда вводится некоторое число и 0): мы договорились выводить для них ответ false.

Очевидно, в данный момент наша программа обрабатывает корректно минимальный случай из двух членов: тогда проходит одно повторение тела цикла, в котором переменные last и first получают значения, затем может произойти выход по break или завершение цикла по вводу нуля, как и должно быть.

Однако если мы введем последовательность из одного члена, то при вводе a и b в переменную a пойдет этот член, а в b окажется ограничивающий ноль, что приведет к невыполнению входа в основной цикл и программа перейдет к оператору вывода writeln(last = first), что неверно, так как значение переменных last и first в данный момент будет не определено и выражение в операторе вывода может дать любой результат. Это значит, что для избегания подобного исхода нам нужно выполнить инициализацию переменных last и first заведомо неравными значениями, чтобы получить гарантированный ответ false при вводе последовательности из одного члена. Это можно сделать так:

first := 1;

last := 0;

Но что будет, если ввести последовательность, состоящую из одного нуля? В нашей программе это невозможно, так как оператор ввода в начале содержит две переменные, и если мы сразу введем 0, то программа «зависнет» в ожидании ввода второго числа. Чтобы избежать этого, мы должны вводить одно число в переменную a, и если оно не равно 0, нужно ввести b. Вместе с этим необходимо заранее присвоить переменной b число 0, так как она была определена в случае последовательности из одного члена, чтобы не осуществился вход в основной цикл:

read(a);

b := 0;

if a <> 0 then read(b);

Эта конструкция заменит оператор read(a, b), который мы описывали в самом начале решения задачи.

Код:

  1. program LastAndFirst;
  2. var
  3. a, b, first, last: word;
  4. begin
  5. first := 1;
  6. last := 0;
  7. read(a);
  8. b := 0;
  9. if a <> 0 then read(b);
  10. while b <> 0 do begin
  11. last := a mod 10;
  12. first := b;
  13. while first > 9 do begin
  14. first := first div 10
  15. end;
  16. if last <> first then break;
  17. a := b;
  18. read(b)
  19. end;
  20. writeln(last = first)
  21. end.