-
Автор темы
- #1
Решил поделиться с вами небольшим алгоритмом для решения типовых задач из ЕГЭ по информатике, основанных на принципе динамического программирования. Об этом интересном олимпиадном направлении хорошо рассказывали на
В общем и целом, такие задачи обычно состоят из задачи найти количество программ, которые с помощью выполнения заданных операций в любом порядке смогут превратить число X в Y. Иногда уточняется обязательное использование или же обход некоторых чисел. Предлагаю вам немного разобраться с одной из них:
Как видите, алгоритм решения не включает ничего сложного, он основывается на, надеюсь, известных вам принципах динамики. Интересным решением, как по мне, будет создание небольшой программы, которая способна вычислять ответ в подобных задачах без какие-либо сторонних расчетов. Основные значения, принимаемые на вход:
Исходный код:
Пример работы на очередном задании из ЕГЭ:
На этом, думаю, стоит закончить. Если вы хотите увидеть продолжение с решением задач по динамике на двумерных массивах или графах - обязательно отпишите в тему, мне важно знать, что интересно аудитории :)
Пожалуйста, авторизуйтесь для просмотра ссылки.
, можете почитать. Я же решил написать небольшую программу, позволяющую решать задания об "Исполнителях Калькулятор, РазДваТри и т.д.", примеров подобных "непосильных" заданий очень много, вот ссылка на небольшой сборник таких -
Пожалуйста, авторизуйтесь для просмотра ссылки.
.В общем и целом, такие задачи обычно состоят из задачи найти количество программ, которые с помощью выполнения заданных операций в любом порядке смогут превратить число X в Y. Иногда уточняется обязательное использование или же обход некоторых чисел. Предлагаю вам немного разобраться с одной из них:
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21, при этом траектория вычислений содержит число 10 и не содержит число 17?
Решение.
Нужно найти количество программ, которые из 1 получают 10, количество программ, которые из 10 получают 21, но не проходит через 17 и перемножить найденные значения. Сначала найдём количество программ, получающих 10 из 1.
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.
Верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n - 1 — прибавление единицы.
2. Пусть n делится на 2.
Если n > 1, то R(n) = R(n / 2) + R(n - 1).
Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).
Теперь можно постепенно вычислить все значения:
R(2) = R(1) + R(1) = 1 + 1 = 2 = R(3)
R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),
R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),
R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),
R(10) = R(5) + R(9) = 4 + 10 = 14
Программ, получающих из числа 10 число 21, и не содержащих 17 всего одна: 21.
Тем самым, находим ответ: 14 · 1 = 14.
Ответ: 14.
1. Прибавить 1
2. Умножить на 2
Программа для исполнителя Калькулятор – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21, при этом траектория вычислений содержит число 10 и не содержит число 17?
Решение.
Нужно найти количество программ, которые из 1 получают 10, количество программ, которые из 10 получают 21, но не проходит через 17 и перемножить найденные значения. Сначала найдём количество программ, получающих 10 из 1.
Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.
Верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n - 1 — прибавление единицы.
2. Пусть n делится на 2.
Если n > 1, то R(n) = R(n / 2) + R(n - 1).
Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).
Теперь можно постепенно вычислить все значения:
R(2) = R(1) + R(1) = 1 + 1 = 2 = R(3)
R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),
R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),
R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),
R(10) = R(5) + R(9) = 4 + 10 = 14
Программ, получающих из числа 10 число 21, и не содержащих 17 всего одна: 21.
Тем самым, находим ответ: 14 · 1 = 14.
Ответ: 14.
- Используемые операции сложения и умножения (с вычитанием и делением дела обстоят ничуть не хуже, вы с легкостью сможете добавить их в свою программу при необходимости)
- Начальное число
- Конечное число
- Обязательно используемые числа
- "Запрещенные" числа
Исходный код:
C++:
#include <iostream>
using namespace std;
void Sort(int* mas, int size) {
int i = 0;
int j = size - 1;
int mid = mas[size / 2];
do {
while (mas[i] < mid)
i++;
while (mas[j] > mid)
j--;
if (i <= j) {
int tmp = mas[i];
mas[i] = mas[j];
mas[j] = tmp;
i++;
j--;
}
} while (i <= j);
if (j > 0)
Sort(mas, j + 1);
if (i < size)
Sort(&mas[i], size - i);
}
int main() {
setlocale(LC_ALL, "ru");
while (true) {
system("cls");
int N, plus[100], multiply[100], k1 = 0, k2 = 0;
cout << "Введите количество возможных операций: ";
cin >> N;
cout << "Введите операции сложения и умножения: ";
for (int i = 0; i < N; i++) {
char c;
int num;
cin >> c >> num;
if (c == '+')
plus[k1++] = num;
else if (c == '*')
multiply[k2++] = num;
}
Sort(plus, k1);
Sort(multiply, k2);
int X, Y;
cout << endl << "Введите X: ";
cin >> X;
cout << "Введите Y: ";
cin >> Y;
cout << endl << "Обязательные числа при вычислении (введите 0, если их нет): ";
int use[100] = {}, notUse[100] = {}, _k1 = 1, _k2 = 0;
use[0] = X;
char c = cin.get();
while (c = cin.get(), c != '\n') {
if ((c == '0' || c == '\n') && _k1 == 1 && !use[_k1] && cin.get() == '\n') {
_k1 = 0;
break;
}
if (c != ' ')
use[_k1] = use[_k1] * 10 + (c - '0');
else {
if (use[_k1] != use[_k1 - 1])
_k1++;
else
use[_k1] = 0;
}
}
if (use[_k1] != Y)
use[++_k1] = Y;
int mas[10000] = {}, count = 0;
mas[0] = 1;
cout << "Запрещенные числа (введите 0, если их нет): ";
while (c = cin.get(), c != '\n') {
if ((c == '0' || c == '\n') && !_k2 && !notUse[_k2] && cin.get() == '\n')
break;
if (c != ' ')
notUse[_k2] = notUse[_k2] * 10 + (c - '0');
else
mas[notUse[_k2++] - X] = -1;
}
mas[notUse[_k2++] - X] = -1;
Sort(use, _k1);
Sort(notUse, _k2);
for (int i = 0; i < _k1; i++) {
for (int j = 0; j < _k2; j++)
if (use[i] == notUse[j]) {
cout << endl << "Невозможно решить задачу!" << endl;
goto end;
}
}
for (int i = 0; i < _k1; i++) {
if (X == Y) {
cout << "Ответ: 1 программа";
break;
}
for (int j = use[i] + 1; j <= use[i + 1]; j++) {
if (mas[j - X] == -1)
continue;
for (int _p = 0; _p < k1; _p++) {
if (j - plus[_p] < use[i])
break;
else if (mas[j - plus[_p] - X] != -1)
mas[j - X] += mas[j - plus[_p] - X];
}
for (int _m = 0; _m < k2; _m++) {
if (!(j % multiply[_m])) {
if (j / multiply[_m] < use[i])
break;
else if (mas[j / multiply[_m] - X] != -1)
mas[j - X] += mas[j / multiply[_m] - X];
}
}
}
if (mas[use[i + 1] - X] <= 0) {
cout << endl << "Невозможно решить задачу!" << endl;
break;
}
count = count <= 0 ? mas[use[i + 1] - X] : count * mas[use[i + 1] - X];
mas[use[i + 1] - X] = 1;
if (i == _k1 - 1) {
cout << endl << "Ответ: " << count << endl;
break;
}
}
end:
system("pause");
}
exit(0);
}На этом, думаю, стоит закончить. Если вы хотите увидеть продолжение с решением задач по динамике на двумерных массивах или графах - обязательно отпишите в тему, мне важно знать, что интересно аудитории :)
