261

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

0x9111A написав:
Master_Sergius написав:

Пора оживити хоч якусь програмістську тему, а то скоро вже тут не буде що робити.
Отже для розминки простенька задача (була на одній Всеукраїнській олімпіаді років з 10 тому):

Дано текстовий файл у якому записані через пробіл послідовні натуральні числа, але не по порядку. Одне із чисел відсутнє. Визначити це число не використовуючи масиви та додаткові файли.

Приклад вхідних даних:
3 1 4 6 5

Приклад вихідних даних:
2

Наступний рівень
Та сама ситуація, але немає двох чисел
"Найкраще" рішення працює за лінійний час і з константною пам’яттю

А два рази пройтись по вхідним даним можна? Це буде 2N, тобто лінійний час. Бо більше не бачу варіантів :)

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: koala, 221VOLT2

262

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

quez написав:
Прихований текст
1. Від суми всіх натуральних чисел від 1 до n віднімаємо суму всіх наявних чисел, отримуємо суму двох відсутніх.
2. Добуток всіх натуральних чисел ділимо на добуток наявних чисел, отримуємо добуток відсутніх.
3. Отримуємо систему x + y = a; x*y = b; розв'язуємо її, отримуємо x та y

Хороше рішення, але продовжуємо боротьбу (є краще рішення)

Без довгої арифметики, факторіал дуже швидко переповнить стандартний тип

Maybe a = Just a | Nothing
Подякували: 221VOLT1

263

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

Master_Sergius написав:

А два рази пройтись по вхідним даним можна? Це буде 2N, тобто лінійний час. Бо більше не бачу варіантів :)

Можна чого ж ні, але що робити ті два рази?
Хешувати не підходить бо пам’ять не константна

Maybe a = Just a | Nothing

264

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

Не втримався і погуглив :)
Але все одно цікаво чи ті операції не будуть важчі за два проходи (хоча все залежить від довжини масиву). Однак, задача цікава, дійсно.

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: 221VOLT1

265

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

Master_Sergius написав:

Не втримався і погуглив :)
Але все одно цікаво чи ті операції не будуть важчі за два проходи (хоча все залежить від довжини масиву). Однак, задача цікава, дійсно.

Мені здається, що ми ймовірно знаємо різні рішення  :)
Це ви про які операції?

Maybe a = Just a | Nothing
Подякували: 221VOLT1

266

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

0x9111A написав:
Master_Sergius написав:

Не втримався і погуглив :)
Але все одно цікаво чи ті операції не будуть важчі за два проходи (хоча все залежить від довжини масиву). Однак, задача цікава, дійсно.

Мені здається, що ми ймовірно знаємо різні рішення  :)
Це ви про які операції?

Див. під спойлер:

Прихований текст
Потрібно також рахувати суму квадратів чисел. В результаті отримуємо звичайну різницю сум і різницю сум квадратів. Рішення зводиться до ровзязання системи з двох рівнянь і двох невідомих.
Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: 221VOLT1

267

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

Master_Sergius написав:
Прихований текст
Потрібно також рахувати суму квадратів чисел. В результаті отримуємо звичайну різницю сум і різницю сум квадратів. Рішення зводиться до ровзязання системи з двох рівнянь і двох невідомих.

Рішення має таку ж проблему як і рішення quez'a, тобто це не найкрще що можна придумати
Найоптимальніше рішення дуже "елегантне" як на мене

Maybe a = Just a | Nothing
Подякували: 221VOLT1

268

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

0x9111A написав:
quez написав:
Прихований текст
1. Від суми всіх натуральних чисел від 1 до n віднімаємо суму всіх наявних чисел, отримуємо суму двох відсутніх.
2. Добуток всіх натуральних чисел ділимо на добуток наявних чисел, отримуємо добуток відсутніх.
3. Отримуємо систему x + y = a; x*y = b; розв'язуємо її, отримуємо x та y

Хороше рішення, але продовжуємо боротьбу (є краще рішення)

Без довгої арифметики, факторіал дуже швидко переповнить стандартний тип

Спробував замінити множення на xor, виходить (a - x) xor x = b. Як його розв'язувати - біс його знає.

МАКЕ ЦКЯАІИЕ БЯЕАТ АБАІИ
Подякували: 0x9111A, 221VOLT2

269

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

Прихований текст
Подякували: 221VOLT1

270

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

Для другої -

Прихований текст
логарифми факторіалів мають працювати.
Подякували: 0x9111A, 221VOLT2

271

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

koala написав:

Для другої -

Прихований текст
логарифми факторіалів мають працювати.

Цікава ідея
Але я досі надіюсь що хтось дійде до гарного рішення за два проходи, без "систем рівнянь"

Maybe a = Just a | Nothing
Подякували: 221VOLT1

272

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

0x9111A написав:
koala написав:

Для другої -

Прихований текст
логарифми факторіалів мають працювати.

Цікава ідея
Але я досі надіюсь що хтось дійде до гарного рішення за два проходи, без "систем рівнянь"

Отже, мій перший здогад за 2 проходи був вірним! Вмієте збити з пантелику. Ось алгоритм:

Прихований текст
Перший прохід - так само рахуємо суму. Визначаємо різницю. Другий прохід - рахуємо суму лише парних або непраних чисел, що менші за отриману різницю. Таким чином ми однозначно будемо знати якого парного чи непарного числа немає. А відтак віднімаючи його від отриманої різниці матимемо ще й друге.
Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: 0x9111A, 221VOLT2

273 Востаннє редагувалося 0x9111A (20.02.2017 15:41:36)

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

Master_Sergius написав:

Отже, мій перший здогад за 2 проходи був вірним! Вмієте збити з пантелику. Ось алгоритм:

Прихований текст
Перший прохід - так само рахуємо суму. Визначаємо різницю. Другий прохід - рахуємо суму лише парних або непраних чисел, що менші за отриману різницю. Таким чином ми однозначно будемо знати якого парного чи непарного числа немає. А відтак віднімаючи його від отриманої різниці матимемо ще й друге.

Це спрацює тільки якщо зниклі числа будуть мати різну "парність" тобто одне парне а друге ні.
Якщо ж обидва парні або обидва непарні то діла не буде
Доречі я коли вирішував то в певний момент теж таку ідею просував

Дати маленьку підказку?

Maybe a = Just a | Nothing
Подякували: 221VOLT1

274

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

0x9111A написав:
Master_Sergius написав:

Отже, мій перший здогад за 2 проходи був вірним! Вмієте збити з пантелику. Ось алгоритм:

Прихований текст
Перший прохід - так само рахуємо суму. Визначаємо різницю. Другий прохід - рахуємо суму лише парних або непраних чисел, що менші за отриману різницю. Таким чином ми однозначно будемо знати якого парного чи непарного числа немає. А відтак віднімаючи його від отриманої різниці матимемо ще й друге.

Це спрацює тільки якщо зниклі числа будуть мати різну "парність" тобто одне парне а друге ні.
Якщо ж обидва парні або обидва непарні то діла не буде
Доречі я коли вирішував то в певний момент теж таку ідею просував

Дати маленьку підказку?

Я ще подумаю )

Мій блог про ОС сімейства *nix - http://nixtravelling.blogspot.com/
Подякували: 221VOLT1

275

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

Люблю подібні задачки, шкода що нових нема, то ж запропоную свою, мені її задавали на першому курсі на контрольну роботу. можливо комусь вона здаватиметься надто простою та типовою але мені вона сподобалась.
Є ряд натуральних чисел, від 1 до n(як показує практика n величиною  більше 10-12 краще не обирати), нехай це будуть числа від 1 до 5. вивести на консоль всі можливі комбінації. числа та комбінації не повторюються.
тобто наприклад

12345
14523
54312
і так далі
11234 буде невірним результатом
12345
12345 також буде невірним результатом якщо комбінація десь повторюватиметься

цей алгоритм можна використовувати не тільки для чисел.

276 Востаннє редагувалося 0x9111A (08.06.2017 17:41:30)

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

Рекурсивно побігати тай готово
Тяжкувато як для першого курсу

упд. а можна й простіше, і правда цікаво

Maybe a = Just a | Nothing

277

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

Це задача на вміння читати документацію до стандартної бібліотеки?
std::next_permutation

278

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

Мова програмування будь яка,  про таку можливість в c++ не знав, писав свій варіант алгоритму

279

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

Можна ще просто цикл з перебором всього що < 55555, і виводом на екран тільки того що підходить. Якщо не хочеться з рекурсією бавитись.
Або якась n-кова система числення, і в ній цикл з викиданням дублів. Але як на мене, то рекурсія краще.