Евгения Константиновна/ 20 ноября, 2020/ Информатика ЕГЭ, Экзамен ОГЭ/ЕГЭ

Что нужно знать:

  • в известных задачах этого типа (не олимпиадных) нет ограничения на время выполнения, по крайней мере, оно несущественно для отрезков, заданных для перебора; поэтому можно использовать простой перебор без оптимизации;
  • задачи этого типа предлагается решать с электронных таблиц или собственной программы;
  • как правило, написать правильную программу значительно проще пусть необходимо перебрать все целые числа на отрезке [a; b] и подсчитать, для скольких из них выполняется некоторое условие; общая структура цикла перебора записывается так:

ПАСКАЛЬ

count := 0;
for n:=a to b do
if условие выполнено then
count := count + 1;
writeln(count);

PYTHON

count = 0
for n in range(a, b+1):
    if условие выполнено:
        count += 1
print( count )
  • проверку условия удобно оформить в виде функции, возвращающей логическое значение (True/False), но можно этого и не делать
  • проверить делимость числа n на число d можно с помощью операции взятия остатка от деления n на x: если остаток равен 0, число n делится на x нацело
  • проверка делимости выглядит так:

ПАСКАЛЬ

if n mod d = 0 then
writeln(‘Делится’)
else writeln(‘Не делится’)

PYTHON

if n % d == 0:
    print(«Делится»)
else:
     print(«Не делится»)
  • Количество делителей — для определения числа делителей натурального числа n можно использовать цикл, в котором перебираются все возможные делители d от 1 до n, при обнаружении делителя увеличивается счётчик делителей:
  • ПАСКАЛЬ

    count := 0;
    for d:=1 to n do
    if n mod d = 0 then
    count := count + 1;
    writeln( count );

    PYTHON

    count = 0
    for d in range(1, n+1):
        if n % d == 0:
            count += 1
    print( count ) # вывести количество делителей
  • Отобразить сами делители— если требуется определить не только количество делителей, но и сами делители, нужно сохранять их в массиве:
  • ПАСКАЛЬ

    в языках Pascal и C++ проще обойтись без динамического массива; здесь есть два варианта:
    1) выделить массив достаточного размера для хранения всех делителей; например, количество делителей числа n явно не превышает n;
    2)хранить только нужное количество делителей, например, если нас интересу ют числа, имеющие 4 делителя, достаточно выделить массив из 4-х элементов, а остальные делители в массив не записывать

    PYTHON

    в языке Python удобно использовать динамический массив: сначала он пуст, а при
    обнаружении очередного делителя этот делитель добавляется в массив:
    divs = []
    for d in range(1,n+1): # перебор всех возможных делителей
    if n % d == 0: # если нашли делитель d
    divs.append(d)
    # то добавили его в массив
    • перебор делителей можно оптимизировать, учитывая, что наименьший из пары делителей, таких что a  b = n, не превышает квадратного корня из n; нужно только аккуратно обработать случай, когда число n представляет собой квадрат другого целого числа;
    • отметим, что для чисел, которые предлагаются в вариантах заданий, такая оптимизация не обязательна; более того, усложнение программы может привести к дополнительным ошибкам…

    ПРОСТЫЕ ЧИСЛА - простое число n делится только на 1 и само на себя, причём единица не считается простым числом; таким образом, любое простое число имеет только два делителя.
    * для определения простоты числа можно считать общее количество его делителей; если их ровно два, то число простое, если не два – не простое:

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

    ПАСКАЛЬ

    prime := True; { сначала считаем число простым }
    for d:=2 to n-1 do
    if n mod d = 0 then begin
    prime := False; { уже не простое }
    break { досрочный выход из цикла }
    end;
    if prime then
    writeln( ‘Число простое’ )
    else
    writeln( ‘Число составное’ );

    PYTHON

    nDel = 0 # количество делителей числа
    for d in range(1, n+1): # все возможные делители
    if n % d == 0:
    nDel += 1 # нашли ещё делитель
    if nDel > 2: # уже не простое число
    break # досрочный выход из цикла
    if nDel == 2:
    print( «Число простое» )
    else:
    print( «Число составное» )
    В этом задании обычно предлагаются большие числа, поэтому проверка делимости на все числа от 2 до n-1 выполняется очень долго, и на устаревших компьютерах время работы приведённого выше алгоритма может быть слишком велико. Программу можно оптимизировать, если вспомнить, что наименьший из пары делителей,таких что a * b = n, не превышает квадратного корня из n; поэтому можно закончить перебор значением n , округлив его до ближайшего целого числа;