161

Re: Цікаві задачі

Yola написав:

Знайти [formula](x^x)'[/formula] і [formula]\int \ln x dx[/formula]

Де тут момент цікавості?

Подякували: koala1

162

Re: Цікаві задачі

Гадав, що в першому потрібно використати логарифмічне диференціювання, що й запропонував koala, а в другому іншу техніку. Радий, що для вас це за виграшки. Наведіть приклад, що для вас цікаво.

163

Re: Цікаві задачі

Давайте без офтопу більше. Всі інші повідомлення по темі.

164

Re: Цікаві задачі

Yola написав:

Гадав, що в першому потрібно використати логарифмічне диференціювання, що й запропонував koala, а в другому іншу техніку. Радий, що для вас це за виграшки. Наведіть приклад, що для вас цікаво.

Ви можете полистати цю тему, побачите, які задачі зацікавили форумчан.
Інтеграл можна взяти вручну, але навіть якби не можна було, то застосувавши ЧМО (чисельні методи обчислення) його можна досить просто порахувати в певних межах. Це нецікаво.
Цікаво придумувати свій алгоритм і потім втілювати його.

165

Re: Цікаві задачі

quez написав:

А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.

А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.

166

Re: Цікаві задачі

Yola написав:
quez написав:

А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.

А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.

За математику Нобелівську премію не дають, але за таку задачу можна і дати.

167 Востаннє редагувалося Yola (02.03.2015 20:04:50)

Re: Цікаві задачі

quez написав:
Yola написав:
quez написав:

А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.

А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.

За математику Нобелівську премію не дають, але за таку задачу можна і дати.

Здаєтесь? :)
Якщо не буде відповіді за 24 години, то я напишу.

168

Re: Цікаві задачі

Здаюсь. А у вас таки є розв’язок?

169 Востаннє редагувалося koala (02.03.2015 20:20:20)

Re: Цікаві задачі

Довів до O(n^2log(n)):
1. Сортуємо масив (якщо злиттям, то O(nlog(n)) операцій, n пам'яті)
2. Будуємо відсортований масив сум n1+n2 ( O(n^2*log(n)) операцій - злиття n впорядкованих масивів, n^2 пам'яті) - найважча операція; мені здається, що її можна якось оптимізувати, але поки нічого принципового не придумав.
3. Для кожного n перевіряємо, чи нема у відсортованому великому масиві елементу -n (складність O(nlog(n)), n бінарних пошуків).
Разом O( nlog(n) + n^2*log(n) + nlog(n) )= O( n^2*log(n) ) операцій, n^2 пам'яті.

Подякували: Yola, leofun012

170 Востаннє редагувалося Yola (02.03.2015 20:48:12)

Re: Цікаві задачі

koala написав:

Довів до O(n^2log(n)):.

Дуже схоже на варіант, що придумав я, але є квадратичний алгоритм, який втім, вимагає певної іскорки ну і практики в алгоритмах. Завтра зранку напишу.

Поки що дам підказку.
У зовнішньому циклі проходяться всі елементи множини, у внутрішньому (while) шукається двійка інших чисел, щоб доповнити до нуля. Додаткова пам'ять - O(1).

Як у відсортованому масиві знайти двійку чисел сума яких задана?

171

Re: Цікаві задачі

А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?

172

Re: Цікаві задачі

koala написав:

2. Будуємо відсортований масив сум n1+n2 ( O(n^2*log(n)) операцій - злиття n впорядкованих масивів, n^2 пам'яті) - найважча операція; мені здається, що її можна якось оптимізувати, але поки нічого принципового не придумав.

Мабуть можна, адже ви знаєте різницю [formula]n_i-n_j[/formula] - між двома твірними елементами масивів. Фактично, один з масивів, то зсунутий інший.

173 Востаннє редагувалося koala (02.03.2015 20:57:15)

Re: Цікаві задачі

quez написав:

А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?

Знайти 3 елементи масиву із сумою 0, звісно.

174 Востаннє редагувалося Yola (02.03.2015 20:59:27)

Re: Цікаві задачі

quez написав:

А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?

Є масив з чисел, виявити три числа з масиву які в сумі дають 0. Якщо вони там є. В англомовній літературі задача відома як 3SUM.

175

Re: Цікаві задачі

Так не чесно, я тепер подивився :)

176

Re: Цікаві задачі

На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.

177

Re: Цікаві задачі

Yola написав:

На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.

Центр вписаного кола, це не цікава задача, imho.

Подякували: quez1

178

Re: Цікаві задачі

Chemist-i написав:
Yola написав:

На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.

Центр вписаного кола, це не цікава задача, imho.

Точка Ферма - не центр вписаного кола, imho.

Подякували: Chemist-i, Yola, leofun013

179 Востаннє редагувалося Yola (13.06.2015 11:12:37)

Re: Цікаві задачі

Знайти k-й найбільший елемент у незростальній купі (MaxHeap) за [formula]O(\log(n)).[/formula]
[formula]k \ll n.[/formula]


ВІДРЕДАГОВАНО:
Оскільки більше доби відповіді немає, то відповідаю я:

Необхідно k разів виконати Extract_Max, часова складність [formula]\textit{k}\log(n) = O(\log(n)).[/formula]

180

Re: Цікаві задачі

А як виконати попереднє завдання за [formula]\textit{k}\log k?[/formula]