21.02.2023

Модуль School. PascalABC.NET. Функция isPrime

 Найдем количество простых чисел на промежутке [ 2 000 000, 10 000 000].

Воспользуемся функцией модуля School. Функция isPrime возвращает логическое True, если число простое.

Формат использования: n.isPrime

Программа решения задачи на языке Паскаль

uses school;

var n,p:integer;

begin

  p:=0;

  for n:=2000000 to 10000000 do

  begin

    if n.IsPrime then p+=1;

  end;

  print(p);

end.

Код выполнился за 17 секунд.

Количество простых чисел на промежутке чисел [2000000, 10000000] равно: 515646

Функция isPrime избавляет от необходимости писать код самостоятельно.

Приведем программу, которая ищет сразу два делителя для текущего числа n.

Программа решения задачи на языке Паскаль

var n,p,t,k:integer;

begin

  p:=0;

  for n:=2000000 to 10000000 do

  begin

    t:=0;

    for k:=2 to trunc(sqrt(n)) do

    begin

      if n mod k=0 then 

        if k<>n div k then t+=2

                      else t+=1;

         

    end;

    if t=0 then p+=1;

  end;

  print(p);

end.

Код выполнился примерно за 6 мин

Использование функции isPrime оправданно, время выполнения программы для больших чисел значительно меньше.

08.02.2023

Массивы в языке Паскаль. Решение задач. 8 класс (сумма, произведение, среднее арифметическое, минимум/максимум с условием)

Список задач для решения

Задача 1. Дан целочисленный массив из N элементов. Элементы массива могут принимать целые значения от 0 до 100. Найти и вывести произведение элементов массива, которые имеют чётное значение и не оканчиваются на 0. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не оканчиваются на 0. 

Задача 2. Дан массив, содержащий N неотрицательных целых чисел, не превышающих 10 000. Найти и вывести сумму всех содержащихся в массиве трёхзначных чисел, которые оканчиваются на 9, но не на 99. 

Задача 3. Дан целочисленный массив из N элементов. Элементы массива могут принимать значения от –1000 до 1000. Найти среднее арифметическое всех элементов массива, оканчивающихся цифрой 5. Гарантируется, что хотя бы один такое элемент в массиве есть.
 
Задача 4. Дан целочисленный массив из N элементов, все элементы которого – целые числа в интервале от -1000 до 1000. Найти минимальное значение из всех нечетных элементов массива, которые делятся на 5. Гарантируется, что хотя бы один такой элемент существует. 

Задача 5. Дан целочисленный массив из N элементов, все элементы которого – неотрицательные числа, не превосходящие 10 000. Найти минимальное трехзначное число, записанное в этом массиве, если таких чисел нет, нужно вывести сообщение "Таких чисел нет".

Программы решений

Задача 1. Дан целочисленный массив из N элементов. Элементы массива могут принимать целые значения от 0 до 100. Найти и вывести произведение элементов массива, которые имеют чётное значение и не оканчиваются на 0. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого чётно и не оканчиваются на 0.

Сформируем массив случайным образом так, чтобы значения элементов были равны числам от 0 до 100 и выведем массив на экран.

for k:=1 to N do

begin

 a[k]:=random(0,100);

print(a[k]);

end;

Произведение элементов примем за 1. Пройдем циклом по массиву и проверим: не оканчивается ли элемент на 0, и является ли он четным.

p:=1;

for k:=1 to N do

begin

if (a[k] mod 10 <> 0) and (a[k] mod 2=0) then p:=p*a[k];

end;

print(p);

Программа решения задачи на языке Паскаль

var a:array[1..100] of integer; N,k,p:integer;

begin 

   readln(N);

   for k:=1 to N do

    begin

     a[k]:=random(0,100):

     print(a[k]);

    end;

    p:=1;

   for k:=1 to N do

    begin

     if (a[k] mod 10 <> 0) and (a[k] mod 2=0) then p:=p*a[k];

    end;

  print('Произведение четных элементов, не оканчивающихся на 0',p);

end.

Задача 2. Дан массив, содержащий N неотрицательных целых чисел, не превышающих 10 000. Найти и вывести сумму всех содержащихся в массиве трёхзначных чисел, которые оканчиваются на 9, но не на 99. 

Сформируем массив случайным образом так, чтобы значения элементов были равны числам от 0 до 10000 и выведем массив на экран.

for k:=1 to N do

begin

 a[k]:=random(0,10000);

print(a[k]);

end;

Сумму элементов примем за 0. Пройдем циклом по массиву и проверим: является ли элемент трехзначным числом, оканчивающимся на 9, но не на 99.

s:=0;

for k:=1 to N do

  begin

   if (a[k]>=100) and (a[k]<=999) and (a[k] mod 10=9) and (a[k] mod 100<>99) then s:=s+a[k];

  end;

Программа решения задачи на языке Паскаль

var a:array[1..100] of integer; N,k,s:integer;

begin 

   readln(N);

   for k:=1 to N do

    begin

     a[k]:=random(0,10000):

     print(a[k]);

    end;

   s:=0;

   for k:=1 to N do

    begin

     if (a[k]>=100) and (a[k]<=999) and (a[k] mod 10=9) and (a[k] mod 100<>99) then s:=s+a[k];

    end;

  print('Сумма элементов',s);

end.

Задача 3. Дан целочисленный массив из N элементов. Элементы массива могут принимать значения от –1000 до 1000. Найти среднее арифметическое всех элементов массива, оканчивающихся цифрой 5. Гарантируется, что хотя бы один такое элемент в массиве есть.

 Для вычисления среднего арифметического значения элементов, оканчивающихся цифрой 5, необходимо найти сумму таких элементов и их количество. Поскольку числа могут быть отрицательными, следует взять модуль числа при проверке abs(a[k]).

Программа решения задачи на языке Паскаль

var a:array[1..100] of integer; N,k,s,t:integer;

Sr:real;

begin 

   readln(N);

   for k:=1 to N do

    begin

     a[k]:=random(-1000,1000):

     print(a[k]);

    end;

   s:=0; t:=0;

   for k:=1 to N do

    begin

    if abs(a[k]) mod 10 = 5 then

        begin

         s:=s+a[k];

         t:=t+1;

        end;

    end;

  sr:=s/t;

  print('Среднее арифметическое элементов, оканчивающихся на 5',Sr);

end.

Задача 4. Дан целочисленный массив из N элементов, все элементы которого – целые числа в интервале от -1000 до 1000. Найти минимальное значение из всех нечетных элементов массива, которые делятся на 5. Гарантируется, что хотя бы один такой элемент существует. 

Поскольку есть гарантия, что такой элемент в массиве есть, то за искомый минимум возьмем самое большое возможное число 1000.

Программа решения задачи на языке Паскаль

var a:array[1..100] of integer; N,k,m:integer;

begin 

   readln(N);

   for k:=1 to N do

    begin

     a[k]:=random(-1000,1000):

     print(a[k]);

    end;

   m:=1000;

   for k:=1 to N do

    begin

    if (a[k] mod 2<>0) and (a[k] mod 5 = 0) and (a[k]<m) then m:=a[k];     

    end;

  print('Минимальный нечетный элемент, кратный 5',m);

end.

Задача 5. Дан целочисленный массив из N элементов, все элементы которого – неотрицательные числа, не превосходящие 10 000. Найти минимальное трехзначное число, записанное в этом массиве, если таких чисел нет, нужно вывести сообщение "Таких чисел нет".

За начальное значение минимума возьмем число -1 (число, которое не может присутствовать в массиве). Поскольку гарантии того, что трехзначное число присутствует в массиве, нет, то для дальнейшего поиска такого минимума, за его значение возьмем любое трехзначное число в массиве. 

Если после поиска значение минимума осталось равно -1, значит трехзначных чисел в массиве нет.

var a:array[1..100] of integer; N,k,m:integer;

begin 

   readln(N);

   for k:=1 to N do

    begin

     a[k]:=random(0,10000):

     print(a[k]);

    end;

   m:=-1;//число -1 выступает признаком того, что трехзначных чисел в массиве нет

   for k:=1 to N do

    begin

    if (a[k]>99) and (a[k]<1000) then m:=a[k];     

    end;

   for k:=1 to N do

    begin

    if (a[k]>99) and (a[k]<1000) and (a[k]<m) then m:=a[k];     

    end;

   if m=-1 then print('Таких чисел нет') else print('Минимальное трехзначное число',m);

end.

В решении задач с использованием массивов можно выделить следующие этапы:

  • формирование массива (ввод с клавиатуры или случайно)
  • вывод массива на экран
  • обработка массива
Каждый этап требует своего цикла для обращения к каждому элементу массива.

20.01.2023

N-ая декартова степень множества элементов, заданного массивом (Cartesian). PascalABC.NET

Применим функцию Cartesian к решению задачи на комбинаторику.

Перевод Cartesian (англ.) декартовский.

Задача. Настя составляет коды из букв слова НАСТЯ. Код должен состоять из 7 букв, буква Н должна встречаться в нём ровно два раза, буква А – как минимум один раз. Сколько различных кодов может составить Настя? 

Для составления слов длины 7 Настя использует 5 различных букв. Количество таких слов будет равно:

5*5*5*5*5*5*5 = 57

Для вычисления такого произведения в PascalABC.NET используется функция Cartesian.

Зададим символьный массив c:

c:=Arr('Н','А','С','Т','Я')

Вычислим 7-ю декартову степень множества элементов, заданного массивом с:

c.Cartesian(7)

Циклом foreach x in c.Cartesian(7) do получим все символьные последовательности в виде массивов x. Склеим символы массива x  в строку s:=x.JoinToString.

Выполним проверку условий и подсчитаем количество искомых слов.

Программа решения задачи на языке Паскаль

var c,x:array of char;  

    s:string;

    k:integer;

begin

  c:=Arr('Н','А','С','Т','Я');

  k:=0;

  foreach x in c.Cartesian(7) do

  begin

    s:=x.JoinToString;

    if (s.CountOf('Н')=2) and (s.CountOf('А')>=1) then k+=1;

  end;

  print(k);

end.

Ответ: 16401 

Демонстрация работы функции Cartesian

var c,x:array of char;  

    s:string;

begin

  c:=Arr('Т','О','К');

  foreach x in c.Cartesian(4) do

  begin

    s:=x.JoinToString;

    print(s,',');

  end;

end.

Вывод:

ТТТТ , ТТТО , ТТТК , ТТОТ , ТТОО , ТТОК , ТТКТ , ТТКО , ТТКК , ТОТТ , ТОТО , ТОТК , ТООТ , ТООО , ТООК , ТОКТ , ТОКО , ТОКК , ТКТТ , ТКТО , ТКТК , ТКОТ , ТКОО , ТКОК , ТККТ , ТККО , ТККК , ОТТТ , ОТТО , ОТТК , ОТОТ , ОТОО , ОТОК , ОТКТ , ОТКО , ОТКК , ООТТ , ООТО , ООТК , ОООТ , ОООО , ОООК , ООКТ , ООКО , ООКК , ОКТТ , ОКТО , ОКТК , ОКОТ , ОКОО , ОКОК , ОККТ , ОККО , ОККК , КТТТ , КТТО , КТТК , КТОТ , КТОО , КТОК , КТКТ , КТКО , КТКК , КОТТ , КОТО , КОТК , КООТ , КООО , КООК , КОКТ , КОКО , КОКК , ККТТ , ККТО , ККТК , ККОТ , ККОО , ККОК , КККТ , КККО , КККК 

Всего таких слов: 34 = 81

16.12.2022

Задание 12. ЕГЭ по информатике. Редактор. Статград 25.10.22

Дана программа для редактора:

НАЧАЛО

ПОКА НЕ нашлось (00)

заменить (011, 20)

заменить (022, 10)

заменить (01, 220)

заменить (02, 110)

КОНЕЦ ПОКА

КОНЕЦ

Известно, что исходная строка A содержала ровно два нуля – на первом и на последнем месте, а также поровну единиц и двоек. После выполнения данной программы получилась строка B, содержащая 40 единиц и больше 50 двоек. Какое наименьшее количество двоек может быть в строке B?

! Ошибка. Решение перебором ищем! Нужно проанализировать, как меняются подстроки в соответствии с алгоритмом. Например, подстрока 1112 меняется на 22211. Остается только подобрать количество 1 и 2. 

Решение подбором (Phyton)

Решение системой уравнений (Phyton)


13.11.2022

Язык Паскаль. Автомат обрабатывает натуральное число N > 1. Для скольких значений N в результате работы алгоритма получится число, принадлежащее отрезку [150; 200]?

 Задача. Автомат обрабатывает натуральное число N > 1 по следующему алгоритму:

1. Строится двоичная запись числа N.

2. В конец записи (справа) дописывается вторая справа цифра двоичной записи.

3. В конец записи (справа) дописывается вторая слева цифра двоичной записи.

4. Результат переводится в десятичную систему.

Пример. Дано число N = 11. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1011.

2. Вторая справа цифра 1, новая запись 10111.

3. Вторая слева цифра 0, новая запись 101110.

4. Результат работы алгоритма R = 46.

Для скольких значений N в результате работы алгоритма получится число, принадлежащее отрезку [150; 200]?

Как будем решать задачу?

Будем искать число N, для которого результат работы алгоритма будет принадлежать отрезку [150; 200].

Обнулим искомый счетчик чисел r:=0.

Запустим цикл по подбираемым числам (по условию задачи это числа, больше 1, правую границу возьмем за 100, эту границу можно подбирать): 

for k:=2 to 100 do

За число N возьмем значение k.

Выполним перевод числа N в двоичную систему счисления: для этого пока число не равно 0, вычислим остаток от деления на 2 (это двоичная цифра), число уменьшим нацело в 2 раза. Чтобы получить двоичный код, превратим цифру n mod 2 в строку d процедурой str(n mod 2, d), и накопим строку s - это и будет двоичный код числа N, причем будем к вновь полученной цифре добавлять строку, тогда цифры двоичного кода будут получены в правильном порядке:

s:=d + s;

Далее по алгоритму, описанному в условии задачи, добавим к полученному коду предпоследний символ и второй символ, это и есть результат работы алгоритма:

s:=s+s[length(s)-1]+s[2];

Далее проверим, принадлежит ли полученный двоичный код результата диапазону чисел [150, 200].

Мы знаем, что числа из данного промежутка имеют длину 8 в двоичной коде, поэтому сравним принадлежность отрезку условием:

(length(s)=8) and (s>='10010110') and (s<='11001000')

Двоичный код числа 150 - это 10010110, а двоичный код числа 200 - это 11001000.

Если условие ИСТИНА, накопим искомый счетчик чисел r, также можно вывести само подходящее число N (это значение счетчика k, значение самой переменной N равно 0 из-за выполненного перевода).

Такую проверку осуществить быстрее, чем переводить полученную строку в десятичное значение.

Программа решения на языке Паскаль

var s,d:stringn,k,r:integer;

  begin

    r:=0;

    for k:=2 to 100 do

    begin

      n:=k; s:='';

      while n<>0 do

      begin

        str(n mod 2,d);

        s:=d+s;

        n:=n div 2;

      end;

      s:=s+s[length(s)-1]+s[2];

      if (length(s)=8)and(s>='10010110')and(s<='11001000')

          then begin print(k); r:=r+1; end;

    end;

    println('Количество чисел:',r);

  end.

Результат запуска программы

Результат запуска

Ответ к задаче: 12 чисел

Способ 2 (используем модуль School и функции bin и dec)

Будем использовать функцию bin из модуля School для перевода числа в двоичную систему счисления, результатом будет строка двоичных цифр.

Далее в соответствие с алгоритмом работы автомата изменим получившуюся двоичную строку. После получения результата, переведем строку в десятичный код функцией dec и выполним проверку условия.

Программа решения задачи на языке Паскаль

uses School;

var N,R,Kol:integer; B:string; 

  begin

    for N:=2 to 100 do

    begin

      B:=bin(N);

      B:=B+B[length(B)-1]+B[2];

      R:=dec(B,2);

      if R in [150..200] then Kol+=1;

    end;

    println(Kol);

  end.