Задания В1. Анализ и построение

алгоритмов для исполнителей

В задачах типа В1  встречается несколько видов Исполнителей :

Калькулятор

Кузнечик  Робот

Утроитель

Чертежник

Вычислитель

Квадратор Отличник и т.д.

Начнем с числа 26 и заменим команды на противоположные.

                                                                                                                                                                                         Ответ:  211211

Ответ: 12121

Решение:

x-    количество команд «Вперед на 5», х ≥0

y-    количество команд «Назад 3», y ≥0

Чтобы кузнечик попал из точки с координатой 0 в точку с координатой  21, должно выполняться условие 

0+5х - 3у =21 преобразуем к виду

5х = 21+ 3у  =>  (21+ 3у) должно быть кратным 5, а  у –минимальным => у=3

Решение: x- количество команд «Вперед 3», х ≥0, тогда количество команд «Назад 4» =   ? х-4

Всего Кузнечик сделал х+ х-4 =20 команд, откуда   х= 12?  

Посчитаем, в какую точку попадёт Кузнечик после выполнения указанных команд:

3*12 -4*(12-4) = 36 – 32 = 4

Следовательно,  из исходной точки можно попасть, выполнив команду

 «Вперед 4» 

                           Ответ: 4                                                Пояснение: 10+ 7х-4у=43

                         ^{Ответ: Назад 5}                                 Пояснение: х+х+12=50,  х=19,   

3*19-2*31= -5

                                 ^{Ответ: 5}                                                   Пояснение: 15+ 17х-6у=36

Можно же пойти другим путем . 

Команды «вперед-назад» или «вверх-вниз»  дают нулевой эффект => их можно вычеркивать, если они стоят рядом. Но т.к. стены отсутствуют =>  не важно где стоят парные команды => 

Ответ: 2

Ответ: 1

Если робот пойдёт назад тем же путём, каким пришёл в конечную клетку, то он точно не разрушится.

Группа команд 1324 круговая, =>  ее можно откинуть => 132

Чтобы Робот попал в ту же клетку, нужно заменить команды на противоположные

                                                                                             1 (вверх)                 2 (вниз)

                                                                                          3 (вправо)                  4(влево)

                                                                                                                                                                                                      Ответ: 241

2 (вниз)   1 (вверх)

Решение:                   

2324142  =>   242

2   ->  1

4    ->   3

                                                                                                                          2     ->  1

33233241 =>   3323

3    ->  4  

2                 ->  1 

3                 ->  4  

Y:  2+3+ 3*0 + 1   = 6

точка, в которую попадет Чертежник (8 ; 6)

Чертёжнику был дан для исполнения следующий алгоритм: Повтори 3 раз

Сместиться на (–3, –2) Сместиться на (2, 1) Сместиться на (3, 0) конец

Какую команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение? Ответ: (-6; 3)

Решение.

Х:   3*(-3+2+3) = 6

У:   3*(-2+1+0) = -3

Точка, в которую попадет Чертежник, имеет координаты (6; - 3).

Следовательно, чтобы вернуться обратно нужно совершить команду Сместиться на (-6;3)

Задания В7.

Кодирование чисел.

Системы счисления

 В системе с некоторым основанием десятичное число 18 записывается в виде 30. Укажите это основание.

Решение

1                0

Т.к. в записи чисел присутствует число 5 =>  x>5, y>5,  x, y – натуральные числа

При  х= 6 получим     

При  х = 8 получим    

y= 6

101₂  = 510

11012  = 1*23+5₁₀ =1310

 > 25

101

Если число в двоичной системе оканчивается на 1 => в десятичной оно должно быть нечетным и выражается след.формулой x = 2y+1

При след.делении должны получить 0 => y= 2z

При след.делении должны получить 1 => z= 2b+1   =>  x= 8b+5 => 

           Число в троичной системе :                      bb x =3y+b , 

           Число в десятичной системе : x               y= 3z +b                                           => x=9z+4b

z < 2,   b<3

Ответ :  4, 8, 9, 13,  17

Укажите через запятую в порядке возрастания все основания   систем счисления, в которых запись числа 31 оканчивается на 11     

Решение. n- основание системы, n>=2   

31_n = ***11 

31=n*x+1 x=n*y+1    n, квадрат которых больше 30 =>  Исключаем те остаются числа  2,3,4,5 у- целое неотрицательное, следовательно,  (30-n) должно быть кратным n²  .   

Ответ: 2,3,5,30

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 23 оканчивается на 2 

Ответ:3,7,21

23=n*x+2 n*x=21

n>=2      и     21 кратно 3  =>   n=3 , n=7, n=21

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 71 оканчивается на 13 

Ответ:4,68

71=n*x+3

x=n*y+1  =>                           =>                      =>  n=4, n=68    n>=4

Задания В9.  Поиск путей в графе

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д,Е, Ж, З, И, К. По каждой дороге можно двигаться  только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ? 

К –количество путей в пункт К,  Е- количество путей в пункт Е и т.д.

Рассматриваем ориентированный  граф с конца

К=Е+И+Ж+З =5+2+2+3 = 12

                                                                                                                                               Е=Б+Ж            =3+2 =5

                                                                                                                                               З=Ж+Г            =2+1 =3

Ж=В      =2 И=Д       =2

                                                                                                                                              Б=А+В    =3

В=А+Г =2 Д=А+Г =2

                                                                                                                                              Г=А        =1

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д,Е, Ж. По каждой дороге можно двигаться  только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж ? 

                                                                                                                                                             Ж=В+Е+Г                                                 =1+6+2=9

                                                                                                                                                              Е=Д+Г                                                =4+2=6

                                                                                                                                                              Д=Г+Б+А                                                 =2+1+1=4

Г=Б+В =2 В=Б    =1

                                                                                                                                                              Б=А            =1

Ответ:     9

Задания В13.  

Перебор вариантов, построение дерева

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

1.   прибавь 2,

2.   умножь на 3.

Первая из них увеличивает число на экране на 2, вторая – увеличивает  число в 3 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 3 команд? 

Ответ: 8 

У исполнителя Калькулятор две команды:  1. прибавь 3,

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая – уменьшает его на 2 (отрицательные числа допускаются).

Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд? 

Решение (2 способ)

1.    порядок команд в программе не имеет значения

2.    поэтому существует всего 6 возможных программ, состоящих ровно из 5 команд (с точностью до перестановки): 

11111

11112

11122

11222

12222

22222

Ответ: 6

У исполнителя Калькулятор две команды:  1. прибавь 4,

2. вычти 3.

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает  написанное на экране.  Программа для калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 0 с помощью программы, которая содержит ровно 17 команд. 

Операция вычитания соответствует сложению с отрицательным числом. Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения. Если n – количество  команд 1 (прибавь 4), то (17-n) – количество  команд 2 (вычти 3).

Тогда число = 0+4*n – 3*(17-n) = 4n-51+3n=7n-51

7n-51 >=0 7n>=51 n>=51/7 n- целое, значит n>=8  и n<=17 .

Всего различных чисел: 10

У исполнителя Множик две команды:  1.умножь на 8,

2. подели на 2.

Сколько различных чисел можно получить из числа 512 с помощью программы, которая содержит ровно 8 команд? 

11111111

11111112

11111122

11111222

11112222

11122222

11222222

12222222

22222222

Ответ: 8

У исполнителя Калькулятор две команды:  1. прибавь 2,

2. вычти 4.

Первая из них увеличивает число на экране на 4, вторая – уменьшает его на 3. Если в ходе вычислений появляется отрицательное число, он выходит из строя и стирает  написанное на экране.  Программа для калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 5 с помощью программы, которая содержит ровно 20 команд. 

Операция вычитания соответствует сложению с отрицательным числом. Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения. Если n – количество  команд 1 (прибавь 2), то (20-n) – количество  команд 2 (вычти 4).

Тогда число = 5+2*n – 4*(20-n) =5+2n-80+4n=6n-75

6n-75 >=0 6n>=75 n>=75/6 n- целое, значит n>=13  и n<=20 .

Всего различных чисел: 8

У исполнителя Множитель две команды: 

1. умножь на 5, 2. раздели на 3.

 Сколько различных чисел можно получить из числа 81 с помощью программы, которая содержит ровно 4 команды. 

Решение:

1111

1112

1122

1222

2222

Ответ: 5 чисел

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

1. прибавь 1, 2. умножь на 2.

 Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд. 

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

 Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команд.