Две красивые задачи по алгоритмам
Время на прочтение
4 мин
Количество просмотров 67K
На этой неделе я начал читать бакалаврам Академического университета базовый курс по алгоритмам. Начинал я совсем с основ, и чтобы тем, кто с базовыми алгоритмами уже знаком, было чем заняться, я в начале пары сформулировал две, наверное, самые свои любимые задачки по алгоритмам. Давайте и с вами ими поделюсь. Решение одной из них даже под катом подробно расскажу. Но не отказывайте себе в удовольствии и не заглядывайте сразу под кат, а попытайтесь решить задачи самостоятельно. Обещаю, что у обеих задач есть достаточно простые решения, не подразумевающие никаких специальных знаний по алгоритмам. Это, конечно, не означает, что эти решения просто найти, но после пары один из студентов подошёл и рассказал правильное решение первой задачи. =) Если же вам интересно посмотреть на начало курса или порешать больше разных задач — приходите к нам на (бесплатный) онлайн-курс, который начнётся 15 сентября.
Задача 1. Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.
Сразу поясню. В условии не говорится, что каждое число от 1 до n встречается в массиве, поэтому повторяющихся элементов там может быть сколько угодно (если бы все числа входили по разу, а одно — дважды, то задача была бы гораздо проще). Ограничение на использование дополнительной памяти означает, что нельзя заводить дополнительный массив линейной длины, но можно заводить переменные.
Задача 2. Дана матрица nxn, содержащая попарно различные натуральные числа. Требуется найти в ней локальный минимум за время O(n).
Локальным минимумом матрицы называется элемент, который меньше всех своих четырёх соседей (или трёх, если этот элемент лежит на границе; или двух, если это угловой элемент). Обратите внимание, что от нас требуется линейное по n время, хотя в матрице квадратичное по n число элементов. Поэтому мы предполагаем, что матрица уже считана в память. И нам нужно найти в ней локальный минимум, обратившись лишь к линейному количеству её ячеек.
Под катом — решение первой задачи. Ещё раз призываю вас заглядывать под кат только после того, как порешаете задачу. По второй задаче могу какую-нибудь подсказку сказать.
Попытаюсь рассказать не только решение, но и то, как до него можно было бы догадаться. Пояснять буду сразу на примере. Из него, надеюсь, будет понятно, как алгоритм работает в общем случае. Рабочий пример:
То есть нам дан массив длины 9, содержащий числа от 1 до 8, и наша цель — найти двойку или пятёрку.
Как мы помним, использовать дополнительную память в условии задачи запрещено. Давайте, однако, поймем, чем она могла бы нам помочь. Мы бы тогда завели новый массив размера n и одним проходом по исходному массиву A посчитали бы, сколько раз каждое из чисел от 1 до n входит в A. По этому массиву было бы сразу видно, кто в A повторяется.
Это в дальнейшем не особо нам поможет, но всё же.
Ограничение на дополнительную память не даёт нам собрать и записать вспомогательную информацию о массиве. Значит, повторяющийся элемент нам нужно найти, как-то «гуляя» по массиву. Гулять по массиву можно слева направо, например, но непонятно, какую информацию можно при этом извлечь. Поэтому попробуем гулять по-другому. Встанем в первый элемент нашего массива и посмотрим, что там написано. Написано там число 7, поэтому давайте посмотрим на седьмой элемент массива. Там записано число 1. Прогулка получилась недолгой, мы зациклились. То, что в массиве есть какие-то циклы, очень нам поможет в дальнейшем. Для примера давайте ещё попробуем прогуляться из второго элемента: оттуда мы пойдём в элемент номер 5, из него — в элемент номер 3, а из элемента номер 3 опять вернёмся обратно в элемент номер 2. То есть нашли ещё один цикл. Давайте изобразим найденные нами два цикла:
И раз уж мы осознали, что наш массив неявно задаёт некоторый граф, то давайте явно этот граф нарисуем. Формально, вершины графа — это числа от 1 до n+1; мы проводим ориентированное ребро из i в j, если A[i]=j.
Интересуют нас в этом графе вершины, в которые входят хотя бы два ребра (если в вершину j входят рёбра из вершин i и k, то A[i]=A[k]=j, то есть j повторяется в массиве A). Нам и так ясно, что такая вершина в графе есть, но давайте это осознаем ещё раз, в терминах графов. В нашем графе из каждой вершины выходит ровно одно ребро (и значит, в графе (n+1) ребро), но есть одна вершина, в которую ничего не входит: это вершина (n+1). Значит, найдётся вершина, в которую входит хотя бы два ребра. В общем-то, это и так было ясно, но вот замечание про вершину (n+1) нам в дальнейшем поможет.
Давайте встанем в вершину (n+1) и будем переходить в нашем графе по исходящим рёбрам. Когда-нибудь мы зациклимся, конечно, но важно то, что мы не вернёмся в вершину (n+1). В нашем рабочем примере мы выйдем из вершины 9 и дойдём до цикла (5,2,3). Видно, что точка входа в этот цикл — это и есть повторяющийся элемент: ведь в эту точку и по ребру цикла можно войти, и по ребру на пути из вершины (n+1) в цикл. В нашем примере такая точка входа — это вершина 5.
Нахождение этой точки — отдельная не слишком простая задача, но её решение очень похоже на решение стандартной задачи о зацикленности списка. Длину цикла найти несложно. Например, сделаем n+1 шаг из вершины n+1. После этого мы обязательно окажемся в вершине на цикле. Запомним эту вершину и будем продолжать шагать, пока не вернёмся в неё. Тем самым узнаем длину цикла k. Теперь сделаем следующее. Поставим два указателя в вершину n+1. Первым указателем сделаем k шагов. После этого будем двигать каждый из указателей на один шаг вперёд, пока они не встретятся (таким образом, первый указатель всегда будет обгонять второй на k шагов). Ясно, что встретятся эти ребята как раз в нужной нам точке входе. В нашем примере длина цикла равна трём. После трёх шагов первый указатель окажется в вершине 2. В этот момент мы начнём двигать и второй указатель. Через два шага указатели встретятся в вершине 5.
На закуску. Мы не обсудили, почему же было запрещено модифицировать массив (и наш алгоритм массив, действительно, не трогал). Придумайте более простое решение, если разрешается портить массив.
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
1 |
|
Найти количество локальных минимумов в матрице22.11.2011, 19:36. Показов 10469. Ответов 37
Можете подсказать как найти кол-во локальных минимумов в двумерном массиве?
0 |
8 / 8 / 2 Регистрация: 08.10.2011 Сообщений: 28 |
|
22.11.2011, 19:40 |
2 |
Перебирай все элементы и каждый проверяй, является ли он минимумом, если да – к счетчику +1
0 |
Заблокирован |
|
22.11.2011, 19:46 |
3 |
student-novi4ok, что за локальный минимум? приведи пример)
0 |
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
22.11.2011, 19:53 [ТС] |
4 |
1 2 3 4
0 |
Заблокирован |
|
22.11.2011, 19:56 |
5 |
1 2 3 4 Правильно ли я понял, что, например, в следующем одномерном массиве { 10, 11, 1, 2 , 3 } 10 и 1 – это два локальных минимума?
0 |
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
22.11.2011, 19:57 [ТС] |
6 |
В одномерном, не знаю, т.к. на сколько я понял, то локальные минимумы бывают только в матрицах
0 |
Заблокирован |
|
22.11.2011, 20:00 |
7 |
В одномерном, не знаю, т.к. на сколько я понял, то локальные минимумы бывают только в матрицах А с каких это пор одномерный массив не является матрицей?!
1 |
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
22.11.2011, 20:20 [ТС] |
8 |
ну матрица это вроде двумерный только, хотя в этом пока не профи=) может и не прав. а так да, поняли правильно Добавлено через 17 минут
0 |
Заблокирован |
||||
22.11.2011, 21:15 |
9 |
|||
student-novi4ok, я понял твою задачу, и, надеюсь, что правильно:
P.S Хотел через классы, но передумал – слишком уж мудрено бы получилось…
1 |
1562 / 1040 / 94 Регистрация: 17.04.2009 Сообщений: 2,995 |
|
22.11.2011, 22:00 |
10 |
масивы с нуля как бэ) Про локальные переменные и отсутствие брейка, при не выполнение условия, можно пока молчать.
0 |
Заблокирован |
|
22.11.2011, 22:09 |
11 |
KuKu, а зачем мне глобальные переменные, если они используются только в цикле?
0 |
1562 / 1040 / 94 Регистрация: 17.04.2009 Сообщений: 2,995 |
|
22.11.2011, 22:13 |
12 |
И без локальных и без глобальных. А брейк из чувства прекрасного. Но это мелочи, есть по-важнее: int mat[n][n]; от нуля до n-1
1 |
student-novi4ok 4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
||||
23.11.2011, 00:18 [ТС] |
13 |
|||
student-novi4ok, я понял твою задачу, и, надеюсь, что правильно:
P.S Хотел через классы, но передумал – слишком уж мудрено бы получилось… Огромное спасибо, а на счет классов, хорошо что без них)) пока не проходили)
0 |
Заблокирован |
|
23.11.2011, 10:53 |
14 |
KuKu, ничего в этом страшного нет! В C++ размерность можно задавать от единицы до n Добавлено через 47 секунд
0 |
1562 / 1040 / 94 Регистрация: 17.04.2009 Сообщений: 2,995 |
|
23.11.2011, 20:27 |
15 |
Скажите об этом Страуструпу.
1 |
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
26.11.2011, 22:57 [ТС] |
16 |
Скажите об этом Страуструпу. Я конечно извиняюсь, но у меня появилась проблема, мы еще булевский тип не проходили, я почитал все понял, но преподаватель требует сделать без булевского типа, не могли бы вы помочь мне сделать простым перебором?
0 |
1562 / 1040 / 94 Регистрация: 17.04.2009 Сообщений: 2,995 |
|
26.11.2011, 23:15 |
17 |
Не могли, если вы поняли логику, то переделать ее можно на раз. Если что-то непонятно – спрашивайте.
1 |
student-novi4ok 4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
||||
26.11.2011, 23:33 [ТС] |
18 |
|||
я сделал, только не работает) Добавлено через 5 минут
Мой код, тут пока поиск не по всем элементам, но мне кажется что это все не правильно)
0 |
KuKu 1562 / 1040 / 94 Регистрация: 17.04.2009 Сообщений: 2,995 |
||||
27.11.2011, 00:05 |
19 |
|||
Как-то так должно быть – не проверял. Правда я не уверен, если i=0, будет ли проверяться второе условие. По идее не должно, хотя кто его знает. Надо спросить у более знающих). Если будет, то разбейте на два if-а.
1 |
4 / 4 / 3 Регистрация: 05.09.2011 Сообщений: 113 |
|
27.11.2011, 00:10 [ТС] |
20 |
Вроде не должно, ведь breakи стоят Добавлено через 2 минуты
0 |
12K
09 января 2010 года
Ghox
297 / / 26.07.2009
Элемент матрицы называется локальным минимумом, если он строго меньше всех имеющихся у него соседей. Подсчитать количество локальных минимумов заданной матрицы 10 на 10 .
Найти сумму модулей элементов выше главной диагонали.
Вопрос по первой части :
1)Что-то он криво считает минимумы в углах там вроде как нужен учёт границ только я не знаю как это сделать ((
Проблема здесь:
Код:
for ( i = 0 ; i < m ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
if( (i==0) && (j==0) && (a[j]<a[j+1]) && (a[j]<a[i+1][j]) && (a[j]<a[i+1][j+1]) )
loc_min = loc_min + 1;
else
if( (a[j]<a[i-1][j-1]) && (a[j]<a[i-1][j]) && (a[j]<a[i-1][j+1]) && (a[j]<a[j-1]) && (a[j]<a[j+1]) && (a[j]<a[i+1][j-1]) && (a[j]<a[i+1][j]) && (a[j]<a[i+1][j+1]))
loc_min = loc_min + 1;
}
}
Всего может быть 9 вариантов, когда у клетки может быть разное число и расположение соседних клеток: 4 – проверяемая клетка находится на одном из углов (и имеет 3 соседних), 4 – клетка находится на краю, но не на углу (имеет 5 соседних), и еще один – клетка находится не на углу и не на краю (8 соседних). У вас реализовано так, как будто есть всего 2 варианта. Если действовать тем, способом, какой вы пытаетесь использовать, то нужно рассматривать все 9 вариантов, что-то вроде такого:
Код:
for ( i = 0 ; i < m ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
if( i == 0)
{
if( j == 0)
{
if( (a[j]<a[j+1]) && (a[j]<a[i+1][j]) && (a[j]<a[i+1][j+1]) )
loc_min = loc_min + 1;
}
else if( j == n – 1)
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
else // случай когда j > 0 && j < n – 1
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
}
else if( i == m – 1)
{
if( j == 0)
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
else if( j == n – 1)
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
else // случай когда j > 0 && j < n – 1
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
}
else // случай когда i > 0 && i < m – 1
{
if( j == 0)
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
else if( j == n – 1)
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
else // случай когда j > 0 && j < n – 1
{
if( /*условие*/ )
loc_min = loc_min + 1;
}
}
}
}
Конечно можно написать хитрую проверку, учитывающую нахождение на краю, но это немного затормозит анализ.
Попытался сделать пример такой хитрой проверки:
Код:
for ( i = 0 ; i < m ; i++ )
for ( j = 0 ; j < n ; j++ )
{
bool is_loc_min = true;
for ( int i1 = i – 1; i1 <= i + 1 && is_loc_min; ++i1 )
for ( int j1 = j – 1; j1 <= j + 1 && is_loc_min; ++j1 )
if(i1 >= 0 && i1 < m && j1 >= 0 && j1 < n && !(i1 == i && j1 == j))
is_loc_min = a[j] < a[i1][j1];
if(is_loc_min)
++loc_min;
}
Форум программистов Vingrad
Модераторы: Daevaorn |
Поиск: |
|
Локальный минимум |
Опции темы |
X |
|
||
Unregistered
|
Всем привет! |
||
|
|||
blackofe |
|
||||
Бывалый Профиль Репутация: 4
|
навскидку.
идея простая: перебрать все элементы и каждый проверить на вшивость – является ли он локальным минимумом (по ходу дела проверяя выход за границы массива). результат работы программы:
не отрицаю наличия более красивого решения. очень спешил . Это сообщение отредактировал(а) blackofe – 9.12.2005, 02:19 |
||||
|
|||||
sergejzr |
|
||
Un salsero Профиль
Репутация: 19
|
Грубо говоря у нас 8 соседей (исключения – значения на границах)
Тут код можно упростить в некоторых местах, где проверки частично совпадают, но это для ярых оптимизаторов ——————– О чём пел В.Высоцкий. |
||
|
|||
X |
|
||
Unregistered
|
Спасибо большое буду разбираться!!! |
||
|
|||
sergejzr |
|
||
Un salsero Профиль
Репутация: 19
|
Вот, товарищ опередил Это конечно не алгоритм, а перебор. Если у тебя массив представляет собой двумерную функцию, существуют более “быстрые” алгоритмы поиска локальных минимумов. Почти все представляют собой спуск в обратном направлении градиента. Разница в основном в нахождении оптимальной ширины шага. ——————– О чём пел В.Высоцкий. |
||
|
|||
X |
|
||
Unregistered
|
sergej.z мне необходимо только это:
проверили границы и соседей, а потом что? Как найти кол-во лок. минимумов? Объясни поподробнее плиз |
||
|
|||
sergejzr |
|
||
Un salsero Профиль
Репутация: 19
|
Дальше разбирать не буду. И так уже достаточно подробно.
——————– О чём пел В.Высоцкий. |
||
|
|||
blackofe |
|
||
Бывалый Профиль Репутация: 4
|
sergej.z про “закрашивание” мысль хорошая. усложнило бы алгоритм (это ж их запоминать надо, или делать “слепок” матрицы с “закрасками”), но повысило бы эффективность. |
||
|
|||
sergejzr |
|
||
Un salsero Профиль
Репутация: 19
|
Если построчно проверять, то конечно “прошедшие” уже не надо проверять будет. то есть проверка только один раз каждого квадрата. Кстати, есть алгоритм для игры в “кораблики”? ИМХО – сюда бы точно подошёл ) Конечно при случайно разбросанных кораблях – тяжело, но кое какие оптимизации при закрашивании можно сделать.. ——————– О чём пел В.Высоцкий. |
||
|
|||
blackofe |
|
||
Бывалый Профиль Репутация: 4
|
sergej.z |
||
|
|||
|
Правила форума “С++:Общие вопросы” | |
|
Добро пожаловать!
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) |
0 Пользователей: |
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема » |
const n_max=100; type matr=array [1..n_max,1..n_max] of integer; var a:matr; j,i,k,n:integer; function LocMin(var i,j:integer;a:Matr):boolean; begin LocMin:=((i=1)or(a[i,j]<a[i-1,j]))and ((j=1)or(a[i,j]<a[i,j-1]))and ((i=10)or(a[i,j]<a[i+1,j]))and ((j=10)or(a[i,j]<a[i,j+1])); end; begin randomize; write('razmer matricy',' n='); readln(n); for i:=1 to n do begin for j:=1 to n do begin a[i,j]:=random(20)-5; write(a[i,j]:4); end; writeln; end; writeln; k:=0; for i:=1 to n do for j:=1 to n do if LocMin(i,j,a)then begin k:=k+1; writeln('Локальный минимум: ',a[i,j],', в строке: ',i,', в столбце: ',j); end; writeln; writeln('Kolichestvo lokalnyh minimumov k=',k); readln; end.