| lesha | Дата: Среда, 30.11.2011, 14:39 | Сообщение # 1 |
Offline
Генералиссимус
Глобальный модератор
| Сообщений: | 1817 |
| Награды: | 20 |
| Замечания: | 0% |
|
Ну так... всем привет) так как не первая тема, то, думаю, и мне можно 
Только что пришёл с олимпиады... задачек решил мало хотя их и было всего 5, но я решил вообще 1 :D. Теперь, из любопытства, запилю задачки сюда... Может, кто решит... Буду благодарен...
Задача 1. Квадратное уравнение
Решена
Хоть задача и решена,незнаю, правильно ли, но хочу посмотреть на другие решения.
Quote В квадратом уравнении аx2 + bx + c = 0 заданы коэффиеценты a и b, а значение с не задано. Известно, что у уравнония ровно один корень.
Например, если a=1, b=-2, то искомое значение с=1.
Требуется написать программу, которая по заданным целым числам a и b (-104<a,b<104) найдт целое число с, такое, что приведённое уравнение имеет ровно один корень, либо выяснит, что это невозможно.
Коментарии
Для того, чтобы уравнение имело ровно один корень, необходимо, чтобы его дискриманант был равен нулю, т.е. b2 - 4*a*c = 0. Отсюда c=b2/(4*a). Поскольку нас интересуют целые с, то, если это число не целое, ответ "невозможно", иначе, число с.
Задача 2. Седловая точка
Недоведена
Данную задачу начал, но довести до конца так и не смог.
Quote РАссмотрим таблицу размером n x n, заполненную целыми числами. Седловой точкой в такой таблице называется число, которое является минимальным в своей строке и одновременно максимальным в своём столбце. Например в таблице: оба числа 3 являются седловыми точками. Других седлых точек в данной таблице нет. Требуется написать программу, которая по числу n(1 <n <50) и таблице размером n x n найдёт количество в ней седловых точек.
Коментарии
Перебрать все элементы таблицы, найти максимум в его строке и столбце. Посчитать количество элементов, для которых данное условие выполняется. Можно заранее посчитать максимумы и минимумы и запомнить в два массива, но, ограничения задачи, вообще говоря, этого не требуют.
Задача 3. Размещения
Нерешена
Размещение из n по k - это набор из k различных чисел, каждое из которых принимает значение от 1 до n. При этому размещения, отличающиеся порядком входящих в них чисел, считаются различными.
Например, существует 6 размещений из 3 по 2:
(1,2);(2,1);(1,3);(3,1);(2,3);(3,2)
В приведённом примере сочетания упорядоченны по сумме входящих в них чисел, а затем - лексиографически - сначала по первому числу, затем по второму и т.д.
Требуется написать программу, которая по заданным n и k выведет все размещения из n по k, упорядоченные указанным образом. (1<k<n<10)
Коментарии
Сгенерируем все размещения из n по k рекурсивной функцией (стандартная задача) и после этого отсортируем размещения требуемым образом. Поскольку при ограничениях задачи максимальное количество размещение равно 252(при n=10, k=5), то сортировать можно любой квадратичной сортировкой. Если применять устойчивую сортировку и генерировать размещения в лексеографическом порядке, то в самой сортировке лексиографическую упорядоченность можно не проверять.
Задача 4. Упаковка рюкзака
Нерешена
Quote Группа школьников собирается в поход и собирается закупить продукты. В магазине есть n типов продуктов, про каждый продукт известна его цена pi, вес wi и питательность ci. Каждого типа продуктов можно купить неограниченное количество.
Продукты складываются в рюкзак, который выдерживает вес не больше W. Общий бюджет, выделенный на продукты, равен P. Школьники хотят купить продукты с максимальной суммарной питательностью.
НАпример, если есть два типа продуктов p1=2, w1, c1, p2, w2=3,c2=3
Требуется написать программу, которая по заданному целому числу n(1< n <50), числам P и W (1<P,W < 500), а также информации о продухтах целым pi, wi и ci (1<pi,wi,ci<50) находит максимальную суммарную питательность продуктов, которые можно взять в поход.
Коментарии
Стандартная трёхмерная задача о рюкзаке. Решается динамическим программированием. Заводим массив d и размером P на W и в элементе d[i][j] храним максимальную стоимость при ограничениях на стоимость и вес i и j соответственно. Пересчитываем по формуле dp[i][j]=max(dp[i][j],dp[i-weight[k]][j-price[k]]+c[k]), где максимум берётся по k, где k пробегает все продукты с 1 до n. Вводим элемент d[P][PW].
Задача 5. Подготовка отчёта
Нерешена
Quote Для подготовки отчёта о проведении олимпиады жюри необходимо разработать n документов. Для каждого документа известен список документов, которые необходимо подготовить перед этим. Жюри хочет выяснить, в какомпорядке необходимо готовить эти документы.
например, пусть n=4, перед документом 1 необходимо подготовить документы 2 и 4, перед документом 2 - документ 3, а перед документом 4- документы 2 и 3. Тогда эти документы можно готовить в следующем порядке: 3, 2, 4, 1.
Требуется написать программу, которая по n(1<n<), и списку зависимостей находит порядок, в котором следует разрабатывать докумены.
Коментарии
Условие задачи задаёт нам граф. Необходимо его топологически отсортировать и вывести вершины в порядке топологической сортировки. Для топологической сортировки необходимо запустить обход в глубину. Требуемой сортировкой будет упорядочение вершин по времен выхода.
|
| |
| |
| lesha | Дата: Среда, 30.11.2011, 14:41 | Сообщение # 2 |
Offline
Генералиссимус
Глобальный модератор
| Сообщений: | 1817 |
| Награды: | 20 |
| Замечания: | 0% |
|
Заранее извиняюсь за недочёты в посте, если есть ошибки или сомнения, задавайте.
|
| |
| |
