Вт, 24.10.2017, 07:13
Форум інформатиків України
Головна Реєстрація Вхід
Вітаю Вас, Гість · RSS
Вітання на форумі
Незнайомець
Вітаємо на форумі,
Незнайомцю!

   
зареєструйтесь
Перед реєстрацією обов’язково прочитайте:
Оновлення Учасники Пошук
Особисті повідомлення
Видавництво ’’Аспект’’ Видавництво

Сторінка 1 з 41234»
Модератор форуму: Bandalak, Ktara, НІКОЛЯ, volevikt 
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Задачі для початківців з сайту http://netoi.org.ua/ (Розв’язуємо разом.)
Задачі для початківців з сайту http://netoi.org.ua/
Ковальчук_Олександр Дата: Нд, 26.09.2010, 23:32 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Пропоную в даній темі обговорювати оптимальні методи розв’язання задач для початківців, що викладені на сайті http://netoi.org.ua/
На мій погляд чудові задачі для тих, хто тільки починає свій рух в напрямку олімпіадного програмування. До того ж є можливість зразу в он-лайні перевірити задачу.
Формат спілкування в цій темі вільний, головне, без особистих образ і приниження учасників форуму. За проявлену відверту зверхність - бан на місяць.
Ковальчук_Олександр Дата: Нд, 26.09.2010, 23:37 | Повідомлення № 2
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Спробував розв’язати першу задачу.

Задача Сircle

Василько взяв великого циркуля та зайшов до кімнати, підлога якої являє собою квадрат зі стороною рівною M (M>1м). Поставивши циркуль на перетині діагоналей цього квадрата він почав будувати кола. Перше коло мало діаметр 10 см., друге – 30, трете – 40, четверте – 60, п’яте – 70, шосте – 90 см. і т.д. Скільки повних кіл може побудувати в цій кімнаті Василько?

Технічні умови. Програма зчитує з клавіатури ціле число M – довжину стіни кімнати в сантиметрах. Програма виводить на екран одне ціле число – кількість повних кіл, які можна тут побудувати.

Приклад.

Введення> 240
Виведення> 16

Введення> 380
Виведення> 25

Тести пройшов успішно, набрано 5 із 5 балів. Проте мій спосіб не здається мені оптимальним. Скажу відверто, що являюсь початківцем в області олімпіадного програмування, але маю бажання навчитись і останнім часом знаходжу для цього час.
Текст програми:

var d,m,k,k1,d1,rez:integer;
begin
readln(m);
d:=10; d1:=30;k:=0;k1:=0;
while d<=m do
begin
d:=d+30;
k:=k+1;
end;
while d1<=m do
begin
d1:=d1+30;
k1:=k1+1;
end;
rez:=k+k1;
writeln(rez);
end.

Буду вдячний за конструктивні зауваження щодо оптимальності розв’язку, зокрема, щоб не використовувати 2х циклів.

pasichov Дата: Нд, 26.09.2010, 23:51 | Повідомлення № 3
Наполегливий учасник
Повідомлень: 946
Нагороди: 3
Рейтинг: 70
Чудова ідея!

Автори ресурсу http://netoi.org.ua (більш відомий, як http://www.olymp.vinnica.ua ) пропонують учасникам форуму надсилати задачі, які вони хотіли би бачити в цьому розділі. Протягом 1-2 днів задачу буде вмонтовано в систему, і розв"язок можна буде перевірити.
Достатньо наділслати умову та авторський розв"язок (тести бажано, але можемо зробити й ми) на адресу olymp@olymp.vinnica.ua
В темі листа вказати "Задачі для початківців- нова задача"

Щодо розв"язку попередньої задачі. Його можна зробити й так, зовсім без циклів
Program Circle;
Var m,rez,z: integer;
begin
Read (m);
Rez:=(m div 30)*2;
if m mod 30 >=10 then inc(rez);
Write(rez);
End.

Відредаговано: pasichov - Пн, 27.09.2010, 00:40
alex Дата: Нд, 26.09.2010, 23:53 | Повідомлення № 4
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Василько взяв великого циркуля та зайшов до кімнати, підлога якої являє собою квадрат зі стороною рівною M (M>1м). Поставивши циркуль на перетині діагоналей цього квадрата він почав будувати кола. Перше коло мало діаметр 10 см., друге – 30, трете – 40, четверте – 60, п’яте – 70, шосте – 90 см. і т.д. Скільки повних кіл може побудувати в цій кімнаті Василько?

Технічні умови. Програма зчитує з клавіатури ціле число M – довжину стіни кімнати в сантиметрах. Програма виводить на екран одне ціле число – кількість повних кіл, які можна тут побудувати.

Приклад.

Введення> 240
Виведення> 16

Введення> 380
Виведення> 25

Якщо буде і зворотня зверхність ( не там кома, не доступно пояснено і т.д.) то і ...

1. Ідея розв'язку ( не претендуючи на її єдиність)^

а) Задача належить до задач підрахунку кількості. Тому логічно насамперед кількості надати значення 0;

k:=0;
б) Оскількі дія проведення (малювання) кола буде повторюватись, то
будемо використовувати команду повторення
в) команда , яка буде повторюватись матиме вид: m:=m-r; де m - це сторона кімнати,
а r - це приріст радіус кола, який проводимо в даний момент;
Зрозуміло, що m - це аргумент і змінювати значення аргументу в процесі роботи програми це ознака "дурного тону в
програмуванні" , якщо про це не сказано в умові задачі. Отже перед циклом y:=m; R отримує значення 10 , як початкове значення радіуса , відповідно до умови задачі.
А в циклі y:=y-r; В підсумку матимемо:

АЛГ кола( ціл m, ціл k)
арг m
рез k
ПОЧ
k:=0; y:=m; r:=10
Поки
пц
k:=k+1
y:=y-r;
кц
КІН

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

АЛГ кола( ціл m, ціл k)
арг m
рез k
ПОЧ ціл r,y
k:=0; y:=m; r:=10
Поки y>=0
пц
k:=k+1
y:=y-r;
кц
k:=k-1
КІН
Але r не є константою;
Один раз відрізають на 10 а інший на 20 більше
АЛГ кола( ціл m, ціл k)
арг m
рез k
ПОЧ ціл r,y
k:=0; y:=m; r:=10
Поки y>=0
пц
k:=k+1
y:=y-r;
Якщо к mod 2=1
то r:=20
інакше r:=10
Все
кц
k:=k-1
КІН

Можливий варіан розв'зку з використання циклу з після умовою так, як
відповідно до умови задачі хоча б одне коло буде проведено.
Пропоную учасникам форуму розвязати таким методом самостійно.

PS. На мою точку зору така форма навчання не є оптимальною. Напевно краще було б
при затрудненнях задавати питання в сособистому листуванні авторам ресурсу та отримувати на свої питання відповіді.

Можливий варіант розв'язку і без використання циклу, хоча як для мене
пояснити його дещо важче ніж з використанням циклу

program circle;
Var
y,r,m,k :integer;
Begin
read(m);
k:= (m div 30)*2;
if m mod 30 >=10
then k:=k+1;
writeln(k);
End.

Відредаговано: alex - Пн, 27.09.2010, 00:40
Ковальчук_Олександр Дата: Пн, 27.09.2010, 00:12 | Повідомлення № 5
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
alex, дякую за розв’язок. Все досить детально і зрозуміло розписано. Красивий розв’язок. Гадаю, подібні теми неймовірно корисні для форуму.
alex Дата: Пн, 27.09.2010, 00:14 | Повідомлення № 6
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Як каже Пасіхов (думаю, що цю фразу він у когось запозичив ;) ) "дорогу осилит идущий."
Ковальчук_Олександр Дата: Пн, 27.09.2010, 00:19 | Повідомлення № 7
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
І ще цікавить питання, якби на районній олімпіаді попалася така задача (ну, можливо, складніша) і учень розв’язав би її в "моєму стилі" чи нарахувались би за такий розв’язок якісь бали?

Quote (alex)
PS. На мою точку зору така форма навчання не є оптимальною. Напевно краще було б
при затрудненнях задавати питання в сособистому листуванні авторам ресурсу та отримувати на свої питання відповіді.

Чому? На мій погляд, користь від цієї теми очевидна. Більш досвідчені в області алгоритмізації допомагають менш досвідченим. Посилання на ресурс вказано.
Bandalak Дата: Пн, 27.09.2010, 00:25 | Повідомлення № 8
Лідер форуму
Повідомлень: 5437
Нагороди: 37
Рейтинг: 247
var m,rez:integer;
begin
readln(m);
rez:=m div 30 + (m+20) div 30;
writeln(rez)
end.
:)
alex Дата: Пн, 27.09.2010, 00:46 | Повідомлення № 9
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Quote (Ковальчук_Олександр)
чи нарахувались би за такий розв’язок якісь бали?

Для такої задачі був би нарахований повний бал так, як

1) ніхто не перевіряє ідею розвязку так, як один може ввжати геніальним той розв'язок, який для іншого тривіальний

2) для такої задачі дуже важко ( практично не можливо ) відсікти не оптимальні варіанти ров'язку
( щоб не бути бути котегоричним , я б не зміг би відсікти не оптимальні варіанти , та і в принципі не потрібно не той рівень)

Додано (26.09.2010, 23:46)
---------------------------------------------

Quote (Bandalak)
var m,rez:integer;
begin
readln(m);
rez:=m div 30 + (m+20) div 30;
writeln(rez)
end.

Зрозуміло, що і такий розв'язок має право на життя. Хоча на мою точку зору, задача не повинна розв'язуватись раді задачі.
На прикладі кожної задачі потрібно показувати як потрібно будувати міркування для отримання результату.
Прошу не сприймати це як критику. Розв'язок з точки зору оптимальності напевно самий оптимальний.

pasichov Дата: Пн, 27.09.2010, 00:47 | Повідомлення № 10
Наполегливий учасник
Повідомлень: 946
Нагороди: 3
Рейтинг: 70
Quote (alex)
program circle;
Var
y,r,m,k :integer;
Begin
read(m);
k:= (m div 30)*2;
if m mod 30 >=10
then k:=k+1;
writeln(k);
End.

Олександре Івановичу, коли дописав свій подібний, побачив ваш...:-) Пробачаюсь! Чесне слово , не списував! :-)

Ковальчук_Олександр Дата: Пн, 27.09.2010, 01:03 | Повідомлення № 11
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Цитата Bandalak
rez:=m div 30 + (m+20) div 30;

Я так розумію, що в цій задачі маємо справу з двома послідовностями - арифметичними прогресіями. Перша з них починається з 10 і зростає з інтервалом 30, друга - з 30 (на 20 більше) і також зростає з інтервалом 30. Щоб знайти кількість повних кіл, потрібно сторону квадрату поділити націло на 30 на першу прогресію (m div 30), потім додати 20 і поділити націло на 30 на другу (m+20) div 30 і результати додати.
pasichov Дата: Пн, 27.09.2010, 18:57 | Повідомлення № 12
Наполегливий учасник
Повідомлень: 946
Нагороди: 3
Рейтинг: 70
Задача 2. Leopold
Кіт Леопольд пішов на рибалку та наловив риби. Кожну рибу він старанно зважив. Перша риба (найменша), яку він зважував важила рівно L грам. Кожна наступна рибина була на К грамів важча за попередню. Скільки заважила вся риба, яку наловив Леопольд, якщо відомо, що спіймав він N (0<N риб?

Технічні умови. Програма зчитує з клавіатури ціле число N - кількість рибин, потім, через пропуск, L - маса першої риби в грамах та, через пропуск - К - на скільки кожна наступна рибина важча від попередньої. Програма виводить на екран одне ціле число - масу всієї упійманої риби в грамах.

Приклад.

Введення> 10 250 100
Виведення> 7000

Введення> 12 100 150
Виведення> 11100
========================================

Може бути такий розв"язок, зрозумілий без особливих коментарів. Але він знову ж ітераційний: в циклі розраховуємо вагу кожної наступної риби і накопичуєм суму.

Code
Program Leopold;
Var i, n, l, k, s, t :integer;
Begin   
   readln(n, l, k);
   s:=0; t:=l;
   for i:=1 to n do
   begin
     s:=s+t;
     t:=t+k;
   end;    
   writeln (s);
end.

Можливо зробити значно краще, використавши формулу суми членів арифметичної прогресії.

s=(2*l+k*(n-1))/2
Але тут є "підводний камінь". Ми сподіваємося отримати цілу відповідь, а оперція "/" дає дійсний результат.
Тому правильно буде:

Code

Program Leopold;
Var n, l, k, s :integer;
Begin   
   readln(n, l, k);
   s:=(2*l+k*(n-1)) div 2
   writeln (s);
end.


Відредаговано: pasichov - Пн, 27.09.2010, 19:49
Bandalak Дата: Вт, 28.09.2010, 01:45 | Повідомлення № 13
Лідер форуму
Повідомлень: 5437
Нагороди: 37
Рейтинг: 247
Quote (pasichov)
спіймав він N (0<N риб?

Умова задана не зовсім однозначно. А який верхній поріг для N?
Якщо N занадто велике, то задача значно ускладнюється, починаючи від опису довгих цілих типів, і навіть до використання довгої арифметики!
Також ніяких обмежень на K та L. Хто сказав, що вага риби ціле число, де це написано?
Люблю, коли умови чіткі та однозначні! :)
Ковальчук_Олександр Дата: Пн, 04.10.2010, 22:01 | Повідомлення № 14
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Щодо першої задачі Circle, то там формула для знаходження кількості може бути ще простіша, ніж запропонував Bandalak.
Мій учень додумався: rez:=m div 15; оскільки 15 - це середнє арифметичне приростів радіусів кіл (10 і 20)
var m,rez:integer;
begin
readln(m);
rez:=m div 15;
writeln(rez)
end.


Задача 3. Slon

Петрик П'яточкін вишикував у рядок слоненят та рахує їх по кожному кольору окремо. Всього буває 8 кольорів слоненят. У рядок вишикувались N (10<N<999) слоненят. Скільки слоненят кожного кольору стоїть перед Петриком? Бажано їх порахувати пройшовши всього один раз перед строєм.

Технічні умови. Програма зчитує з клавіатури ціле число N - кількість слоненят, потім, через пропуск - N чисел від 1 до 8, якими ми пронумеровали кожен колір в тій послідовності, в якій вони потрапляли на очі Петрику від початку рядка. Програма виводить на екран в один рядок через пропуски пари цілих чисел, де перше число пари - колір, а друге - кількість слоненят такого кольору.

Приклад.

Введення>12 1 1 2 3 3 1 5 6 8 7 6 5
Виведення> 1 3 2 1 3 2 4 0 5 2 6 2 7 1 8 1



Code

var k1,k2,k3,k4,k5,k6,k7,k8,n,i:integer; a:array[1..999] of integer;
begin
   read(n);
   for i:=1 to n do
   begin
   read(a[i]);
   case a[i] of
   1: k1:=k1+1;
   2: k2:=k2+1;
   3: k3:=k3+1;
   4: k4:=k4+1;
   5: k5:=k5+1;
   6: k6:=k6+1;
   7: k7:=k7+1;
   end;
   end;
   k8:=n-(k1+k2+k3+k4+k5+k6+k7);
   write(1,' ',k1,' ',2,' ',k2,' ',3,' ',k3,' ',4,' ',k4,' ',5,' ',k5,' ',6,' ',k6,' ',7,' ',k7,' ',8,' ',k8);
end.

Хтось запропонує оптимальніший код?

vitert Дата: Вт, 05.10.2010, 00:31 | Повідомлення № 15
Тут живе...
Повідомлень: 174
Нагороди: 1
Рейтинг: 22
Quote (Ковальчук_Олександр)
Мій учень додумався: rez:=m div 15

Якщо m=101, 102,103, 104 то m div 15=6, а правильно як?

Quote (Ковальчук_Олександр)
Хтось запропонує оптимальніший код?

Можна так:
var n,i,k:integer; a:array[1..8] of integer;
begin
read(n);
for i:=1 to n do begin read(k); inc(a[k]); end;
for i:=1 to 8 do write(i,' ',a[i],' ');
end.
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Задачі для початківців з сайту http://netoi.org.ua/ (Розв’язуємо разом.)
Сторінка 1 з 41234»
Пошук:


© Форум інформатиків України, 2007-2017.