Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Март 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Служба Рассылок Subscribe.Ru
Олимпиадные задачи c решениями на Turbo Pascal

Олимпиадные задачи с решениями на Turbo Pascal

Рассылка проекта Sapisoft.By.Ru [#024]

Подписчиков на 18.03.2002 - 2785 человек.
Главная Программы Задачи Рассылки Гостевая книга Контакты

Здравствуйте, уважаемые подписчики!
  1. Наконец-то на сайте заработал форум! Там вы можете попросить консультацию по решению задчи, обсудить алгоритм, поделиться впечатлениями с олимпиады, и ещё много чего;). Заходите, будем рады!

  2. Наш проект становиться довольно популярным в Рунете. Рамблер на запрос "олимпиадные задачи по информатике" наш сайт sapisoft.by.ru выводит на первое(!) место. И это при том, что я раскрутке времени практически не уделял ;].
 
  3. Меня не будет с недельку, так что вы не скучайте;). И про сайт не забывайте. Можете пока на форуме пообщаться...

Письма читателей:
Я конечно думал, что заметка про обмен значений переменных вызовет некоторое количество замечаний, но в таком объёме...;[]
From: Andy Ice <AndyIce@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:32:19 AM
Subject: Олимпиадные задачи с решениями на Turbo Pascal

Хотелось бы предостеречь от явной ошибки в данном алгоритме. Дело в том, информатика - это, все таки, не "чистая математика", и возможно сразу же в первой строчке получить ошибку переполнения.

Пример:
a, b: Byte;
a0 := 250;
b0 := 200;

Результат?
From: Andrew Ezhguroff <eandr@com2com.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 11:29:42 AM
Subject: Обмен значений переменных

Здравствуйте.

Если в языке возможны битовые операции с целыми числами (не знаю, есть ли это в TP), то subj можно записать забавнее:

a:=a xor b; {a=a0^b0, b=b0}
b:=a xor b; {a=a0^b0, b=a0^b0^b0=a0}
a:=a xor b; {a=a0^b0^a0=b0, b=a0}

С уважением, Андрей.
From: zugr <zugr@unikon-ua.net>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 2:10:18 PM
Subject: Обмен значений переменных

А на С это ищё красивее:

a^=b;
b^=a;
a^=b;

:-)
From: Boris Bukh <brbukh@yahoo.com>
To: sapisoft@yandex.ru
Date: Thursday, March 14, 2002, 6:20:58 PM
Subject: Неточность в теории

Hello,

В последней рассылке неточность в разделе теория. Если использовать +,- то тогда если нечайно откомпилировать прогу с проверкой переполнения, то тогда можете получить run-time error в самый неприятный момент. Лучше пользоваться xor.

a:=a xor b; {a=a0 xor b0 }
b:=a xor b; {b=a0}
a:=a xor b; {a=b0}

Проблемы в том что это работает только на целочисленных и булевых переменных, а вот на вещественных как быть? Ваш прием на вещественных также не пройдет еще по причине неассоциативности сложения в компьютерной арифметики. Предлагаю выставить эту задачу в раздел "Нерешенные задачи".
From: Serhiy Serbin <serhiys@adarvo.com>
To: sapisoft@yandex.ru
Date: Friday, March 15, 2002, 9:32:38 AM
Subject: Обмен значений переменных

Привет, то что придумали давно не спорю :)) Но знать должен каждый :)) Есть еще один вариант, по идее должен роботать быстрее:

a = a ^ b;
b = a ^ b;
a = b ^ a;

, где = - оператор присваивания, а ^ - xor. К сожалению Паскакаль не знаю, так что в его нотации записать не могу.

Best regards,
Serhiy Serbin
From: Alex <malex@ua.fm>
To: sapisoft@yandex.ru
Date: Friday, March 15, 2002, 2:45:38 PM
Subject: Обмен значений переменных

Hi!

хорошая рассылка! только imho: 1 - мало:(, 2 - только самые известные проблемы!

в рассылке от 11.03.2002 был известный пример Сабжа от HellMan

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
procedure swap(var a, b: char);
begin
if a = b then
exit;
byte(a) := byte(a) xor byte(b);
byte(b) := byte(a) xor byte(b);
byte(a) := byte(a) xor byte(b);
end;
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-==

дык этот обмен имеет несложное продолжение на циклический сдвиг n переменных:

procedure rotR(var x1, x2, ...., xn: longint);
begin
x1:= x1 xor x2 xor x3 xor ..... xor xn;
x2:= x1 xor x2 xor x3 xor ..... xor xn;
x3:= x1 xor x2 xor x3 xor ..... xor xn;
.....
xn:= x1 xor x2 xor x3 xor ..... xor xn;
x1:= x1 xor x2 xor x3 xor ..... xor xn;
end;

зы: ну и далее можно развивать экстенсивно....

ззыы: в частности можно любую !ИЗВЕСТНУЮ! (!) перестановку n чисел реализовать - за n+1 строчку!

Gby! Gby! See you later...
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Saturday, March 16, 2002, 6:37:40 AM
Subject: Теоретическая часть: обмен значений переменных

Здравствуйте, Алексей.

Хотелось бы прокомментировать хитрость, которую вы продемонстрировали в теоретическом разделе выпуска 23.

Есть практически аналогичный способ, обеспечивающий нам полную устойчивость. Оператор A := A + B; может выполниться с ошибкой, т.к. никто нам не гарантирует, что размер переменной A позволяет хранить значение суммы A + B. Чтобы избежать такого маленького недоразумения, как переполнение, можно тот же приём проделать через XOR-сумму. Например так:

A := A xor B; {A = a0 xor b0}
B := A xor B; {B = a0 xor b0 xor b0 = a0}
A := A xor B; {A = a0 xor b0 xor a0 = b0}

Ещё хотелось бы предостеречь читателей от типичной ошибки:

Procedure Swap(Var A, B : Integer);
begin
A := A xor B;
B := A xor B;
A := A xor B;
end;

Если такой процедурке задать в качестве параметров одну и ту же переменную, она обнулиться. Т.к. получится, что A и B - это одна и та же переменная, а как известно A xor B = 0. То есть если вы пишите алгоритм, в котором вы не застрахованны от подобного вызова, лучше не жадничать, и выделить лишних несколько байт для обмена через 3-ю переменную. (эта ошибка касается так же обмена через сумму).
Алексей Шамис: От себя хочу добавить, что на существование имеет право любой из представленых алгоритмов, просто каждый из них имеет те или иные ограничения. Начинающему легче понять первый вариант решения задачи, а "продвинутые" программисты могут использовать функцию XOR для сложения чисел. В любом случае, спасибо за активность!

ЗАДАЧИ

Последовательность (3 уровень)
Условие:
Дана последовательность натуральных чисел (значение каждого числа от 1 до 1000). Последовательность может быть не отсортирована. Надо найти вариант самой большой (по количеству элементов) неубывающей последовательности, составленной из чисел этого ряда. Порядок включения чисел в неубывающую последовательность должен соответствовать порядку следования чисел в первоначальной последовательности. Иными словами, числа с большими номерам и в новой последовательности размещаются правее чисел с меньшими номерами.

Технические требования:
Файл INPUT.TXT в 1-й строке содержит количество чисел в последовательности - N (1<=N<=100). Со 2-й строки и далее указан ряд чисел, каждое число размещается на новой строке. Поиск ошибок в файле не требуется, входные данные корректны.

В файле OUTPUT.TXT помещаются выходные данные. 1-я строка содержит длину максимальной неубыващей последовательности.
2-я строка и далее - пример такой последовательности, каждое число в порядке следования размещается на новой строке.

Пример файлов входных и выходных данных:

Input.txt

Output.txt
12
59
4
21
36
18
27
79
34
45
47		 7
4
21
27
34
45
47
93

Решение: by Александр Никитин <http://g6prog.narod.ru>:

{$M $8000,0,$4ffff}

Const MaxItem = 100;
  TimeLimit = 29*18; {29 sec}

var Numbers, Seq, Best: array[1..MaxItem] of integer;
  pc,maxpc,num:integer;
  timer:longint absolute $0040:$006C;
  jiffy:longint;

Procedure Init;
var i:integer;
begin
  jiffy:=timer;
  fillchar(Numbers, Sizeof(Numbers),#0);
  Seq:=Numbers; Best:=Numbers; pc:=0; maxpc:=0;
  assign(input,'seq.in'); reset(input);
  readln(num); if num>MaxItem then num:=MaxItem;
  for i:=1 to num do readln(Numbers[i]);
  close(input);
end;

Procedure Done;
var i:integer;
begin
  assign(output,'seq.out'); rewrite(output);
  writeln(maxpc);
  for i:=1 to maxpc do writeln(Best[i]);
  close(output);
end;

procedure StoreChain;
begin
  if (pc>maxpc) then begin
    Best:=Seq;
    maxpc:=pc;
    if (maxpc=num) then begin
      Done;
      Halt(0);
    end;
  end;
end;

function testFWD(i:integer):integer;
var m:integer;
begin
  m:=Numbers[i]; inc(i);
  while (i<=num) and (m>Numbers[i]) do inc(i);
  if i>num then testFWD:=0 else testFWD:=i;
end;

procedure solution(n:integer); { Основная процедура }
var i,s:integer;
begin
  if ((timer-jiffy)>TimeLimit) then exit;
  i:=testFWD(n);
  if (i=0) then begin
    StoreChain;
  end else begin
    inc(pc); {проверили этот путь}
    Seq[pc]:=Numbers[i];
    solution(i);
    dec(pc); {идем по другому}
    s:=Numbers[i]; Numbers[i]:=-1; {вычеркнули}
    solution(n);
    Numbers[i]:=s; {вернули}
  end;
end;

var index:integer;

begin
  Init;
  index:=1;
  repeat
    pc:=1;
    Seq[pc]:=Numbers[index];
    solution(index);
    while (index<=num) and (Numbers[index]>=Seq[pc]) do inc(index);
  until (index>num);
  Done;
end.

ТЕОРИЯ

Немного математики...

  Часто на олимпиадах по информатике предлагаются задачи с математическим (а точнее с геометрическим уклоном). Поэтому я решил, что не лишним будет напомнить читателям некоторые факты, которые необходимо знать при решении таких задач.

  Как известно, любая прямая задается уравнением вида Y=K*X+B. Так вот. Следует помнить, что:
 
  - Если две прямые перпендикулярны, то K1*K2=1;
  - Если две прямые паралельны, то K1=K2;

  Ну, и раз уже заговорили о прямых, то напомним еще и формулу вычисления координат середины отрезка:

  X = (X1+X2)/2;  Y = (Y1+Y2)/2;

  Продолжение следует...

  Если у вас есть интересная информация для данной рубрики - пишите: sapisoft@yandex.ru.

ТЕМЫ ФОРУМА:

2. Петров Денис [Помогите решить задачку] 15-Мар (15:56)
     Алексей Ильичёв [re: Помогите решить задачку] 17-Мар (00:30)

1. Webmaster [Дизайн на сайте] 14-Мар (16:01)

Реклама в рассылке:

RLE    

  

Рассылки проекта Sapisoft:
Новости проекта Sapisoft [Шамис Алексей]
Информация о выходе новых версий программ и прочих обновлениях на сайте.

 Уроки программирования на Turbo Pascal [Галин Павел]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Шамис Алексей]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Периодичность - 2-3 раза в неделю. Каждый выпуск содержит решение 2-3 задач с подробным анализом описанием алгоритма решения.

 Задача в неделю. Олимпиадные задачи по информатике [Алексеев Александр]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть вас на нашем сайте!
Aleksey Shamis - sapisoft@yandex.ru
Sapisoft Project - http://sapisoft.by.ru
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное