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

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

Модератор форуму: Bandalak, Ktara, НІКОЛЯ, volevikt  
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Розв'язування задач методами процедурного програмування (Розв'язки цікавих задач олімпіадного та шкільного рівнів.)
Розв'язування задач методами процедурного програмування
Ковальчук_Олександр Дата: Нд, 21.10.2007, 16:37 | Повідомлення № 1
Ветеран спілкування
Повідомлень: 3705
Нагороди: 18
Рейтинг: 209
Пропоную в даній темі таке спілкування: хтось пише умову цікавої задачі з програмування, інші - намагаються розв'язати цю задачу і надіслати текст програми в цю тему з повним роз'ясненням розв'язку. Задачі можуть бути як шкільного, так і олімпіадного рівнів. Дана тема допоможе реально підвищити знання з програмування вчителям, які погано розуміються на задачах олімпіадного рівня. Нажаль, я також відносюся до цієї групи вчителів. Соромно, але факт.

Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!!
login Дата: Пт, 16.11.2007, 22:41 | Повідомлення № 31
Новий користувач
Повідомлень: 16
Нагороди: 0
Рейтинг: 1
Quote (login)
в своїй протрамі "тюль", Newbie (та баго інших вчитлів в аналгічних випадках) обнуляє змнні перд першим їх використанням
Код
s1:=0; s2:=0;
Чи варто це робити?

Як ніхто нчого не каже то скажу Я.

Я вваю, що обнулення змінних зародилось за тих часів, коли в школах домінуючою мовою прогамування був Basic, а про Pascal мало хто думав (~1990) саме тоді я вперше зустрівся з компютерами "УКНЦ", на яких крім вбудового бйсіка нічого не було. Це був нвіть не копілятор а інтерпретатор, який після заінчення виконання прогами залишав кінцеві значення змінних в памяті. Якщо на початку прогрми не обнуляти ці змінні то при другому виконанні пограма давала некоректні результати. Ця ж істрія спостерігалася мною і в наступній версії бейсіка - GwBasic. В паскаліподібнї проблеми не спостерігав, і вважаю тут онулення недоцільним. Думаю, що вчителі (і навіть дякі автори книг) обнуляють змінні лише за старою звичкою не задумуючись над цим.

Можливо вхтось не згоден зі мню і в нього є інша думка.

А для Вас, Newbie, привожу свій варіант задачі "тюль", який на мою думку більш цікавіший і оптимальніший. Крім того пропоную всім для офомлення програми використвувати відступи для більш зручного сприйняття.

Code
Var F1, F2: Text;
     D, S, I, J, M, N: Integer;
Begin
   Assign (F1, 'z2.dat');
   Assign (F2, 'z2.sol');
   Reset (F1);
   Readln(F1, D, S);
   For I:=1 to D Do
     For J:=1 To S Do
       Begin
         Read(F1, M);
         If M=0 Then N:=N+1 Else N:=N-1;
       End;
   Close(F1);
   ReWrite(F2);
   If N=0 Then Write (F2, 'yes') Else Write (F2, 'no');
   Close (F2);
   Write (N);
   ReadLn;
End.
KulAlex Дата: Сб, 17.11.2007, 11:27 | Повідомлення № 32
Знаток програмування
Повідомлень: 326
Нагороди: 6
Рейтинг: 19
Quote (login)
Можливо вхтось не згоден зі мню і в нього є інша думка.

А відносно Pascal то в нього ще більше глюків ніж в Basic. Зокрема в обнуленні змінних, їх потрібно обнулювати.
А відносно Вашої задачі результат був би 0, тому що останє ReadLn все спортить.

Додано (17.11.2007, 11:21)
---------------------------------------------
var t:text;
i,j,d,s,x,k:integer;
begin
Assign(t,'z2.dat');
Reset(t);
readln(t,d,s);
k:=0;
for i:=1 to d do
for j:=1 to s do
begin
read(t,x);
if x=0 then inc(k)
end;
Close(t);
Assign(t,'z2.sol');
Rewrite(t);
if k=d*s-k then write(t,'yes') else write(t,'no');
Close(t)
end.

А це мій роз'язок.

Добавлено (17.11.2007, 11:23)
---------------------------------------------

Quote (KulAlex)
А відносно Вашої задачі результат був би 0, тому що останє ReadLn все спортить.

І крім того лишній вивід на екран Write (N);

Додано (17.11.2007, 11:27)
---------------------------------------------
доцільніше використовувати замість
i:=i+1 => inc(i)
i:=i+n => inc(i,n)
i:=i-1 => dec(i)
i:=i-n => dec(i,n)

при умові i,n цілі числа

Ковшун Дата: Сб, 17.11.2007, 11:43 | Повідомлення № 33
Досвідчений учасник
Повідомлень: 1462
Нагороди: 1
Рейтинг: 25
Quote (SLKuty)
Ну скажіть хто небудь хоч слово!!!!
Хто бачив мою візуальну черепаху в приваті?
цілий місяць писав!

Я бачив. І скачав. Сподобалось.
Ми зараз з гуртківцями розпочинаємо вивчення ООП.
Тому подібні роботи завантажуємо, аналізуємо.
Словом, вчимося ООП.
Newbie Дата: Сб, 17.11.2007, 12:07 | Повідомлення № 34
Хелпер
Повідомлень: 1414
Нагороди: 9
Рейтинг: 91
так, справді цікавіші варіанти. дякую, панове KulAlex та login!
саме тому і люблю програмування - кожна задача маю множину розв*язків: якісь гірші, якісь кращі, але не може бути єдино правильного smile
mouse Дата: Нд, 02.12.2007, 02:53 | Повідомлення № 35
Ветеран спілкування
Повідомлень: 2026
Нагороди: 4
Рейтинг: 62
Трохи про ЧЕРЕПЕШКУ.

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

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

Мені здається так цікавіше. А вас? sad

SLKuty Дата: Чт, 13.12.2007, 23:52 | Повідомлення № 36
Монтажер
Повідомлень: 833
Нагороди: 8
Рейтинг: 118
ЩОсь тема заглохла

Хто сидить на візуальних мовах попробуйте зробити реальну модель світлофора
мої гуртківці зробили на Дельфі
кожен колір загоряється і гасне через пару секунд без участі людини
заодно освоїли компоненти таймер і шейп
пробуйте зі своїми потім обміняємося прогами, наша невелика.

Newbie Дата: Пт, 14.12.2007, 08:58 | Повідомлення № 37
Хелпер
Повідомлень: 1414
Нагороди: 9
Рейтинг: 91
Quote (SLKuty)
Хто сидить на візуальних мовах попробуйте зробити реальну модель світлофора

яка гарна ідея!!! smile

ми колись з робили заставку на екран - будь-яке вибране зображення з*являється і гасне з періодичністю в пару секунда ще на ту ж тему - рух Місяця навколо Землі. звичайно примітивні форми, по коло- чи еліспо-подібній траекторії, але теж ідейка непогана

SLKuty Дата: Ср, 26.12.2007, 03:07 | Повідомлення № 38
Монтажер
Повідомлень: 833
Нагороди: 8
Рейтинг: 118
Розвиваємо ідею
наступне завдання для гуртківців - розробити модель роздоріжжя з двома світлофорами для машин і двома для пішоходів

Про заставку
на Дельфі дуже просто зробити скрінсейвер

Добавлено (19.12.2007, 00:54)
---------------------------------------------
Зробили вже мої хакери-крекери роздоріжжя з свіллофорами - блимають вони там гарно і час можна регулювати. Я їм тепер сказав, щоб машин запустили туди і пішоходів, щоб була зовсім реальна модель.
Сидять вже друге заняття - ваяють. Як складуть - дозволю грати ігри ціле наступне заняття.

Добавлено (26.12.2007, 01:13)
---------------------------------------------
Про підручники для малих дітей - всі говорять, а тема програмування заглохла вже тиждень
Ну Володимир Ілліч ви де?

Додано (26.12.2007, 03:07)
---------------------------------------------
десь говорили про олімпіаду для вчителів
я вже і задачу придумав

Varkan Дата: Пт, 08.02.2008, 13:13 | Повідомлення № 39
Викладач ВУЗу
Повідомлень: 425
Нагороди: 0
Рейтинг: 6
Quote (SLKuty)
На квадратній дошці розставлені цілі додатні числа. Черепашка, що знаходиться в лівій верхній клітинці, мріє потрапити у праву нижню. При цьому вона може переповзати тільки в клітинку, що знаходиться праворуч або знизу від даної і хоче, щоб сума всіх чисел, які вона зустріне на шляху, була максимальною. Визначити цю суму та маршрут черепашки (враховуючи стартову та фінішну клітинки).

задача з теорії графів. просто знаходження максимального або мінімального шляху (в залежності від умови) від однієї вершини графа в іншу. див. Дискретна математика, розділ - графи.

Добавлено (08.02.2008, 12:50)
---------------------------------------------

Quote (Newbie)
здається, що черепашка має переходити до поточного найбільшого елемента, який може побачити в своєму рядку та стовпці. якщо по дорозі до нього знайде ще більший, то піде вже до нього.
чи я не все враховую?

Quote (badm)
Дана задача називається класичною задачею динамічного програмування.
Суть полягає у виборі найкращого шляху на у кожній точці руху. Такий принцип, основа динамічного програмування. Уявіть масив 300Х300, якщо розглядати перебір, то варіантів буде дужу і дуже багато.

приклад коли не буде працювати такий алгоритм

1 2 2 1 1
1 1 2 1 1
1 1 2 2 1
1 1 1 2 2
50 1 1 1 2

Добавлено (08.02.2008, 13:13)
---------------------------------------------
що стосується задачі про тюль то фрагмент розвязку такий
n-висота m-ширина

s:=0;
for i:=1 to n
for j:=1 to m
if a[i,j]=0 then s:=s+1;
if s=n*m/2 then writeln('yes') else writeln('no');

деякі учасники рахують і 1 і 2 і 0, я вважаю це не раціонально, але шо робити коли розмір масиву n*m буде непарний (наприклад n-3 m-3 причому 0 нехай буде 4, 1 буде 3, 2 буде 2) в такому випадку замальованих і незамальованих клітинок ніколи не буде рівна кількість.

oleg_teacher Дата: Пт, 08.02.2008, 18:23 | Повідомлення № 40
Любитель дискутувати
Повідомлень: 177
Нагороди: 0
Рейтинг: 2
Quote (KulAlex)
доцільніше використовувати замість
i:=i+1 => inc(i)
i:=i+n => inc(i,n)
i:=i-1 => dec(i)
i:=i-n => dec(i,n)

А як раз то і ні процесор швидше виконує i:=i+1 ніж inc(i). При другому варіанті процесор виконує більше дій.

dpi Дата: Пн, 11.02.2008, 12:03 | Повідомлення № 41
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (login)
обнуляють змінні лише за старою звичкою

Quote (login)
Можливо вхтось не згоден зі мню і в нього є інша думка.

При объявлении переменных им выделяется место на винте где уже сидят в хаотичном порядке "0" и "1"
Если в дальнейшем не выполняется операция присвоения, то использование переменной выдаст абракадабру в лучшем случае (-23564), или ответ "6" - в худшем, тогда усложняется отладка.
Это касается бейсика, С++, С#, a вполне возможно, и паскаля, для других компиляторов.
Вывод: обнуляйте, в дальнейшем эта привычка пригодится.
_____
dpi

KulAlex Дата: Вт, 12.02.2008, 09:32 | Повідомлення № 42
Знаток програмування
Повідомлень: 326
Нагороди: 6
Рейтинг: 19
Quote (oleg_teacher)
А як раз то і ні процесор швидше виконує i:=i+1 ніж inc(i). При другому варіанті процесор виконує більше дій.

Це щось нове. Ви спробуйте, перевірте, а потім говоріть. Трішки літературу почитайте. А для підказки наберіть, запустіть і переконайтесь.

uses dos;
var i,s:longint;
a,b,c,d:word;
begin
gettime(a,b,c,d);
writeln(c,'.',d);
s:=0;
for i:=1 to 2000000000 do
inc(s); {s:=s+1}
gettime(a,b,c,d);
writeln(c,'.',d);
end.

Різниця становить приблизно 0,02 секунди.

Varkan Дата: Вт, 12.02.2008, 09:42 | Повідомлення № 43
Викладач ВУЗу
Повідомлень: 425
Нагороди: 0
Рейтинг: 6
Розробіть алгоритм для розвязку задачі
"Тур шахового коня"

Всі напевне гралися на парах цією іграшкою. малюємо квадрат 8*8. вибираємо будь-яку клітинку і ставимо там 1, далі з тієї клітинку по принципу ходу шаховим конем (буквою г) вибираємо іншу і ставимо 2 і так далі поки не поставимо 64 (ставити числа можна тільки у вільні клітинки)

Добавлено (12.02.2008, 09:35)
---------------------------------------------
Інша задача:
є монети номіналом 1, 2, 5. набрати певну суму цими монетами, так, щоб використати найменше монет.

Добавлено (12.02.2008, 09:36)
---------------------------------------------
Побудувати алгоритм та відповідну програму для обчислення площі довільного N-кутника, що задається координатами вершин.

Додано (12.02.2008, 09:42)
---------------------------------------------
впорядкувати деякий масив елементів шляхом послідовного розділення його на дві частини, окремого сортування кожної із цих частин, злиття отриманих впорядкованих наборів у один впорядкований набір

dpi Дата: Чт, 06.03.2008, 08:57 | Повідомлення № 44
Досвідчений вчитель
Повідомлень: 1438
Нагороди: 1
Рейтинг: 39
Quote (Varkan)
Розробіть алгоритм для розвязку задачі"Тур шахового коня"

Рекурентно выйти на цифру 64 (хотя и не самый быстрый способ)
Quote (Varkan)
є монети номіналом 1, 2, 5. набрати певну суму цими монетами ...

Целочисленное деление на 5, 2 и 1
Quote (Varkan)
Побудувати алгоритм та відповідну програму для обчислення площі довільного N-кутника, що задається координатами вершин.

площадь многоугольника - замкнутой ломаной без самопересечений, заданной своими вершинами в порядке обхода, вычисляется: при k от 1 до n S = S + (x[k]+x[k+1])*(y[k]-y[k+1] где x[0],y[0] = x[n+1],y[n+1] ответ: 1/2*S
Можно проще например для пятиугольника 2S = y1(x5-x2) + y2(x1-x3) + y3(x2-x4) + y4(x3-x5) + y5(x4-x1).
Quote (Varkan)
впорядкувати деякий масив елементів шляхом послідовного розділення його на дві частини, окремого сортування кожної із цих частин, злиття отриманих впорядкованих наборів у один впорядкований набір

Создать два массива из одного, отсортировать их, затем слить в один (если ... то)
Varkan Дата: Чт, 06.03.2008, 09:42 | Повідомлення № 45
Викладач ВУЗу
Повідомлень: 425
Нагороди: 0
Рейтинг: 6
Quote (dpi)
Рекурентно выйти на цифру 64 (хотя и не самый быстрый способ)

трішечки не зрозумів, поясніть будь-ласка

Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Розв'язування задач методами процедурного програмування (Розв'язки цікавих задач олімпіадного та шкільного рівнів.)
Пошук:


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