Модуль school, встроенный в последние версии PascalABC.Net, содержит реализацию алгоритмов, часто встречающихся в школьных задачах. Их использование сильно сокращает программный код и упрощает решение задачи. Каждая реализация в основном имеет два формата – для вызова в виде функции и для записи в точечной нотации. Рассмотрим типовые для номера 25 задачи ЕГЭ и их решение двумя способами: без использования функций модуля school и с его помощью.
Нахождение делителей числа
При нахождении нетривиальных делителей натурального числа ? (которые отличны от 1 и самого числа ?) часто предлагается перебирать числа из диапазона от 2 до [?/2] (скобки [] обозначают операцию взятия целой части числа), поскольку на интервале от [?/2]+1 до ?−1 у числа ? нет делителей. При таком подходе для нахождения делителей, например ?=10000 придется перебрать 4999 чисел (от 2 до 5000).
Перебор делителей числа ? можно оптимизировать, учитывая, что наименьший из пары делителей, таких что ?∗?=?, не превышает квадратного корня из ?; нужно только аккуратно обработать случай, когда число ? представляет собой квадрат целого числа. В этом случае для нахождения делителей, например ?=10000 придется перебрать уже 99 делителей (от 2 до 100=sqrt(10000)).
Получается, что для определения количества делителей числа ? достаточно перебирать только числа от 2 до √N; если очередной делитель ? – это точный квадратный корень, добавляем в список делителей только один делитель, если нет – то добавляем пару делителей (?, [?/?]). Потом (или сразу) необходимо добавить к списку делителей единицу и само число ?.
PascalABC модуль school: список делителей числа
В PascalABC.Net для получения списка ????, содержащего все натуральные делители числа ?, включая 1 и ?, могут быть использованы:
- функция ????????(?), которая в зависимости от типа ?, возвращает значение типа ????<???????> или ????<???64>;
- расширение ?.???????? – делает то же самое.
Задача
Вывести все делители натурального числа ?.
Способ 1 (без school)
##
var n := ReadInteger;
var lstDel := Lst(1); // в список делителей добавили 1
if n > 1 then lstDel.add(N); // числа от 1 имеют два делителя: 1 и N
var lim := round(sqrt(N));
for var d := 2 to lim do
if n.Divs(d)
then if d = sqrt(N)
then lstDel.add(d)
else begin
lstDel.Add(d);
lstDel.Add(N div d)
end;
lstDel.Sort;
println('Делители:', lstDel);
println('Количество делителей:', lstDel.Count);Способ 2 (используя модуль school)
##
uses school;
var n := ReadInteger;
println('Делители:', n.Divisors); Разложение числа в произведение простых множителей
Факторизацией натурального числа называется его разложение в произведение простых множителей. Причем такое разложение единственно.
PascalABC модуль school: разложение числа ? на простые множители
В PascalABC.Net для получения списка ????, содержащего все простые делители числа ?, могут быть использованы:
- функция ?????????(?) – выполняет разложение числа ? типа ??????? или ???64 на простые множители, результат помещается в список ????;
- расширение ?.????????? делает то же самое.
Задача
Разложить натуральное число ? в произведение простых множителей.
Рассмотрим реализацию решения задачи без использования функции ?????????(?) модуля ??ℎ???, а затем с её использованием.
Способ 1 (без school)
##
var n := ReadInteger;
var ans := n.ToString + ' = ';
var prime := true;
var lstPrimeDel := new List <integer>;
for var d := 2 to n do
begin
while n mod d = 0 do begin
lstPrimeDel.Add(d);
prime := false;
n := n div d
end;
if n = 1
then break
else if (d*d>n) and prime
then break
end;
if prime then lstPrimeDel.Add(n);
ans += lstPrimeDel.JoinToString(' * ');
ans.Println;Способ 2 (используя модуль school)
##
uses school;
var n := ReadInteger;
var rez := Factorize(n);
var ans := n.ToString + ' = ' + rez.JoinToString(' * ');
ans.Println;Другие полезные функции модуля school
PascalABC модуль school: простые числа
- функция ??????(?) – возвращает список ????, содержащий простые числа на отрезке [2; ?];
- функция ???????????(?) – возвращает список ????, содержащий первые ? простых чисел;
- расширение ?.??????? – возвращает ????, если ? – простoе и ????? в противном случае. Переменная ? должна быть типа ??????? или ???64.
PascalABC модуль school: нахождение НОД и НОК пары чисел a и b
- функция НОД(?,?) – возвращает НОД типа ??????? или ???64;
- расширение ?.НОД – возвращает НОД для кортежа ?=(?,?) с данными типа ??????? или ???64;
- функция НОК(?,?) – возвращает НОК типа ???64;
- функция НОДНОК(?,?) – возвращает кортеж вида (НОД,НОК) для пары чисел ? и ? типа ???64.
##
uses School;
var (n, m) := ReadInteger2;
НОД(n, m).Println;
НОК(n, m).Println;PascalABC модуль school: список цифр числа
Получение списка ????, содержащего все цифры числа ? в порядке их следования слева направо:
- функция ??????(?) – возвращает список типа ????<???64>;
- расширение ?.?????? делает то же, возвращая список типа ????<???????> или ????<???64>.
##
uses school;
var n := ReadInteger;
n.Digits.Sum.print;Решение типовых задач ЕГЭ
Демо к ЕГЭ 2021
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
Ответ:
3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251
Способ 1 (без school)
##
var (a, b) := (174457, 174505);
var maxd: integer;
for var n := a to b do
begin
var kd := 0;
for var d := 2 to n div 2 do
if n mod d = 0
then begin
kd += 1;
maxd := d;
end;
if kd = 2 then println(n div maxd, maxd)
end;Способ 2 (используя модуль school и лямбда-выражения)
##
uses school;
(174457..174505) // возврати все числа из диапазона
.Select(n → Divizors(n)) // получи (Select) из n все его делители
.Where(L → L.Count = 4) // оставь те, у кого 4 делителя
.Foreach(L → Println(L[1], L[2])) // для тех, что остались, выведи первые 2 Статград вариант ИН2010103
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
Ответ: 1225043; 1295029; 1442897
Способ 1 (без school)
##
var (a, b) := (123489567, 223456789);
var ans := new List<integer>; //список наибольших нетривиальных делителей
for var n := a to b do
if trunc(sqrt(n))=sqrt(n) then
begin
var lstDel := new List <integer>; //список нетривиальных делителей N
var lim := round(sqrt(N));
for var d := 2 to lim do
begin
if n.Divs(d)
then if d = sqrt(N)
then lstDel.add(d)
else begin
lstDel.Add(d);
lstDel.Add(N div d)
end;
if lstDel.Count > 3 then break;
end;
if lstDel.Count = 3
then begin
lstDel.Sort;
ans.Add(lstDel.Last);
end;
end;
ans.Sort;
ans.Println;Способ 2 (используя модуль school)
##
uses school;
var a := 123489567;
var b := 223456789;
var ans := new List<integer>;
for var n := a to b do
if trunc(sqrt(n)) = sqrt(n) then
begin
var s := Divisors(n).RemoveLast;
if s.Count - 1 = 3 then ans.Add(s.last)
end;
ans.Sort;
ans.Println;Способ 3 (используя модуль school и лямбда-выражения)
##
uses school;
(123489567..223456789)
.Where(x → trunc(sqrt(x))=sqrt(x))
.Select(x → divisors(x))
.Where(L → L.count = 5)
.foreach(L → print(L[3])); Статград вариант ИН2010201
Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 16 получим: 16=16∗1=8∗2=4∗416=16∗1=8∗2=4∗4, множество разностей содержит числа 15, 6 и 0. Найдите все натуральные числа, принадлежащие отрезку [1000000;2000000], у которых составленное описанным способом множество разностей будет содержать не меньше трёх элементов, не превышающих 100. В ответе перечислите найденные числа в порядке возрастания.
Ответ: 1113840; 1179360; 1208844; 1499400
Способ (без school)
##
var a := 1000000;
var b := 2000000;
for var n := a to b do
begin
var count := n - 1 <= 100? 1 : 0;
var lim := trunc(sqrt(n));
for var d := 2 to lim do
begin
if n mod d = 0
then if abs(n div d - d) <=100
then count += 1
end;
if count >= 3 then
println(n);
end;Способ 2 (используя модуль school)
##
uses school;
var a := 1000000;
var b := 2000000;
for var n := a to b do
begin
var s := Divisors(n);
var lst := new List<integer>;
for var i := s.Count - 1 downto (s.count div 2) do
lst.add(s[i] - s[s.Count - i - 1]);
if lst.Count(x → x <= 100) >= 3 then
println(n);
end;Статград вариант ИН2010301 (Решу ЕГЭ № 33527)
Найдите все натуральные числа, принадлежащие отрезку [101000000;102000000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.
Ответ: 101075762; 101417282; 101588258; 101645282
Способ (без school)
##
var (a, b) := (101000000, 102000000);
var n := a;
while n <= b do
begin
var keven := 1; //само число уже чётно и оно делитель себя
var lim := trunc(sqrt(n));
for var d := 2 to lim do
begin
if n mod d = 0
then begin
if d mod 2 = 0 then keven+=1;
if (d <> lim) //если d=lim, то будет чётное число чётных делителей
then if (n div d) mod 2 = 0 then keven += 1;
end;
if keven > 3 then break;
end;
if keven = 3 then println(n);
n += 2; //перебираем только чётные
end;Способ 2 (используя модуль school)
##
uses school;
(101000000..102000000)
.Where(n → Divisors(n).Count(x → x.IsEven)=3)
.Println;P.S. Если Вы заметили ошибку, буду благодарна за комментарии.
Загрузка ...
Свежие комментарии