Вторник, 21.08.2018, 03:45Главная | Регистрация | Вход

Форма входа

Поиск

Наш опрос

Кто по вашему мнению лучший куратор комнаты?
Всего ответов: 32

Статистика

Три задачи по программированию, которые потрясли мой мозг - Простор для общения ЛНШат
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: Геральт, Katie  
Простор для общения ЛНШат » Учеба...Учеба...Учеба » Форум дружеской помощи в учебе » Три задачи по программированию, которые потрясли мой мозг (Программисты, где вы!)
Три задачи по программированию, которые потрясли мой мозг
KatieДата: Понедельник, 25.02.2008, 20:44 | Сообщение # 1
Мастер
Группа: Преподаватели
Сообщений: 129
Репутация: 12
Статус: Нет на форуме
Вот такие вот задачки, для которых надо предложить алгоритм решения.

1. Дан массив из N элементов, в котором произвольным образом распиханы числа от 1 до N включительно. Затем берут произвольное число х из того массива и меняют его на у. В результате в массиве оказывается два раза у и ни разу х. За О(N) операций найти х и у.

2. Дан массив из нескольких действительных чисел. Можно суммировать числа, стоящие в этом массиве подряд. Найти максимальную такую сумму за 1 проход массива.

3. Дана таблица N на N. В ней числа убывают по строкам и по столбцам (сверху вниз и слева направо). Известно, что в таблице есть число х. Найти то число за O(N) операций.


Все, что есть хорошего в жизни - либо незаконно, либо аморально, либо ведет к ожирению...
 
ЭрастДата: Понедельник, 25.02.2008, 23:21 | Сообщение # 2
Великий магистр
Группа: Преподаватели
Сообщений: 135
Репутация: 9
Статус: Нет на форуме
Третья - это, кажется, просто. У меня похожая задача возникла в рамках научной работы в прошлом году, только таблица была не квадратная.
Начни, например, спускаться по последнему столбцу, пока не найдешь x или не проскочишь. Если только видишь, что проскочила, идешь влево до первого числа больше x. С него опять начинаешь спускаться, и т.д. O(N).

Добавлено (25.02.2008, 23:14)
---------------------------------------------
Вспомнил вторую. Это вообще-то очень известная задача по программированию, просто я после 12 часов непрерывного проганья туго соображаю. Да и вообще она больше по математике задача.
Надо просто идти по массиву и суммировать все подряд. В процессе суммирования надо смотреть на экстремумы получающейся суммы и места, где они встретились. Самое крутое сочетание инфимума и идущего за ним экстремума и даст ответ - максимальная сумма между ними. Во время работы программа должна помнить лучшую пару инфимум-супремум (изначально обе величины равны первому встречному положительному числу, дальше по обстановке) и координаты инфимума-кандидата (абсолютно лучший инфимум, который встретился после экстремума из лучшей на данный момент пары, имеет шанс стать началом бОльшей суммы).

Добавлено (25.02.2008, 23:21)
---------------------------------------------
Первая. Не знаю, есть ли в ней еще какие-либо ограничения. Если нет, то за 1 проход массива считаем сумму всех элементов С и произведение П. Потом из С вычитаем N(N+1)/2, а произведение делим на N! Обнаруживаем, что
С = y - x
П = y/x.
Решаем систему. ;-)


Мы могли бы играть в разведку,
мы могли бы служить в кино,
но идем собирать объедки.
Нам теперь уже все равно.
 
KatieДата: Вторник, 26.02.2008, 11:33 | Сообщение # 3
Мастер
Группа: Преподаватели
Сообщений: 129
Репутация: 12
Статус: Нет на форуме
Quote
Не знаю, есть ли в ней еще какие-либо ограничения.

В том-то и дело, что ограничение на разумность есть:)
То есть посчитать сумму мы можем, а вот произведение быстро начнет обламываться. Был еще вариант во второй задаче просуммировать логарифмы, но тогда начнет обламываться точность вычислений.
Задавший ее препод намекнул, что есть решение "которое очевидно свободно от всяких подобных нюансов"...
-----------
А по поводу 3-ей - можно ли сделать это за N операций? или за N+c, где с от N не зависит?


Все, что есть хорошего в жизни - либо незаконно, либо аморально, либо ведет к ожирению...
 
ErДата: Вторник, 26.02.2008, 13:05 | Сообщение # 4
Злостный преп
Группа: Преподаватели
Сообщений: 52
Репутация: 6
Статус: Нет на форуме
Первая задача. Если нет ограничений на использование удобных структур данных, то её можно решить так.
1. Считаем сумму чисел от 1 до N = N(N+1)/2
2. Проходим по массиву, и пытаемся добавить в созданный ранее словарь (Dictionary в C#, std::map, насколько я помню, в C++) пару, ключом которой является очередной элемент массива (число), а значением - пофиг что. Как только нам не удается добавить элемент - мы нашли y. Запоминаем его и проходим массив до конца. При прохождении массива считаем сумму S добавляемых в словарь ключей.
3. x = N(N+1)/2 - S

В общем, удалось обойтись лишь подсчетом сумм (хотя этот способ не такой красивый, как решение системы уравнений). Вместо словаря может использоваться любой список, в котором элементы уникальны.

Добавлено (26.02.2008, 12:49)
---------------------------------------------
Правда ,я хз, какая сложность у алгоритма добавления элемента в словарь:)

Добавлено (26.02.2008, 13:05)
---------------------------------------------
По поводу третьей. За именно N или N+C операций в общем случае, наверное, не удасться сделать, т.к. начинаем мы из любого угла, а объект поиска может находиться в противоположном (по диагонали) углу. Соответственно, чтобы до него добраться, потребуется 2N переходов (сложность все ещё O(N)).


Think for yourself. Question authority.
 
ЭрастДата: Вторник, 26.02.2008, 21:47 | Сообщение # 5
Великий магистр
Группа: Преподаватели
Сообщений: 135
Репутация: 9
Статус: Нет на форуме
По поводу первой задачи. Так никто тебя не заставляет считать факториал отдельно (можно, конечно, и считать, но тогда придется писать функции умножения/деления чисел произвольной длины. Поскольку в конечном итоге тебе нужно не произведение, а произведение, деленное на факториал (причем не обязательно деленное очень точно, вполне достаточно, чтобы несколько первых значащих цифр были верными), можно умножать и делить одновременно, что существенно повышает живучесть алгоритма. А вообще, скорее всего, если решение с произведением не подходит, задача сводится к замене его на какую-то другую функцию, обладающую подобным свойством, искать которую мне, честно говоря, лень. Произведение я привел просто для примера и понимаю, что факториал считать сложно.
Решение со словарем мне не особо понравилось, потому что с тем же успехом можно со старта завести массив [N] и отмечать в нем, какие числа уже встретились. Можно и сумм никаких не считать, а потом пройти вспомогательный массив еще раз и посмотреть, что встретилось дважды - O(N) от этого не нарушится. Согласен с Егором, что про то, что так делать нельзя, в задаче ничего не сказано. Да и вообще по условию довольно сложно понять, чего все-таки хочет автор.

Добавлено (26.02.2008, 16:52)
---------------------------------------------
P.S. Я тут посмотрел - если просто делить параллельно умножению (т.е., умножив на первое число, делить результат на 1, потом на 2 и т.д.), алгоритм работает нормально (ошибка меньше 0.2) до N порядка 1000 даже на "подлом" примере (когда исходный массив записан как 1000, 999, 998... 1). Вопреким моим ожиданиям, изменение порядка деления (я борьбы с "подлыми" исходными данными я пробовал делить на 1, 1000, 2, 999, 3, 998 и т.д.) не дает существенного выигрыша: 10000 "не вытягивается". Самые неприятные значения x и y - наибольшие (близкие к N). Для больших N надо программировать на ReXXе, где есть оператор NUMERIC DIGITS, который можно поставить в сколько угодно. :-) Либо использовать long double на C. Но это все шутки, на самом деле я думаю, что задача все же на то, чтобы какую-нибудь функцию поинтереснее найти.

Добавлено (26.02.2008, 21:47)
---------------------------------------------
P.P.S. Вы будете смеяться, но "нахаляву" решить ее лучше, чем с подсчетом произведения, не удается. Я тут прикола ради попробовал посмотреть разные функции. Например, красиво получается, если вместо произведения складывать квадраты:
x=П/(2С)-С/2
y=x+С
Но при 9 значащих цифрах эта функция тоже, естественно, N=10000 не вытянет. В качестве забавного изврата можно складывать логарифмы - тогда
x=С/(e^П-1)
y=С+x!!!
e^П - это e в степени "русская П", а не Пи!!! К сожалению, решения быстро разваливаются, т.к. логарифмы считаются с большой погрешностью, а то красиво выглядит. Чтой-то мне это все башню и барометр напоминает...
А произведение описанным выше способом считать лучше, т.к. это единственный способ, который, даже "развалившись", дает неточные решения, в принципе более или менее близкие к истинным.

Quote (Эраст)
где есть оператор NUMERIC DIGITS

"Не спеши решать поставленную задачу - подожди, может быть, появятся язык или программная среда, в которой они решаются одним оператором." © Очков, Пухначев - "128 советов начинающему программисту". Вроде и столько лет прошло, и книга написана про программирование на Бейсике, а актуальность не теряется. :-]


Мы могли бы играть в разведку,
мы могли бы служить в кино,
но идем собирать объедки.
Нам теперь уже все равно.


Сообщение отредактировал Эраст - Вторник, 26.02.2008, 16:07
 
ErДата: Среда, 27.02.2008, 16:27 | Сообщение # 6
Злостный преп
Группа: Преподаватели
Сообщений: 52
Репутация: 6
Статус: Нет на форуме
Quote (Эраст)
"Не спеши решать поставленную задачу - подожди, может быть, появятся язык или программная среда, в которой они решаются одним оператором." © Очков, Пухначев

Бугага. Товарищ Очков ведь шутил, когда такое написал?..

ЗЫ. Ну не люблю я русских аффтаров, ох не люблю!...


Think for yourself. Question authority.
 
ЭрастДата: Среда, 27.02.2008, 17:25 | Сообщение # 7
Великий магистр
Группа: Преподаватели
Сообщений: 135
Репутация: 9
Статус: Нет на форуме
Quote (Er)
Бугага. Товарищ Очков ведь шутил, когда такое написал?..

Шутил. При этом, правда, особо отмечая, что в каждой щутке доля правды.

Авторы, помнится, придумали ряд операторов Бейсика SWITCH OFF ..., выключающих периферию и компьютер. Все железо в те годы выключалось огромными тугими клавишами и о APM/ACPI , думаю, очень мало кто задумывался. ;-)

Quote (Er)
Ну не люблю я русских аффтаров, ох не люблю!...

Я не люблю не русских авторов вообще, а распространенную, к сожалению, манеру писать книги с модными словами в названии, не имея представления о теме. Помню, был какой-то герой, добившийся особых успехов на этом поприще (он еще учебник по C++ написал), я его успешно забыл. Это свойство, IMHO, связано с тем, что компьютеры в России получили повсеместное распространение после ее образования - когда "урви побольше и побыстрее не важно как" стало нормой общественной морали - а на компьютерной литературе как раз заработать можно было очень неплохо; соответственно, на качество никто внимания не обращал. Не буду утверждать, что этот период закончился (я "компьютерных" книжек не читаю никаких авторов, ни наших, ни не наших), хотя по отзывам друзей мне кажется, что в последнее время стало лучше. А Очков и Пухначев писали в Советском Союзе до того, как все это началось.


Мы могли бы играть в разведку,
мы могли бы служить в кино,
но идем собирать объедки.
Нам теперь уже все равно.
 
ErДата: Пятница, 29.02.2008, 14:52 | Сообщение # 8
Злостный преп
Группа: Преподаватели
Сообщений: 52
Репутация: 6
Статус: Нет на форуме
Хм, приятно постигать неизвестные ранее стороны...

Think for yourself. Question authority.
 
Простор для общения ЛНШат » Учеба...Учеба...Учеба » Форум дружеской помощи в учебе » Три задачи по программированию, которые потрясли мой мозг (Программисты, где вы!)
  • Страница 1 из 1
  • 1
Поиск:

Copyright MyCorp © 2018 | Хостинг от uCoz