Текст книги "Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс"

Задача №14. Позиционные системы счисления

Для решения этого типа задач нам нужно вспомнить, как происходит сложение и вычитание «в столбик». При сложении происходит поразрядное суммирование записанных друг под другом цифр, начиная с младших разрядов. В случае если полученная сумма двух цифр больше или равна основанию системы счисления, под суммируемыми цифрами записывается остаток от деления этой суммы на основание системы, а целая часть от деления этой суммы на основание системы прибавляется к сумме следующих разрядов. Например, 01+01=10, складывая 1+1=2, но т.к. остаток от деления 2 на 2 равен нулю, то запишем 0 и единицу перенесем в следующий левый разряд. И сложим 0+0=0, да еще один разряд от предыдущей операции, то получаем 0+1=1.

При вычитании происходит поразрядное вычитание записанных друг под другом цифр, начиная с младших разрядов. В случае если первая цифра меньше второй, мы «занимаем» у соседнего (большего) разряда единицу. Занимаемая единица в текущем разряде равна основанию системы счисления. В привычной десятичной системе – это 10, в двоичной – 2, в троичной – 3 и т.д., например, 100—010=10. Отнимаем сначала старший разряд, что выделен полужирным шрифтом 100—010, получается 0—0=0, далее средний разряд 100—010, получается 0—1=1 (занимаем двойку в следующем разряде и получаем 2—1=1), 000—010=0, в самом младшем разряде я поставил ноль, т.к. мы оттуда его забрали, поэтому 0—0=0.

Пример 14.1

Сколько единиц содержится в двоичной записи значения выражения: 4²⁰²⁰ +22⁰¹⁷ – 16?

Решение:

Представим все числа выражения как степени двойки:

4²⁰²⁰ +22⁰¹⁷ – 15= 2⁴⁰⁴⁰ +2²⁰¹⁷ – 2⁴.

В двоичной записи двойка в степени n выглядит как 1 и n нулей, т.е. 2⁴⁰⁴⁰ =100..00₂

(4040 нулей). Тогда, суммируя 2⁴⁰⁴⁰ и 2²⁰¹⁷, получим число, содержащее 2 единицы:

Теперь вычтем из получившегося числа 16₁₀=10000₂. По правилам вычитания при недостатке занимаем у следующего разряда. 2017—4=2013 (количество единиц).

Видим, что у результата 2013 +1 = 2014 единиц.

Давайте решим эту задачу cпособом программирования на языке Python.

 
k = 4 **2020 + 2 **2017 – 16
count = 0
while k > 0:
    s = k % 2 # находим остаток в двоичной системе
    k = k // 2 # откидываем последнюю цифру
    if s == 1: # подсчитываем число единиц
        count +=1
print(count)
Ответ: 2014.
 

Пример 14.2

Значение арифметического выражения 9⁸ +35 – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Решение:

Представим все числа выражения как степени тройки: 3¹⁶ +35 – 3².

В системе счисления с основанием три число 3ⁿ выглядит как 1 и n нулей. Тогда, суммируя 3¹⁶ и 3⁵, получим 17-разрядное число, содержащее 2 единицы (в первой и шестой справа позициях) и 15 нулей:

10000000000000000₃+000000000001000003= =10000000000100000₃.

Вычтем из полученного числа 3²=100₂

10000000000100000₃ – 100₃

По правилам вычитания при недостатке занимаем у следующего разряда:

10000000000100000₃ – 100₃=10000000000022200₃. Получилось 3 двойки.

Решим задачу cпособом программирования на языке Python.

 
k = 3 **16 + 3 **5 – 9
count = 0
while k > 0:
    s = k % 3 # находим остаток в троичной системе
    k = k // 3 # откидываем последнюю цифру
    if s == 2: # подсчитываем число двоек
        count +=1
print(count)
Ответ: 3.
 
 
Пример 14.3
 

Результат выражения 5¹⁵⁰ +41²⁰ – X записали в восьмеричной системе счисления. Укажите три младших разряда числа Х, записанного в восьмеричной системе счисления, если известно, что в результате получилось 7531.

Решение:

5¹⁵⁰ +41²⁰ – X = 75318

Х = 5¹⁵⁰ +88⁰ – 7531₈ =…

Запрограммируем данное выражение:

 
x = 5 ** 150 + 4* 128 – int ('7531', 8) # перевод в десятичную через int
while x > 0:
    print(x % 8 ) # выводим число поразрядно, первые три цифры в обратном порядке – это и есть младшие разряды.
    x //= 8
Ответ: 560.
 
 
Пример 14.4
 

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

Решение:

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

 
x = ((7**120 – 7**30)//10)*((7**77 – 7**33)//6)
s = 0
while x > 0:
    s += x % 7 # считаем сумму разрядов в семеричной системе
    x //= 7 # откидываем последнюю цифру числа
print(s)
Ответ: 632.
 

Задачи для самостоятельного решения

Задача 14.5

Значение выражения 729⁷ +31⁶ – 18 записали в системе счисления с основанием 9. Сколько раз в этой записи встречается цифра 0?

Задача 14.6

Значение арифметического выражения: 49⁷ +72¹ – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?

Глава 7. Алгебра логики

Задача №15. Законы алгебры логики

В этом задании для решения необходимо знать некоторые законы алгебры логики. Приведу все основные законы. Чаще всего на ЕГЭ используется самый нижний в таблице – закон Де Моргана.

Необходимо также знать правило раскрытия импликации A -> B= A + B. Плюсу соответствует логическая операция «Или, v». Также знак импликации -> в программировании соответствует знаку меньше либо равно, т.е. -> = <=.

Пример 15.1

Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула (A <50) / (¬ДЕЛ (x, A) → (ДЕЛ (x, 10) → ¬ДЕЛ (x, 12))) тождественно истинна, т. е. принимает значение 1 при любом натуральном x?

Сначала решим задачу cпособом программирования на языке Python.

Решение:

 
    for a in range (1, 400):
    flag = 0 # задание флага
    for x in range (1, 4000):
       f = (a <50) and ((x % a!=0) <= ((x % 10==0) <= (x % 12!=0)))
       if f==0:# если значение ложь, то меняем флаг
          flag = 1
          break
    if flag==0: #если флаг не поменялся, то выводим значение а
        print (a)
Ответ: 30.
 

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

A <50 и (Не (Дел (X,A)) → (Дел (X,10)) → (Не (Дел (X%12) = (A <50) и (Дел (X,A) + Не (Дел (X,10)) + Не (Дел (X,12)) (по закону Де Моргана, имеем) = (A <50) и (Дел (X,A) + Не ((Дел (X,10)) * Не (Дел (X,12))). Если Дел (X, A) =1, то Не ((Дел (X,10)) * Не (Дел (X,12))) =0. Применю отрицание к обоим частям неравенства и получу Дел (X,10)) * Не (Дел (X,12) =1 По сути, требуется найти такие x, которые делятся на 10 и на 12. Это x = 60, 120, 180, 240… Из условия дел (x, a) числа (60, 120, 180, 240) должны делиться на какое-то А – меньше 50. Какое это наименьшее число?

Ответ: 30.

Пример 15.2

Определите наибольшее натуральное число A, такое что выражение

(𝑥 &𝐴 ≠ 0) → ((𝑥&28 = 0) → ((𝑥&53 ≠ 0) ∧ (𝑥&20 = 0))) тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной X).

Решение:

Данную задачу решим ручным cпособом программирования на языке Python. Символ амперсанд & – побитовая операция записывается нажатием клавиши Shift+7. Cмотрим программу и после пробуем ее набрать, чтобы она работала.

 
for A in range(1, 200):
    flag = 0 # задание флага
    for x in range(1, 200):
        if ((x & A ==0) or ((x&31!=0) or (x&53!=0) and        (x&20==0))) == False:
            flag = 1
            break
    if flag == 0: # если флаг поменялся, то печатаем параметр А
        print(A)
 

Ответ: 63.

Пример 15.3

На числовой прямой заданы отрезки P = [10; 27], Q = [20;40] и R = [32; 50]. Определите максимальную длину отрезка А, для которого значение выражения ¬ (𝑥 ∈ 𝐴) ∨ (𝑥 ∈ 𝑄) ∧ ((𝑥 ∈ 𝑃) ∨ (𝑥 ∈ 𝑅)) будет истинным при любом значении переменной x.

Решение:

Проанализируем часть без параметра.

(𝑥 ∈ 𝑄) ∧ ((𝑥 ∈ 𝑃) ∨ (𝑥 ∈ 𝑅)). Это не что иное, как пересечение отрезка Q с объединением отрезков P и R. [20; 40] ∩ ([10; 27] ∪ [32; 50]). Отразим это на числовой оси и получим 2 отрезка [20; 27] ∪ [32; 40].

Следовательно, все точки, которые не входят в обозначенный диапазон от 10 до 50, также должны не входить в отрезок А. Значит, отрезок А полностью лежит внутри найденного диапазона.

Отрезок максимальной длины, который можно поместить в найденный диапазон – [32; 40]. 40—32=8.

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

 
P = range(10, 28) # задание отрезков
Q = range(20, 41)
R = range(32, 51)
for A in range(0, 1000):
    k = 0
    for x in range(0, 1000):
        if not(x == A) or (x in Q) and ((x in P) or (x in R)): # проверка принадлежности отрезкам
            k += 1
    if k == 1000:# если тысяча итераций цикла прошла, то число принадлежит отрезку
        print(A)
 

Ответ: 8

Задачи для самостоятельного решения

Задача 15.4

Для какого наименьшего целого числа А выражение

((x – 20 <A) ∧ (20 – x <A)) ∨ (x*y> 50) тождественно истинно, т.е. принимает значение 1 при любых целых положительных x и y?

Задача 15.5

Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Для какого наименьшего натурального числа A формула

ДЕЛ (A, 45) / (ДЕЛ (750, x) → (¬ДЕЛ (A, x) → ¬ДЕЛ (120, x)))

тождественно истинна, то есть принимает значение 1 при любом натуральном x?

Глава 8. Элементы теории алгоритмов

Задача №16. Рекурсия

Рекурсия – это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта. Для того чтобы задать рекурсию, необходимо писать: условие остановки рекурсии (базовый случай), рекуррентную формулу. В программировании, если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным и более длительным. Некоторые языки программирования не содержат циклических конструкций вовсе, предоставляя программистам организовывать повторения с помощью рекурсии (например, Пролог, где рекурсия – основной прием программирования).

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

В Питоне функция располагается выше основной программы и оформляется следующим образом (вместо многоточия могут быть любые операторы):

def Имя (аргументы):

Тело (инструкции)

return [значение, которое возвращается]

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

def print_sum (a = 2, b = 2): # определяем функцию

sum = a + b

print (sum)

#вызываем её

print_sum (5, 1)

Пример 16.1

Алгоритм вычисления значения функции F (n), где n – натуральное число, задан следующими рекуррентными соотношениями:

F (n) = 1 при n = 1;

F (n) = F (n – 1) · n при n ≥ 2.

Чему равно значение функции F (6)?

В ответе запишите только натуральное число.

Решение:

Последовательно найдем значения функции от базового случая F (1) до искомого значения F (6):

F (1) = 1; – по условию задачи

 
F (2) = F (2—1) * 2=1*2=2;
F (3) = F (3—1) * 3=2*3=6;
F (4) = F (4—1) *4= 6*4= 24;
F (5) = F (5—1) *5=24*5=120;
F (6) = F (6—1) * 6=120*6 = 720.
 

Эта задача достаточно быстро решается ручным способом, а если бы нас попросили вычислить значение F (40) вместо F (6), то ручным способом считать довольно долго. Поэтому давайте напишем и программу для вычисления.

 
def F(n): # задаем функцию
    if n == 1:
        return (1) # возврат значения 1, при n=1
    else:
        return F(n-1) * n
print(F(6)) # вызов функции и печать результата
 

Ответ: 720.

Пример 16.2

Алгоритм вычисления значения функции F (n), где n – натуральное число, задан следующими соотношениями:

F (n) = 1 при n = 1;

F (n) = n + F (n – 1), если n – чётно,

F (n) = 2 × F (n – 2), если n> 1 и при этом n – нечётно.

Чему равно значение функции F (30)?

Решение:

В ограниченном времени на ЕГЭ по информатике подсчитать аналитически значение функции F (26) – достаточно длительная задача. Поэтому напишем программу.

 
def F(n):
    if n == 1:
        return (1)
    if n % 2 ==0 :
        return (n + (F(n – 1)))# возврат значения функции, если число четное
    else:
        return (2 * (F(n – 2))) # возврат значения функции, если число нечетное
print(F(30))
Ответ: 16414.
 
 
Пример 16.3
 

Алгоритм вычисления функций F (n) и G (n) задан следующими соотношениями:

F (n) = G (n) = n, при n ≤ 2

F (n) = G (n) + F (n – 2), при n> 2

G (n) = F (n – 1) – G (n – 2), при n> 2

Здесь «//» обозначает деление нацело.

Определите значение, полученное при вызове G (20).

Решим задачу cпособом программирования на языке Python, объявив две функции F и G.

 
def F(n):
    if n <= 2:
        return n
    else:
        return G(n) + F(n – 2) # возврат при n>2
def G(n):
    if n <= 2:
        return n
    else:
        return F(n – 1) – G(n – 2) # возврат при n>2
print (G (20))
Ответ: 205.
 
 
Пример 16.4
 

Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F (n), будет больше 100000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

 
def F(n):
    print(n+1)
    if b >1:
        print(2*n)
        F(n-1)
        F(n-3)
 

Решение:

Введем дополнительную переменную S и накопим в ней значение функции F.

 
def F (n):
    s=0
    s += n +1
    if n >1:
        s += 2 *n
        s += F(n-1)
        s += F (n -3)
    return s
for i in range (1, 10000):
    x = F(i)
    if x > 10**5:
        print(i,x) # нахождение наименьшего и суммы
        break # прерывание цикла
 

Ответ: 24 126001

Задачи для самостоятельного решения

Задача 16.5

Алгоритм вычисления функций F (n) и G (n) задан следующими соотношениями:

F (1) = G (1) = 1

F (n) = 2·F (n—1) + G (n—1) – 2n, если n> 1

G (n) = F (n—1) +2·G (n—1) + n, если n> 1

Чему равно значение F (14) + G (14)?

Задача 16.6

Алгоритм вычисления функции F (n) задан следующими соотношениями:

F (n) = n % 3, для n <5,

F (n) = 2*F (n -2) + n*2, при четном значении n> 4,

F (n) = F (n – 2) + n % 4, при нечетном значении n> 4.

Для какого наибольшего натурального значения n результат F (n) не превышает 1500?

Задача №17. Программирование условий и циклов

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

• объявление переменных;

• оператор присваивания;

• оператор вывода;

• операторы цикла.

Пример 17.1

Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа: сначала количество, затем максимальное число. Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.

Данную задачу можно решать в Excel и программированием. Рассмотрим решение программированием.

 
b = 0
a = 0
s = []
for i in range(1016, 7938):
    a = i
    if a % 3 == 0 and a % 7> 0 and a % 17> 0 and 
      a % 19> 0 and a % 27> 0: # условие из задачи
        b = b + 1 # количество таких чисел
        s.append(a)# метод помещает в cписок s – значение а
print(«количество чисел -», + b)
print(«максимальное число -», + max(s)) # max – функция для поиска максимального значения
 

Давайте попробуем решить данную задачу в Excel. Помните, как записать условие делимости и неделимости? Условие достаточно длинным получится, хотя можно ведь пользоваться копированием.

Попробуйте проделать это в Excel и после посмотреть решение, которое ниже

=ЕСЛИ (И (ОСТАТ (A1;3) =0;ОСТАТ (A1;7) <> 0;ОСТАТ (A1;17) <> 0;ОСТАТ (A1;19) <> 0;ОСТАТ (A1;27) <> 0) =ИСТИНА;1;0) – если число делится на 3 и не делится на 7,17,19,27. Достаточно записать эту формулу и протянуть ее вниз. Цифры от 1016 до 7937 также протягиваются вниз мышкой. Далее суммируем все цифры по столбцу B, которые в этом файле https://yadi.sk/i/e00ZHC9jwfLvmw. И получаем 1568. Далее находим единицу, которая находится в самом низу столбца B и напротив нее число 7935.

Ответ: 1568, 7935.

Пример 17.2

Определите количество принадлежащих отрезку [2*10⁹; 4*10⁹] натуральных чисел, которые делятся на 7 и на 100000 и при этом не делятся на 13, 29, 43 и 101, а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Решение:

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

 
min = 4 * 10**10 # для поиска минимума берем максимальное число
count = 0
for i in range(2 * 10**9, 4 * 10**9, 100000):
    if i % 7 == 0 and i % 13!= 0 and i % 29!= 0 and  i % 101!= 0 and  i % 43!= 0:
        count += 1
        if i < min:# поиск минимального
            min = i
print(count , min)
 

Ответ: 2463 2000600000.

Пример 17.3

Найдите количество чисел в диапазоне [15000; 42000], которые в пятеричной системе счисления оканчиваются на 3, в девятеричной – на 5 и не оканчиваются на 7 в восьмеричной системе счисления.

Решение:

Попробуйте набрать программу сами, а потом сравните с той, что ниже. Младшая цифра числа в системе счисления с основанием N находится путем взятия остатка от деления числа на N, например, x mod 5 == 3 – проверяет, оканчивается ли число в пятеричной системе счисления на 3.

 
count, m = 0, 0
for i in range(42000, 15000, -1): # задаем шаг в минус, т.к. проход осуществляем с конца
    if i % 5 == 3 and i % 9 == 5 and i % 8 != 7:
        count += 1
        m = i
print(count, m)
 

Ответ: 525 15008.

Пример 17.4

Назовем натуральное число подходящим, если ровно два из его делителей входят в список (7, 17, 37, 47, 57). Найдите все подходящие числа, принадлежащие отрезку [15000; 30000].

В ответе запишите два целых числа: сначала количество, затем сумму всех найденных чисел.

Решение:

Число входит в список, если остаток от деления на любое из чисел этого списка равен нулю, поэтому зададим каскадное условие.

 
count = 0
s_two = 0
for i in range(15000, 30001):
    c_del = 0
    if i % 7 == 0:  c_del = c_del + 1#  проверка, подходит ли число, и увеличение счетчика
    if i % 17 == 0: c_del = c_del + 1
    if i % 37 == 0: c_del = c_del + 1
    if i % 47 == 0: c_del = c_del + 1
    if i % 57 == 0: c_del = c_del + 1
    if c_del == 2: # если таких делителей два, то запоминаем
        count = count + 1 # подсчет количества
        s_two = s_two + i  # подсчет суммы чисел
print(count, s_two)
Ответ: 312 6983374.
 

Задачи для самостоятельного решения

Задача 17.5

Рассматривается множество целых чисел, принадлежащих отрезку [3542; 15876], которые делятся на 2 или на 9 и не делятся на 11, 13, 17 и 23. Найдите количество таких чисел и максимальное из них. В ответе запишите два числа через пробел: сначала количество, затем максимальное число.

Задача 17.6

Назовём натуральное число подходящим, если у него ровно 3 различных простых делителя. Например, число 180 подходящее (его простые делители —2, 3 и 5), а число 12 – нет (у него только два различных простых делителя). Определите количество подходящих чисел, принадлежащих отрезку [10 001; 50 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

Задача №18. Исполнитель робот

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

Пример 18.1

Квадрат разлинован на N×N клеток (1 <N <17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.

В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

Пример входных данных:

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

41 22

Решение:

Решенное задание представлено по ссылке https://yadi.sk/i/K-F2HlZs1g3Dwg. Опишем кратко алгоритм решения задачи. Копируем число 51 и вставляем его в ячейку А27. Т.к. робот перемещается вниз и вправо по условию задачи, то для перемещения вниз в ячейку запишем формулу А1528=A2+A27 – растянем ее вниз левой кнопки мыши, потянем за крестик до ячейки А36. То же самое проделаем с ячейкой B27=B1+A27 и протянем ее до ячейки J27. Для подсчета минимального значения в ячейки B28 запишем формулу B28=МИН (A28;B27) +B2. Протянем эту формулу вправо до ячейки J28. И затем протянем вниз от ячейки J28 до J502. Т.к. робот по условию задачи заканчивает свой путь в правой нижней ячейке, то она и будет ответом в виде минимума на данную задачу, т.е. 502. Чтобы подсчитать максимум, для этого меняем формулу в ячейки B28 на B28=Макс (A28;B27) +B2. Далее протягиваем эту формулу аналогично тому, когда искали минимум, т.е. сначала вправо, потом вниз и получаем макс=1204

Ответ: 1204 502.

Пример 18.2

Квадрат разлинован на N×N клеток (2 <N <21). В каждой клетке записано целое положительное число – количество монет.

Исполнитель Сборщик имеет две команды ВПРАВО и ВВЕРХ, которые, соответственно, перемещают его на одну клетку вправо или на одну клетку вверх. Проходя через клетку, Сборщик собирает все монеты, лежащие на ней. На поле существуют стены, обозначенные жирной линией, через которые Сборщик проходить не может.

Исполнитель начинает движение в левой нижней клетке и заканчивает в правой верхней. Какое максимальное и минимальное количество монет может собрать Сборщик, пройдя от начальной клетки до конечной?

В ответе укажите сначала максимальный, затем минимальный результат, который может быть получен исполнителем.

Исходные данные представляют собой электронную таблицу в файле 18—2 размером N×N, каждая ячейка которой соответствует клетке квадрата.

Решение:

Здесь задача усложняется тем, что нам поставлены стенки. Решение и начальная обстановка приведены в файле по ссылке https://yadi.sk/i/8oDh1K-Ud6bJMQ. Для того чтобы стенки не затирались при копировании формул, закрасим ячейки желтым и оранжевым по примеру в файле. Число 160 перенесем в ячейку А43. Аналогично предыдущей задаче в ячейку В43 введем формулу = A43+B20 и растянем ее до ячейки T43. Также заполним ячейку А42=A43+A19 и растянем данную до А24. В ячейку B42 внесем формулу =МАКС (A42;B43) +B19 и протянем ее по всей таблицы, кроме закрашенных зон оранжевого и желтого цвета. По той причине, что сквозь стенку робот двигаться не может, т.е. попасть из Е35 в Е36 невозможно, то в Е35 внесем формулу=D35+E12 и протянем ее до F35. В остальных оранжевых сделаем аналогичную операцию. Робот попасть из F31 в G31 не может по той причине, что он двигаться сквозь стенку не может, то ячейка G31 примет вид =G32+G8 и протянем ее до G35. В правом верхнем углу будет ответ максимума 5955. Все то же самое проделаем, только вместо B42=МАКС (A42;B43) +B19, внесем B42=Мин (A42;B43) +B19 и протянем аналогично, не касаясь закрашенных ячеек.

Ответ: 5995 3867.

Задачи для самостоятельного решения

Задача 18.3

Исходные данные записаны в файле 18—9.xls (файл находится по ссылке https://yadi.sk/i/inds6yWzP-0_PA) в виде электронной таблицы прямоугольной формы. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой НИЖНЕЙ клетки в правую ВЕРХНЮЮ. В ответе укажите два числа – сначала максимальную сумму, затем минимальную.

Задача 18.4

Квадрат разлинован на N*N клеток (1 <N <17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается, при столкновении со стеной Робот разрушается. В каждой клетке записано число – количество монет, которое добавляется к счету Робота. Определите максимальное и минимальное значения счёта, которые может получить Робот после окончания работы в лабиринте. Начальным значением счёта является значение стартовой клетки. Робот движется из левой верхней в правую нижнюю клетки.

Исходные данные записаны в электронной таблице. В ответ запишите два числа друг за другом без разделительных знаков – сначала максимальное значение счёта, затем минимальное. Файл с условием приведен по ссылке https://yadi.sk/i/l_57rx0iehySCQ.