Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Цікаві задачі
Сторінки Попередня 1 … 7 8 9 10 11 … 20 Наступна
Для відправлення відповіді ви повинні увійти або зареєструватися
Знайти [formula](x^x)'[/formula] і [formula]\int \ln x dx[/formula]
Де тут момент цікавості?
Гадав, що в першому потрібно використати логарифмічне диференціювання, що й запропонував koala, а в другому іншу техніку. Радий, що для вас це за виграшки. Наведіть приклад, що для вас цікаво.
Гадав, що в першому потрібно використати логарифмічне диференціювання, що й запропонував koala, а в другому іншу техніку. Радий, що для вас це за виграшки. Наведіть приклад, що для вас цікаво.
Ви можете полистати цю тему, побачите, які задачі зацікавили форумчан.
Інтеграл можна взяти вручну, але навіть якби не можна було, то застосувавши ЧМО (чисельні методи обчислення) його можна досить просто порахувати в певних межах. Це нецікаво.
Цікаво придумувати свій алгоритм і потім втілювати його.
А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.
А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.
quez написав:А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.
А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.
За математику Нобелівську премію не дають, але за таку задачу можна і дати.
Yola написав:quez написав:А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.
А ось і ні. От вам і цікава задача, щоб знайти розв'язок за квадратичний час.
За математику Нобелівську премію не дають, але за таку задачу можна і дати.
Здаєтесь? 
Якщо не буде відповіді за 24 години, то я напишу.
Здаюсь. А у вас таки є розв’язок?
Довів до 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 пам'яті.
Довів до O(n^2log(n)):.
Дуже схоже на варіант, що придумав я, але є квадратичний алгоритм, який втім, вимагає певної іскорки ну і практики в алгоритмах. Завтра зранку напишу.
Поки що дам підказку.
У зовнішньому циклі проходяться всі елементи множини, у внутрішньому (while) шукається двійка інших чисел, щоб доповнити до нуля. Додаткова пам'ять - O(1).
Як у відсортованому масиві знайти двійку чисел сума яких задана?
А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?
2. Будуємо відсортований масив сум n1+n2 ( O(n^2*log(n)) операцій - злиття n впорядкованих масивів, n^2 пам'яті) - найважча операція; мені здається, що її можна якось оптимізувати, але поки нічого принципового не придумав.
Мабуть можна, адже ви знаєте різницю [formula]n_i-n_j[/formula] - між двома твірними елементами масивів. Фактично, один з масивів, то зсунутий інший.
А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?
Знайти 3 елементи масиву із сумою 0, звісно.
А можна саму задачу, а то Yola задав одну, я подумав про другу, а koala розв’язує третю?
Є масив з чисел, виявити три числа з масиву які в сумі дають 0. Якщо вони там є. В англомовній літературі задача відома як 3SUM.
Так не чесно, я тепер подивився
На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.
На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.
Центр вписаного кола, це не цікава задача, imho.
Yola написав:На площині відомі позиції (x,y) 3 людей. Знайти точку таку, що сума відстаней від неї до кожної людини найменша.
Центр вписаного кола, це не цікава задача, imho.
Точка Ферма - не центр вписаного кола, imho.
Знайти k-й найбільший елемент у незростальній купі (MaxHeap) за [formula]O(\log(n)).[/formula]
[formula]k \ll n.[/formula]
ВІДРЕДАГОВАНО:
Оскільки більше доби відповіді немає, то відповідаю я:
Необхідно k разів виконати Extract_Max, часова складність [formula]\textit{k}\log(n) = O(\log(n)).[/formula]
А як виконати попереднє завдання за [formula]\textit{k}\log k?[/formula]
