Отправляет 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
28.02.2002
00:18:54
23:38:21


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


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

Автор
Aslof

Статистика

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

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


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

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

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

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

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

Шахматный номер (3 уровень)
Условие:
Телефонный номер называется «шахматным», если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных «шахматных» номеров, начинающихся с заданной цифры.
  
1 2 3
4 5 6
7 8 9
  0  

Технические требования:
Входной файл INPUT.TXT содержит число N [0..9]. Выходной файл OUTPUT.TXT должен содержать единственное число - решение задачи.

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

Input.txt

Output.txt
1 136
4 168
5 0
8 104

Решение:
Вначале для каждой цифры нужно задать все возможные пути перемещения (конём). Затем, используя рекурсивную процедуру, выполняем поиск всех семизначных номеров, удовлетворяющих условию...

const
  mas:array[0..9,1..3] of integer =
      ((4,6,-1), (6,8,-1), (7,9,-1),
      (4,8,-1), (3,9,0), (-1,-1,-1),
      (1,7,0), (2,6,-1), (1,3,-1), (2,4,-1));
  input = 'input.txt';
  output = 'output.txt';

var
  N:integer;
  Tel:integer;
  f1,f2:text;

procedure Find(digit:integer; count: integer);
var i:integer;
begin
  if digit=-1 then exit;
  if count =7 then begin inc(Tel);exit;end;
  for i:=1 to 3 do
  Find(mas[digit,i],count+1);
end;

begin
  assign(f1,input);
  reset(f1);
  read(f1,n);
  close(f1);

  find(N,1);

  assign(f2,output);
  rewrite(f2);
  write(f2,Tel);
  close(f2);
end.
Ваша почта:

From: Fyodor Menshikov <mfv@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Wednesday, February 27, 2002, 8:49:26 AM
Subject: Задачи на TP от 21.02.2002

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

Решение (by Boris Bukh <brbukh@yahoo.com>) не является правильным. На тесте "50 250" оно вообще ничего не выдаёт. Видимо, ломается. Дело в том, что используемый в решении тип comp может представить только 18 или 19 разрядов целого числа (не помню). Уже на тесте "20 100" оно выдаёт 33-х значное решение. (Очевидно, оно не точно.) Из всего этого я могу заключить, что для решения задачи требуется длинная арифметика. Причём в том числе и длинное возведение в квадрат, что совсем уже нетривиально.

Ещё комментарии насчёт приведённого решения. Да, оно по-видимому, работает для маленьких S и N. Но оно имеет следующие недостатки:

1. очень запутанная формула. Почему бы просто не сложить V[i,j]=sum(k=0..9,V[i-1,j-k]) в явном виде? Число действий тут небольшое, торопиться некуда.

2. Выражение FillChar(V,SizeOf(V),0); не слишком корректно. Если быть совсем "крутым", то нужно просто считать, что в TP глобальные переменные уже инициализированы нулями. А если вообще не использовать примочки, то нужно выполнить цикл с обнулением. Что касается FillChar в цикле, то оно вообще необязательно. В цикле j возрастает, а по формуле там идёт обращение только к j-1-му элементу из текущего ряда.
Очевидно, оно уже вычислено. Что касается отрицательных индексов, то их нулевые значения в алгоритме не меняются.

3. Не нужно делать дополнительных ограничений на S (тут было ограничение до 1000). Просто больше N*2*9 сумма быть не может. (Это максимальная сумма в 2N-значном числе.) А это 900 при N=50. Т.е. ограничение 1000 - это, конечно, разумно, но в нём нет необходимости.

Несмотря на все отмеченные недостатки приведённого решения, его идея является абсолютно правильной. Однако ещё в выпуске упоминается алгоритм от Hellman'a (alexec@newmail.ru). Этот алгоритм в принципе неверен. Для N=50 за разумное время нельзя пойти ни по первому, ни по второму пути, обозначенному этим товарищем.

С уважением,
Фёдор Меньшиков.

From: Fyodor Menshikov <mfv@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Wednesday, February 27, 2002, 8:55:26 AM
Subject: Задачи на TP от 23.02.2002

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

Возможно, решения (by Antrax <antrax@mail.nnov.ru>) неверны - это зависит от формулировки задачи. Если в условии гарантируется, что входные числа все разные, то решение верно, если можно повторять перестановки, то решение верно. А вот если числа могут повторяться и перестановки должны выводиться по одному разу, то решение неверно.

С уважением,
Фёдор Меньшиков.

From: Fyodor Menshikov <mfv@mail.ru>
To: "Aleksey Shamis" <sapisoft@yandex.ru>
Date: Wednesday, February 27, 2002, 9:41:40 AM
Subject: Задачи на TP от 25.02.2002

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

Комментарий к решению (by HellMan [alexec@polarcom.ru]).

1. В решении используется факт, что для любого N найдётся простое число между N+1 и 2N включительно. Не могли бы Вы в рассылках давать обоснование в явном виде и хотя бы ссылку на доказательство, а то я доказательства этого факта не знаю. Я понимаю, что для N<=500000 это, скорее всего, соблюдается, но вообще обоснование нужно. Или доказательство для общего случая.

[Давайте попробуем обратиться с этим вопросом к автору решения. - комментарий ведущего]

2. В решении рассматриваются 3 случая через else if: когда N=2, когда N простое и остальной случай. Решение для последнего случая является решением и для первых двух, поэтому их выделять не надо.

С уважением,
Фёдор Меньшиков.
Реклама в рассылке:

RLE Banner Network    

  

Рассылки проекта 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 		Отписаться
Убрать рекламу
В избранное