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

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

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

ВІдрізком послідовності ввжааємо множину чисел. Оскільки множина чисел може складатися з
одного елемента, то і відрізок послідовності може бути одне число.
Quote (Ковальчук_Олександр)
чому їх слід ділити на 2 послідовності

Елементи підпослідовності деякої послідовності можуть давати більшу суму чисел,
ніж елементи самої послідовності.
Ковальчук_Олександр Дата: Пн, 01.11.2010, 19:25 | Повідомлення № 47
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Дякую за роз’яснення. Ну що ж починаємо думати над розв’язком:)
Ковальчук_Олександр Дата: Ср, 03.11.2010, 21:48 | Повідомлення № 48
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Задача Newcircle.

Знову Влад розв’язав цю задачу своїм оригінальним методом. Можливо не найоптимальнішим, проте гадаю, його розв’язок заслуговує на увагу і має право на життя. Програма набирає максимально 10 із 10 балів при перевірці он-лайн. Я понаписував коментарі, профі зрозуміють.

program newcircle;
type massyv=array[1..1000]of longint;
var i,n,kl,g,x,h,maxn,maxp,kp,kd:longint;x1,x2,a,sum:massyv;
begin

read(n);
for i:=1 to n do
begin
read(a[i]);
if a[i]>0 then inc(kd); {Підраховуємо кількість додатніх елементів}
end;

for i:=1 to n do
if a[i]+1<>a[i+1] then inc(kp); {Підраховуємо кількість відрізків}

if kd>0 then {якщо є додатні елементи, тоді...}
begin
g:=0;
for h:=1 to kp do {послідовно переглядаємо відрізки}
begin
for i:=g+1 to n do {послідовно переглядаємо елементи відрізка}
if a[i]>=0 then {якщо елемент додатній}
if a[i]+1=a[i+1] {та якщо поточний+1=наступному}
then inc(x) {тоді підраховуємо їх кількість. Тобто підраховується кількість елементів у відрізку, в якому елементи йдуть один за одним}
else
begin
x2[h]:=i; {в масив х2 виписуємо останній номер елементу поточного відрізка}
x1[h]:=x2[h]-x; {в масив х1 виписуєм номер першого елементу поточного відрізка}
g:=i; {для розгляду наступного відрізка}
x:=0; {обнулити кількість елементів відрізку}
break;
end;
end;

for h:=1 to kp do
for i:=x1[h] to x2[h] do
sum[h]:=sum[h]+a[i]; {обчислення сум кожної послідовності}

maxn:=1;
maxp:=sum[1];
for h:=2 to kp do
if sum[h]>maxp then
begin
maxp:=sum[h]; {шукаємо максимальну суму}
maxn:=h; {шукаємо номер максимальної суми}
end;
end

else
if kd=0 then {якщо додатні елементи відсутні, тоді...}
begin
maxp:=a[1];
maxn:=1;
x1[maxn]:=1;
x2[maxn]:=1;
for i:=2 to n do
if a[i]>maxp then
begin
maxp:=a[i]; {шукаємо найбільший недодатній елемент}
x1[maxn]:=i; {шукаємо номер найбільшого недодатнього елементу}
x2[maxn]:=i; {шукаємо номер найбільшого недодатнього елементу}
end;
end;
writeln(x1[maxn],' ',x2[maxn],' ',maxp);
end.

alex Дата: Ср, 03.11.2010, 22:45 | Повідомлення № 49
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Quote (Ковальчук_Олександр)

for i:=1 to n do
if a[i]+1<>a[i+1]
then inc(kp);

Алгоритмічна помилка. Вихід за рамки масива. При і=n йде звертання до a[n+1] елемента, а такого немає.
Таких помилок не одна.

НЕ претендуючи на оптимальність, пропоную двопрохідний алгоритм розв'язку

1) проходими 1 раз і розглядаючи "зростаючі" відрізки, визначає відрізок з максимальною сумою.

2) проходими 2 раз і розглядаючи "спадаючі" відрізки, визначає відрізок з максимальною сумою.

3) З відрізків , знайдених в пунктах 1 та 2 вибираємо відрізок з найбільшою сумою .Це і є відповідь.

Ковальчук_Олександр Дата: Ср, 03.11.2010, 22:54 | Повідомлення № 50
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Quote (alex)
При і=n йде звертання до a[n+1] елемента, а такого немає.

Так, але нам і не потрібно, щоб він був, оскільки останній елемент не буде дорівнювати неіснуючому в будь-якому разі, умова справдиться і останній відрізок порахується.
alex Дата: Ср, 03.11.2010, 23:41 | Повідомлення № 51
Активний учасник
Повідомлень: 586
Нагороди: 1
Рейтинг: 17
Quote (Ковальчук_Олександр)
Так, але нам і не потрібно, щоб він був

Quote (Ковальчук_Олександр)
останній елемент не буде дорівнювати неіснуючому

Не можна порівнювати число з тим, чого нема.
Це щось на кшталт:"Іди туди не знаю куди, принеси то не знаю що"

Bandalak Дата: Чт, 04.11.2010, 15:27 | Повідомлення № 52
Лідер форуму
Повідомлень: 5531
Нагороди: 39
Рейтинг: 260
Quote (Ковальчук_Олександр)
не буде дорівнювати неіснуючому

Поняття "неіснуючий елемент" не має. Насправді це або нуль, або якесь числове сміття, залежно від компілятора!
Але якщо n+1 виходить за межі описаного в Array діапазону, то буде відповідне повідомлення про помилку.
pasichov Дата: Пт, 05.11.2010, 19:17 | Повідомлення № 53
Наполегливий учасник
Повідомлень: 946
Нагороди: 3
Рейтинг: 70
Я вимушений принести вибачення за цю задачу.
ЇЇ мені передали з ОІПОПП, попросили встановити в систему для курсів учителів. Я, особливо не вчитуючись, розмістив, використав надані тести...Зараз, прочитавши дискусію, вчитався,і ...взявся за голову.
Задача НЕ ДЛЯ ПОЧАТКІВЦІВ. Насправді - це СКЛАДНА задача, на динамічне програмування, ще й зіпсована!
Пояснюю. З прикладів робимо висновок, "Відрізок послідовності утворюють числа, що йдуть в послідовності підряд" - щось типу х,x,...2,3,4....x,x,x або х,х,х.....,2,1,0,-1,-2.....х,х,х . Це слідує з умови та ПРИКЛАДІВ. Так зрозуміли всі, крім "авторів"....ВОНИ РОЗУМІЛИ "ПІДРЯД" як виключно ЗРОСТАЮЧИЙ ряд , тобто типу 1,2,3.....або -3,-2,-1.....Це слідує з аналізу тестів, які волни мені надали ("авторського" розв"язку, зрозуміло, не дали), отже при перевірці повні бали МОЖУТЬ НАБИРАТИ НЕПРАВИЛЬНІ РОЗВ"ЯЗКИ!!!!!!

АЛЕ САМЕ СМІШНЕ, ЩО В ОРИГІНАЛІ (Арсак, "Програмування ігор та головоломок"), звідки взято цю задачу, відрізок - це будь-який фрагмент підряд вишикуваних елементів, головне, щоб номер початку фрагмента був не більше номера кінця, і все! ТОБТО ВІДРІЗОК СКЛАДАЄТЬСЯ З БУДЬ-ЯКИХ ЕЛЕМЕНТІВ, ЩО ЙДУТЬ ПІДРЯД ОДИН ЗА ОДНИМ!
ЦЕ СЛІДУЄ З УМОВИ, НАВЕДЕНОЇ НА САЙТІ, АЛЕ НЕ СЛІДУЄ З ПРИКЛАДІВ, ЩО ЇХ НАДАЛИ "АВТОРИ"!!!!
ВИЙШЛО ДУЖЕ ПОВЧАЛЬНО:-( І СУМНО: - УМОВА ОДНІЄЇ (КЛАСНОЇ, АЛЕ СКЛАДНОЇ) ЗАДАЧІ, ПРИКЛАДИ І ТЕСТИ(!) ВІД ДРУГОЇ, А ВСІ РОЗВ"ЯЗУВАЛИ ТРЕТЮ І ОТРИМУВАЛИ "ПРАВИЛЬНИЙ" РЕЗУЛЬТАТ!

ЩЕ РАЗ ПРОШУ ВИБАЧЕННЯ ЗА свою неуважність...і за "авторів"
Пропоную такий вихід з положення. Я вношу незначну правку в умову- означаю відрізок як в прикладах і тестах, тобто типу 1,2,3... (нова версія умови http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=106 ), це відповідає тестам і прикладам - саме ІМХО, це мали на увазі "автори" . Задача стала простішою, але все рівно цікавою ....
Нашвидку написва розв'язок - здається, що так:

Code
Program NewCircle;
         Const z=1000;
          Var a:array[1..z] of longint;
              i,j,n,nMax,k,kMax,s,sMax:longint;
         BEGIN
           Read(j);
           for i:=1 to j do
           Read(a[i]);
           n:=1;k:=1;s:=a[1];
           nMax:=n;kMax:=k;sMax:=s;
           for i:=2 to j do
           Begin
               if (a[i]=a[i-1]+1)and (a[i]>0) then begin inc(k);s:=s+a[i]   end
                          else begin s:=a[i]; n:=i;k:=i end;
               if s>sMax then begin sMax:=s;Nmax:=n;kMax:=k   end;
           end;
           Write(nMax,' ',kMax,' ',sMax);
         END.                

Як видно, задача робиться "за один прохід, тобто алгоритм має лінійну складність.

А ось дійсно оригінальну умову з првильними прикладами і нормалними текстами додаю в розділ ЗАДАЧІ ДЛЯ ПОЧАТКІВЦІВ під назвою NewCircle2

(далі буде)

Додано (04.11.2010, 17:58)
---------------------------------------------
Розмістив НОВУ задачу NewCircle2
http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=992
Саме в такому варіанті вона була в першоджерелі, і тут ВІДРІЗОК - це просто пдряд розміщені члени послідовності, починаючи з будь-якого, і закінчуючи будь-яким з не меншим номером. (див приклади!!!!).
Ось тепер вийшла ДІЙСНО ЦІКАВА ЗАДАЧА!!!

ДЛЯ БАЖАЮЧИХ: ПОВНИЙ ОПИС РОЗВ"ЯЗКУ ВИКЛАВ НА http://disted.edu.vn.ua/courses/learn/2947
(тут не можу - таблиці треба креслити...)

Додано (05.11.2010, 19:17)
---------------------------------------------
За добу - ЖОДНОГО відвідування за вказаним ппосиланнм

Відредаговано: pasichov - Чт, 04.11.2010, 20:21
Ковальчук_Олександр Дата: Пт, 05.11.2010, 20:35 | Повідомлення № 54
Ветеран спілкування
Повідомлень: 3621
Нагороди: 17
Рейтинг: 192
Як тільки звільнюсь від роботи - щонайменше 1 відвідування появиться. Ми з моїм учнем проаналізуємо нову задачу і спробуємо розв’язати. Чим більше цікавлюсь цією темою, тим більше усвідомлюю, що цікавіше за програмування може бути тільки програмування. Жалко, що не всі учні (та й вчителі) це усвідомлюють.
TarasBTS Дата: Вт, 11.10.2011, 21:58 | Повідомлення № 55
Новий користувач
Повідомлень: 1
Нагороди: 1
Рейтинг: 4
Задача Worms. Її можна розвязати без циклів.
Code

program worms;
var n,h,c: integer;
begin
       read(n);
       h:=n div 10;
       c:=2;
       c:=round(c*exp(ln(2)*h));
       writeln(c);
end.



Відредаговано: TarasBTS - Ср, 12.10.2011, 21:44
Форум інформатиків » РОЗДІЛ VIІІ: ОБМІН ДОСВІДОМ (УРОКИ, ФАКУЛЬТАТИВИ, ПОЗАКЛАСНА РОБОТА) » 8.6 Факультатив з програмування » Задачі для початківців з сайту http://netoi.org.ua/ (Розв’язуємо разом.)
Сторінка 4 з 4«1234
Пошук:


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