Письма читателей 28

  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения, публикации не подлежит.

From: Hilary <lars@ezmail.ru>
To: sapisoft@yandex.ru
Date: Friday, April 12, 2002, 9:29:30 PM
Subject: Вопрос: требуются задачи по определенной тематике

Добрый день!

Проблема следующая: ищу задачи (олимпиадные и не олимпиадные), решаемые Методом индукции (как Вы понимаете, это не только математический метод, но и метод построения конструкций, метод доказательства).

Очень прошу помочь в моем поиске, можно конкретными задачами, можно указанием мест, где их можно поискать (литературу или интернет-странички).

Если Вы сможете чем-то помочь - большое спасибо (а если нет - так что ж:)

Лариса
mailto:lars@ezmail.ru

Алексей Шамис: Попробуйте задать вопрос на форуме...

From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Sunday, April 14, 2002, 8:38:15 PM
Subject: Ответ на письмо Станислава Балданова, опубликованное в # 27

Я не буду изобретать велосипед, я просто скопирую небезызвестную реализацию алгоритма Хоара "быстрой сортировки":

procedure sort(l,r: integer);
var
  i,j,x,y: integer;
begin
  i:=l; j:=r; x:=a[(l+r) DIV 2];
  repeat
    while a[i]<x do i:=i+1;
    while x<a[j] do j:=j-1;
    if i<=j then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

Как вы думаете, будет ли она работать, если вместо строчки "y:=a[i]; a[i]:=a[j]; a[j]:=y;" написать обмен через XOR?

From: Z.M. <st-zhilin@belgtts.ru>
To: sapisoft@yandex.ru
Date: Saturday, April 13, 2002, 8:36:28 AM
Subject: none

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

Это снова я (Mike). Я только вернулся из Перми, где проходила Всероссийская олимпиада по информатике. Поэтому ранее я не мог ответить. Я нашел данный тест к задаче о последовательности. Вот он:

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

Теперь мне очень интересно, откуда там 93 в выходном файле? А так вроде все правильно (если конечно вникнуть в условие).

С уважением, Mike.

Алексей Шамис: Да, действительно, и семерка вначале тоже лишняя.