Розв'язування задач методами процедурного програмування

Дата: Нд, 21.10.2007, 16:37 | Повідомлення № 1

Ветеран спілкування

Повідомлень: 3767

Нагороди: 19

Рейтинг: 217

Пропоную в даній темі таке спілкування: хтось пише умову цікавої задачі з програмування, інші - намагаються розв'язати цю задачу і надіслати текст програми в цю тему з повним роз'ясненням розв'язку. Задачі можуть бути як шкільного, так і олімпіадного рівнів. Дана тема допоможе реально підвищити знання з програмування вчителям, які погано розуміються на задачах олімпіадного рівня. Нажаль, я також відносюся до цієї групи вчителів. Соромно, але факт.

Шановні форумчани!!!!!
Повідомлення, які не відповідають темі або несуть некорисний зміст будуть видалятись без попередження!!!

SLKuty

Дата: Пн, 22.10.2007, 11:41 | Повідомлення № 2

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

Попробуйте розвязати таку задачу.

На квадратній дошці розставлені цілі додатні числа. Черепашка, що знаходиться в лівій верхній клітинці, мріє потрапити у праву нижню. При цьому вона може переповзати тільки в клітинку, що знаходиться праворуч або знизу від даної і хоче, щоб сума всіх чисел, які вона зустріне на шляху, була максимальною. Визначити цю суму та маршрут черепашки (враховуючи стартову та фінішну клітинки).

Технічні умови: Вхідні дані читаються із текстового файлу in.txt. Вихідні дані записуються в текстовий файл out.txt. Зчитування вхідних даних з клавіатури і виведення вихідних даних на екран карається штрафом 25% від кількості балів за задачу.
Формат вхідних даних: Перший рядок - N - розмір дошки. Далі N рядків, кожний з яких містить N цілих чисел, що представляють дошку.
Формат вихідних даних: Перший рядок -- максимальна сума. Наступні рядки – пари чисел - координати клітинок маршруту. Якщо оптимальних маршрутів декілька, то вивести будь-який із них.

Вхідні дані:
5
12 3 7 10 3
8 4 15 7 9
11 10 1 5 9
17 2 9 4 7
3 8 9 10 17

Задача була запропонована на районній олімпіаді 2005 року. Звичайно ніхто з дітей і вчителів її не розвязали.

Через деякий час я запропоную свій варіант відповіді. Можливо в когось є якісь ідеї щодо розвязання, бо мій розвязок трохи складний. Чекаю на Ваші варіанти, а також на цікаві умови задач. Я люблю задачі, які без компютера розвязати дуже важко. Бажаю успіхів.

badm

Дата: Пн, 22.10.2007, 12:57 | Повідомлення № 3

Знаток програмування

Повідомлень: 185

Нагороди: 0

Рейтинг: 3

Задача тривіальна на динамічне програмування. Тиждень назад розбирали з учнями 8 кл. так було популярна у 2004/5 році була на обласній олімпіаді. Шляхів рішення один описаний в книзі Окулова, на кожному кроці вибирати оптимальний варіант переглядаючи масив.
Найбільш цікаве для мене в рішенні спросіб створення шляху, а потім його розкрутка у чергу.

SLKuty

Дата: Вт, 23.10.2007, 10:13 | Повідомлення № 4

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

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

Добавлено (Сегодня, 10:13)
---------------------------------------------
Знайшов в неті і закачав "Программирование в алгоритмах / С. М. Окулов. —
М.: БИНОМ. Лаборатория знаний, 2002. — 341 с:" В кінці розвязки багатьох олімпіадних задач але такої немає. Може не та книжка, а може я не уважний.

badm

Дата: Вт, 23.10.2007, 11:09 | Повідомлення № 5

Знаток програмування

Повідомлень: 185

Нагороди: 0

Рейтинг: 3

begin
L[n,m]:=A[n,m];{L масив який буде містити результат, передаєем значення з якого починаєм обчислення}
s[n,m]:=0; {для запису переходів}
цикли з кінця
For i:=n-1 downto 1 do
begin
L[i,m]:=L[i+1,M]+A[i,m];{cума по останьому рядку}
s[i,m]:=0;{якщо немає переходів по стопцям то 0 }
end;
{так само шукаємо суму для останього стовпця, тому для останього стовпця і рядка лише 1 шлях}
...
{основна частина}
For j:=m-1 downto 1 do
For i=n-1 downto 1 do
begin
{порівнюємо сусіді точки де може перебувати черепашка і вибираємо на кожному шляху найкращий}
if L[i,j+1]<L[i+1,j] then
begin
l[i,j]:=a[i,j]+l[i,j+1]; s[i,j]:=1; end
else begin
l[i,j]:=a[i,j]+l[i+1,j]; s[i,j]:=1; end;
end;
{тут для мене саме цікаве розкрутка шляху}
i:=1;
j:=1;
k:=1;
while k<N+M do
begin
p[1,k]:=i; p[1,k]:=j; k:=k+1;
if s[i,j]=1 then j:=j+1 else i:=i+1;
end;
...
далі виведення результати. Сам розв’язок не складний головне пояснити метод. Щоб зрозуміти суть треба малюнки.

Добавлено (Сегодня, 11:06)
---------------------------------------------
книжка та дивіться задачу про динамічне програмування.

Добавлено (Сегодня, 11:09)
---------------------------------------------
книжка та. Дивіть розділ динамічне програмування. Там немає розв’язку, але є опис методу з прикладами.

Newbie

Дата: Вт, 23.10.2007, 20:57 | Повідомлення № 6

Хелпер

Повідомлень: 1414

Нагороди: 9

Рейтинг: 91

ще не дивилась детально розв*язку від badm, але мала час трошки подумати над задачкою.

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

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

badm

Дата: Ср, 24.10.2007, 09:26 | Повідомлення № 7

Знаток програмування

Повідомлень: 185

Нагороди: 0

Рейтинг: 3

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

SLKuty

Дата: Ср, 24.10.2007, 18:40 | Повідомлення № 8

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

Програма на перший погляд не складна, але, щоб розібратися в ній треба трохи часу.

Quote (Newbie)

другий зразу заперечив,

другий ваш хакер цілком правий; великі елементи можуть бути на початку шляху, а далі всі малі...

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

Десь через два тиждні роздумів я опустився до рівня тої черепахи і вирішив пройти всіма маршрутами випадковим чином. В умові сказано, що рухатися можна тільки право і вниз. Позначимо 1-вправо, 0-Вниз. Від початку до кінця маршруту - 8 кроків.

Генератор випадкових чисел генерує 5000 (так, щоб вистачило з запасом) випадкових нулів і одиниць
вказівка Randomize намагається виключити повторення.
записуємо їх в масив рядками по 8 знаків
перебираємо масив і залишаємо ті рядки де однакова кількість нулів і одиниць, щоб черепаха дойшла до протилежного кутка, а не вийшла десь збоку.
знову перебираємо масив і викидаємо ті ланцюжки нулів і одиниць які повторюються
виводимо все в файл і отримуємо текстовий файл зі всіма можливими маршрутами
потім зробив іншу програму, яка читає той файл і імітує рух черепахи рахуючи по дорозі цифри

ніби також закручено, але без динамічного програмування

Дата: Ср, 24.10.2007, 23:41 | Повідомлення № 9

Новий користувач

Повідомлень: 16

Нагороди: 0

Рейтинг: 1

Пропоную трішки знизити планку, оскільки 90% вчителів злякаються слова "динамічне програмування".
Почнімо з простого.
пропоную задачу (пізніше викладу ще пару штук) з тренувального туру заочної олімпіади по програмуванню з сайту Ребрини:
Оскільки офіційно ребрина приймає відповіді до 25.10.2007 року, то велике прохання НЕ публікувати відповіді на цю задачу раніше ніж 26.10.2007 року, щоб учасники олімпіади не могли іх тут знайти.

"Гноми-письменники"
Група з 11 прогресивних гномів вирішила написати посібник з програмування для казкової школи. Щоб посібник не був занадто грубим, вони вирішили, що кожен напише не більше ніж 200 сторінок. Коли робота була закінчена, виникла потреба порахувати, скільки сторінок матиме книга. Складіть програму, щоб за відомою кількістю сторінок, які написав кожен з гномів, визначити загальну кількість сторінок.
Вхідні дані: зі стандартного вхідного потоку вводиться 11 цілих чисел - кількості сторінок, написаних кожним з учасників проекту.
Вихідні дані: у стандартний вихідний потік вивести одне ціле число - загальну кількість сторінок у книзі.

Приклад вхідних даних:
1 2 3 4 5 6 7 8 200 9 1
Приклад вихідних даних:
246

SLKuty

Дата: Чт, 25.10.2007, 23:44 | Повідомлення № 10

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

Класно!!! Прочитав 10 разів поки зрозумів де тут задача. Це олімпіада для 5 класу? Може не треба так низько планку опускати, але всеодно дякуємо за активність. Присилайте інші задачі.

Дата: Пт, 26.10.2007, 21:40 | Повідомлення № 11

Новий користувач

Повідомлень: 16

Нагороди: 0

Рейтинг: 1

Пропоную ще одну задачу з тренувального туру заочної олімпіади по програмуванню з сайту Ребрини:
Шановні формучани! при публікації розвязків обовязково вказуйте назву задачі до якої приводите розвязок!!!

"Тюль"
На фабриці, яка випускає тюль - тканину, що складається з окремих квадратних комірок, розташованих рівними рядками і стовпцями, працює відділ з розробки візерунків. Для утворення візерунку дизайнер деякі комірки зафарбовує повністю, частину комірок зафарбовує наполовину, інші залишає незафарбованими. Оптимальним вважається візерунок, у якому незафарбованих комірок стільки ж, як всіх інших разом. Потрібно скласти програму для перевірки того, чи є візерунок оптимальним.
Вхідні дані: у першому рядку текстового файлу Z2.DAT записані два цілі числа D та S, відокремлені пропуском - кількість комірок по довжині та ширині візерунку відповідно. У наступних D рядках записані по S чисел: 0, якщо відповідна комірка порожня, 1 - зафарбована наполовину, 2 - зафарбована повністю. Жоден з розмірів візерунку не перевищує 1000.
Вихідні дані: у текстовий файл Z2.SOL вивести слово, що складається з англійських літер: "yes", якщо візерунок оптимальний, "no" - в іншому випадку.

Приклад 1
Файл Z2.DAT:
5 6
1 1 1 1 1 1
1 0 0 0 0 1
0 0 2 2 0 0
1 0 0 0 0 1
1 1 1 1 1 1
Файл Z2.SOL:
no
Приклад 2
Файл Z2.DAT:
2 3
1 2 2
0 0 0
Файл Z2.SOL:
yes

SLKuty

Дата: Нд, 28.10.2007, 18:04 | Повідомлення № 12

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

Це вже цікавіша задача обовязково дам своїм гуртківцям після канікул.

Дата: Вт, 30.10.2007, 22:09 | Повідомлення № 13

Новий користувач

Повідомлень: 16

Нагороди: 0

Рейтинг: 1

Можна дати "Вопрос на засыпку" на факультативі з програмування ждя 2-хвилинної розминки:

Цей код вконує обмін значень в двох змінних A і B

Code

.....
Var A, B, C: integer
.....
C:=A;
A:=B;
B:=C;
.....

Як обміняти значення двої змінних не використовуючи додаткової змінної?

Code

.....
Var A, B: integer
.....
?????
?????
?????
.....

Відредаговано: login - Вт, 30.10.2007, 22:13

badm

Дата: Ср, 31.10.2007, 09:10 | Повідомлення № 14

Знаток програмування

Повідомлень: 185

Нагороди: 0

Рейтинг: 3

var a,b:integer;
begin
readln(a,b);
a:=a+b;
b:=a-b;
a:=a-b;
writeln(a,' ',b);
end.

SLKuty

Дата: Пн, 05.11.2007, 14:10 | Повідомлення № 15

Монтажер

Повідомлень: 833

Нагороди: 8

Рейтинг: 118

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