Алгоритм как найти число 1 информатика - Сайт, где вы сможете решить свои вопросы

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

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

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

  var  
  n,i: longint;
  flag: boolean;
  begin  writeln('vvod n');
  read(n);  
  if n = 2 then flag := true
         else if not odd (n) then flag :=  false           
         else  begin                 
              flag := true;                 
              for i := 2 to n-1 do                 
              if n mod i = 0 then flag  := false                 
              end;
  if flag then writeln('Yes') else writeln('No'); 
  readln;
  end.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, – простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

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

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

 var
 m,n,i,k: longint;
 flag: boolean;
 begin
 writeln('vvod m>3');
 readln(m);
 write('      2      3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag :=  false;
                    break
                end;
   if flag then begin
                write(n:7);
                k := k+1;
                if k mod 10 = 0 then writeln
                end;
 n := n+2
 end;
 writeln;
 writeln('kol-vo = ',k);
 readln
 end.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

 var
 m,n,n1,n2,i,k: longint;
 flag: boolean;
 begin
 m :=1000;
 n1 := 2; n2 := 3; n := n2+2; k:=0;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin  n1 := n2; n2 := n;
                 if (n2 -n1) = 2 then  begin
                               k := k+1;
                               write(n1:4,n2:4,' ');
                               if k mod 5 = 0 then writeln
                               end
             end;
 n := n+2
 end;
 writeln;
 writeln('kol -vo par =',k);
 readln
 end.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

 var
 m,n,i,k: longint;
 flag: boolean;
 f:text;
 begin
 assign(f,'output.txt'); rewrite(f);
 writeln('vvod m > 3');
 readln(m);
 write(f,'  2  3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin
            write(f,n:7);
            k := k+1;
            if k mod 10 = 0 then  writeln(f)
            end;
 n := n+2
 end;
 writeln(f);
 writeln(f,'kol-vo = ',k);
 close(f)
 end.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

Вводим правую границу диапазона – m;
Записываем двойку и тройку в файл;
Пока очередное нечетное число i <= m :
1. проверять очередное нечетное число на наличие делителей из данного файла;
2. если есть делители, рассматривать очередное нечетное число, если нет – производить дозапись в “хвост” файла.
По окончании просмотра диапазона ( i > m ), вывести в файл количество простых чисел.

{Простые  до m}
   label n1;
   var 
   m,i,j,k,q : longint;
   f : text;
   begin
      assign(f,'output.txt');
      rewrite(f);
      Writeln('vvod  m');  {m – правая граница диапазона чисел}
      readln(m);
      k := 0;             {k – счетчик количества  простых чисел}
      if  m >= 2 then begin
                   write(f,'  ':6,'2',' ':6);
                   k:=k+1
                 end;
      if m >= 3 then begin
                  write(f,'3');
                  k:=k+1
                end;
      close(f);
      i:=5;                {В i находится текущее  нечетное число}
      while  i <= m do
       begin  
        reset(f);
         {проверка делимости i на простые числа  q из файла}
         for j:=1  to k do
           begin
            read(f,q);
            if (q*q>i) then break;
            if (i mod q=0) then goto n1
           end;
        close(f); 
             {дозапись в ‘хвост’ файла простых  чисел}
        append(f);
            k:=k+1;
            Write (f,i:7);
            if k mod 10 = 0 then  writeln(f);
            close(f);
        {следующее нечетное число I  <= m}
        n1: i:=i+2
        end;
       {дозапись в конец файла количества простых  чисел} 
        append(f);
   writeln(f);
   writeln(f,'     kol -vo = ',k);
   close(f)
   end.

Эратосфеново решето

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод.

Пусть написаны числа от 2 до n:

2 3 4 5 6 7 8 9 10 11 12 . . .

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

2 3 4 5 6 7 8 9 10 11 12 . . .

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

2 3 4 5 6 7 8 9 10 11 12 . . .

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
Затем циклически повторим действия:
1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

{Выделение всех простых чисел из первых n целых}
 const
 n = 255; {Количество элементов исходного множества}
 type
 SetOfNumber = set of 1..n;
 var
 n1, next, i: word;                    {Вспомогательные  переменные}
 BeginSet,                             {Исходное  множество}
 PrimerSet: SetOfNumber;               {Множество простых чисел}
 begin
   BeginSet := [2..n];                 {Создаем исходное множество}
   PrimerSet  :=[2];                 {Поместить в PrimerSet  первое число из BeginSet}
   next := 2;                          {Первое простое  число}
    while BeginSet  <> [] do            {Начало  основного цикла}
          begin
           n1 := next;   {n1 –число, кратное  очередному простому (next)}
            {Цикл удаления из исходного  множества непростых чисел:} 
           while n1  <= n do
  begin
  Exclude(BeginSet,n1);
  n1 := n1+next         {Следующее кратное}
  end;        {Конец цикла  удаления}
  Include(PrimerSet,next);
  {Получение следующего простого, которое  есть первое невычеркнутое
  из исходного множества}

  repeat
  Inc(next);
  until  (next in BeginSet) or (next > n)
  end;  {Конец основного цикла}
  {Вывод результатов:}

  for  i := 1 to n do
  if i in PrimerSet then write(i:5);
  readln
  end.

Литература:

Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. – 255 с.
В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. – 616 с.

Источник

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

Цифра 0

Алгоритм:

использовать Чертежник
алг цифра_0
нач
  опустить перо
  сместиться на вектор(0,2)
  сместиться на вектор(1,0)
  сместиться на вектор(0,-2)
  сместиться на вектор(-1,0)
  поднять перо
  сместиться на вектор (2,0)
кон

Цифра 1

Алгоритм:

использовать Чертежник
алг цифра_1
нач
  сместиться на вектор (0,1)
  опустить перо
  сместиться на вектор (1,1) 
  сместиться на вектор (0,-2) 
  поднять перо
  сместиться на вектор (1,0)
кон

Рекомендуем: как настроить координатную плоскость исполнителя

Цифра 2

Алгоритм:

использовать Чертежник
алг цифра_2
нач
  сместиться на вектор (0,2)
  опустить перо
  сместиться на вектор (1,0) 
  сместиться на вектор (0,-1) 
  сместиться на вектор (-1,-1)
  сместиться на вектор (1,0)
  поднять перо
  сместиться на вектор (1,0)
кон

Цифра 3

Алгоритм:

использовать Чертежник
алг цифра_3
нач
  опустить перо
  сместиться на вектор (1,1) 
  сместиться на вектор (-1,0) 
  сместиться на вектор (1,1)
  сместиться на вектор (-1,0)
  поднять перо
  сместиться на вектор (2,-2)
кон

Цифра 4

Алгоритм:

использовать Чертежник
алг цифра_4
нач
  сместиться на вектор (0,2)
  опустить перо
  сместиться на вектор (0,-1) 
  сместиться на вектор (1,0) 
  сместиться на вектор (0,1)
  сместиться на вектор (0,-2)
  поднять перо
  сместиться на вектор (1,0)
кон

Цифра 5

Алгоритм:

использовать Чертежник
алг цифра_5
нач
  опустить перо
  сместиться на вектор (1,0) 
  сместиться на вектор (0,1) 
  сместиться на вектор (-1,0)
  сместиться на вектор (0,1)
  сместиться на вектор (1,0)
  поднять перо
  сместиться на вектор (1,-2)
кон

Рекомендуем: все уроки для исполнителя Чертежник в среде Кумир

Цифра 6

Алгоритм:

алг цифра_6
нач
  сместиться на вектор(1,2)
  опустить перо
  сместиться на вектор(-1,-1)
  сместиться на вектор(0,-1)
  сместиться на вектор(1,0)
  сместиться на вектор(0,1)
  сместиться на вектор(-1,0)
  поднять перо
  сместиться на вектор (2,-1)
кон

Цифра 7

Алгоритм:

использовать Чертежник
алг цифра_7
нач
  опустить перо
  сместиться на вектор (0,1) 
  сместиться на вектор (1,1) 
  сместиться на вектор (-1,0)
  поднять перо
  сместиться на вектор (2,-2)
кон

Цифра 8

Алгоритм:

использовать Чертежник
алг цифра_8
нач
  опустить перо
  сместиться на вектор(0,2)
  сместиться на вектор(1,0)
  сместиться на вектор(0,-2)
  сместиться на вектор(-1,0)
  сместиться на вектор(0,1)
  сместиться на вектор(1,0)
  поднять перо
  сместиться на вектор (1,-1)
кон

Цифра 9

Алгоритм:

использовать Чертежник
алг цифра_9
нач
  опустить перо
  сместиться на вектор(1,1)
  сместиться на вектор(-1,0)
  сместиться на вектор(0,1)
  сместиться на вектор(1,0)
  сместиться на вектор(0,-1)
  поднять перо
  сместиться на вектор (1,-1)
кон

( 10 оценок, среднее 4.2 из 5 )

Источник

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

Версия для печати и копирования в MS Word

У исполнителя Альфа две команды, которым присвоены номера:

1. прибавь 1;

2. умножь на b

(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Альфа увеличивает число на экране на 1, а выполняя вторую, умножает это число на b. Программа для исполнителя Альфа  — это последовательность номеров команд. Известно, что программа 11211 переводит число 6 в число 82. Определите значение b.

У исполнителя Альфа две команды, которым присвоены номера:

1. прибавь 1;

2. умножь на b

(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Альфа увеличивает число на экране на 1, а выполняя вторую, умножает это число на b. Программа для исполнителя Альфа  — это последовательность номеров команд. Известно, что программа 11211 переводит число 3 в число 62. Определите значение b.

У исполнителя Бета две команды, которым присвоены номера:

1. прибавь 2;

2. умножь на b

(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Бета увеличивает число на экране на 2, а выполняя вторую, умножает это число на b. Программа для исполнителя Бета  — это последовательность номеров команд. Известно, что программа 12111 переводит число 7 в число 51. Определите значение b.

У исполнителя Бета две команды, которым присвоены номера:

1. прибавь 2;

2. умножь на b

(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Бета увеличивает число на экране на 2, а выполняя вторую, умножает это число на b. Программа для исполнителя Бета  — это последовательность номеров команд. Известно, что программа 11121 переводит число 4 в число 72. Определите значение b.

У исполнителя Гамма две команды, которым присвоены номера:

1. прибавь 3;

2. умножь на b

(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Гамма увеличивает число на экране на 3, а выполняя вторую, умножает это число на b. Программа для исполнителя Гамма  — это последовательность номеров команд. Известно, что программа 11211 переводит число 1 в число 97. Определите значение b.

Пройти тестирование по этим заданиям

Источник

Сегодня изучим 5 задание из ОГЭ по информатике 2023. Это задание понятное и несложное.

Обычно в 5 задании из ОГЭ по информатике даются команды, которые может делать исполнитель, и зная начальное и конечное положение, нужно найти какой-нибудь параметр одной из команд.

Лучше один раз решить, чем сто раз услышать, приступим к первой тренировочной задаче.

Задача (Составляем программу)

У исполнителя Вычислитель две команды, которым присвоены номера:

приписать 1
разделить на 3

Первая из них приписывает к числу справа 1, вторая уменьшает его в три раза.

Составьте алгоритм получения из 5 числа 19, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 22121 – это алгоритм
разделить на 3
разделить на 3
приписать 1
разделить на 3
приписать 1,
который преобразует число 18 в 71.)

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

Решение:

Нам нужно получить из 5 число 19, используя только две вышеуказанные команды. Здесь нужно пробовать составить команды, опираясь на интуицию и здравый смысл. Важно знать, что решение точно есть! Следим за тем, чтобы длина алгоритма не превышала 5 команд.

5 → 51 (Команда 1)
51 : 3 = 17 (Команда 2)
17 → 171 (Команда 1)
171 : 3 = 57 (Команда 2)
57 : 3 = 27 (Команда 2)

Ответ: 12122

Задача (Составляем программу, закрепление)

У исполнителя Квадратор две команды, которым присвоены номера:

возведи в квадрат
вычти 3

Первая из них возводит число на экране во вторую степень, вторая вычитает из числа 3.

Исполнитель работает только с натуральными числами.

Составьте алгоритм получения из числа 14 числа 58, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 21221 – это алгоритм
вычти 3
возведи в квадрат
вычти 3
вычти 3
возведи в квадрат
который преобразует число 7 в 100.)

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

Решение:

Здесь, скорее всего, нужно добраться до 64. Потом два раза сделать -3, получится 58.

14 – 3 = 11 (Команда 2)
11 – 3 = 8 (Команда 2)
8² = 64 (Команда 1)
64 – 3 = 61 (Команда 2)
61 – 3 = 58 (Команда 2)

Ответ: 22122

Задача (Составляем программу, ещё раз)

У исполнителя Квадратор две команды, которым присвоены номера:

возведи в квадрат
прибавь 2

Первая из них возводит число на экране во вторую степень, вторая прибавляет к числу 2.

Составьте алгоритм получения из числа 1 числа 85, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 21221 – это алгоритм
прибавь 2
возведи в квадрат
прибавь 2
прибавь 2
возведи в квадрат
который преобразует число 1 в 169.)

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

Решение:

Здесь, скорее всего, нужно добраться до 81. Потом два раза прибавить 2, получится 85.

1 + 2 = 3 (Команда 2)
3² = 9 (Команда 1)
9² = 81 (Команда 1)
81 + 2 = 83 (Команда 2)
83 + 2 = 85 (Команда 2)

Ответ: 21122

Задача (Стандартная)

У исполнителя Гамма две команды, которым присвоены номера:

1. прибавь 3;
2. умножь на b
(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Гамма увеличивает число на экране на 3, а выполняя вторую, умножает это число на b. Программа для исполнителя Гамма  — это последовательность номеров команд. Известно, что программа 11121 переводит число 3 в число 75. Определите значение b.

Решение:

В начале у нас есть число 3. С ним начинаем делать команды из программы (11121).

Сперва нужно выполнить три раза команду 1.

3 + 3 = 6
6 + 3 = 9
9 + 3 = 12

В 5 задании из ОГЭ по информатике важно знать: мы делаем очередную команду к предыдущему результату.

Следуя программе, дальше нужно сделать команду под номером 2. Получается 12 * b. Затем выполним последнюю команду под номером 1. В результате будет выражение 12 * b + 3. Это выражение в итоге должно равняться 75.

12 * b + 3 = 75

Теперь осталось решить уравнение и найти b.

12 * b = 72
b = 6

В ответе напишем 6.

Ответ: 6

Задача (С делением)

У исполнителя Омега две команды, которым присвоены номера:

1. прибавь 3;
2. раздели на b
(b  — неизвестное натуральное число; b ≥ 2).

Выполняя первую из них, Омега увеличивает число на экране на 3, а выполняя вторую, делит это число на b. Программа для исполнителя Омега  — это последовательность номеров команд. Известно, что программа 11121 переводит число 30 в число 6. Определите значение b.

Решение:

К первоначальному числу 30 применим три раза команду под номером 1.

30 + 3 = 33
33 + 3 = 36
36 + 3 = 39

Затем применим вторую команду. Получается 39 / b. Последней командой будет снова команда под номером один 39 / b + 3. Результат должен быть равен 6.

39 / b + 3 = 6

Решим это уравнение.

39 / b = 3
b = 39 / 3 = 13

Получаем b = 13.

Ответ: 13

Задача (Квадратное уравнение)

У исполнителя Алго две команды, которым присвоены номера:

1. прибавить 1
2. умножить на b
(b — неизвестное натуральное число; b ≥ 2)

Выполняя первую из них, Алго — это последовательность команд.

Известно, что программа 12121 переводит число 4 в число 49.

Определите значение b.

Решение:

Сделаем команды из программы для первоначального числа 4.

4 + 1 = 5
5b
5b+1
(5b+1)*b = 5b² + b
5b² + b + 1

Конечный результат должен равняться 49.

5b² + b + 1 = 49

Получили квадратное уравнение!

5b² + b – 48 = 0
D = 1 + 4 * 5 * 48 = 961

Иногда без калькулятора бывает трудно определить, какое число нужно возвести в квадрат, чтобы получить дискриминант. В этом случае нужно посмотреть на последнюю цифру. У нас это 1. Какое число при возведении в квадрат получает на конце единицу ? Это 1 и 9. Значит, на эти цифры может оканчиваться искомое число. Чтобы подобраться к числу 900, можно попробовать возвести 31 в квадрат. Проверив столбиком число 31, подтверждаем, что 31 это и есть корень из дискриминанта.

b=(-1 + 31) / (2 * 5) = 3

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

Ответ: 3

Задача(Двухэтажная дробь)

У исполнителя Омега две команды, которым присвоены номера:

1. вычти b
2. раздели на 3
(b  — неизвестное натуральное число).

Выполняя первую из них, Омега уменьшает число на экране на b, а выполняя вторую, делит это число на 3.

Программа для исполнителя Омега — это последовательность номеров команд.

Известно, что программа 211212 переводит число 42 в число 1.

Определите значение b.

Решение:

Выполним команду под номером 2 с первоначальным числом 42.

Далее нужно сделать два раза команду под номером 1.

Далее идёт команда под номером 2.

Ещё раз команду 1.

Выполним последний раз команду под номером 2.

Это выражение после выполнения программы должно равняться 1. Получаем уравнение, которое нужно решить.

Ответ: 1

Задача (Возведение в квадрат)

У исполнителя Омега две команды, которым присвоены номера:

1. прибавь b
2. возведи в квадрат
(b — неизвестное натуральное число).

Выполняя первую из них, Омега увеличивает число на экране на b, а выполняя вторую, заменяет число на экране на это же число, возведённое в квадрат.

Программа для исполнителя Омега — это последовательность номеров команд.

Известно, что программа 11112 переводит число 2 в число 100.

Определить значение b.

Решение:

Начнём делать с первоначальном числом 2 все команды из программы.

2 + b
2 + b + b = 2 + 2b
2 + 2b + b = 2 + 3b
2 + 3b + b = 2 + 4b

Мы сделали первые четыре команды из программы. Получили 2 + 4b. Теперь применим последнюю команду возведение в квадрат. В итоге получаем (2 + 4b)². Это выражение должно равняться числу 100. Получается уравнение.

(2 + 4b)² = 100

Здесь можно применить формулу квадрата суммы, тогда получится квадратное уравнение, но мы воспользуемся формулой разностью квадратов!

(2 + 4b)² – 100 = 0
(2 + 4b – 10)*(2 + 4b + 10) = 0
2 + 4b – 10 = 0 или 2 + 4b + 10 = 0
4b – 8 = 0 или 4b + 12 = 0

В правом уравнении получается отрицательное b. Оно нам не подходит, т.к. b — натуральное число. Левое уравнение даёт результат.

4b – 8 = 0
4b = 8
b = 8 / 4 = 2

В ответе получается 2.

Ответ: 2

Задача(Припиши справа b)

У исполнителя Сигмы две команды, которым присвоены номера:

1. вычти 1
2. припиши справа b
(b — неизвестная цифра)

Выполняя первую из них, Сигма уменьшает число на экране на 1, а выполняя вторую, приписывает к этому числу справа b.

Алгоритм для исполнителя Сигма — это последовательность номеров команд.

Известно, что алгоритм 12121 переводит число 3 в число 244.

Определите число b.

Решение:

Действие приписать справа b — это значит умножить число на 10 и прибавить b. Пример: пусть b=3, применим эту команду к числу 4. Тогда 4*10 + 3 = 43.

Выполним программу с первоначальным числом 3.

3 – 1 = 2
2*10 + b = 20 + b
20 + b – 1 = 19 + b
(19 + b)*10 + b = 190 + 10*b + b = 190 + 11*b
190 + 11*b – 1 = 189 + 11*b

Конечный результат равен 244.

189 + 11*b = 244
11*b = 55
b = 5

В ответе получилось 5.

Ответ: 5

Источник

На этой странице вы узнаете

Как быстро работает программа?
Есть ли смысл перебирать делители после корня?
Что количество делителей может сказать о самом числе?

Гадание на кофейной гуще или на картах Таро? Может, на ромашке? Хотя лучше не доверять свои отношения цветку. Наша судьба — только в наших руках. А судьба чисел предопределена заранее. Сегодня мы будем предсказывать их жизнь и судьбу по делителям. Но главная проблема — найти эти делители.

Постановка проблемы. Переборное решение

Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 50 арбузов? А что подумаете, если ваш учитель математики задаст найти число, у которого 50 делителей?

Поиск делителей в математике не самый сложный процесс. Есть разные способы: разложение на простые множители, обычный перебор и так далее. Сложность задания будет зависеть от самого числа. Довольно быстро получится найти делители числа 24 — число небольшое, красивое, удобное. Нахождение делителей числа 1234567 займет гораздо больше времени.

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

Идея в следующем:

Создадим список, в который мы сохраним все делители числа.
С помощью цикла for переберем все числа из диапазона от 1 до самого числа.
Если в переборе мы нашли такое число, которое является делителем исходного — остаток от деления будет равен 0 — сохраним это число в список.

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

number = 1234567
dels = []

for i in range(1, number + 1):
	if number % i == 0:
		dels.append(i)

print(dels)
_____________________________________________________________________
Вывод: [1, 127, 9721, 1234567]

У этого метода есть очень большая проблема — время его работы.

Программа выполняет команды очень быстро, но не бесконечно быстро.

Как быстро работает программа?

Время работы программы можно измерить. Например, Sublime Text 3 занимается этим автоматически. И он помог посчитать, что программа выше выполнилась за 0.2 секунды. Давайте постепенно повышать ставки и смотреть, сколько времени понадобится этой же программе для поиска делителей других чисел:
— число 1234567 — 0.2 секунды;
— число 12345670 — 0.9 секунды;
— число 123456700 — 8.0 секунд;
— число 1234567000 — 115.7 секунд.

С числом 1234567 программа сделала 1234567 шагов цикла for, и справилась неимоверно быстро. Но чем больше ей придется выполнять команд, тем дольше придется работать.

Замеры времени зависят от многих факторов, например, мощности компьютера. Но мы можем повысить эффективность работы программы.

Ускоренный перебор делителей

Идея ускоренного перебора делителей заключается в том, что, найдя один делитель, мы сразу можем подобрать второй — его пару.

Возьмем число 24. Найдя его делитель 2, мы сразу можем сказать, что у 24 есть еще один делитель — 12, потому что 12 = 24 / 2. Интересная мысль? Давайте ее развивать.

Найдем по такой логике все делители числа 16.

Самый простой делитель числа — 1. И по этой логике сразу найдем второй делитель — само число 16, так как 16 / 1 = 16.

Проверим число 2. Это делитель, так что сразу найдем его пару: 16 / 2 = 8.

Проверяем число 3 — это не делитель, его просто пропускаем.

При проверке числа 4 мы столкнемся с интересной ситуацией. Его парой будет 16 / 4 = 4 — то же самое число, а мы ищем различные пары. Значит, у корня числа пары не будет: найдя корень, мы найдем только один делитель.

Если мы продолжим перебор, числа 5, 6 и 7 — не будут делителями. А за ними — 8, делитель, который мы уже нашли.

Есть ли смысл перебирать делители после корня?

Нет. Найдя “маленький” делитель, при ускоренном переборе мы можем найти его пару, которая будет “большим” делителем. Перебирая делители, рано или поздно мы дойдем до корня числа, у которого нет пары. Перебирая числа после корня, мы будем находить только “большие” делители, которые уже нашли в паре с “маленькими”.

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

Логика программы будет такой:

Перебираем числа от 1 до корня исходного числа.
Если мы нашли корень числа, добавляем в список делителей только его.
Если мы нашли не корень, а обычный делитель — добавляем в список сразу пару делителей.

Пример реализации ускоренного перебора делителей для числа 1234567000:

number = 1234567000
dels = []

for i in range(1, int(number ** 0.5) + 1):
	if i * i == number:
		dels.append(i)
	elif number % i == 0:
		dels.append(i)
		dels.append(number // i)

print(len(dels))
_____________________________________________________________________
Вывод: 64

Эта программа нашла все делители числа и выдала их количество — 64. А на ее работу ушло меньше секунды.

Но и это не панацея. Что, если нам придется проверить делители сразу нескольких чисел? Например, мы хотим найти все числа, у которых ровно 7 делителей, в диапазоне от 1 до 10000.

Программу надо немного модифицировать:

заведем переменную-счетчик, которая будет считать подходящие числа;
number сделаем перебираемой переменной по нужному диапазону с помощью цикла for;
ускоренный перебор будет внутри перебора number;
в конце каждого шага цикла проверяем — если делителей у числа ровно 7, то увеличиваем наш счетчик на 1.

Теперь программа будет выглядеть следующим образом:

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)

	if len(dels) == 7:
		count += 1

print(count)
_____________________________________________________________________
Вывод: 2

Эта программа работала всего 0.2 секунды. Звучит неплохо, но давайте снова поднимать ставки:

диапазон 1 — 10000 — 0.2 секунды;
диапазон 1 — 100000 — 2.6 секунды;
диапазон 1 — 1000000 — 80.2 секунды.

Время снова увеличивается очень быстро. Что можно с этим сделать?

Еще более ускоренный перебор делителей

Не считаем, что не нужно

Обратите внимание — программа выше нашла среди чисел 1–10000 всего 2 числа, имеющих ровно 7 делителей. А сколько же у остальных? Может быть и больше, может быть и меньше. Например, у числа 9864 делителей аж 24 штуки. Стоило ли тратить время на поиск их всех, если количество делителей больше 7?

Конечно, нет. Как только мы нашли 8 штук, мы уже можем понять, что анализировать число далее нам неинтересно. Значит, нужно остановить работу цикла.

Команда break полностью останавливает работу цикла.

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

count = 0
for number in range(1, 10000):
	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

При этом завершится именно цикл перебора делителей i, так как break находится именно в нем, а цикл перебора number продолжит свою работу.

Давайте произведем замеры еще раз:

диапазон 1-10000 — 0.2 секунды;
диапазон 1-100000 — 2.1 секунды;
диапазон 1-1000000 — 53.5 секунды.

В последнем случае мы сэкономили около трети от времени работы программы. Но и это не предел.

Не считаем, что не нужно 2.0

Вернемся на несколько абзацев выше, когда мы искали делители числа 16. Мы нашли 5 делителей — 2 пары и 1 корень, который не даст пару. Это справедливо для любого числа: целый корень не будет давать пару ни с каким другим числом, а все остальные делители — будут.

Что количество делителей может сказать о числе?

Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем.
Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару.

Нам нужны числа, у которых ровно 7 делителей. Следовательно, нам нужны числа, у которых есть целый корень. Это можно проверить, вычислив точный корень числа и его округленное значение. Если они совпадут, значит, округлять корень было некуда и он целый.

Но как пропускать числа, которые нам не нужны?

Команда continue останавливает работу текущего шага цикла и сразу переходит к следующему.

Если мы найдем число number, у которого нет целого корня, мы можем применить команду continue: данный шаг цикла перебора number завершается, и мы сразу перейдем к следующему.

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

count = 0
for number in range(1, 10000):
	if number ** 0.5 != int(number ** 0.5):
		continue

	dels = []

	for i in range(1, int(number ** 0.5) + 1):
		if i * i == number:
			dels.append(i)
		elif number % i == 0:
			dels.append(i)
			dels.append(number // i)
		if len(dels) > 7:
			break

	if len(dels) == 7:
		count += 1

print(count)

Снова посмотрим на время работы программы при разных диапазонах:

диапазон 1-100000 — 0.1 секунды;
диапазон 1-1000000 — 0.5 секунды;
диапазон 1-10000000 — 4.5 секунды;
диапазон 1-100000000 — 44.4 секунды.

А делители — это вообще для чего? А таблицы со временем — это точно важно? Может, подождать проще, чем учить все это?

Нахождению делителей чисел посвящена задача 25 ЕГЭ, и без этих теоретических знаний решить ее крайне сложно. Что же касается времени работы, то за ним приходится следить внимательнейшим образом, ведь в задачах могут встречаться ситуации, когда надо найти делители для сотен миллионов чисел за раз!

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

Фактчек

Ускоренный перебор делителей подразумевает нахождение делителей попарно, при этом перебирать делители достаточно только до корня числа.
Команда break полностью останавливает работу цикла, а команда continue завершает работу лишь текущего шага цикла, перенося нас сразу на следующий.
Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем. Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару.

Проверь себя

Задание 1.
Для чего нужен ускоренный перебор делителей?

Обычный перебор слишком скучный
Для большей точности вычислений
Для ускорения работы программы

Задание 2.
Найдите количество делителей числа 2568568668.

Задание 3.
Найдите, сколько чисел из диапазона от 2000 до 1002000 имеют ровно 5 делителей.

Ни одного
1
10
8

Ответы: 1. — 3; 2. — 3; 3. — 4.

Источник

Задача 1. Определение простого числа.

Задача 2. Нахождение простых чисел в заданном интервале.

Задача 3. Поиск пар чисел близнецов.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

На этой странице вы узнаете

Постановка проблемы. Переборное решение

Ускоренный перебор делителей

Еще более ускоренный перебор делителей

Не считаем, что не нужно

Не считаем, что не нужно 2.0

Фактчек

Проверь себя

Вам также может понравиться

Как найти more tv на телевизоре

Тема выставки писатели детям как лучше организовать эту выставку составь список

Как составить сочинение про свою семью

Добавить комментарий Отменить ответ