Отправляет 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


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


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

Автор
Aslof

Статистика

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

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


Служба Рассылок Subscribe.Ru

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

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

Подписчиков на 2002-04-08 - 2968 человек(а).
Главная Программы Задачи Рассылки Гостевая книга Контакты

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

Письма читателей:
  Письма в данный раздел отбираются по усмотрению автора рассылки, интересные для большого круга подписчиков. Корреспонденция, оскорбляющая чьё-либо достоинство или содержащая нецензурные выражения, публикации не подлежит.
From: Stanislav Baldanov <steve@mail.ru>
To: sapisoft@yandex.ru
Date: Wednesday, April 03, 2002, 4:07:09 AM
Subject: На счёт целесообразности использования процедуры для обмена значения с помощью xor

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

Алексей Ильичёв, как вы думаете насколько оправдано использование той процедуры, которую вы представили?

Procedure swap(Var a, b : integer);
begin
a := a xor b;
b := a xor b;
a := a xor b;
end;

Вместо того чтобы использовать:

a := a xor b;
b := a xor b;
a := a xor b;

Вы будете использовать:

swap(a, b);

Да, конечно, это более кратко. Но этим вы напрочь "снесли" то преимущество, которое имеет непосредственное использование xor без вызова процедуры. А именно скорость и элегантность. И та проблема, о которой вы говорите, в таком случае отпадает за невозможностью её возникновения. Да и в вашем варианте она тоже немыслима. Зачем менять значениями а и а? Вы
может, и найдёте алгоритм, при котором возникает такая необходимость, но это будет говорить лишь о недостатках такого алгоритма.

В чём я не прав?
From: Serhiy Serbin <serhiys@adarvo.com>
To: sapisoft@yandex.ru
Date: Thursday, April 04, 2002, 8:29:57 AM
Subject: "Хорошее" решение задачи, предложенной Serhiy Serbin в #25

Привет,

==================
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 28, 2002, 11:43:46 PM
Subject: "Хорошее" решение задачи, предложенной Serhiy Serbin в #25

Зачем же уравнение прямой? Гораздо проще посмотреть знак векторного
произведения. Формула для нахождения векторного произведения через координаты
векторов очень простая: x2*y1-x1*y2.

Д.З.: посмотреть на примере, какой знак принимает это произведение при левом
повороте ;-)
==================

Ответ: Да конечно, это абсолютно правильное решение, по крайней мере, я так считаю, опираясь на свои математические знания:). Хочу только добавить, что < 0 для левого, больше для правого и = 0 для продолжения. Но все-таки, если взять уравнение прямой, то эту задачу можно решить чуть иначе.

Построим по точкам i - (i+1) уравнение прямой, конечно же, вида Ax + By + C = 0 (y = kx + b - это частный случай). Коэффициенты находятся однозначно, при условии что i и (i+1) - разные точки. Далее вычислим значение функции: Ax(i+2) +
By(i+2) + C, где x(i+2) и y(i+2) соотвественно координаты третей точки. Далее такое же правило, если больше нуля то правый, если меньше то левый, и равно 0 лежит на первоначальной прямой. Я просто хотел дополнительно подчеркнуть, что
знание этого факта также бывает полезно. Хотя согласен, что первое решение более оптимально :))

==================
From: Алексей Ильичёв <alex_z77@mail.ru>
To: sapisoft@yandex.ru
Date: Thursday, March 28, 2002, 11:16:56 PM
Subject: Ответ на ложное обвинение Yuri Y. Roumega, опубликованное в #25

2.Рекомендуется всем, кто не понял перечитать моё послание ещё разок ;-)

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

Procedure swap(Var a, b : integer);
begin
a := a xor b;
b := a xor b;
a := a xor b;
end;

Если в параметрах вызова указана одна и та же переменная, то после выполнения оператора a := a xor b обнулится не только A, но и B. Можете проверить на опыте.
Я бы не стал писать об этом, если бы сам несколько раз на этом не погорел...
==================

Ответ: опять-таки повторюсь, я не силен в синтаксисе Паскаля, но догадываюсь, что речь идет, конечно же, о ссылках на параметры. Просто нет смысла вызывать данную функцию, с параметрами по значению. И конечно, следующий вызов будет
ошибочный, если a <> 0: swap(a, a); Поэтому приведенное замечание абсолютно верно, но данное замечание следует рассматривать более в контексте реализации, а не с точки зрения теории:)) Но в любом случае факт полезный.

Best regards,
Serhiy Serbin
From: Jupiter <jupiter_the_god@hotmail.com>
To: "sapisoft" <sapisoft@yandex.ru>
Date: Saturday, April 06, 2002, 4:53:34 PM
Subject: Тема в теорию

Приветствую!

Я хочу предложить тему (потому что я сам не раз на этом обламывался) - "Работа с большими числами".

Jupiter
jupiter@au.ru
Алексей Шамис: На сервере "vseolimp.by.ru" есть прекрасная статья на эту тему. У кого нет возможности зайти на сайт, напишите, могу бросить по почте. URL: http://vseolimp.by.ru/train/lessons.shtml. А в этом номере предлагаем задачу на эту тему. Детальный разбор читайте на сайте.

ЗАДАЧИ

Произведение длиных чисел (3 уровень)

Условие:
Даны два n-значных числа, где n<=200. Вычислить их произведение.

Технические требования:
Ограничение по времени тестирования: по 5 секунд на один тест.

Решение:
Для решения поставленной задачи необходимо уметь выполнять следующие действия:

1) ввод "длинного" числа;
2) собственно умножение двух "длинных" чисел;
3) вывод "длинного" числа;
4) определение количества цифр в записи числа.

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

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

Так же разработаем функцию определения количества значащих цифр в записи числа, поскольку она потребуется при реализации подпрограммы умножения.

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

Const NMax = 2000;
Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;
Var S : String;
  M, N, R, F : DlChislo;
  I, MaxF : Word;
  Logic : Boolean;

{Процедура обнуления длинного числа}
Procedure Zero(Var A : DlChislo);
Var I : Integer;
Begin
  For I := 1 To NMax Do A[I] := 0;
End;

{Функция определения количества цифр в записи длинного числа}
Function Dlina(C : DlChislo) : Integer;
Var I : Integer;
Begin
  I := NMax;
  While (I > 1) And (C[I] = 0) Do I := I - 1;
  Dlina := I
End;

{Процедура печати длинного числа}
Procedure Print(A : DlChislo);
Var I : Integer;
Begin
  For I := Dlina(A) DownTo 1 Do Write(A[I] : 1);
  WriteLn
End;

{Процедура преобразования длинного числа в массив цифр}
Procedure Translate(S : String; Var A : DlChislo;
Var OK : Boolean);
Var I : Word;
Begin
  Zero(A); I := Length(S); OK := True;
  While (I >= 1) And OK Do
  Begin
    If S[I] In ['0'..'9']
    Then A[Length(S) - I+ 1] := Ord(S[I]) - 48
    Else OK := False;
    I := I - 1
  End
End;

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);
Var I, J : Integer; P : Digit; VspRez : 0..99;
Begin
  Zero(C);
  For I := 1 To Dlina(A) Do
  Begin P := 0;
    For J := 1 To Dlina(B) Do
    Begin
      VspRez := A[I] * B[J] + P + C[I + J - 1];
      C[I + J - 1] := VspRez Mod 10;
      P := VspRez Div 10
    End;
    C[I + J] := P
  End
End;

{Основная программа}
Begin
  Repeat {повторяем ввод, пока число не будет введено правильно}
    Write('Введите первый множитель: ');
    ReadLn(S); Translate(S, M, Logic)
  Until Logic;
  Repeat
    Write('Введите второй множитель: ');
    ReadLn(S); Translate(S, N, Logic)
  Until Logic;
  Multiplication(M, N, R); Print(R);
  Readln;
End.

ТЕОРИЯ

Функции  и процедуры для работы со строками

  Продолжаем обзор функций и процедур языка Turbo Pascal. Материал представлен сайтом "g6prog.narod.ru".

  Следующие процедуры и функции используются для работы со строками Паскаля.

Функция Описание
Cоncat Выполняет конкатенацию последовательности строк.
Cору Возвращает подстроку строки.
Delete Удаляет из строки подстроку.
Insert Добавляет в строку подстроку.
Length Возвращает динамическую длину строки.
Pоs Производит поиск подстроки в строке.
Str Преобразует численное значение в его строковое представление.
Val Преобразует строковое значение в его численное представление.

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

ТЕМЫ ФОРУМА:

11. Владимир [Помогите плиз с РГЗ] 07-Апр (21:09) new!

10. Antrax [Поиск с возвращением] 04-Апр (19:39)

9. Катюшка [Помогите стать программистом!] 04-Апр (12:54)
     Александр [re: Помогите стать программистом!] 05-Апр (16:48)

8. Алексей Ильичёв [Удачи всем!] 03-Апр (07:27)

7. Алексей Ильичёв [Зачем этот форум?] 01-Апр (16:24)
     Алексей Шамис [re: Зачем этот форум?] 01-Апр (23:51)

6. Anton [Системы линейных уравнений] 25-Мар (18:15)
     Алексей Ильичёв [re: Системы линейных уравнений] 01-Апр (16:21)

5. Михаил [Правило Варнсдорфа] 20-Мар (14:30)

4. Сергей [ПОМОГИТЕ!!!!!] 19-Мар (20:31)
     Berdan [re: ПОМОГИТЕ!!!!! (+)] 24-Мар (17:26)

3. Тоня [Помогите пожалуйста решить задачу!!!!] 19-Мар (08:38)
     Петрович [re: Помогите пожалуйста решить задачу!!!!] 30-Мар (00:59)
       Тоня [re: Помогите пожалуйста решить задачу!!!!] 30-Мар (09:45)
         Konstantin [re: Помогите пожалуйста решить задачу!!!!] 05-Апр (18:36)
     Mad Wild [re: Помогите пожалуйста решить задачу!!!!] 01-Апр (00:17)
       Mad Wild [re: Помогите пожалуйста решить задачу!!!!] 03-Апр (00:30)

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

1. Webmaster [Дизайн на сайте.] 14-Мар (16:01)
     Максим [re: Дизайн на сайте.] 22-Мар (12:48)

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

RLE    

  

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

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

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

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

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