🗊Презентация Разбор задач

Категория: Математика
Нажмите для полного просмотра!
Разбор задач, слайд №1Разбор задач, слайд №2Разбор задач, слайд №3Разбор задач, слайд №4Разбор задач, слайд №5Разбор задач, слайд №6Разбор задач, слайд №7Разбор задач, слайд №8Разбор задач, слайд №9Разбор задач, слайд №10Разбор задач, слайд №11Разбор задач, слайд №12Разбор задач, слайд №13Разбор задач, слайд №14Разбор задач, слайд №15Разбор задач, слайд №16Разбор задач, слайд №17Разбор задач, слайд №18
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Разбор задач. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Разбор задач 26.12.2016
Описание слайда:
Разбор задач 26.12.2016

Слайд 2


Задача 1. Незнайка учиться считать Областная олимпиада 2005 года
Описание слайда:
Задача 1. Незнайка учиться считать Областная олимпиада 2005 года

Слайд 3


Постановка задачи Дана строка, состоящая из цифр; Найти такую подстроку, которая представляет собой последовательность подряд идущих натуральных чисел и является самой длинной по количеству чисел.
Описание слайда:
Постановка задачи Дана строка, состоящая из цифр; Найти такую подстроку, которая представляет собой последовательность подряд идущих натуральных чисел и является самой длинной по количеству чисел.

Слайд 4


Решение Перебираем начальную позицию, с которой начинается искомая последовательность; Перебираем длину начального числа; Прибавляем единицу к начальному числу и проверяем следующее; Проделываем тоже самое до тех пор пока строка не закончится либо число не будет удовлетворять последовательности; Сложность решения O(|S|3).
Описание слайда:
Решение Перебираем начальную позицию, с которой начинается искомая последовательность; Перебираем длину начального числа; Прибавляем единицу к начальному числу и проверяем следующее; Проделываем тоже самое до тех пор пока строка не закончится либо число не будет удовлетворять последовательности; Сложность решения O(|S|3).

Слайд 5


Трудности Прибавление единицы к длинному числу (представленному в виде массива); 0 не является натуральным числом;
Описание слайда:
Трудности Прибавление единицы к длинному числу (представленному в виде массива); 0 не является натуральным числом;

Слайд 6


Задача 2. Поврежденная карта Областная олимпиада 2005 года
Описание слайда:
Задача 2. Поврежденная карта Областная олимпиада 2005 года

Слайд 7


Постановка задачи Дан двумерный массив, состоящий из нулей и единиц; Найти наибольший по площади квадратный подмассив, который состоит из единиц; Вычислить площадь найденного подмассива.
Описание слайда:
Постановка задачи Дан двумерный массив, состоящий из нулей и единиц; Найти наибольший по площади квадратный подмассив, который состоит из единиц; Вычислить площадь найденного подмассива.

Слайд 8


Решение Задача решается с помощью динамического программирования; Пусть A – исходный массив, D – массив состояний ДП; D[i][j] – максимальная площадь квадрата из единиц, правая нижняя вершина которого находится в точке (i, j); Если клетка (i, j) повреждена, то D[i][j] = 0; Если не повреждена D[i][j] = min(D[i – 1][j], D[i][j – 1], D[i – 1][j – 1]) + 1; Первая строка и первый столбец заполняются отдельно D[1][j] = A[1][j] и D[i][1] = A[i][1]; Сложность решения O(N * M);
Описание слайда:
Решение Задача решается с помощью динамического программирования; Пусть A – исходный массив, D – массив состояний ДП; D[i][j] – максимальная площадь квадрата из единиц, правая нижняя вершина которого находится в точке (i, j); Если клетка (i, j) повреждена, то D[i][j] = 0; Если не повреждена D[i][j] = min(D[i – 1][j], D[i][j – 1], D[i – 1][j – 1]) + 1; Первая строка и первый столбец заполняются отдельно D[1][j] = A[1][j] и D[i][1] = A[i][1]; Сложность решения O(N * M);

Слайд 9


Задача 3. Abracadabra Региональная олимпиада РФ за 2012 год
Описание слайда:
Задача 3. Abracadabra Региональная олимпиада РФ за 2012 год

Слайд 10


Постановка задачи Дан набор строк s1, s2, s3, …, sm; Для каждой из строк si определить сколько слов из словаря t1, t2, …, tn имеют суффикс и префикс равный si; iй суффикс – это последние i символов строки t; iй префикс – это первые i символов строки t;
Описание слайда:
Постановка задачи Дан набор строк s1, s2, s3, …, sm; Для каждой из строк si определить сколько слов из словаря t1, t2, …, tn имеют суффикс и префикс равный si; iй суффикс – это последние i символов строки t; iй префикс – это первые i символов строки t;

Слайд 11


Решение Преобразуем каждую строку t, состоящую из n символов к виду: t0 tn-1 t1 tn-2 … tn-2 t1 tn-1 t0 Например слово table будет преобразовано в tealbblaet Отсортируем преобразованный словарь в лексикографическом порядке; Таким образом, все слова с одинаковым супрефиксом идут подряд;
Описание слайда:
Решение Преобразуем каждую строку t, состоящую из n символов к виду: t0 tn-1 t1 tn-2 … tn-2 t1 tn-1 t0 Например слово table будет преобразовано в tealbblaet Отсортируем преобразованный словарь в лексикографическом порядке; Таким образом, все слова с одинаковым супрефиксом идут подряд;

Слайд 12


Решение (1) Для каждой из строк s проделаем аналогичное преобразование; Двоичным поиском найдем самое левое вхождение (left) и самое правое вхождение (right); Тогда ответом для строки si будет right – left + 1; Сложность решения O(n * Log(m));
Описание слайда:
Решение (1) Для каждой из строк s проделаем аналогичное преобразование; Двоичным поиском найдем самое левое вхождение (left) и самое правое вхождение (right); Тогда ответом для строки si будет right – left + 1; Сложность решения O(n * Log(m));

Слайд 13


Пример Пусть задан набор строк из примера задачи; Тогда строки будут преобразованы следующим образом: abacaba => aabbaaccaabbaa; abracadabra => aabrrbaacdaadcaabrrbaa; aa => aaaa; abra => aabrrbaa;
Описание слайда:
Пример Пусть задан набор строк из примера задачи; Тогда строки будут преобразованы следующим образом: abacaba => aabbaaccaabbaa; abracadabra => aabrrbaacdaadcaabrrbaa; aa => aaaa; abra => aabrrbaa;

Слайд 14


Пример (1) Отсортируем словарь в лексикографическом порядке: aaaa aabbaaccaabbaa aabrrbaacdaadcaabrrbaa aabrrbaa Для образца a (aa) left = 1, right = 4, ответ = 4; Для образца abra (aabrrbaa) left = 3, right = 4, ответ = 2; Для образца abac (acbaabca) left = -1, right = -1, ответ = 0;
Описание слайда:
Пример (1) Отсортируем словарь в лексикографическом порядке: aaaa aabbaaccaabbaa aabrrbaacdaadcaabrrbaa aabrrbaa Для образца a (aa) left = 1, right = 4, ответ = 4; Для образца abra (aabrrbaa) left = 3, right = 4, ответ = 2; Для образца abac (acbaabca) left = -1, right = -1, ответ = 0;

Слайд 15


Задача 4. Землетрясение USACO Open 2001
Описание слайда:
Задача 4. Землетрясение USACO Open 2001

Слайд 16


Постановка задачи Задан неориентированный граф из N вершин и M ребер; Каждое из ребер необходимо восстановить за время t и потратив на это c денежных единиц; Задача состоит в том, чтобы восстановить ребра таким образом, чтобы граф оказался связным; При этом обещано вознаграждение F за выполненную задачу; Требуется вычислить максимально возможную прибыльность (т.е. количество денег, которые можно заработать за час работы);
Описание слайда:
Постановка задачи Задан неориентированный граф из N вершин и M ребер; Каждое из ребер необходимо восстановить за время t и потратив на это c денежных единиц; Задача состоит в том, чтобы восстановить ребра таким образом, чтобы граф оказался связным; При этом обещано вознаграждение F за выполненную задачу; Требуется вычислить максимально возможную прибыльность (т.е. количество денег, которые можно заработать за час работы);

Слайд 17


Решение Допустим, что нам известна прибыльность работ v; Тогда очевидно, что мы можем вычислить стоимость каждого из ребер как t * v + c: первое слагаемое – полученная прибыть, второе – стоимость восстановления дороги; В этом случае мы можем построить минимальное остовное дерево и если его стоимость меньше вознаграждения F, то такая прибыльность нам подходит;
Описание слайда:
Решение Допустим, что нам известна прибыльность работ v; Тогда очевидно, что мы можем вычислить стоимость каждого из ребер как t * v + c: первое слагаемое – полученная прибыть, второе – стоимость восстановления дороги; В этом случае мы можем построить минимальное остовное дерево и если его стоимость меньше вознаграждения F, то такая прибыльность нам подходит;

Слайд 18


Решение (1) Заметим, что если увеличивать прибыльность v, то и стоимость дерева будет расти; Следовательно, cost(v) – возрастающая (монотонная функция); Таким образом, v можно перебирать двоичным поиском; Найденное оптимальное значение прибыли и будет ответом; Сложность решения O(Log(C * M) * M * Log(M));
Описание слайда:
Решение (1) Заметим, что если увеличивать прибыльность v, то и стоимость дерева будет расти; Следовательно, cost(v) – возрастающая (монотонная функция); Таким образом, v можно перебирать двоичным поиском; Найденное оптимальное значение прибыли и будет ответом; Сложность решения O(Log(C * M) * M * Log(M));

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию