Задача № 37. Проверить, является ли натуральное число счастливым билетом
Формулировка. Дано натуральное число n. Проверить, является ли оно счастливым билетом.
Примечание: вообще, в математике обычно рассматриваются счастливые билеты с четным количеством цифр, потому что у них можно явно выделить левую и правую половины одинаковой длины, суммы цифр которых и сравниваются. Однако мы несколько расширим это определение, полагая, что если число имеет нечетную длину, его центральную цифру можно отбросить, так как ее логично было бы прибавить к накапливаемым суммам обоих половин, что, собственно, не изменит отношения между ними.
Например, число 14350 – счастливый билет, так как 1 + 4 = 5 + 0, а центральную цифру мы отбросили.
Решение. Задача является общим случаем задачи 10. Для ее решения необходимо знать длину числа (то есть его разрядность), вследствие чего нам необходимо скопировать переменную n в некоторую другую (например, a), чтобы на основе a посчитать количество десятичных разрядов n и сохранить его в некоторой переменной digits (digits в пер. с англ. означает «цифры»). Сделать это можно так:
a := n;
digits := 0;
while a <> 0 do begin
a := a div 10;
inc(digits)
end;
Здесь мы в каждой итерации цикла отбрасываем одну цифру от a и увеличиваем значение счетчика digits на 1. На некотором шаге число a будет однозначно и станет равным нулю при делении на 10, и после инкрементации счетчика, который теперь уже будет содержать количество цифр числа, произойдет выход из цикла.
|
|
|
Чтобы посчитать суммы левой и правой половины цифр числа (для накопления которых мы предусмотрим переменные left и right), мы должны запустить два последовательных цикла от 1 до digits div 2, в которых прибавлять каждый полученный разряд к соответствующей переменной и отбрасывать его. Если длина нечетная, нам необходимо отбросить серединную цифру числа без прибавления к какой-либо сумме. Так как в первом цикле мы обработали и отбросили правую половину цифр числа, то по выходе из него серединная цифра как раз будет находиться в разряде единиц. Поэтому необходим следующий шаг:
if odd(digits) then n := n div 10;
Напомним, что функция odd( n) возвращает значение true, если n нечетно, и false, если n четно. То есть, написанный выше оператор проверяет счетчик digits (в котором хранится длина исходного числа) на нечетность, и если оно нечетно, отбрасывает последнюю его цифру.
Далее необходимо накопить сумму цифр левой половины числа и вывести на экран результат сравнения сумм левой и правой половины.
Код :
| 1. program HappyTicket; 2. 3. var 4. n, a: longint; 5. left, right, digits, i: byte; 6. 7. begin 8. readln(n); 9. a := n; 10. digits := 0; 11. while a <> 0 do begin 12. a := a div 10; 13. inc(digits) 14. end; 15. left := 0; 16. right := 0; 17. for i := 1 to digits div 2 do begin 18. right := right + n mod 10; 19. n := n div 10 20. end; 21. if odd(digits) then n := n div 10; 22. for i := 1 to digits div 2 do begin 23. left := left + n mod 10; 24. n := n div 10 25. end; 26. writeln(left = right) 27. end. |
Представим, как должен работать алгоритм при вводе числа 14350:
|
|
|
1) Считаем длину числа, она равна 5 (строки 11-14);
2) В цикле из 5 div 2 = 2 повторений прибавляем к right крайние справа цифры 0 и 5, после чего отбрасываем их и имеем в n 143 (строки 17-20);
3) Так как odd( digits) = odd(5) = true, отбрасываем 3, после чего имеем в n 14 (строка 21);
4) В цикле из 5 div 2 = 2 повторений прибавляем к left оставшиеся цифры 1 и 4, после чего n становится равно 0, что, впрочем, нас уже не интересует (строки 22-25);
5) Выводим на экран значение выражения left = right – ответ положительный (строка 26).
Задача № 38. Проверить, является ли натуральное число палиндромом
Формулировка. Дано натуральное число n. Проверить, представляет ли собой палиндром его десятичная запись.
Решение. Задача является общим случаем задачи 9. Чтобы решить ее, необходимо разделить число n на две половины одинаковой длины, отбросить серединную цифру в случае нечетной длины n и проверить равенство одной из частей реверсной записи другой части.
Так как нам заранее неизвестна десятичная разрядность n, мы можем посчитать ее с помощью следующего цикла (подробнее это описывалось в предыдущей задаче):
|
|
|
a := n;
digits := 0;
while a <> 0 do begin
a := a div 10;
inc(digits)
end;
Теперь рассмотрим варианты проверки числа на палиндром вместе с разбором на примере.
Пусть дано число нечетной длины, например, 79597. Мы можем отделить его правую половину 97, проведя ряд последовательных делений с взятием остатка в цикле из digits div 2 повторений. При этом необходимо сразу сформировать ее реверс в переменную right (мы делали это в задаче 31):
right := 0;
for i := 1 to digits div 2 do begin
right := right * 10;
right := right + n mod 10;
n := n div 10
end;
Так как число нечетно, нужно отбросить его центральную цифру 5, после чего в переменной n (равной 79) будет содержаться левая половина числа, а в переменной right (также равной 79) – его перевернутая правая половина. Они равны, следовательно, ответ положительный.
Тот же порядок действий применяется и для чисел четной длины, однако теперь нам не нужно ничего отбрасывать после накопления реверсной левой части числа в переменную right, так как в числах четной длины нет серединной цифры. Например, дано число 1551: переворачиваем правую половину числа 51 (получим 15) и сравниваем ее с левой половиной: 15 = 15, ответ положительный.
|
|
|
Эти допущения говорят о том, что необходима проверка длины числа n на нечетность и, соответственно, отбрасывание серединной цифры в случае нечетности:
if odd(digits) then n := n div 10;
Код :
| 1. program CheckPalindrome; 2. 3. var 4. n, a, right: longint; 5. digits, i: byte; 6. 7. begin 8. readln(n); 9. a := n; 10. digits := 0; 11. while a <> 0 do begin 12. a := a div 10; 13. inc(digits) 14. end; 15. right := 0; 16. for i := 1 to digits div 2 do begin 17. right := right * 10; 18. right := right + n mod 10; 19. n := n div 10 20. end; 21. if odd(digits) then n := n div 10; 22. writeln(n = right) 23. end. |
Выполним «ручную прокрутку» алгоритма на числе 147741:
1) Считаем длину числа, она равна 6 (строки 11-14);
2) В цикле из 6 div 2 = 3 повторений прибавляем к right (формируя реверсную запись) последние три цифры числа n, после чего отбрасываем их и имеем в n 147, в right 147 (строки 16-20);
3) Так как odd( digits) = odd(6) = false, ничего не делаем (строка 21);
4) Выводим на экран значение выражения n = right – ответ положительный (строка 22).
Дата добавления: 2018-10-25; просмотров: 292; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!