Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Цікаві задачі
Сторінки Попередня 1 … 5 6 7 8 9 … 20 Наступна
Для відправлення відповіді ви повинні увійти або зареєструватися
І код у вас неправильний, від 1 до 10 11 цифр, а не 10.
Порівняння швидкості: http://ideone.com/Z8MFQw
А ще ваш варіант некоректно працює, якщо n > MAX_INT/10, тому що i*10 стає від'ємним.
Треба уточнити правила гри. От пробував я крутити ось цю формулу:
s = (9 + 90*2+900*3+...+9n*10^(n-1))
Вона зводиться до такої:
s = n*10^n - число_що_складається_з_(n-1)_одиничок
Обидва доданки мають логарифмічну складність, проте перший скоріше всього законний (я сумніваюсь, що ваша формула не містить піднесення до n-ної степені), а другий — ні. В такому разі я не бачу сенсу в подальшій оптимізації.
Це саме той випадок, коли за деревами не видно лісу. Першу формулу я перетворював на таку:
s = 10^n - 1 + (10^(n-1) - 1)*10 + (10^(n-2) - 1)*10^2+...+(10-1)*10^(n-1).
Якщо розкрити дужки, отримуємо
s = n*10^n - 1 - 10 - 100 - ... - 10^(n-1).
З одної сторони, всі доданки, крім першого, і є тим числом_з_n-1_одиничок, а з іншої - це геометрична прогресія, і її сума (10^(n-1) - 1)/(10 - 1). Формула приймає вигляд
s = n*10^n - (10^(n-1) - 1)/(10 - 1)
і обчислюється за константний час.
The previous task provided a way to compute three elements i, j, k of S whose sum is zero—if there exist
three such elements. Suppose you wanted to determine if there were a hundred elements of S whose sum is
zero. What would go wrong if you used the approach used in the previous task? Can you think of a clever
way to quickly and reliably solve the problem, even if the integers making up S are very large?
Зламав собі мозок над цим «clever way», а гуглити не хочеться. Давайте думати разом.
Ну ще непогано би було побачити розвязок попередньої задачі про яку говориться, а потім вже шукати розумний шлях.
А, я думав, що це очевидно. В попередній задачі є масив, потрібно визначити, чи є в ньому три елементи, сума яких дорівнює нулю. Розв’язком були очевидні три вкладені цикли і перевірка суми на нуль всередині.
Ну тобто зовсім не оптимальний шлях) тепер треба знайти оптимальний.
Типу того. Хоча ніколи не подумав би, що є щось краще за Nk для суми k елементів.
Я почав би із сортування. Але навряд чи це б допомогло. Точніше, це б точно не допомогло. Тому ще ця задача NP-повна.
Розглянемо 3 класи задач P, NP, NPC.
Клас P складається із задач, які можна розв'язати за поліноміальний час, тобто час O(nk), де n - розмір вхідних даних, а k це певна стала.
Клас NP складається із задач пропонований розв'язок до яких можна перевірити за поліноміальний час. Наприклад, якщо нам потрібно знайти гамільтонів цикл в орієнтованому графі і нам дана послідовність вершин, то ми легко можемо перевірити чи це дійсно гамільтонів цикл. Тоді як гарантовано знайти цю послідовність за поліноміальний час неможливо. Кожна проблема з P належить також до NP.
Проблема належить до NPC, тобто є NP-повною, якщо вона настільки складна як і будь-яка інша проблема із NP. Тобто, ми можемо звести будь-яку задачу з NP до будь-якої задачі з NPC за поліноміальний час. В якомусь сенсі NPC - найскладніші задачі з NP. Додам, що якщо ви колись знайдете поліноміального часу алгоритм для розв'язання будь-якої з NPC задача, то ви вважайте, що ви ввергли нас усіх у хаос, зруйнували всі криптозахисти і т.п.
Отже, якщо ми знаємо якусь NPC задачу, яку ми можемо за поліноміальний час звести до нашої задачі, то це означає, що або наша задача також не може бути розв'язана за поліноміальний час, або всі NPC задачі можуть бути розв'язані за поліноміальний час, що навряд чи.
Тут ми й згадаємо про задачу про суму підмножини. Яка полягає в данні відповіді на запитання чи є у множини підмножина яка сумується в нуль. І ця задача приналежить до NPC.
Доведення, що цю задачу можна звести до нашої скоріше просте коли очікувана потужність підмножини до 100, тоді ми просто додаємо нулі до множини, і складніше якщо очікувана потужність підмножини більша ніж 100. Але, мені здається, що це воно і той, хто поставив таку задачу, лише хотів подивитись на вашу реакцію.
Значить, лектор на Курсері мене затролив. Сильно, нічого не скажеш.
Прямо там по лінку наведений експонтеціальний алгоритм де O(2N/2)
Прямо там по лінку наведений експонтеціальний алгоритм де O(2N/2)
А ще цей алгоритм використовує принаймні O(2N/2) пам'яті. Як на мене, він не тягне на "clever way".
Прямо там по лінку наведений експонтеціальний алгоритм де O(2N/2)
Для експоненціальних алгоритмів існує спеціальний технічний термін - ПОВІЛЬНІ. Тому ми не беремо їх до уваги. Їх неможливо виконати на комп'ютері для задачі з пристойним розміром вхідних даних. Повний перебір для цієї задачі і буде експоненційним алгоритмом.
Нехай у нас є куб і шість кольорів, скільки варіантів пофарбувати куб у нас є у випадку, якщо всі грані куба між собою однакові, тобто, якщо пофарбування можна отримати з іншого лише обертанням куба, то вони рахуються як одне фарбування.
Нехай у нас є куб і шість кольорів, скільки варіантів пофарбувати куб у нас є у випадку, якщо всі грані куба між собою однакові, тобто, якщо пофарбування можна отримати з іншого лише обертанням куба, то вони рахуються як одне фарбування.
Непофарбовані грані можливі?
А до чого тут C++? Задача на комбінаторику, трохи складніша за базовий рівень.
Непофарбовані грані можливі?
Потрібно використати всі 6 кольорів.
А до чого тут C++? Задача на комбінаторику, трохи складніша за базовий рівень.
Доречі, якщо тут буде проходити модератор, пропоную розглянути пропозицію перенести тему в алгоритми, адже не всі вміють писати на С, кому можуть бути цікавими задачі, які тут розміщуються.
Вважаю, що хто не вміє писати сями, той VTrim про математичні абстракції не знає. Єдине виключення - Чароўны Трусік, але його нема.
