261

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

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

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

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

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

Прихований текст

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

Подякували: 221VOLT1

262

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

Master_Sergius написав:
Прихований текст

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

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

Подякували: 221VOLT1

263

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

0x9111A написав:
quez написав:
Прихований текст

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

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

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

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

Подякували: 0x9111A, 221VOLT2

264

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

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

265

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

Для другої -

Прихований текст

логарифми факторіалів мають працювати.

Подякували: 0x9111A, 221VOLT2

266

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

koala написав:

Для другої -

Прихований текст

логарифми факторіалів мають працювати.

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

Подякували: 221VOLT1

267

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

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

Для другої -

Прихований текст

логарифми факторіалів мають працювати.

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

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

Прихований текст

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

Подякували: 0x9111A, 221VOLT2

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

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

Master_Sergius написав:

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

Прихований текст

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

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

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

Подякували: 221VOLT1

269

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

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

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

Прихований текст

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

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

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

Я ще подумаю )

Подякували: 221VOLT1

270

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

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

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

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

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

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

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

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

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

272

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

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

Подякували: leofun01, Betterthanyou2

273

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

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

274

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

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

275

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

2andnot написав:
Люблю подібні задачки ...

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

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

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

Рішення мовою PHP:

<?php
    function print_all_int_permutations($columns, $maxValue)
    {
        echo 'columns = '.$columns.', maxValue = '.$maxValue." :<br/>\r\n\t";
        for($digits = array_fill(0, $columns, 1), $i = 0; $i >= 0; )
        {
            echo implode(', ', $digits)."<br/>\r\n\t";
            for($i = $columns; --$i >= 0 && ++$digits[$i] > $maxValue; )
                $digits[$i] = 1;
        }
        echo '<br/>';
    }
    print_all_int_permutations(5,5);
?>

В прикріпленому файлі функції f_while і f_for роблять одне й те саме (що і в наведеному тут коді), просто це був такий навчальний приклад для мого знайомого, щоб показати, що while і for працюють однаково.

Post's attachments

index.php_ 1.01 kb, 340 downloads since 2017-10-16 

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

276

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

leofun01 написав:
2andnot написав:
Люблю подібні задачки ...

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

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

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

Рішення мовою PHP:

<?php
    function print_all_int_permutations($columns, $maxValue)
    {
        echo 'columns = '.$columns.', maxValue = '.$maxValue." :<br/>\r\n\t";
        for($digits = array_fill(0, $columns, 1), $i = 0; $i >= 0; )
        {
            echo implode(', ', $digits)."<br/>\r\n\t";
            for($i = $columns; --$i >= 0 && ++$digits[$i] > $maxValue; )
                $digits[$i] = 1;
        }
        echo '<br/>';
    }
    print_all_int_permutations(5,5);
?>

В прикріпленому файлі функції f_while і f_for роблять одне й те саме (що і в наведеному тут коді), просто це був такий навчальний приклад для мого знайомого, щоб показати, що while і for працюють однаково.

Прихований текст

фу, у вас php...

erlang

L = [1,2,3,4,5],
[io:format("~p~p~p~p~p~n",[A,B,C,D,E]) || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A=/=E, B=/=C, B=/=D, B=/=E, C=/=D, C=/=E, D=/=E].
Прихований текст

трошки тупо, проте працює

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

277

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

0x9111A, так який все ж "красивий" розв'язок у пошуку двох відсутніх чисел у два проходи?

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

278

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

koala написав:

0x9111A, так який все ж "красивий" розв'язок у пошуку двох відсутніх чисел у два проходи?

1) Шукаємо суму чисел [1..N] по шкільній формулі і від неї віднімаємо суму вхідного масиву.
На виході сума відсутніх чисел, хай буде (x+y).
2) Оскільки числа не однакові, одне з них буде гаратновано <= (x+y)/2. Менше рівне щоб цілочисельне ділення запрацювало ( (3 + 4) / 2 = 3 ).
3) Використовуючи той самий метод що й у кроці 1, шукаємо x:
Тепер ми знаємо, що одне з чисел в діапазоні [1..(x+y)/2], а друге точно ні. Шукаємо суму чисел [1..(x+y)/2] по шкільній формулі і віднімаємо суму чисел з нашого масиво що підходять в цей діапазон.
4) Як знайти 'у' має бути зрозуміло тим хто дочитав :)

Графоманія

Подякували: koala, 221VOLT2

279

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

Вимоги:
Мова програмування: будь-яка, можна використовувати фреймворкі, бібліотеки, т.д.
Час: 24 хв одна задача (4год для всіх)

A i B

http://не-дійсний-домен/i9/cb6a69c8548fd55c0970e34756aeb7d5/1521584287/422595/1230951/1.jpghttp://не-дійсний-домен/i9/cb6a69c8548fd55c0970e34756aeb7d5/1521584287/422595/1230951/1.jpg

C i D

http://не-дійсний-домен/i9/3e4057b07fcb04b2eb06bd4f2f5cdef6/1521584108/425314/1230951/11.jpghttp://не-дійсний-домен/i9/3e4057b07fcb04b2eb06bd4f2f5cdef6/1521584108/425314/1230951/11.jpg

E i F

http://не-дійсний-домен/i9/3de151f864c9c8bdcc6b1103103c6824/1521584084/308083/1230951/12.jpghttp://не-дійсний-домен/i9/3de151f864c9c8bdcc6b1103103c6824/1521584084/308083/1230951/12.jpg

G i H

http://не-дійсний-домен/i9/6329013d2b98b23763fa592c035a66ca/1521584102/282351/1230951/13.jpghttp://не-дійсний-домен/i9/6329013d2b98b23763fa592c035a66ca/1521584102/282351/1230951/13.jpg

I i J

http://не-дійсний-домен/i9/c3d5175826db83bf2b2ae3774da19e31/1521584130/476027/1230951/14.jpghttp://не-дійсний-домен/i9/c3d5175826db83bf2b2ae3774da19e31/1521584130/476027/1230951/14.jpg

Подякували: 221VOLT1

280

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

Щось не дуже цікаві. Ну, крім, хіба, B - але там всього 1440 комбінацій, перебором легко знайти всі за даний час. І над J треба ще трохи подумати.

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