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

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

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.825 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.825 подписчиков
0 за неделю
←   Все выпуски   →

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


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

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

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

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

Здравствуйте!
1. Опять я перепутал коды рассылок и разослал вам "Новости проекта Sapisoft". Дико извиняюсь:(.
2. В связи с весной, всем желаю много-много счастья и любви!;)
3. В этом выпуске (20 - a little юбилей;) предлагаем ещё одно решение задачи "Шахматный номер" (by Алексей Ильичёв).

Шахматный номер (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

Решение: by Алексей Ильичёв alex_z77@mail.ru:

{$A+,B-,D+,E+,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 16384,0,655360}

const
canmove : array [0..9, 1..3] of shortint =
          ((4, 6, -1),(6, 8, -1),(7, 9, -1),
          (4, 8, -1),(0, 3, 9),(-1, -1, -1),
          (0, 1, 7),(2, 6, -1),(1, 3, -1),(2, 4, -1));
          {Так мы задаём откуда и куда может ходить конь}

var
  n, i, j, k : byte;
  res : array[1..7, -1..9] of integer;
  {-1 -й элемент массива нужен, чтобы не проверять лишний раз,
  не равен ли элемент массива canmove -1}
  sum : integer;

begin
  assign(input, 'input.txt');
  reset(input);
  read(n);
  close(input);

  {применяем метод динамического программирования: }
  res[1, n] := 1; {в элементе [x, y] этого массива будем хранить кол-во
  номеров длины x, заканчивающихся цифрой y и отвечающих условию}
  for i := 1 to 6 do {зная i-ю колонку массива res, можем посчитать i+1-ю}
  for j := 0 to 9 do
  for k := 1 to 3 do
  inc(res[i+1, canmove[j, k]], res[i, j]);

  {осталось только просуммировать последнюю колонку и вывести результат}
  for i := 0 to 9 do inc(sum, res[7, i]);
  assign(output, 'output.txt');
  rewrite(output);
  writeln(sum);
  close(output);
end.

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

From: Екатерина <speaker101010@yahoo.com>
To: sapisoft@yandex.ru
Date: Thursday, February 28, 2002, 3:19:59 PM
Subject: Вопрос

Здравствуйте, Алексей!
Я являюсь подписчиком Вашей рассылки "Олимпиадные задачи с решением на Turbo Pascal". Мне очень нравится эта рассылка.
Поэтому когда у меня возникла задача распределения файлов по папкам, я решила обратиться к Вам. Задача сосотоит в следующем. Имеется набор файлов. Необходимо распределить их по папкам так, чтобы размер папки не превышал заданного значения. При этом файл может быть разрезан на части. Задан размер папки, процент заполнения папки (если папка заполнена на х%, тогда она может считаться заполненной). Также задается значание у - размер документа. Документы размера меньше у не разрезаются.

Не могли бы Вы предложить алгоритм решения такой задачи?

С уважением, Екатерина.

Шамис Алексей: Может, у кого-то есть наработки - помогите девушке.

From: santavlas <santavlas@regionnet.ru>
To: sapisoft@yandex.ru
Date: Friday, March 01, 2002, 5:54:06 AM
Subject: basic

Здравствуйте!
Не подксажите ли где происходит обучение языку Basic - qbasic or gwbasic.

Спасибо.
С уважением.

Шамис Алексей: Поищите в рассылах на Subscribe.ru. А вообще рекомендую хороший сайт по VB - http://vbnet.ru.

From: HellMan <alexec@newmail.ru>
To: sapisoft@yandex.ru
Date: Thursday, February 28, 2002, 3:19:55 PM
Subject: Олимпиадные задачи с решениями на Turbo Pascal || #019 || комментарии

Два раза ку, Алексей!

> From: Fyodor Menshikov <mfv@mail.ru>
> Однако ещё в выпуске упоминается алгоритм от Hellman'a (alexec@newmail.ru).
> Этот алгоритм в принципе неверен. Для N=50 за разумное время нельзя пойти ни
> по первому, ни по второму пути, обозначенному этим товарищем.
Нет мне прощения! Извините, читатели, что ввел Вас в блуд ;)
Могу сказать, что когда увидел динамическое решение той задачи, то долго
ходил и бился головой об стенку.

> Комментарий к решению (by HellMan [alexec@newmail.ru]).
> 1. В решении используется факт, что для любого N найдётся простое число
> между N + 1 и 2 * N включительно. Не могли бы Вы в рассылках давать
> обоснование в явном виде и хотя бы ссылку на доказательство, а то я
> доказательства этого факта не знаю. Я понимаю, что для N <= 500000 это,
> скорее всего, соблюдается, но вообще обоснование нужно. Или доказательство
> для общего случая.
В доказательствах не силен. Но могу поделиться опытными данными. Вот
программа, которая ищет простые числа и интервалы между ними. Можно
заметить, что интервал всегда меньше половины следующего числа.

var
  i, j, n, ln: longint;
  ok: boolean;
begin
  assign(output, 'output.txt');
  rewrite(output);
  writeln('2');
  ln := 2;
  for i := 3 to 1000 do begin
    ok := true;
    for j := 2 to trunc(sqrt(i)) do
    if i mod j = 0 then begin
      ok := false;
      break;
    end;
    if ok then begin
      writeln(i, ' (', i - ln, ')');
      ln := i;
    end;
  end;
  close(output);
end.

Интересно, сколько ошибок читатели найдут в этой программе? ;)

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

Искренне свой, HellMan [28.02.2002]
Реклама в рассылке:

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