 |
Вітаю Вас, Гість · RSS |
 |
Задачі для початківців з сайту http://netoi.org.ua/
| |
kom_adm |
Дата: Su, 26.09.2010, 22:32 | Повідомлення № 1 |
Ветеран спілкування
Повідомлень: 3767
| Пропоную в даній темі обговорювати оптимальні методи розв’язання задач для початківців, що викладені на сайті http://netoi.org.ua/ На мій погляд чудові задачі для тих, хто тільки починає свій рух в напрямку олімпіадного програмування. До того ж є можливість зразу в он-лайні перевірити задачу. Формат спілкування в цій темі вільний, головне, без особистих образ і приниження учасників форуму. За проявлену відверту зверхність - бан на місяць.
|
|
| |
kom_adm |
Дата: Mo, 18.10.2010, 20:01 | Повідомлення № 31 |
Ветеран спілкування
Повідомлень: 3767
| Щось тема притихла. Спробую оживити Задача Сlock виявилась однією з найцікавіших в розділі "Для початківців". Як виявляється, описаний Юрієм Яковичем спосіб розв’язку не єдиний, мій учень самостійно знайшов ще один спосіб, який на мій погляд 100% правильний, оскільки по-перше, задача проходить перевірку і набирає 20 із 20 можливих балів, по-друге, якщо вважати розв’язок Юрія Яковича за еталон, який видає правильні результати при будь-яких значеннях аргументу, то програма мого учня також видає такі ж результати, оскільки він написав ще одну програму, яка порівнює результати обох сбособів при всіх можливих значеннях аргументу і підраховує кількість неспівпадаючих резульатів. Але таких не виявилося, хоча й в початкових версія програми були. Наводжу код запатентованого Владом :) розв’язку: Code var h, m, rez, x: integer; begin read(h, m); if (h mod 2 = 0) and (h <> 12) then x := 65 else x := 64; h := h * 5; if m > h then h := h + 60; h := h + (h div 11); rez := h - m; if rez > x then rez := rez - (x + 1); write(rez); end. Спробуйте розібратись в ньому самостійно. Нижче наводжу код мого розв’язку, який також проходить тест на валідність і набирає максимальний бал: Code var m, h, rez, i1, i2, t: integer;c, c1, c2, k1, k2, k3, p: real; begin read(h, m); h := h * 5; p := h / 11; k1 := h + p; rez := trunc(k1 - m); k2 := h + m / 12; c := 60 - m + k2 + (60 - m + k2) / 12; c1 := c + (c - (60 - m + k2)) / 12; c2 := c1 + ((c1 - c + (c - (60 - m + k2)) / 12) / 12); if m > h then rez := trunc(c2); write(rez); end. Але моя програма відрізняється від попередньої тим, що не всі результати виявляються правильними. Серед всіх можливих результатів є 25 неправильних, але її можна скоригувати, тоді вона показуватиме правильні результати в 100% випадків. Хочу почути чиїсь коментарі щодо розв’язку і чи зрозумілий він вам? Якщо ні, напишу детальні коментарі через декілька днів. P.S. На останок приводжу код програми, що звіряє резульати способів Пасіхова і Влада. Code var h, m, i1, i2, rez, t, kil, x: integer;f: text; begin assign(f, 'file1.txt'); rewrite(f); for i1 := 1 to 12 do for i2 := 0 to 60 do begin begin h := i1; m := i2; write(f, h, ' : ', m, ' - '); if (h mod 2 = 0) and (h <> 12) then x := 65 else x := 64; h := h * 5; if m > h then h := h + 60; h := h + (h div 11); rez := h - m; if rez > x then rez := rez - (x + 1); write(f, rez, ' / '); end; begin h := i1; m := i2; t := 11 * (60 * h + m) mod 720; if t <> 0 then t := 720 - t; write(f, t div 11, ' ---'); end; if (t div 11) <> rez then begin inc(kil); end else writeln(f, 'результати співпадають'); end; write(f, kil); close(f); end.
|
|
| |
alex |
Дата: Tu, 19.10.2010, 08:14 | Повідомлення № 32 |
Активний учасник
Повідомлень: 586
| Quote (Ковальчук_Олександр) Щось тема притихла. Спробую оживити Через причини, про які говорилось раніше, це навряд чи це буде успішно.
|
|
| |
Bandalak |
Дата: Tu, 19.10.2010, 10:17 | Повідомлення № 33 |
Лідер форуму
Повідомлень: 6386
| Quote (Ковальчук_Олександр) а останок приводжу код програми, що звіряє резульати способів Пасіхова і Влада. Програма реалізовує обидва алгоритми і порівнює результати обчислень? Quote (Ковальчук_Олександр) ка порівнює результати обох сбособів при всіх можливих значеннях аргументу Цікаво, як Ви підбирали всі можливі значення аргументу, щоб врахувати всі можливі випадки? Інколи це буває архіскладно!!!
|
|
| |
kom_adm |
Дата: Tu, 19.10.2010, 13:18 | Повідомлення № 34 |
Ветеран спілкування
Повідомлень: 3767
| Quote (Bandalak) Цікаво, як Ви підбирали всі можливі значення аргументу, щоб врахувати всі можливі випадки? За допомогою циклів (це видно з останньої програми) for i1 := 1 to 12 do for i2 := 0 to 60 do Зовнішній цикл змінює години, внутрішній - хвилини. Спочатку i1 набуває значення 1 і відпрацьовує повністю внутрішній цикл for i2 := 0 to 60 do. Тобто виходить 1 година 1 хвилина, 1 година 2 хвилини і т.д. Потім i1 набуває значення 2 і знову відпрацьовує внутрішній цикл: 2 година 1 хвилина, 2 година 2 хвилина... І кожен раз h та m отримують значення i1 та i2 відповідно. Таким чином розглядаються всі можливі значення аргументів.
|
|
| |
volodschool2 |
Дата: Tu, 19.10.2010, 15:57 | Повідомлення № 35 |
Досвідчений учасник
Повідомлень: 1609
| Quote (Ковальчук_Олександр) for i2 := 0 to 60 do Здається, так буде краще: for i2:=0 to 59 do
|
|
| |
pasichov |
Дата: Tu, 19.10.2010, 20:00 | Повідомлення № 36 |
Наполегливий учасник
Повідомлень: 946
| п. Олександре! Прграма вашого учня працює фактично за тим же алгоритмом, просто дещо по-іншому представлені дані, а отже і іншим "способом" ведуться розрахунки (ІМХО), не дуже зручно, але (ІМХО) ПРАВИЛЬНО!!!! Quote (Ковальчук_Олександр) Але моя програма відрізняється від попередньої тим, що не всі результати виявляються правильними А ось тут вже гносіологічна помилка. З теорії надійності алгоритму слідує, що якщо хоч в одному випадку результат неправильний - алгоритм неправильний. Чіпляння "латок", звичайно, може дати правильний результат, але не може його ГАРАНТУВАТИ. На олімпіадах, на жаль, від учасників не вимагається доведення надійності, а будь-який, самий класний набір тестів перевірку на 100% надійність не гарантує. Це породжує масові "правдоподібні" розв"язки, що масово "гуляють" від книжки до книжки, від олімпіади до олімпіади. Знаю випадок, коли учень на Всеукраїнській олімпіаді отримав 100% балів за задачу, а в поїзді, коли їхали додому, сам знайшов контрприклад, коли його алгоритм давав помилковий результат.... А щодо заачі, слід сказати, що вона з книжки Ставровького та Порубльова "Алгоритми і програми", на це є посилання в дистанційному курсі для учителів, де вона описана мною вперше.
|
|
| |
kom_adm |
Дата: Tu, 26.10.2010, 14:00 | Повідомлення № 37 |
Ветеран спілкування
Повідомлень: 3767
| Задача Bracket Дано алгебраїчний вираз з дужками, записаний одним рядком. Вірно чи не вірно в ньому розставлено дужки? Технічні умови: Програма читає з клавіатури рядок з виразом (не довший за 255 символів) . Програма виводить на екран відповідь в вигляді текстового рядка. Якщо дужки розставлено вірно - друкує слово True, якщо не вірно - Folse Приклад: Введення: (a+b) Виведення: True На мою думку, розв’язок може бути таким (за один прохід): Code program vyraz; var s:string; i,d1,d2,l:byte; rez:boolean; begin read(s); d1:=0; d2:=0; l:=length(s); for i:=1 to length(s) do begin if s[i]='(' then inc(d1); if s[i]=')' then inc(d2); end; if (d1=d2) and ( (s[1]<>')') and (s[l]<>'(') ) then rez:=true else rez:=false; if rez then writeln('True') else writeln('False'); end. Даний розв’язок базується на таких міркуваннях: якщо кількість відкриваючих і закриваючих дужок однакова і перший символ рядка не починається з ")" та останній символ не закінчується на "(", то дужки розставлені правильно, інакше - не правильно.
|
|
| |
alex |
Дата: Tu, 26.10.2010, 14:07 | Повідомлення № 38 |
Активний учасник
Повідомлень: 586
| Quote (pasichov) В курсі, з якого цей розбір, є ще багато цікавих і, головне КОРИСНИХ розібраних задач. Ми з Олександром Івановичем намагалися його провести позаминулим літом для бажаючих учителів. Таких виявилося небагато. Але (хочеться вірити) все-таки комусь це може бути корисно. Отже, якщо когось цікавлять такі задачі: 1. Зареєструватися в системі http://disted.edu.vn.ua 2. Зайти, як зареєстрований користувач, обрати ПОЗАКЛАСНА РОБОТА. ДИСТАНЦІЙНІ КУРСИ=>Методика розв`язування олімпіадних задач з інформатики (для учителів) (Пасіхов Ю.Я. Олійник О.І.) Уроки доступні в послідовності вивчення - кожен наступний після вивчення матеріалу попереднього. Повний розбір задачі для випадку різних типів дужок.
Відредаговано: alex - Tu, 26.10.2010, 14:14 |
|
| |
vitert |
Дата: Tu, 26.10.2010, 14:20 | Повідомлення № 39 |
Тут живе...
Повідомлень: 174
| Quote (Ковальчук_Олександр) Даний розв’язок базується на таких міркуваннях: якщо кількість відкриваючих і закриваючих дужок однакова і перший символ рядка не починається з ")" та останній символ не закінчується на "(", то дужки розставлені правильно, інакше - не правильно. ()))((() - слідуючи вашим міркуванням дужки розставлені правильно Найкраща ідея - перебираємо впідряд всі символи, якщо дужка відкриваюча то збільшуємо лічильник на 1, якщо закриваюча то мінус 1. Якщо в кінці лічильник 0 то TRUE інакше FALSE. Якщо в будь-який момент лічильник <0 то break відповідь FALSE.
|
|
| |
kom_adm |
Дата: Tu, 26.10.2010, 17:59 | Повідомлення № 40 |
Ветеран спілкування
Повідомлень: 3767
| vitert, я зрозумів свою помилку. Просто не врахував того, що дужки в виразі можуть бути розставлені типу ))((, орієнтувався тільки на типову помилку при записі виразів, коли кількість відкриваючих дужок не співпадає з кількістю закриваючих. Але моя програма також набрала максимальний бал Ось програма, що базується на ваші ідеї і враховує всі можливі варіанти: Code program vyraz2; var s:string; i,d,l:integer; rez:boolean; begin read(s); d:=0; l:=length(s); while (d>=0) and (i<=l) do begin i:=i+1; if s[i]='(' then inc(d); if s[i]=')' then d:=d-1; end; if d=0 then rez:=true else rez:=false; if rez then writeln('True') else writeln('False'); end.
|
|
| |
alex |
Дата: Tu, 26.10.2010, 18:58 | Повідомлення № 41 |
Активний учасник
Повідомлень: 586
| Цю задачу краще всього використати для пояснення роботи з використанням організації даних "стек". Для випадку наявності в виразі трьох типів дужок еврістика дає не дуже красивий і зрозумілий розв'язок.
|
|
| |
pasichov |
Дата: We, 27.10.2010, 00:11 | Повідомлення № 42 |
Наполегливий учасник
Повідомлень: 946
| Quote (vitert) Найкраща ідея - перебираємо впідряд всі символи, якщо дужка відкриваюча то збільшуємо лічильник на 1, якщо закриваюча то мінус 1. Якщо в кінці лічильник 0 то TRUE інакше FALSE. Якщо в будь-який момент лічильник <0 то break відповідь FALSE. Quote (alex) Цю задачу краще всього використати для пояснення роботи з використанням організації даних "стек". Насправді описаний лічильник і є найпростішою реалізацією стека. Це найкращий спосіб розі"язати цю задачу. Хоча, якщо дужи різні (, [.{ , то стек буде трішки складнішим... Дійсно, в дистанційному курсі ця задача ДЕТАЛЬНО ОПИСАНА, розглянуто варіанти розв"язку. Я зняв необхідність реєстрації. Пряме посилання: http://disted.edu.vn.ua/courses/learn/1140
Відредаговано: pasichov - We, 27.10.2010, 19:09 |
|
| |
kom_adm |
Дата: Su, 31.10.2010, 19:27 | Повідомлення № 43 |
Ветеран спілкування
Повідомлень: 3767
| Задача NewCircle Дано послідовність цілих чисел. Відрізок послідовності утворюють числа, що йдуть в послідовності підряд. Знайти номери чисел, якими починається і закінчується перший відрізок з максимальною сумою, а також цю суму. Технічні умови. Програма читає спочатку кількість елементів послідовності, а потім саму цю послідовність. Всі числа в одному рядку, їх розділено пропусками. Гарантовано, що послідовність не порожня, і всі розрахунки можна вести в межах типу longint. Програма виводить в один рядок 3 числа через пропуск - номера першого і останнього елемента шуканого відрізка і суму чисел відрізку Приклади Введення 3 -2 -1 0 Виведення 3 3 0 Введення 5 1 2 -3 3 0 Виведення 1 2 3 На мою думку не зовсім зрозуміла умова задачі. Я так розумію, що програма має аналізувати відрізки послідовності - числа, що йдуть підряд, наприклад, 1 2 3... Далі познаходити суму цих відрізків і визначити першу максимальну з них. Результатом виведення будуть перший і останній номер такого відрізка і сума його чисел. Чому 0 розглядається як відрізок, це ж лише одне число? І взагалі -2 -1 0 - хіба це не відрізок. Чи від’ємні числа не розглядаються?
|
|
| |
pasichov |
Дата: Su, 31.10.2010, 23:26 | Повідомлення № 44 |
Наполегливий учасник
Повідомлень: 946
| Quote (Ковальчук_Олександр) На мою думку не зовсім зрозуміла умова задачі. Я так розумію, що програма має аналізувати відрізки послідовності - числа, що йдуть підряд, наприклад, 1 2 3... Далі познаходити суму цих відрізків і визначити першу максимальну з них. Результатом виведення будуть перший і останній номер такого відрізка і сума його чисел. Чому 0 розглядається як відрізок, це ж лише одне число? І взагалі -2 -1 0 - хіба це не відрізок. Чи від’ємні числа не розглядаються? Відрізок послідовності (ЗА УМОВОЮ ЦІЄЇ ЗАДАЧІ) цілі числа, що стоять підряд. Треба знайти початк, кінець першого такого відрізку з масимальною сумою і саму суму. -2, -1, 0 - це відрізок, елементи йдуть підряд, але сума їх -3, а відрізок довжиною в 1 елемент 0 має суму 0, що більше, ніж -3. Так що умова і приклади коректні.
|
|
| |
kom_adm |
Дата: Mo, 01.11.2010, 01:01 | Повідомлення № 45 |
Ветеран спілкування
Повідомлень: 3767
| Quote (pasichov) Відрізок послідовності (ЗА УМОВОЮ ЦІЄЇ ЗАДАЧІ) цілі числа, що стоять підряд. Quote (pasichov) а відрізок довжиною в 1 елемент 0 має суму 0, що більше, ніж -3. Я розумію так, що відрізком послідовності слід вважати мінімум 2 числа, які йдуть підряд, всі інші числа нас не цікавлять. Наприклад, в послідовності 1 2 3 8 10 12 13 є два відрізки: 1 2 3 і 12 13. В іншому випадку до цих двох ще треба враховувати і 8 та 10, тобто матимемо чотири відрізки. Саме це я мав наувазі, що на перший погляд потрібно враховувати за відрізки тільки ті числа, що йдуть підряд (збільшення на 1), але тепер суть задачі зрозуміла. Quote (pasichov) -2, -1, 0 я ці три числа розглядав як одну послідовність і до цих пір не розумію, чому їх слід ділити на 2 послідовності, адже вони йдуть підряд (з кроком збільшення на 1)?
|
|
| |
© Форум інформатиків України, 2007-2022.  |