Язык Паскаль. Циклический алгоритм. Решение задач. 8 класс

В этой публикации рассмотрим решение некоторых задач по теме "Циклический алгоритм".

Задача 1. С клавиатуры вводится N натуральных чисел. Найти количество чисел, оканчивающихся на 3.

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

Воспользуемся оператором цикла с счетчиком для ввода N чисел.

for k:=1 to N do

begin

readln(a);

end;

Чтобы узнать, оканчивается ли число на 3, воспользуемся операцией mod (целый остаток от деления).

Пусть число a=463.

Последнюю цифру вычислим так: a mod 10.

Действительно, 463 mod 10 равно 3.

Будем копить количество чисел (переменная p), оканчивающихся на 3, оператором:

if a mod 10 = 3 then p:=p+1;

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

var k, N, p, a:integer;

begin

   writeln('Введите количество чисел N ');

   readln(N);

   p:=0;

   for k:=1 to N do

   begin

     writeln('Введите натуральное число ');

     readln(a);

    if a mod 10 = 3 then p:=p+1;

   end;

   writeln('Количество чисел, оканчивающихся на 3 равно ',p);

end.

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

А что, если бы числа были не натуральные, а целые (как отрицательные, так и положительные), изменилось бы условие в операторе if?

Задача 2. С клавиатуры вводится N целых чисел. Найти среднее арифметическое двузначных чисел.

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

Воспользуемся оператором цикла с счетчиком для ввода N чисел.

for k:=1 to N do

begin

readln(a);

end;

Как узнать двузначное перед нами число или нет. Приведем примеры целых двузначных чисел: 23, -34, -99, 55.

Таким образом, минимальное двузначное положительное число это 10, а максимальное 99. 

Минимальное отрицательное двузначное число это -99, а максимальное -10.

Значит для проверки условия, является ли число двузначным, можно воспользоваться условием:

(a>=10) and (a<=99) or (a>=-99) and (a<=-10)

то есть число отрицательное двузначное или положительное двузначное.

Ранее в этом блоге мы рассматривали способы проверки такого условия. Читайте статью "Как проверить, является ли число двузначным".

Если число a двузначное, то будем копить сумму s и количество p таких чисел (будем использовать операторные скобки для объединения этих двух действий).

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

var k, N, p, a, s:integer; sr:real;

begin

   writeln('Введите количество чисел N ');

   readln(N);

   p:=0; s:=0;

   for k:=1 to N do

   begin

     writeln('Введите целое число ');

     readln(a);

     if (a>=10) and (a<=99) or (a>=-99) and (a<=-10) then 

      begin

        p:=p+1;

        s:=s+a;

      end;

   end;

   sr:=s/p;

   writeln('Среднее значение равно ',sr);

end.

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

А что, если ни одного двузначного числа мы не введем, что выведет программа?

Язык Паскаль. Верно ли, что только одно число из пары кратно 3?

Задача. С клавиатуры вводятся два целых числа. Верно ли, что только одно число кратно 3?

Приведем примеры:

Пусть A = 12, B = 11. В этом случае ответ ДА, первое число кратно 3, а второе не кратно 3.

Пусть A = 11, B = 12. В этом случае ответ ДА, второе число кратно 3, а первое не кратно 3.

Пусть A = 12, B = 12. В этом случае ответ НЕТ, оба числа кратны 3.

Пусть A = 11, B = 11. В этом случае ответ НЕТ, оба числа не кратны 3.

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

1 способ

Проверим условие

Если число А кратно 3 и при этом число В не кратно 3 или число А не кратно 3, а число В кратно 3, то ответ ДА, иначе НЕТ.

if (A mod 3 = 0) and (B mod 3<>0) or (A mod 3<>0) and (B mod 3=0) then print('ДА') else print('НЕТ');

2 способ

Проверим условие

НЕВЕРНО, что условие (число А кратно 3) равносильно условию (число В кратно 3)

if not ((A mod 3 = 0) = (B mod 3 = 0)) then print('ДА') else print('НЕТ');

3 способ

Для проверки такого условия можно использовать логическую операцию Исключающее ИЛИ (xor), по сути она равна логическому неравенству.

if (A mod 3 = 0) xor (B mod 3 = 0) then print('ДА') else print('НЕТ');

Если ввести обозначения двум условиям X и Y, то верно следующее:

not (X = Y) равно (X xor Y)

Язык Паскаль. Списки (объявление, операции, методы, решение задач). PascalABC.NET

 До начала работы

В данной публикации покажем, что такое список в PascalABC.NET, рассмотрим объявление списков, заполнение значениями, операции и некоторые методы, а также решим задачу с применением списка.

Список (List) представляет собой структуру данных на основе динамического массива с динамическим изменением его размера во время выполнения программы.

Объявление списка в блоке Var

var L:list<integer>;

Создание нового пустого списка в теле программы

L:=new List<integer>;

Создание нового списка и заполнение его значениями

M:=Lst(-9, 213);

Добавление значений в конец списка

L.Add(21); // [21]

L+=5; // [21, 5]

L+=-6; // [21, 5, -6]

Вывод списка на экран

println(L); // [21, 5, -6]

println(M); // [-9, 213]

Все остальное в виде программы на языке Паскаль

var L, M:list<integer>;//объявление списка

    x:integer;

begin

  L:=new List<integer>;//создание нового пустого списка

  M:=Lst(-9,213);//создание и заполнение нового списка значениями

  L.println; //вывод значений списка на экран, пусто

  println(M);//вывод списка на экран [-9,213] 

  L.Add(21);//добавление значения в конец списка

  M+=21;//добавление значения в конец списка

  L+=5;

  L+=-6;

  println(L);// [21,5,-6] 

  println(M);// [-9,213,21] 

  println(M.Count);//длина списка M, 3

  println(M.Item[0]);//обращение к элементу с индексом 0, -9

  println(L[L.Count-1]);//обращение к последнему элементу, -6

  L.Insert(1,100);//вставка на 1 позицию значения 100, [21,100,5,-6] 

  println(L);

  L.RemoveAt(2);//удаление элемента с индексом 2, [21,100,-6] 

  println(L);

  L:=L+M;//сложение списков, [21,100,-6,-9,213,21] 

  println(L);

  L.RemoveAll(x->x<0);//удаление элементов, значения которых меньше 0, [21,100,213,21] 

  println(L);

  L.Sort;//сортировка списка по возрастанию [21,21,100,213] 

  println(L);

  L.IndexOf(21).Println;//индекс первого по счету элемента, равного 21, 0

  L.LastIndexOf(21).println;//индекс последнего по счету элемента, равного 21, 1

  L.Reverse; //реверс списка 213 100 21 21 

  for x:=0 to L.Count-1 do //проход по списку

    print(L[x]);

  println;

  L.Max.Println; //максимальное значение списка, 213

 L.AddRange(arr(19,34,67));//функция arr возвращает массив, заполненный значениями; метод addRange добавляет массив в список, 213 100 21 21 19 34 67

  L.Println;

  L.RemoveRange(1,3);//удаление элементов списка с 1 по 3 индексы, 213 19 34 67

  L.println;

  L.Clear; //очистка списка

end.

Задача. Список S из N элементов заполнить случайными целыми числами из промежутка [1, 20]. Все числа списка S, кратные 3, поместить в новый список M, а из списка S эти числа удалить.

Для заполнения списка случайными числами воспользуемся функцией ArrRandom()

ArrRandom(N, A, B) возвращает N случайных целых чисел из промежутка [A, B]

В цикле пройдем по списку S, и если элемент списка кратен 3, добавим это значение в список M. После обработки списка S удалим из него все значения, кратные 3.

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

var S, M:list<integer>;

    N,k:integer;

begin

  write('Введите количество элементов списка N=');

  readln(N);

  S:=Lst(ArrRandom(N,1,20));

  print('Исходный список S:');

  println(S);

  M:=New List<integer>;

  for k:=0 to S.count-1 do

  begin

    if S[k] mod 3 = 0 then M+=S[k];

  end;

  print('Новый список M:');

  println(M);

  S.RemoveAll(k->k mod 3=0);

  print('Список S без элементов, кратных 3:');

  println(S);

end.

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

Язык Паскаль. Наибольший общий делитель двух натуральных чисел НОД(m,n)

Приведем 3 программы поиска наибольшего общего делителя двух натуральных чисел, основанных на:

• алгоритме Евклида
• перебора возможных делителей числа
• разложения чисел на простые множители

Что такое наибольший общий делитель двух натуральных чисел m и n, или НОД(m, n)

НОД двух натуральных чисел - это такое наибольшее натуральное число, которое одновременно делит без остатка оба этих числа.

Алгоритм Евклида

Евклид - древнегреческий математик, геометр, автор первого из дошедших до нас теоретических трактатов по математике.

Алгоритм Евклида - один из наиболее ранних численных алгоритмов в истории. Евклид впервые дал описание этого алгоритма в книгах «Начала». Изначально этот алгоритм назывался «взаимным вычитанием», так как его принцип заключался в последовательном вычитании из большего числа меньшего, пока в результате не получится ноль.

Сформулируем алгоритм

Пусть даны два натуральных числа m и n. Пока числа m и n не равны (или их разница не равна 0), большее число заменить их разницей. В качестве ответа взять любое из чисел.

Пример:

Пусть m = 12, n = 18

12<>18, n = 18 - 12 = 6

12<>6, m = 12 - 6 = 6

6<>6, НОД(12, 18) = 6

Программа на языке программирования Паскаль (алгоритм Евклида)

var m, n:integer;

begin

  writeln('Введите два натуральных числа m и n:');  

  readln(m,n);

  while m<>n do

  begin

    if m>n then m:=m-n

           else n:=n-m;

  end;

  writeln('НОД(m,n): ',m);

end.

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

Перебор возможных делителей числа

Будем использовать алгоритм, разобранный ранее в этом блоге.

Запустим цикл for с счетчиком k от 1 до n, будем проверять условие: если число n делится на значение счетчика k без остатка (n mod k = 0), то значение счетчика k - это делитель числа n, значение k можно вывести на экран или сохранить в отдельной переменной.

Поскольку нам нужен наибольший общий делитель чисел m и n, поэтому запустим цикл до минимального из чисел m и n (другое будет лишним), и будем проверять условие: если число m делится на значение счетчика цикла k без остатка и число n делится на значение счетчика цикла k без остатка одновременно (воспользуемся операцией and), это и будет их общий делитель.

Программа на языке программирования Паскаль (перебор возможных делителей числа)

var m, n, k, p:integer;

begin

  writeln('Введите два натуральных числа m и n:');

  readln(m,n);

  for k:=1 to min(m,n) do 

  begin

    if (m mod k = 0) and (n mod k=0) then p:=k;

  end;

  writeln('НОД(m,n): ',p);

end.

Функция min будет работать в PascalABC.NET, в случае использования другой среды, нужно до цикла определить наибольшее число из m и n.

Разложение чисел на простые множители

Ранее мы разбирали алгоритм разложения натурального числа на простые множители. 

Как связаны простые множители числа и НОД. Приведем пример.

Пусть m = 18,  n = 12

Выполним разложение на простые множители.

Множители числа m: 2 3 3

Множители числа n: 2 2 3

Выделим их общие простые множители - это числа 2 и 3. В качестве наибольшего общего делителя нужно взять из произведение: 2 * 3 = 6. НОД(12, 18) = 6.

Пусть m = 36,  n = 48

Множители числа m: 2 2 3 3

Множители числа n: 2 2 2 2 3

Общие простые множители - это числа 2 2 3. Произведение этих множителей равно 12. НОД(36, 48) = 12.

Для нахождения НОД двух чисел нужно выполнить их разложение на простые множители и в качестве ответа взять произведение их общих множителей.

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

Для хранения множителей числа воспользуемся списком (PascalABC.NET), в него легко добавлять значение командой add.

Описание списка с именем nod в блоке var

var nod:List<integer>;

Создание нового пустого списка в теле программы

nod:=new List<integer>;

Добавление значения в конец списка

nod.add(значение);

Создадим два списка (s1 и s2) для хранения множителей числа m и n соответственно. С помощью конструкции вложенных циклов переберем все элементы списков и сравним на равенство, если множители равны, сохраним их в списке nod, а значения элементов списков сделаем равными -1 и -2 соответственно (чтобы далее их повторное сравнение на равенство было ложным) . В качестве ответа возьмем произведение элементов списка nod командой nod.Product.

Программа на языке программирования Паскаль (разложение чисел на простые множители)

var

  m, n, k1, k2: integer;      

  s1, s2, nod: List<integer>;

begin

  writeln('Введите два натуральных числа m и n:');   

  readln(m, n);  

  s1 := new List<integer>; 

  s2 := new List<integer>; 

  nod := new List<integer>;

  k1 := 2; k2 := 2;  

  while (m > 1) or (n > 1) do   

  begin

    while m mod k1 = 0 do     

    begin

      m := m div k1;      

      s1.Add(k1); //добавить значение в список можно и так: s1+=k1;

    end;     

    k1 += 1;     

    while n mod k2 = 0 do    

    begin

      n := n div k2;       

      s2.Add(k2);     

    end;     

    k2 += 1;   

  end;   

  //writeln(s1, s2); 

  for k1:=0 to s1.Count-1 do //элементы списка нумеруются с 0, длина списка s1.count

    for k2:=0 to s2.Count-1 do

      if s1[k1]=s2[k2] then //s1[k1] - обращение к элементу списка по его номеру

        begin 

        nod.Add(s1[k1]);

        s1[k1]:=-1;

        s2[k2]:=-2;

        end;

  //println(s1,s2,nod);

  println('НОД(m,n): ',nod.Product);

end.

Это программа состоит из самого большого количества строк. Насколько она эффективна?

Задача на применение НОД

Даны числа: a = 2³ • 3¹⁰ • 5 • 7² , b = 2⁵ • 3 • 11. Чему равен  НОД (a,b)?

Язык Паскаль. Найти наибольшую длину возрастающей подпоследовательности

 Задача. С клавиатуры вводится набор N целых чисел. Найти наибольшую длину возрастающей подпоследовательности.

Пример

N = 10

10 11 20 3 9 27 100 10 5 4

Наибольшая длина: 4

В этом ряду возрастающих подпоследовательностей две: числа 10 11 20 и 3 9 27 100. Наибольшая длина - 4, четыре числа в подпоследовательности 3 9 27 100.

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

Введем N - количество чисел в наборе.

Введем с клавиатуры первое число a и за длину возрастающей подпоследовательности возьмем k = 1. За искомую максимальную длину возьмем m = 1.

Далее в цикле для t от 2 до N:

1. введем число b
2. выполним проверку b>a, если условие истинно, то значение k увеличим на 1 (считаем длину возрастающей подпоследовательности), иначе значением k возьмем за 1 (возрастающая подпоследовательность оборвалась)
3. найдем максимальную длину m
4. значение переменной a перезапишем на значение b

Таблица выполнения алгоритма

a	b	b > a	k	k > m	m
10			1		1
11	11	11 > 10 да	2	2 > 1 да	2
20	20	20 > 11 да	3	3 > 2 да	3
3	3	3 > 20 нет	1	1 > 3 нет
9	9	9 > 3 да	2	2 > 3 нет
27	27	27 > 9 да	3	3 > 3 нет
100	100	100 > 27 да	4	4 > 3 да	4
10	10	10 > 100 нет	1	1 > 4 нет
5	5	5 > 10 нет	1	1 > 4 нет
4	4	4 > 5 нет	1	1 > 4 нет
					Вывод 4

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

var a,b,k,m,t,N:integer;

begin

  readln(N);

  read(a); k:=1; m:=1;

  for t:=2 to N do

  begin

    read(b);

    if b>a then k+=1 else k:=1;

    m:=max(k,m); //функция нахождения максимума из двух значений

    a:=b;

  end;

  writeln('наибольшая длина возрастающей подпоследовательноси: ',m);

end.

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