Ниже представлен алгоритм работы кассира, выдающего покупателю сдачу наименьшим количеством банкнот: 1000 , 500 , 100 , 50 и 10 рублей. k1000 := s div 1000 s := s mod 1000 k500 :=…
Ниже представлен алгоритм работы кассира, выдающего покупателю сдачу наименьшим количеством банкнот: 1000 , 500 , 100 , 50 и 10 рублей. k1000 := s div 1000 s := s mod 1000 k500 := s div 500 s := s mod 500 k100 := s div 100 s := s mod 100 k50 := s div 50 s := s mod 50 k10 := s div 10 Исполните алгоритм для s=745 и составьте таблицу значений для переменной. Задание 4 ФИПИ У исполнителя Делитель две команды, которым присвоены номера: 1 — раздели на 2; 2 — прибавь 1. Первая из них уменьшает число на экране в два раза, вторая увеличивает его на один. Исполнитель работает только с натуральными числами. Составьте алгоритм получения из числа 89 числа 24, содержащий не более пяти команд. В ответе запишите только номера команд. (Например, 21121 — это алгоритм: прибавь 1 раздели на 2 раздели на 2 прибавь 1 раздели на 2 Он преобразует число 75 в 10 .) Если таких алгоритмов более одного, то запишите любой из них.
Давайте постепенно решим каждую из задач.
Задача 1: Выдача сдачи
Мы должны определить, как кассир выдает сдачу в размере 745 рублей, используя минимальное количество банкнот номиналами 1000, 500, 100, 50 и 10 рублей. Для этого будем следовать алгоритму.
Вводим сумму:
- \( s = 745 \)
Применяем алгоритм для определения количества каждой банкноты:
Банкноты по 1000 рублей: \[ k1000 = s \div 1000 = 745 \div 1000 = 0 \] \( s = s \mod 1000 = 745 \mod 1000 = 745 \)
Банкноты по 500 рублей: \[ k500 = s \div 500 = 745 \div 500 = 1 \] \( s = s \mod 500 = 745 \mod 500 = 245 \)
Банкноты по 100 рублей: \[ k100 = s \div 100 = 245 \div 100 = 2 \] \( s = s \mod 100 = 245 \mod 100 = 45 \)
Банкноты по 50 рублей: \[ k50 = s \div 50 = 45 \div 50 = 0 \] \( s = s \mod 50 = 45 \mod 50 = 45 \)
Банкноты по 10 рублей: \[ k10 = s \div 10 = 45 \div 10 = 4 \] \( s = s \mod 10 = 45 \mod 10 = 5 \)
Итог:
- \( k1000 = 0 \)
- \( k500 = 1 \)
- \( k100 = 2 \)
- \( k50 = 0 \)
- \( k10 = 4 \)
- Остаток = 5 (который невозможно выдать с помощью имеющихся банкнот)
Таблица значений для переменной:
| Номинал | Количество | Остаток |
|---|---|---|
| 1000 | 0 | 745 |
| 500 | 1 | 245 |
| 100 | 2 | 45 |
| 50 | 0 | 45 |
| 10 | 4 | 5 |
Итак, для суммы 745 рублей кассир выдает 1 банкноту по 500 рублей, 2 банкноты по 100 рублей и 4 банкноты по 10 рублей, оставляя 5 рублей невыданными.
Задача 2: Алгоритм получения числа
Теперь нам нужно составить алгоритм, чтобы преобразовать число 89 в 24, используя команды:
- Разделить на 2
- Прибавить 1
Рассмотрим обратный процесс: как из 24 получить 89, чтобы потом определить последовательность команд в обратном порядке.
- Начнем с числа 24:
- 24 → (прибавить 1) → 25
- 25 → (разделить на 2) (нельзя, так как 25 нечетное)
- 25 → (прибавить 1) → 26
- 26 → (разделить на 2) → 13
- 13 → (прибавить 1) → 14
- 14 → (разделить на 2) → 7
- 7 → (прибавить 1) → 8
- 8 → (разделить на 2) → 4
- 4 → (разделить на 2) → 2
- 2 → (разделить на 2) → 1
- 1 → (прибавить 1) → 2
- 2 → (разделить на 2) → 1
Пробуем составить протяженный путь. Если минимизировать:
- 89 → (разделить на 2) → 44 (первый шаг)
- 44 → (разделить на 2) → 22 (второй шаг)
- 22 → (разделить на 2) → 11 (третий шаг)
- 11 → (прибавить 1) → 12 (четвертый шаг)
- 12 → (разделить на 2) → 6 (пятый шаг)
- 6 → (разделить на 2) → 3 (шестой)
- 3 → (прибавить 1) → 4 (седьмой)
Обратно:
- 24 (1)
- 25 (2)
- 26 (2)
- 27 (1)
- 28 (4)
Поэтому один из возможных алгоритмов, который приводит к 24 из 89: 21111 — где:
- 2: Раздели на 2
- 1: Прибавь 1
- 1: Прибавь 1
- 1: Прибавь 1
- 1: Прибавь 1
Есть много различных вариантов алгоритмов, и этот — один из них. Вы можете использовать другой порядок команд, если это приведет к такому же результату.
