 |
Вітаю Вас, Гість · RSS |
 |
Задачі для початківців з сайту http://netoi.org.ua/
| |
kom_adm |
Дата: Su, 26.09.2010, 22:32 | Повідомлення № 1 |
Ветеран спілкування
Повідомлень: 3767
| Пропоную в даній темі обговорювати оптимальні методи розв’язання задач для початківців, що викладені на сайті http://netoi.org.ua/ На мій погляд чудові задачі для тих, хто тільки починає свій рух в напрямку олімпіадного програмування. До того ж є можливість зразу в он-лайні перевірити задачу. Формат спілкування в цій темі вільний, головне, без особистих образ і приниження учасників форуму. За проявлену відверту зверхність - бан на місяць.
|
|
| |
alex |
Дата: Tu, 05.10.2010, 07:45 | Повідомлення № 16 |
Активний учасник
Повідомлень: 586
| На мою думку не початку програми елементи масиву потрібно занулити. Можливо помиляюся, але не доводилось читати, що після опису масиву всі його елементи дорівнюють 0. Опис передбачає виділення і поіменування певної ділянки памяті, а що там знаходилось до того не відомо.
|
|
| |
Bandalak |
Дата: Tu, 05.10.2010, 13:22 | Повідомлення № 17 |
Лідер форуму
Повідомлень: 6386
| Quote (alex) а що там знаходилось до того не відомо. Там можуть бути випадкові числа. Але все залежить від компілятора. Деякі компілятори самі автоматично онулюють доступні їм ділянки пам'яті під час запуску програми, а деякі залишають все так як є. Тому крще обнулити самому.
|
|
| |
kom_adm |
Дата: Tu, 05.10.2010, 22:12 | Повідомлення № 18 |
Ветеран спілкування
Повідомлень: 3767
| Задача 4. Vinni Вінні Пух любить складати віршики говорячи речення задом наперед. Якось йому попалось довге складне речення і він забув свій віршик, пробуючи його виговорити. Складіть програму, яка б допомагала ведмедику легко складати такі віршики. Зауваження: віршик може складатись як із 1 слова, так і з декількох, розділених пропусками. Технічні умови. Програма зчитує з клавіатури стрічку-віршик. В кінці віршика ніколи не ставиться крапка. Довжина віршика менша за 255 символів. Програма виводить на екран стрічку, яку отримано внаслідок повороту. На мою думку вся ідея розв’язку зводиться до друкування символів з кінця до початку, використовуючи цикл downto: Code var s:string; i:integer; begin read(s); for i:=length(s) downto 1 do write(s[i]); end. Задача 5. Worms Черв’ячки - цікаві тваринки. Якщо їх залишити вдвох і не турбувати, то через 10 хвилин їх стане четверо, через 20 хвилин – восьмеро, через 30 хвилин – 16 штук. Скільки їх стане через N (N>1) хвилин? Зауваження: на появу нових черв’ячків потрібно рівно 10 хвилин. Всі нові черв’ячки появляються одночасно. Технічні умови. Програма зчитує з клавіатури ціле число N – кількість хвилин. Програма виводить на екран одне ціле число – кількість черв’ячків через вказаний час. Приклад. Введення> 5 Виведення> 2 Введення> 48 Виведення> 32 На мою думку розв’язок може бути таким: початкова кількість черв’яків = 2 (k:=2), кожних 10 хвилин їх кількість збільшується вдвічі (к:=к*2). Але цикл поділу черв’яків триває з 10 по 20, з 20 по 30 хв. і т.д., тобто якщо користувач вводить значення 11-19, то це буде один поділ. Визначити кількість таких поділів можна за формулою n:=n div 10. Якщо, наприклад, було введено значення n, що дорівнює 26, то кількість поділів буде n:=26 div 10 = 2. Код програми: Code var n,i,k:integer; begin read(n); n:=n div 10; k:=2; for i:=1 to n do k:=k*2; writeln(k); end. Задача 6. Nhex Дано число в системі числення з основою m (2≤m≤16) . Написати програму що переводить дане число в систему числення з основою 10. Технічні умови: Програма читає з клавіатури першому рядку число m (основу системи числення), а в другому - текстовий рядок, в якому записано саме число Ch (0≤Ch≤2+109) . Програма виводить на екран відповідь в вигляді десяткового числа. Приклад: Введення: 16 FFFF Виведення: 65535 Для того, щоб перевести число з однієї системи в іншу (в десяткову), потрібно: представити в десятковій системи число Р (основу) та цифрри запису; обчислити суму добутків значень цифр та відповідних степенів числа Р Наприклад: Відповідно ця формула дає можливість написати програму. Ще один момент: оскільки ми вводими дані в стрічку, то текст потрібно перетворити в числа і записати їх в масив. Це можна зробити за допомогою функції Val. Code var m, l, i, code: integer; s: real;ch: string;mas: array[1..999] of integer; begin read(m); read(ch); l := length(ch); for i := 1 to length(ch) do begin l := l - 1; else val(ch[i], mas[i], code); s := s + mas[i] * exp(ln(m) * l); end; write(s); end. Програма буде працювати і видавати результат, коли основа <=10. Якщо основа більша 10, то результат роботи програми буде не правильним. Оскільки, наприклад, в 16 річній системі числення, після цифри 9 ідуть букви А - 10, B - 11 і т.д. і при спробі обчислення суми будуть братися не цифри 10, а окремо 1 і 0. Цього уникнути можна, якщо доповнити програму так: Code var m, l, i, code: integer; s: real;ch: string;mas: array[1..999] of integer;
begin read(m); read(ch); l := length(ch); for i := 1 to length(ch) do begin l := l - 1; if ch[i] = 'A' then mas[i] := 10 else if ch[i] = 'B' then mas[i] := 11 else if ch[i] = 'C' then mas[i] := 12 else if ch[i] = 'D' then mas[i] := 13 else if ch[i] = 'E' then mas[i] := 14 else if ch[i] = 'F' then mas[i] := 15 else val(ch[i], mas[i], code); s := s + mas[i] * exp(ln(m) * l); end; write(s); end. Тепер програма працює начебто коректно, але є одне але: при перевірці он-лайн не проходить тест на валідність. Підкажіть, будь-ласка, в чому помилка.
|
|
| |
vitert |
Дата: Tu, 05.10.2010, 22:58 | Повідомлення № 19 |
Тут живе...
Повідомлень: 174
| Quote (Ковальчук_Олександр) Тепер програма працює начебто коректно, але є одне але: при перевірці он-лайн не проходить тест на валідність. Підкажіть, будь-ласка, в чому помилка. Відповідь ціле число а не Real.
|
|
| |
pasichov |
Дата: Tu, 05.10.2010, 23:04 | Повідомлення № 20 |
Наполегливий учасник
Повідомлень: 946
| Quote (Bandalak) Умова задана не зовсім однозначно. А який верхній поріг для N? Згоден. Зауваження слушне. Виправляю. Додано (05.10.2010, 23:04) --------------------------------------------- Quote (alex) На мою думку не початку програми елементи масиву потрібно занулити. Можливо помиляюся, але не доводилось читати, що після опису масиву всі його елементи дорівнюють 0. Опис передбачає виділення і поіменування певної ділянки памяті, а що там знаходилось до того не відомо. Це залежить від комілятора. Але правила хорошого тону вимагають обнуляти масив перед використанням в будь-якому випадку. Зручно (і економно за часом) це робити за допомогою стандартної процедури FillChar
Відредаговано: pasichov - Tu, 05.10.2010, 23:09 |
|
| |
kom_adm |
Дата: We, 06.10.2010, 14:52 | Повідомлення № 21 |
Ветеран спілкування
Повідомлень: 3767
| Quote (vitert) Відповідь ціле число а не Real. Виправив програму до такого змісту: Code var m,l,i,code,s:integer;ch:string; mas:array[1..10]of integer; begin readln(m); readln(ch); l:=length(ch); for i:=1 to length(ch) do begin l:=l-1; if ch[i]='A' then mas[i]:=10 else if ch[i]='B' then mas[i]:=11 else if ch[i]='C' then mas[i]:=12 else if ch[i]='D' then mas[i]:=13 else if ch[i]='E' then mas[i]:=14 else if ch[i]='F' then mas[i]:=15 else val(ch[i],mas[i],code); s:=s+round(mas[i]*exp(ln(m)*l)); end; write(s); end. Результати перевірки: Тест Результат Время работы 01 FAILED (Wrong Answer) 0.01 сек. 02 PASSED (+1) 0.01 сек. 03 PASSED (+1) 0.01 сек. 04 FAILED (Wrong Answer) 0.01 сек. 05 FAILED (Wrong Answer) 0.01 сек. 06 FAILED (Wrong Answer) 0.01 сек. 07 PASSED (+1) 0.01 сек. 08 FAILED (Wrong Answer) 0.01 сек. 09 FAILED (Wrong Answer) 0.01 сек. 10 PASSED (+1) 0.01 сек. Прошло тестов: 4 из 10. Набрано баллов: 4 из 10.
|
|
| |
vitert |
Дата: We, 06.10.2010, 15:32 | Повідомлення № 22 |
Тут живе...
Повідомлень: 174
| Quote (Ковальчук_Олександр) Набрано баллов: 4 из 10. Вставте long у потрібне місце вашої проги і витріть eger і буде вам щастя 10 із 10.
Відредаговано: vitert - We, 06.10.2010, 15:33 |
|
| |
Bandalak |
Дата: We, 06.10.2010, 16:53 | Повідомлення № 23 |
Лідер форуму
Повідомлень: 6386
| vitert, правий. Сума дійсно може вийти за область значень типу Integer. Змінну S потрыбно описати типом Longint.
|
|
| |
pasichov |
Дата: Th, 07.10.2010, 11:20 | Повідомлення № 24 |
Наполегливий учасник
Повідомлень: 946
| Code Program Nhex; Var a :array [0..300] of byte; n,k,b :longint;
Procedure input; var st : string; i,ec : integer; begin readln(n); read(st); k:=length(st); for i:=k downto 1 do begin val(st[i],a[k-i],ec); if ec<>0 then a[k-i]:=ord(st[i])-55; end; end;
procedure main; var i,p:longint; begin b:=0; p:=1; for i:=0 to k-1 do begin b:=b+a[i]*p; p:=p*n; end; end;
procedure output; begin write(b); end;
begin input; main; output; end. Ось цей код проходить повністю перевірку. Він є прикладом реалізації "структурованого" підходу до задачі і дозволяє конструювати алгоритм розв"язку на псевдокоді, не переймаючись введенням-виведенням. Не варто боятися лишніх стрічок - "прозорість" коду важливіша! В першу чергу для того, хто його пише! Що ж стосується помилок в попередньому розв'язку, то вони виникли дійсно через вихід за межі типу integer
Відредаговано: pasichov - Th, 07.10.2010, 11:23 |
|
| |
kom_adm |
Дата: Fr, 08.10.2010, 00:08 | Повідомлення № 25 |
Ветеран спілкування
Повідомлень: 3767
| Красивий розв’язок, Юрію Яковичу. І інтуєтивно зрозумілий, все розкладено по поличках. Буду намагатися виробляти культуру програмування. Про функцію ord я попросту забув, а це дає змогу уникнути розгалужень if ch[i]='A' then mas[i]:=10 else ... Дуже дякую.
|
|
| |
pasichov |
Дата: Fr, 08.10.2010, 08:16 | Повідомлення № 26 |
Наполегливий учасник
Повідомлень: 946
| Задача Hex Дано число Ch в десятковій системі числення. Написати програму що переводить дане число в систему числення з основою m. Технічні умови: Програма читає з клавіатури в першому рядку число m (2≤m≤16), в другому - число Ch (0≤Ch≤2*10^9) в десятковій системі. Програма виводить на екран відповідь в вигляді текстового рядка. Приклад: Введення: 16 1024 Виведення: 400 ==================================================================================== == Розглянемо шлях отримання розв'язку Відомий алгоритм перведення числа, записаного в десястковій системі числення в систему числення з основою m зводиться до: Code поки ЧИСЛО <>0 пц знаходимо залишок від ділення ЧИСЛО на m зберігаємо залишок від ділення ділимо націло ЧИСЛО на m - результат => нове ЧИСЛО кц Виписуємо залишки в зворотньому порядку. Далі - лише технічні складнщі. Як їх подолати - видно з кода. Code Program Hex; type tab=array[0..35] of integer; var chislo:longint; t:tab; rez:string; m,i:integer;
procedure inp; begin readLn(m); Read(Chislo); end;
procedure main(n:integer;ch:longint;var p:integer;var z:tab); var k:byte; begin p:=-1; while ch<>0 do begin k:=ch mod n; p:=p+1; z[p]:=k; ch:=ch div n; end; end;
function peret(chch:integer):char; begin if chch<10 then peret:=chr(chch+48) else peret:=chr(chch+55); end;
procedure out(pp:integer;zz:tab;var otv:string); var w:char; ch:integer; begin otv:=''; while pp>=0 do begin ch:=zz[pp]; pp:=pp-1; w:=peret(ch); otv:=otv+w; end; end; begin inp; main(m,chislo,i,t); out(i,t,rez); if rez='' then write('0') else write(rez); end.
Відредаговано: pasichov - Fr, 08.10.2010, 14:03 |
|
| |
kom_adm |
Дата: Fr, 08.10.2010, 21:51 | Повідомлення № 27 |
Ветеран спілкування
Повідомлень: 3767
| Задача Hex мені здалась значно складнішою, за Nhex в плані технічної реалізації. Задача Clock Стрілки годинника рухаються з постійним кутовими швидкостями h годин m хвилин. Найти число повних хвилин до найближчого моменту, в яких стрілки співвпадуть. Технічні умови: Програма читає два цілих числа h та m з клавіатури. Програма виводить. ціле число хвилин на екран. Приклади. Введення: 0 0 Виведення 0 Введення: 1 1 Виведення: 4. Ось ця дійсно для початківців. Але чомусь знову не проходить повністю перевірку, набирає лише 5 із 20 балів. В чому може бути помилка? Code program clock; var h,m,rez:byte; begin read(h,m); rez:=h*5-m; write(rez); end.
|
|
| |
alex |
Дата: Fr, 08.10.2010, 23:40 | Повідомлення № 28 |
Активний учасник
Повідомлень: 586
| Зайдіть будь-ласка на disted.edu.vn.ua. Там є повний розбір цієї задачі в розділі "Позакласна робота. Дистанційні курси. =>Методика розвязування олімпіадних задач з інформатики (для вчителів)." Правда вхід тільки для зареєстрованих користувачів.
Відредаговано: alex - Fr, 08.10.2010, 23:42 |
|
| |
pasichov |
Дата: Sa, 09.10.2010, 14:57 | Повідомлення № 29 |
Наполегливий учасник
Повідомлень: 946
| Quote (Ковальчук_Олександр) Ось ця дійсно для початківців. Але чомусь знову не проходить повністю перевірку, набирає лише 5 із 20 балів. В чому може бути помилка? Код Дублюю власний текст з дистанційного курсу. (адреса вище, потрібно зарєструватися) Задача Сlock (надана службою точного часу) Стрілки годинника рухаються з постійними кутовими швидкостями і показують h годин m хвилин. Найти число повних хвилин до найближчого моменту, в яких стрілки співпадуть. Технічні умови: Програма читає два цілих числа h та m з клавіатури. Програма виводить ціле число хвилин на екран. Приклади. Введення: 0 0 Виведення 0 Введення: 1 1 Виведення: 4
Ця задача - типовий приклад "задач на придумку". Для того, щоб такі задачі розв'язувати, не потрібно знати якісь спеціальні методи. Потрібно лише ДУЖЕ АКУРАТНО і послідовно думати. Ця якість (точніше - її відсутність) саме "акуратного" способу мислення дуже часто заважає учням навіть з непоганою математичною підготовкою успішно справлятися з задачами з інформатики. Спробуємо провести "сеанс акуратного думання" :-). Спочатку з'ясуємо, як часто стрілки сходяться: рівно в 0:00, потім приблизно в 1:05, в 2:11, і так далі, в 10:55 - всього одинадцять положень. Кутові швидкості стрілок постійні, тому «збіги» настають через рівні проміжки часу. Отже, між ними проходить 12/11 години, або (12*60) /11 хвилин. Проміжок часу від моменту першого збігу 0:00 до моменту h : m (h годин m хвилин) рівний 60*h+m хвилин і є проміжком часу від одного із збігів стрілок до моменту h:m. Причому, це збіг останній, якщо 60*h+m <(12*60)/11. Якщо ж 60*h+m >= (12*60)/11, то можна обчислити 60*h+m - (12*60) /11 (час після другого збігу), 60*h+m - 2*(12*60) /11 (після третього) і так далі. На деякому кроці отримаємо різницю t в межах від 0 до (12*60) /11. Це і буде проміжок часу після останнього збігу до моменту h: m. Отже, до наступного "збігу" залишилося (12*60) /11 - t хвилин, і залишається лише узяти цілу частину цього числа. Якщо ви все зрозуміли - спробуйте написати розв'язок Власне, розв'язок задачі Clock За одиницю часу приймемо не хвилину, а одну одиннадцяту хвилини. Тоді всі числа будуть цілими, і t можна обчислити не в циклі, а за допомогою операції mod, як в наступній програмі: Code Рrogram Сlock; var h, m, t : integer;
begin readln(h, m);
t := 11*(60*h+m) mod 720;
if t <> 0 then t := 720 - t;
writeln (t div 11); {ціле число хвилин}
end. В курсі, з якого цей розбір, є ще багато цікавих і, головне КОРИСНИХ розібраних задач. Ми з Олександром Івановичем намагалися його провести позаминулим літом для бажаючих учителів. Таких виявилося небагато. Але (хочеться вірити) все-таки комусь це може бути корисно. Отже, якщо когось цікавлять такі задачі: 1. Зареєструватися в системі http://distd.edu.vn.ua 2. Зайти, як зареєстрований користувач, обрати ПОЗАКЛАСНА РОБОТА. ДИСТАНЦІЙНІ КУРСИ=>Методика розв`язування олімпіадних задач з інформатики (для учителів) (Пасіхов Ю.Я. Олійник О.І.) Уроки доступні в послідовності вивчення - кожен наступний після вивчення матеріалу попереднього.
Відредаговано: pasichov - Sa, 09.10.2010, 15:12 |
|
| |
kom_adm |
Дата: Sa, 09.10.2010, 22:51 | Повідомлення № 30 |
Ветеран спілкування
Повідомлень: 3767
| Я зрозумів помилку. Дякую за розв’язок. Цікава задача.
|
|
| |
© Форум інформатиків України, 2007-2022.  |