Урок 9. Задачи школьного курса

В этом уроке — задачи, которые встречаются почти в каждом школьном курсе информатики и на контрольных. Все они собраны из того, что уже было: div и mod, условия, циклы, строки. Сначала попробуйте решить задачу сами, а потом сверьтесь с разбором.

Цифры числа

Задача. Дано целое число. Сколько в нём цифр и чему равна их сумма?

Последняя цифра числа — n mod 10, а n div 10 отбрасывает её. Так повторяется, пока число не кончится:

program Digits;
var
  n, sum, count: longint;
begin
  readln(n);
  n := abs(n);
  sum := 0;
  count := 0;
  repeat
    sum := sum + n mod 10;
    count := count + 1;
    n := n div 10;
  until n = 0;
  writeln('Цифр: ', count, ', сумма цифр: ', sum);
end.

90210

Цифр: 5, сумма цифр: 12

repeat выбран не случайно: у числа 0 одна цифра, и тело цикла должно выполниться хотя бы раз. abs убирает минус, чтобы mod не давал отрицательных цифр. Тот же приём — произведение цифр, самая большая цифра, число наоборот. Подробнее — в справке Сумма цифр числа.

Простые числа

Задача. Вывести все простые числа от 2 до n. Простое число делится только на 1 и на себя.

Проверку удобно вынести в функцию. Делители достаточно перебирать, пока d * d <= x: если у числа есть делитель больше корня, то есть и парный ему меньше корня.

program PrimesToN;
var
  n, i: integer;

function IsPrime(x: integer): boolean;
var
  d: integer;
begin
  IsPrime := x >= 2;
  d := 2;
  while d * d <= x do
  begin
    if x mod d = 0 then
    begin
      IsPrime := false;
      exit;
    end;
    d := d + 1;
  end;
end;

begin
  readln(n);
  for i := 2 to n do
    if IsPrime(i) then
      write(i, ' ');
  writeln;
end.

30

2 3 5 7 11 13 17 19 23 29

Как проверить одно число и что такое решето Эратосфена — в справке Как проверить, простое ли число.

НОД и НОК

Задача. Найти наибольший общий делитель и наименьшее общее кратное двух натуральных чисел.

Алгоритм Евклида: НОД(a, b) = НОД(b, a mod b), а когда остаток станет нулём, ответ — оставшееся число. НОК находится через НОД: a · b / НОД(a, b).

program GcdLcm;
var
  a, b, x, y, t: longint;
begin
  readln(a, b);
  x := a;
  y := b;
  while y <> 0 do
  begin
    t := x mod y;
    x := y;
    y := t;
  end;
  writeln('НОД = ', x);
  writeln('НОК = ', a div x * b);
end.

84 36

НОД = 12
НОК = 252

Копии x и y нужны, чтобы исходные a и b сохранились для НОК. НОК считается как a div x * b, а не a * b div x: сначала деление, и промежуточное число не выходит за предел longint раньше времени.

Факториал

Задача. Вычислить n! = 1 · 2 · … · n.

program Factorial;
var
  n, i: integer;
  f: int64;
begin
  readln(n);
  f := 1;
  for i := 2 to n do
    f := f * i;
  writeln(n, '! = ', f);
end.

15

15! = 1307674368000

Факториал растёт очень быстро: в longint помещается только до 12!, в int64 — до 20!. Копилку произведения начинают с 1, а не с 0 — иначе всё произведение будет нулём.

Числа Фибоначчи

Задача. Вывести первые n чисел Фибоначчи (n ≥ 2): первые два равны 1, каждое следующее — сумма двух предыдущих.

program Fibonacci;
var
  n, i: integer;
  a, b, c: longint;
begin
  readln(n);
  a := 1;
  b := 1;
  write(a, ' ', b);
  for i := 3 to n do
  begin
    c := a + b;
    write(' ', c);
    a := b;
    b := c;
  end;
  writeln;
end.

10

1 1 2 3 5 8 13 21 34 55

Хранятся только два последних числа: после вычисления c они «сдвигаются» — a становится b, b становится c.

Перевод в двоичную систему

Задача. Записать натуральное число в двоичной системе.

Остатки от деления на 2 — это двоичные цифры справа налево. Каждая новая цифра приклеивается к строке слева:

program ToBinary;
var
  n: longint;
  s: string;
begin
  readln(n);
  if n = 0 then
    s := '0'
  else
    s := '';
  while n > 0 do
  begin
    if n mod 2 = 0 then
      s := '0' + s
    else
      s := '1' + s;
    n := n div 2;
  end;
  writeln(s);
end.

13

1101

Проверка: 1 · 8 + 1 · 4 + 0 · 2 + 1 · 1 = 13. Для другой системы счисления число делят на её основание, а остаток записывают цифрой этой системы; в системах с основанием больше 10 вместо остатков 10, 11, 12… пишут буквы A, B, C…

Палиндром

Задача. Проверить, читается ли строка одинаково слева направо и справа налево.

Первый символ сравнивается с последним, второй — с предпоследним и так до середины:

program Palindrome;
var
  s: string;
  i, n: integer;
  ok: boolean;
begin
  readln(s);
  n := length(s);
  ok := true;
  for i := 1 to n div 2 do
    if s[i] <> s[n - i + 1] then
      ok := false;
  if ok then
    writeln('Палиндром')
  else
    writeln('Не палиндром');
end.

racecar

Палиндром

Символу s[i] в пару стоит s[n - i + 1]: для i = 1 это последний символ, для i = 2 — предпоследний.

Как решать новые задачи

• Сначала решите задачу на бумаге для маленьких чисел — так видно, что повторяется.
• Подумайте, какой цикл нужен: известно число повторов — for, нет — while или repeat.
• Проверьте крайние случаи: 0, 1, отрицательные числа, пустую строку, одно число в массиве.
• Посмотрите, не выйдет ли результат за предел типа, — тогда longint или int64.

Коротко

• Цифры числа: n mod 10 — последняя цифра, n div 10 — без неё.
• Простое число: делители перебирают, пока d * d <= n.
• НОД — алгоритм Евклида через mod, НОК = a div НОД · b.
• Произведение начинают с 1, сумму — с 0; для факториала — int64.
• Двоичная запись — остатки от деления на 2, приклеенные слева.

Проверьте себя