Тема: Перебор последовательности целых чисел. Проверка делимости
Что нужно знать:
в известных задачах этого типа (не олимпиадных) нет ограничения на время выполнения, по крайней мере, оно несущественно для отрезков, заданных для перебора; поэтому можно использовать простой перебор без оптимизации;
задачи этого типа предлагается решать с помощью электронных таблиц или собственной программы; как правило, написать правильную программу значительно проще
пусть необходимо перебрать все целые числа на отрезке [a; b] и подсчитать, для скольких из них выполняется некоторое условие; общая структура цикла перебора записывается так (Python):
count = 0
for n in range(a, b+1):
if условие выполнено:
count += 1
print( count )
Pascal:
count := 0;
for n:=a to b do
if условие выполнено then
count := count + 1;
writeln(count);
C++:
int count = 0;
for(int n = a; n
if( условие выполнено )
count += 1;
std::cout
проверку условия удобно оформить в виде функции, возвращающей логическое значение (True/False), но можно этого и не делать
проверить делимость числа n на число d можно с помощью операции взятия остатка от деления n на d: если остаток равен 0, число n делится на d нацело
проверка на языке Python выглядит так:
if n % d == 0:
print("Делится")
else: print("Не делится")
if n mod d = 0 then
writeln('Делится')
else writeln('Не делится')
if( n % d == 0 )
std::cout
else std::cout
Пример 1.
Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число. Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Решение (простой перебор):
поскольку заданный отрезок [1016; 7937] содержит не так много чисел, можно решать задачу простым перебором, особо не заботясь об эффективности вычислений
условие будем понимать так: интересующие нас числа делятся на 3 и не делятся ни на одно из чисел 7, 17, 19 и 27
нам выгоднее перебирать числа в порядке возрастания, тогда последнее найдённое число – это и есть искомое максимальное подходящее число (если требуется найти наименьшее подходящее число, удобнее перебирать числа в порядке убывания)
полная программа на языке Python:
count = 0
maxGood = 0
for n in range(1016, 7937+1):
if (n % 3 == 0) and (n % 7 != 0) and \
(n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0):
maxGood = n
count += 1
print(count, maxGood)
ещё один вариант программы (с функцией):
def isGood(n):
return (n % 3 == 0) and (n % 7 != 0) and \
(n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0)
count = 0
maxGood = 0
for n in range(1016, 7937+1):
if isGood(n):
maxGood = n
count += 1
print(count, maxGood)
Ответ: 1568 7935
Решение (программа на языке Pascal):
аналогичная программа на языке Pascal:
var count, n, maxGood: integer;
begin
count:= 0;
maxGood:= 0;
for n:=1016 to 7937 do
if (n mod 3 = 0) and (n mod 7 0) and
(n mod 17 0) and (n mod 19 0) and
(n mod 27 0) then begin
maxGood:= n;
count := count + 1
end;
writeln(count, ' ', maxGood)
end.
вариант с функцией:
var count, n, maxGood: integer;
function isGood(n: integer): boolean;
begin
isGood := (n mod 3 = 0) and (n mod 7 0) and
(n mod 17 0) and (n mod 19 0) and
(n mod 27 0);
end;
begin
count:= 0;
maxGood:= 0;
for n:=1016 to 7937 do
if isGood(n) then begin
maxGood:= n;
count:= count + 1
end;
writeln(count, ' ', maxGood)
end.
Ответ: 1568 7935
Пример 2.
Рассматривается множество целых чисел, принадлежащих отрезку [1033; 7737], которые делятся на 5 и не делятся на 11, 17, 19 и 23. Найдите количество таких чисел и максимальное из них. В ответе запишите два числа через пробел: сначала количество, затем максимальное число.
Решение (простой перебор):
поскольку заданный отрезок [1033; 7737] содержит не так много чисел, можно решать задачу простым перебором, особо не заботясь об эффективности вычислений
условие будем понимать так: интересующие нас числа делятся на 5 и не делятся ни на одно из чисел 11, 17, 19 и 23
нам выгоднее перебирать числа в порядке возрастания, тогда последнее найдённое число – это и есть искомое максимальное подходящее число (если требуется найти наименьшее подходящее число, удобнее перебирать числа в порядке убывания)
полная программа на языке Python:
count = 0
maxGood = 0
for n in range(1033, 7737+1):
if (n % 5 == 0) and (n % 11 != 0) and \
(n % 17 != 0) and (n % 19 != 0) and (n % 23 != 0):
maxGood = n
count += 1
print(count, maxGood)
ещё один вариант программы (с функцией):
def isGood(n):
return (n % 5 == 0) and (n % 11 != 0) and \
(n % 17 != 0) and (n % 19 != 0) and (n % 23 != 0)
count = 0
maxGood = 0
for n in range(1033, 7737+1):
if isGood(n):
maxGood = n
count += 1
Ответ: 1040 7730
Решение (программа на языке Pascal):
аналогичная программа на языке Pascal:
var count, n, maxGood: integer;
begin
count:= 0;
maxGood:= 0;
for n:=1033 to 7737 do
if (n mod 5 = 0) and (n mod 11 0) and
(n mod 17 0) and (n mod 19 0) and
(n mod 23 0) then begin
maxGood:= n;
count := count + 1
end;
writeln(count, ' ', maxGood)
end.
вариант с функцией:
var count, n, maxGood: integer;
function isGood(n: integer): boolean;
begin
isGood := (n mod 5 = 0) and (n mod 11 0) and
(n mod 17 0) and (n mod 19 0) and
(n mod 23 0);
end;
begin
count:= 0;
maxGood:= 0;
for n:=1033 to 7737 do
if isGood(n) then begin
maxGood:= n;
count:= count + 1
end;
writeln(count, ' ', maxGood)
end.
Ответ: 1040 7730
1 475
34 204 
