Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Цікаві задачі
Сторінки Попередня 1 … 4 5 6 7 8 … 20 Наступна
Для відправлення відповіді ви повинні увійти або зареєструватися
взагалі то суть черги і стеку і тому подібне в тому, що в неї стають/добавляються коли приходять, а не тоді коли в ній є вільне місце, і виходять/обслуговуються, тоді коли є ресурси для обробки.
умовно кажучи якщо ви читаєте з черги зі швидкістю 1 елемент в хвилину, то за цю хвилину в вас можуть прийти нові елементи які потрібно поставити в кінець черги. Тобто потрібно мати переривання на запис, який буде переключати переганяючи стеки туди сюди конструкцію з читання на запис.
Задача.
40 піратів ділять ящик з золотом,вони сидять в крузі.
Кожен четвертий вбиває себе і виходить з черги.
Ввести номер пірата,з якого починається черга (від 1 до 40).
Вивести номер пірата,який залишиться. Якому і дістанеться золото 
.
Завдання виконати без бд та файлів.
http://uk.wikipedia.org/wiki/Задача_Йосифа_Флавія
Завдання виконати без бд та файлів.
Як на мене, цікавіше тут - як використати бд чи файли для обчислення цієї формули...
Vtrim
Красти в Йосипа Флавія і Кнута завдання некрасиво. Ви тепер для мене гірше за Пугачову і Кобзона разом узятих.
Vtrim
Красти в Йосипа Флавія і Кнута завдання некрасиво. Ви тепер для мене гірше за Пугачову і Кобзона разом узятих.
Ви так написали,наче я вкрав чийсь код і видав за свій. P.s побачив цю задачу на одному з ру форумів,переклав сюди,тому ні про яких Флавіів та Кнутів і близько не чув:)
взагалі то суть черги і стеку і тому подібне в тому, що в неї стають/добавляються коли приходять, а не тоді коли в ній є вільне місце, і виходять/обслуговуються, тоді коли є ресурси для обробки.
умовно кажучи якщо ви читаєте з черги зі швидкістю 1 елемент в хвилину, то за цю хвилину в вас можуть прийти нові елементи які потрібно поставити в кінець черги. Тобто потрібно мати переривання на запис, який буде переключати переганяючи стеки туди сюди конструкцію з читання на запис.
Не зрозумів як це пов'язано з тим, щоб не повертати елементи до першого стеку. Наведіть use-case коли відбувається помилка.
хм...
Я напевно не правильно зрозумів ваше перше повідомлення, Тобто ви пропонуєте використовувати перий стек як буфер запису, другий стек як буфер читання. Коли буфер читання порожній, то переганяємо в нього весь буфер запису, так?
Так напевно буде працювати. Я чогось був зациклився на думці, що всю чергу треба тримати в одному місці.
VTrim,
потренуйтесь на менших цифрах.
візьмем 5 і кожен 3-й
1234512452424
6 І 3
1234561245125151
Введіть у стек послідовність символів.Вилучіть з цієї послідовності всі літери "а".
Введіть у стек послідовність символів.Вилучіть з цієї послідовності всі літери "а".
Чому ви серед цих трьох задач
Розмістили в даній темі тільки цю задачу?
чи інші задачі менш цікаві?
ihor102 написав:Введіть у стек послідовність символів.Вилучіть з цієї послідовності всі літери "а".
Чому ви серед цих трьох задач
▼Прихований текстРозмістили в даній темі тільки цю задачу?
чи інші задачі менш цікаві?
Мені ця саме більше чомусь сподобалась.
два рядочки напишіть хоть як то робиться я далі вже найду як зробити.
Введіть у стек послідовність символів.Вилучіть з цієї послідовності всі літери "а".
Придумайте цікаве формулювання для цієї задачі, тоді ми вам допоможемо.
Знайти кількість цифр в числах від 1 до n зі складністю алгоритму O(1).
Знайти кількість цифр в числах від 1 до n зі складністю алгоритму O(n).
Я не дуже розумію, що таке "O(n)" (мабуть функція від n), але..
В числах від 1 до 1234 ви знайшли всього 4 цифри?
І, вибачте, описався зі складністю, зараз виправлю.
Короткий лікнеп: складність O(n) означає, що зі зростанням n час роботи програми зростатиме пропорційно n (точніше, лінійно, але для великих n це несуттєво). Наприклад, якщо там є цикл до n.
Складність O(1) означає, що час роботи алгоритму константний.
Можете для простоти вважати, що на 1000 питань про числа від 1e9 до 2e9 ця програма відповість за 1с.
O(log(n))
http://ideone.com/XeJDpB
Оце-так-так. Не встиг побити O(n), як уже треба O(1).
Ви на вірному шляху. Лишилося трохи посидіти над папером і знайти лінійну формулу для суми в циклі (знадобиться формула суми геометричної прогресії і трохи фантазії).
Треба уточнити правила гри. От пробував я крутити ось цю формулу:
s = (9 + 90*2+900*3+...+9n*10^(n-1))
Вона зводиться до такої:
s = n*10^n - число_що_складається_з_(n-1)_одиничок
Обидва доданки мають логарифмічну складність, проте перший скоріше всього законний (я сумніваюсь, що ваша формула не містить піднесення до n-ної степені), а другий — ні. В такому разі я не бачу сенсу в подальшій оптимізації.
Якщо вважати піднесення до степеня складною операцією, то логарифм також не за один такт обчислюється. Звісно, операції FPU слід вважати за одну операцію кожну - там логарифм і піднесення в степінь по одному разу виходять.
А формула схожа, але трохи не така.
