пятница, 5 декабря 2014 г.

Треугольник Паскаля

Сегодня мы рассмотрим не сложную, но интересную задачу - построение "Треугольника Паскаля".

Вы из курса математики знаете такие формулы сокращенного умножения:

(a + b)2 = a2 + 2ab + b2

(a + b)3 = a3 + 3a2b + 3ab2 + b3

Теперь давайте посмотрим на картинку, изображающую треугольник Паскаля:

какая связь между цифрами в каждой из строк треугольника и приведенными выше формулами? Догадались? Проверяем!


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

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

Проверьте свой вывод по картинке:


Теперь давайте сформулируем вывод на языке информатики. 
Пусть каждый элемент треугольника обозначается как a[ i , j ], где  a - сам элемент,  i - номер строки, в которой он находится, а j - порядковый номер этого элемента в строке. Например, обведенные в красные кружки элементы - это a[ 3 , 2 ] = 2 и a[ 7 , 3 ] = 15.
Мы не можем использовать строку с номером 0, поэтому наша нумерация строк будет на 1 больше степени n на приведенном рисунке.

Тогда мы можем сделать вывод, что ПОЧТИ каждый элемент треугольника - это сумма элементов строкой выше, один из которых идет под тем же номером, что и искомый элемент, а у второго номер на 1 меньше.

Слово ПОЧТИ в утверждении выше указывает на то, что первый и последний элементы в каждой строке равны 1, вне зависимости от номера строки.

Из всего вышесказанного вытекает задание:

Написать программу, которая из входного файла будет считывать n - степень, до которой строится треугольник, а файл вывода будет содержать треугольник Паскаля из n + 1  строк - мы выше говорили, что 0 степень есть, а 0 строки нет.

Например, в файле ввода число 8.

Тогда файл вывода должен выглядеть так:


Можете проверить результат для 8 степени, сверив с рисунком выше.

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

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

Если самостоятельно справиться - не судьба, смотрим решение задачи по ссылке.

Но давайте сначала самостоятельно, да?! Удачи!

суббота, 29 ноября 2014 г.

Задачи районной олимпиады по программированию. Задача 11_2

Итак, полное условие задачи:

     В I туре Интернет-олимпиады по программированию n учеников все задачи решили верно, но время выполнения у всех было разным: X1, X2, X3,...Xn, (Xi - натуральное число, время выполнения работы i-ым участником,  n <20). Как выяснилось, у тех, кто справился с заданием быстрее, и решение было более эффективным. Задания можно было решать на протяжении двух дней. 

Задание: Жюри необходимо выбрать четырех программистов с лучшим результатом для участия во II туре олимпиады, при этом необходимо указать номера, под которыми они принимали участие в олимпиаде.

Формат входных данных: В файле input.txt в первой строке - количество учеников, которые все выполнили, а в остальных n строчках - результаты: X1, X2, X3,...Xn

Формат выходных данных: В файле output.txt 4 строки, каждая содержит по два числа через пробел: первое число в строке - один из четырех лучших результатов, второе число - номер участника олимпиады, имеющего этот результат.

Решение:

Давайте сначала еще раз прочитаем условие. Красным цветом я выделю те слова, которые нас действительно интересуют.

  В I туре Интернет-олимпиады по программированию учеников все задачи решили верно, но время выполнения у всех было разным: X1, X2, X3,...Xn, (Xi - натуральное число, время выполнения работы i-ым участником,  n <20). Как выяснилось, у тех, кто справился с заданием быстрее, и решение было более эффективным. Задания можно было решать на протяжении двух дней. 

Задание: Жюри необходимо выбрать четырех программистов с лучшим результатом для участия во II туре олимпиады, при этом необходимо указать номера, под которыми они принимали участие в олимпиаде.

Какие действия, исходя из этого, должна выполнять программа?
  1. Открыть файл с входными данными.
  2. Считать первое число в файле - это n, относительно которого с этого момента мы будем запускать все наши циклы.
  3. Открыть цикл от 1 до n и считывать результаты участников. ВНИМАНИЕ! В этом пункте скрывается первая тонкость - нам недостаточно запомнить результаты участников. Нам надо еще запомнить их номера. На этом этапе номера, конечно, будут совпадать с переменной i, которая является счетчиком цикла, но, по условию задачи, далее будет необходимо провести сортировку результатов. При этом положение элементов в массиве изменятся, а значит их исходные номера проще запомнить в отдельный массив. Предлагаю результаты запоминать в массив X, а номера участников в массив Y. 
  4. Получив исходные данные, мы можем закрыть файл input.txt.
Решение, приведенное далее, далеко не самое рациональное. Но для тех, кто познакомился с основами программирования два месяца назад, более важно, что данное решение а) верно выполняет поставленную задачу; б) использует те команды и методы, которые известны начинающим программистам на данном этапе. 

     5. Предлагаю завести еще один массив. Например, Z. И заполнить его элементами массива X. На данном этапе массивы Z и X полностью совпадают.

      6. Применим к массиву Z сортировку по возрастанию: самый маленький по значению элемент должен оказаться на 1 месте, самый большой по значению - на последнем. Как сортировать одномерные массивы мы говорили в ЭТОМ занятии.

     7. Теперь мы могли бы уже вывести в нужном порядке результаты четырех победителей. Но ведь по условию задачи каждый из результатов должен сопровождаться номером участника олимпиады, показавшего этот результат. И вот тут нам поможет то, что исходные и отсортированные данные хранятся в разных массивах. Я предлагаю такую конструкцию:



For i:=1 to n do

For j:=1 to n do

if z[i]=x[j] then

m[i]:=y[j];

Первый цикл (по i) перебирает отсортированный массив Z. При этом мы берем, допустим, на первом шаге Z[1] и, благодаря внутреннему циклу по j, сравниваем этот элемент со всеми элементами массива X. Когда мы считывали массив X, напомню, в отдельный массив, Y, мы сохраняли номер участника олимпиады. Так вот, используя еще один массив, M, мы записываем в элемент массива М с номером, равным номеру проверяемого Z, номер участника, который соответствует X, совпавшему с Z.

8. Осталось только вывести результат в соответствующий файл.

Напишите код к этой задаче самостоятельно и проверьте работу задачи. Если не получится - смотрите решение ЗДЕСЬ

САМОСТОЯТЕЛЬНО:

Продумайте решение задачи с меньшим количеством дополнительных массивов.

суббота, 15 ноября 2014 г.

Задачи районной олимпиады по программированию. 11 класс задача 1.

Задача 1. Клякса.

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

Задание. Необходимо найти координаты левой нижней и правой верней вершин этой ленты.
Формат входных данных. В файле input.txt в первой строке записано число N- количество пятнышек-клякс (2< =N<=100). В следующих N строчках, через пробел, введены значения координат Xi.Yi(/Xi/,/Yi/<=10 в 9 степени) .
Формат выходных данных. В файле output.txt в одной строке выведены координаты правой верхней и левой нижней вершин прямоугольной ленты.

К чему сводится задача?

Даны различные координаты точек. Количество точек n мы узнаем из первого прочтенного числа в входном файле. С этого момента мы можем создавать циклы 

For i:=1 to n do

Необходимо найти максимальные и минимальные значения для координат X и Y, и вывести в файл вывода 4 числа: Xmax, Ymax, Xmin, Ymin.

Решите эту задачу самостоятельно. Если не получится - смотрим в решение.



Задачи районной олимпиады по программированию. Разбор задачи 3.

Задача про нефтяные пятна 

бродит по интернету с 2010 года. Вот ее условие:

После аварии на морской нефтяной скважине в океан вылилось много нефти. Она растеклась по воде, после чего образовалась определенное количество нефтяных пятен. Для ликвидации последствий аварии был создан штаб по координации действий. Сотрудники штаба хранят информацию о пятнах в компьютере в виде матрицы размерностью M x N. Ячейка матрицы содержит 0, если нефтяное пятно в этих координатах отсутствует и 1, если есть (2 ≤ M, N ≤ 100). В матрице ячейки пятен не могут касаться друг к другу ни сторонами, ни углами.

Задание. Для облегчения ликвидации последствий аварии нужно написать программу OIL .*, которая будет находить общее количество пятен и количество пятен с одинаковой площадью.

Входные данные. Входной текстовый файл OIL.DAT содержит в первой строке два числа M и N, далее следуют M строк, в каждой по N целых чисел разделенных пробелами - элементы матрицы.

Исходные данные. Выходной текстовый файл OIL.SOL содержит в первой строке целое число k - общее количество пятен, далее в каждом из рядов содержится по два числа, первое - площадь пятна, второе - их количество. Данные сортировать по площадям в порядке возрастания.

Изображения задания, входного и выходного файлов можно увидеть, например, ЗДЕСЬ.

Это самая сложная задача в этой олимпиаде для 8-9 классов, не даром она оценена в 25 баллов. Тех знаний, которые вы получили в материалах этого блога на данный момент, на всю задачу, пожалуй, не хватит. Но кое-что мы найти могли.

Итак, начинаем с разбора условия.

Нам необходимо считать размер матрицы - двумерного массива, числа m и n. Поскольку известно, что (2 ≤ M, N ≤ 100), то наша матрица при объявлении переменных может быть заданна так:

Var

a:array[2..100,2..100] of integer;

Подробнее о матрицах можно почитать в предыдущих уроках - Матрица и Решение задач с матрицей

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

ВОТ И НАПИШИТЕ с целью тренировки такую программку. Сами.

А трудность в решении поставленной задачи состоит в том, что необходимо с одной стороны посчитать каждую загрязненную клетку не саму по себе, а вместе с соседними загрязненными, и при этом ни одну из них не посчитать дважды.

Для того, чтоб полностью разобраться с решением задачи, я рекомендую ознакомиться с понятиями "Процедура" в языке Paskal, и "Рекурсия" в математике и программировании.







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

четверг, 13 ноября 2014 г.

Задачи районной олимпиады по программированию. Разбор задачи 2.

Задача 2.

Разведчики получили шифрованную радиограмму. Для ее расшифровки надо знать специальный ключ, который они получили вместе с радиограммой отдельной строкой. Эта строка – набор произвольных символов, среди которых обязательно будут цифры. Для получения ключа найдите сумму цифр этой строки. Известно, что строка не длиннее 255 символов.

Входной файл – строка не длиннее 255 символов.

Выходной файл – ключ.

К чему сводится условие задачи? У нас есть строка символов. Читаем строку. Если символ совпадает с одной из цифр – добавляем его к сумме.

program Olimp_9_2;
var
i,sum:integer;
a:array[1..255] of char;
f,g:text;

begin
assign (f,'input.txt');
reset (f);

i:=1;                - счетчик элементов в массиве
sum:=0;              - начальное значение суммы

while not eof (f) do    - пока есть элементы в строке…

begin
read (f,a[i]);          - читаем элемент, загоняем его в массив

case a[i] of            - если элемент оказался цифрой – добавляем к сумме
'1': sum:=sum+1;
'2': sum:=sum+2;
'3': sum:=sum+3;
'4': sum:=sum+4;
'5': sum:=sum+5;
'6': sum:=sum+6;
'7': sum:=sum+7;
'8': sum:=sum+8;
'9': sum:=sum+9;

end;                  - оператор case не содержит begin, но заканчивается end;

i:=i+1;               - меняем счетчик на 1
end;

close (f);            - закрыли файл f

assign (g,'output.txt');
rewrite (g);
writeln (g,sum);
close (g);

end.

Вот и все... 

Задачи районной олимпиады по программированию. Разбор задачи 1.

Задача 1.
Дано целое число, записанное в десятичной системе счисления. Посчитать количество единиц в его двоичной записи.

Как перевести число из системы в систему?

Вот число 7 (в десятичной записи). В двоичной системе это 111. Почему?

Десятичная
Двоичная
0
0
1
01
2
10
3
11
4
100
5
101
6
110
7
111
 
Ну не вручную же писать все эти цифры, правильно? Заводим массив mas [k], и считаем, что начальное число у нас – это переменная a. Заводим техническую переменную b.
И используем новый для нас вид цикла – repeat. Это цикл с постусловием. Мы не знаем, сколько раз будет повторяться действие.

k:=0;        - счетчик элементов массива.

repeat       - повторять (массив выполнится минимум 1 раз)

b:=a mod 2;  - технической переменной присваиваем остаток от деления нашего числа на 2. Это может быть только 0 или 1.

k:=k+1;      - меняем счетчик на 1

mas[k]:=b;   - записываем в очередной элемент массива остаток от деления

c:=a div 2;  - переменной с присваиваем значение целой части деления нашего числа на 2.

if c>=2 then a:=c; - пока c>=2 меняем начальное число на с

until c<2; - если с оказалось меньше 2- число полностью переведено в двоичную систему, но последний из остатков – последнее значение с – мы пока не записали.

mas[k+1]:=c; - и мы записываем последнее число в последний элемент массива. k+1 – потому, что k мы меняли внутри цикла, а из цикла мы уже вышли.

Рассмотрим на примере конкретного числа 7.
a=7, b= остатку от деления 7 на 2, т.е. 1, k=0+1=1, mas[1]=b=1, c=целой части от деления 7 на 2, т.е. 3, c=3>=2 , a:=3, условие конца цикла не достигнуто, начинаем цикл сначала.

a=3, b= 3 mod 2 = 1, k=1+1=2, mas [2]= b=1, c=a div 2=3 div 2=1, 1<2 – мы вылетаем из цикла.

mas [2+1]=mas [3] = c = 1

Мы получили три элемента массива, каждый из которых равен 1.

Теперь их надо просто сложить и вывести в файл сумму. Причем заметьте, что кроме 1 у нас могут быть в массиве только 0, т.е. сумма всех элементов и будет нам давать искомое количество 1.

А вот если бы нам надо было вывести число в двоичной записи – мы бы столкнулись с такой проблемой: в наш массив мы записываем цифры двоичной записи не от начала, а с конца числа. Потому, что берем ОСТАТОК от деления. Это значит, что для того, чтоб вывести правильное число, мы должны запустить такой простой цикл:

For i:= k+1 downto 1 do

Write(mas[i]);

При такой записи выводится будут элементы массива от последнего по счету к первому.
Самостоятельно:
  • Написать работающую программу к олимпиадной задаче.
  • Изменить ее так, чтоб она выводила не только количество 1, но и само число.
  • Решить задачи:

a.       Вводится число в двоичной записи. Вывести его в десятичной записи.


b.      Выведите все десятичные числа не превышающие 25 в порядке возрастания, двоичная запись которых оканчивается на 11.

вторник, 11 ноября 2014 г.

Занятие 10. Задачи про время.

Мы уже умеем выполнять различные действия с числами. Складывать, умножать, делить и даже подбирать корни... Но давайте решим пару задач, связанных не с числовой прямой, бесконечной в обе стороны, а со временем.

Начнем с суток. В них, как известно, 24 часа. В каждом из часов 60 минут, в каждой из минут 60 секунд.

Задача 1

Рассмотрим простую задачу:

Текущее показание часов m ч (0 <= m <= 23), n мин (0 <= n <= 59), k сек (0 <= k <= 59). 
Какое время будут показывать часы через p ч (0 <= p <= 100) q мин (0 <= q <= 59) r сек (0 <= r <= 59)?

Ход рассуждений примерно такой:

Сколько нужно переменных и какого типа? 


  • Три переменных для текущего времени ( m, n, k)
  • Три переменных для изменения времени (p, q, r)
  • Я рекомендую взять еще три переменных - для итогового времени. Например, n1, n2, n3
"Защита от дурака"

Обратите внимание, в условии вполне резонно указаны ограничения на каждую из переменных. Значит, стоит прописать в начале программы метки (Label, в Словарике посмотрите, если не помните), и отправлять пользователя на ввод той самой переменной, которую он ввел неверно, еще раз.

Внимательно посмотрите на ограничения. Минуты и секунды ограничены числом 59 включительно сверху, начальное время - 23 часами, а вот время изменения часов ограничено числом 100, т.е. возможен выход далеко за текущие сутки.

Что делать будем?

  1. Запросим начальное время (отдельно час, минуты и секунды, чтоб можно было вернуть, если введено неправильное число).
  2. Запросим  время, на которое произойдет изменение (отдельно час, минуты и секунды, чтоб можно было вернуть, если введено неправильное число).
  3. Начнем с секунд. Сложим начальные и добавленные. Если получим число более 59, то выполним такие действия:
  • запомним, что минут у нас будет на 1 больше
  • получим верное количество секунд, отняв от суммы одну минуту, которая, как известно, равна 60 секундам.
4. Продолжим с минутами. Сложим начальные и добавленные. Если получим число более 59, действуем аналогично схеме для секунд.

5. Часы. Если сумма окажется более 23, то отнимать надо целые сутки, т.е. 24 часа, и, возможно, не один раз - ведь мы можем добавить до 100 часов включительно. Здесь нам поможет цикл While.

6. Выведем на экран итоговое значение времени.

У меня получилось примерно так:


Решите задачу самостоятельно. Если не получится - смотрите в решениях к занятию .

Задача 2

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

С клавиатуры вводится дата рождения человека: год (не менее 1900, не более 2014), месяц (не менее 1, не более 12), день (не менее 1, не более 31, проверить, есть ли такой день в месяце). Затем вводится текущая дата. Год, месяц, день (проверить, чтоб год был не больше 2014, месяц от 1 до 12, и день с таким числом был в месяце). 
Посчитать, сколько дней прожил человек от одной введенной даты до другой.

Ход решения:

  1. Запросим у пользователя дату рождения, отправляя его на повторный ввод данных, если он ошибся. При этом очень рекомендую:
  • Получив год рождения, сразу узнать количество високосных годов в жизни человека (в решении - переменная p , и запомнить, какие это годы конкретно. В решении - массив vis[i]. Тогда, считая общее количество прожитых дней, вы можете умножить количество лет на 365, и добавить p - запомненное вами количество високосных годов, каждый из которых на один день длиннее стандартного года. Кроме того, знание конкретных високосных лет позволит вам проверить, может ли быть 29 февраля в дате рождения.
  • Получив месяц и день рождения, стоит проверить, не родился ли наш клиент, например, 31 июня (такого дня нет в календаре).
  • Аналогично проверяем вводимую текущую дату.
  • Теперь проверяем, был ли день рождения у человека уже в этом году. Если текущий месяц больше месяца рождения, то годы жизни равны текущему году - год рождения. А если дня рождения в этом году еще не было, то годы жизни равны текущему году - год рождения - 1.
  • С днями все просто: отнимаем от текущего дня день рожденья и результат прибавим к итогу. 
  • С месяцами рекомендую доработать. В решении для простоты мы считаем, что все месяцы по 30 дней. Что создает погрешность вычислений дней в 6. Можете исправить. :-)
Самостоятельная работа:

  1. Решить задачи 1 и 2 из этого занятия самостоятельно.
  2. Решить задачу: Известна дата рождения человека и сегодняшняя дата. Через сколько лет, месяцев и дней этому человеку будет 100 лет?
  3. Известны даты приема на работу и увольнения с работы за всю трудовую деятельность человека. Мест работы от 1 до 5. Посчитать суммарный трудовой стаж.


пятница, 7 ноября 2014 г.

Занятие 9. Палиндром, или почему Аргентина манит негра?

Сегодня мы рассмотрим еще одну стандартную олимпиадную (уровня районной олимпиады) задачу: проверить, является ли НЕЧТО палиндромом.

Во-первых: что такое палиндром. Палиндром - это запись, которая одинаково читается слева направо и справа налево. Например, число 12321 можно считать палиндромом. Как и слово кабак. А бывают целые фразы - палиндромы: Аргентина манит негра; А роза упала на лапу Азора... Встречаются стихи - палиндромы и даже рассказы - палиндромы. О романах-палиндромах лично я не слышала, но я верю в людей.

Во-вторых: почему НЕЧТО. Потому, что в зависимости от того, исследуем мы на палиндромность число, слово или фразу - задача может быть решена по-разному. Давайте рассмотрим все варианты решений.

Итак, вариант 1.


Проверить, является ли число палиндромом.

Идея решения: вводим число a - то, которое будем проверять. Потом, используя цикл While - "пока" с помощью двух меняющихся в ходе выполнения цикла переменных b и c делаем следующую операцию: "откусываем" последнюю цифру от  a и запоминаем её как временное значение c. На следующем витке цикла мы умножаем полученное ранее  c на 10, и прибавляем следующую цифру... И так, пока не получим конечное число c,  которое по сути является числом a, записанным задом наперед.

Затем мы сравниваем a и c, и, если числа равны, выводим сообщение о том, что число - палиндром, или о том, что не палиндром, в противном случае.

Перед вами результат работы программы, реализовавшей эту идею решения:

Введите целое положительное число a=123456

c=6 b=12345

c=65 b=1234

c=654 b=123

c=6543 b=12

c=65432 b=1

c=654321 b=0

654321

Не палиндром

Понятен ли вам принцип? Возникает вопрос, как "откусить" цифру. Тут нам помогут функции div и  mod, о которых вы можете прочесть в Словарике. Коротко:

19:5=3 (остаток 4)
19 div 5 = 3
19 mod 5=4

Попробуйте решить задачу сами. Если не получится - смотрите в Решения к уроку 9.

Рассмотрим 2 вариант этой задачи. 


Проверить, является ли введенное слово палиндромом.

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

Итак:

 Program pal_2;
Var
s: string;  - заводим переменную, в которой запомним наше слово.
i,f: byte; - две технических переменных: счетчик и "переключатель" "ДА" - "НЕТ"

begin 

   write('String: ');  - запросили слово
   readln(s);            - запомнили слово
   f := 0;                   - обнулили переключатель 

for i := 1 to length(s) div 2 do  - ДЛЯ (for) i от 1 до ДЛИНЫ СЛОВА (length(s)) деленного на 2                                                       без остатка (div) ДЕЛАТЬ (do)

if s[i] <> s[length(s)-i+1] then - ЕСЛИ (if) дальше будет изменение в зависимости от номера                                                          шага: 
                                                     на первом шаге ПЕРВАЯ БУКВА (s[i], i=1) не равна                                                                          ПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=1, +1) 
                                                     на втором шаге ВТОРАЯ БУКВА (s[i], i=2) не равна                                                                          ПРЕДПОСЛЕДНЕЙ БУКВЕ (s[длина слова - i, i=2, +1)
                                                     и так до середины слова... 

   begin                                        - делать такой набор действий
        writeln('No palindrome');   - написать "Не палиндром"
        f := 1;                                   - присвоить f значение 1
        break                                   - прервать выполнение программы (ну смысл нам проверять                                                               слово до конца, если уже вторая пара букв, скажем, не                                                                    совпала?)
    end;                                            - конец блока действий, если " все плохо"

 if f = 0 then write('Palindrome');  - если к концу проверки не совпавших пар не нашлось, f                                                                         осталось равным 0, написать сообщение, что слово -                                                                       палиндром.

end.                                                   - конец программы.

Чем интересно это решение?

  • Во-первых, мы повторили оператор div, который использовали для сокращения количества шагов в цикле. Слово проверяется за количество шагов, равное половине длины слова. Это позволяет корректно проверять слова, состоящие из нечетного количества букв. Например, слово "КАБАК" будет проверено так: сравним первую и последнюю буквы - это "К", все хорошо. Затем сравним вторую и предпоследнюю. Обе - "А". У буквы "Б" нет пары, но ее наличие не мешает слову быть палиндромом. Эту букву мы вообще не проверяем, потому, что...
  • Во-вторых мы познакомились с оператором  length(s) , который считает ДЛИНУ любой переменной типа String, типа, который соответствует значению "много букв". Так вот, мы теперь можем узнать, сколько - много.
  • В-третьих посмотрите, почему цикл задан только до середины слова. На примере "КАБАК" - length(s) = 5. length(s) div 2 = 2. Именно по этой причине мы не трогали букву "Б", о чем было сказано в разделе "Во-первых".
  • В-четвертых, эта программа будет проверять ЛЮБЫЕ введенные символы. Т.е. ей будет все равно, введете вы реально существующее слово, случайный набор букв, число или смесь букв разных языков и цифр. Если введенная вами строка будет читаться одинаково с обоих концов - вам сообщат, что это - палиндром. 

А теперь - вариант 3.

Проверить, является ли палиндромом фраза.

Первый вариант решения не подходит, так как фраза не может быть типа integer. Второй вариант решения тоже не подходит, так как в фразе, в отличие от слова, есть пробелы между словами. И они крайне редко совпадают по своему положению при чтении с разных концов. Например, фразу "Кабак казак кабак" вариант 2 посчитает палиндромом. А вот фразу "Аргентина манит негра", с которой мы начинали - нет, так как на 6 шаге проверки встретятся буква "Т" из слова "Аргентина" и пробел перед словом "негра"... 

Но мы справимся и с этой задачей.

Итак, ход решения. Давайте сразу договоримся, что мы будем брать фразу из файла input.txt и выводить сообщение о том, палиндром это или нет, в файл output.txt.

Давайте будем считать, что в наших фразах для проверки будет не более 50 символов вместе с пробелами. 

Опираясь на этот факт мы заведем себе три массива типа CHAR:
  • Массив a, в который мы запишем всю введенную нам фразу, в том числе и пробелы, по одному символу в каждой a[ i ].
  • Массив b, в котором мы будем сохранять только те символы, которые окажутся НЕ пробелами.
  • Массив c, в который мы запишем массив b в обратном порядке.
Если бы мы точно знали, сколько символов в нашей фразе, мы могли бы сразу сократить программу на четверть, но...

Мы введем переменные типа INTEGER:
  • i , j - счетчики переменных. Уже при вводе массива a и массива b мы получим разное количество элементов. Ведь с пробелами наша фраза - пример "Аргентина манит негра" займет 21 элемент массива a (столько символов, включая пробелы, в этой фразе), и только 19 элементов массива b - откинем два пробела.
  • k - у меня в программе это счетчик итогового количества элементов в массиве b. Если я нахожу "не пробел" в массиве a, я записываю этот символ в массив b и увеличиваю k на 1. Тогда к концу цикла я буду знать, сколько у меня букв без пробелов в фразе.
  • d - эту переменную я использую при проверке совпадений массивов b и c. Если находится несовпадение - увеличивается на 1. В итоге я смогу даже сказать, сколько конкретно несовпадений в фразе, если они есть. В этой программе я не делала сброса при первом же несовпадении, но вы можете это сделать.
  • f, g - традиционные переменные типа TEXT для организации работы с файлами ввода и вывода.
С переменными разобрались. Теперь - ход работы:

Открываем файл input.txt и ДО КОНЦА ФАЙЛА (мы же помним про оператор eof?) записываем ВСЕ символы в массив a, а если символ оказывается НЕ ПРОБЕЛОМ, то и в массив b. 
В процессе мы считаем количество элементов, не являющихся пробелами.

Получив массив b, мы записываем его в обратном порядке в массив c. 

Затем мы сравниваем элементы массивов b и c. Если пара не совпадает, переменной d присваивается значение d+1.  

Если к концу сравнения d =0, выводим сообщение, что фраза - палиндром. В противном случае - что нет.

пятница, 31 октября 2014 г.

Занятие 8. Решаем задачи с матрицей.

Рисование фигурок в матрице - это замечательно. Кстати, один из способов создания компьютерных шрифтов - это прорисовка каждого символа внутри матрицы определенного размера путем расстановки "0" и "1" в определенных позициях. Но не только для этого нам нужны матрицы.

Рассмотрим несколько задач с решениями:

Задача 1. 

Создать двумерный массив из 8 строк по 5 столбцов в каждой из случайных целых чисел из отрезка [10;99]. Вывести массив на экран.

Учимся читать условие задачи и сразу делать выводы.

1. Двумерный массив из 8 строк и 5 столбцов, целые числа. Значит, в разделе переменных необходима запись:

a: array [1..8,1..5] of integer;

2. Числа случайные. Т.е. не мы их вводим с клавиатуры или из файла, а компьютер их сам себе придумывает. Для этой ситуации есть специальная команда:

random; - возвращает случайным образом "0" или "1"

random(n); - возвращает выбранное случайным образом число из промежутка от "0" до "n-1", например  random(100); означает, что будут выбираться случайным образом числа от 0 до 99 включительно.

random(a,b);  - выбирает случайным образом числа из числового промежутка [a, b].

Поскольку нам задан числовой промежуток  [10;99] , то нам нужен будет третий вариант оператора random. 

3. О внешних файлах никто не говорит, значит выводим все, как и сказано в условии, на экран.

Теперь задача:

Program lesson8_1;

Var

a:array[1..8,1..5] of integer;
i,j:integer;

begin

For i:=1 to 8 do begin
For j:=1 to 5 do begin

a[i,j]:=random(10,99);
write (a[i,j]:3);

end;
writeln;
end;

end.

Если у вас есть вопросы по тексту задачи - спросите в комментариях к уроку, я отвечу. Если вопросов нет - ответьте мне, зачем нужен оператор writeln; между двумя операторами end; ?

Мы уже говорили, что научиться программировать можно только самостоятельно написав определенное количество программ. Вперед!

Самостоятельная работа:

  1. Создать двумерный массив из 5 строк по 8 столбцов в каждой из случайных целых чисел из отрезка [-99;99]. Вывести массив на экран. После на отдельной строке вывести на экран значение максимального элемента этого массива (его индекс не имеет значения).
  2. Cоздать двумерный массив из 7 строк по 4 столбца в каждой из случайных целых чисел из отрезка [-5;5]. Вывести массив на экран. Определить и вывести на экран индекс строки с наибольшим по модулю произведением элементов. Если таких строк несколько, то вывести индекс первой встретившейся из них.
  3. Создать двумерный массив из 6 строк по 7 столбцов в каждой из случайных целых чисел из отрезка [0;9]. Вывести массив на экран. Преобразовать массив таким образом, чтобы на первом месте в каждой строке стоял её наибольший элемент. При этом изменять состав массива нельзя, а можно только переставлять элементы в рамках одной строки. Порядок остальных элементов строки не важен (т.е. можно соврешить только одну перестановку, а можно отсортировать по убыванию каждую строку). Вывести преобразованный массив на экран.
  4. Для проверки остаточных знаний учеников после летних каникул, учитель младших классов решил начинать каждый урок с того, чтобы задавать каждому ученику пример из таблицы умножения, но в классе 15 человек, а примеры среди них не должны повторяться. В помощь учителю напишите программу, которая будет выводить на экран 15 случайных примеров из таблицы умножения (от 2*2 до 9*9, потому что задания по умножению на 1 и на 10 — слишком просты). При этом среди 15 примеров не должно быть повторяющихся (примеры 2*3 и 3*2 и им подобные пары считать повторяющимися).

среда, 29 октября 2014 г.

Занятие 7. Матрица.

Я сейчас вас удивлю. Матрица - это не боевик. Матрица - это такой математический термин, перешедший в программирование. И вообще, очень полезная и удобная вещь. Если с ней уметь обращаться, конечно.

Немного истории. 

Впервые матрицы упоминались ещё в древнем Китае, называясь тогда «волшебным квадратом». Основным применением матриц было решение линейных уравнений. Также волшебные квадраты были известны чуть позднее у арабских математиков, примерно тогда появился принцип сложения матриц. 

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




В математике матрицы используют, например, при решении систем уравнений. Но в это искусство вас посвятят на лекциях по высшей математике в ВУЗах. А мы научимся просто работать с матрицами, чтоб потом вы могли написать программку для подсчета чего угодно...

По сути матрица - это НАБОР МАССИВОВ. с массивами мы с вами уже сталкивались, когда задавали строку элементов вида a[1], a[2], a[3],... Теперь мы будем говорить не только о номере элемента в строке, но и о номере строки, в которой этот элемент стоит. Например, элемент, стоящий в 3 строке на 5 месте мы обозначим a[3,5]. Номер строки - на первом месте, номер столбца (положение в строке) на втором. Номера строк в общем виде обозначают обычно буквой i, номера столбцов буквой  j. Тогда элемент стоящий в i -ой строке на j -ом месте обозначим  a[i,j]. Правило обозначения элементов лучше поможет понять такая таблица:

Рассмотрим простую задачу: 

Заполните таблицу 5 на 5 значениями "0" и "1" так, чтоб "1" стояли по всем крайним строкам и столбцам, а в центре были символы "0".

Другими словами. я хочу примерно такую картинку:

Program matr;
Var
a:array[1..5,1..5] of integer; - готовим ячейки памяти для нашей матрицы. По условию - 5*5.
i,j:integer;

begin
For i:=1 to 5 do begin - начинаем считать строки
For j:=1 to 5 do begin- начинаем считать столбцы
If ((i=1) or (j=1) or(i=5) or(j=5)) then - если номер элемента совпадает с номером крайней                                                                           строки или столбца...
a[i,j]:=1 - присвоить этому элементу значение 1
else
a[i,j]:=0; - иначе - присвоить значение 0
write (a[i,j]:2); - печатать элементы в строчку с интервалом 2 между ними
end; - закончили работу в строке, пройдя по всем столбцам
Writeln; - перешли на новую строку
end; - и начали работать со следующей строкой, если следующая строка есть.
end.

Давайте изменим программу так, чтоб "1" стояли на диагоналях матрицы. Для этого нам надо познакомиться еще с двумя понятиями. Вернемся к нашему рисунку:


Уже знакомая вам матрица с обозначением номеров элементов. Красной линией выделена ГЛАВНАЯ диагональ, зеленой линией выделена ПОБОЧНАЯ диагональ матрицы.

Каким свойством обладают номера элементов, попавших на главную диагональ? Это элементы a[1,1], a[2,2], a[3,3]. Если бы матрица была большего размера, то на главной диагонали лежали бы и другие элементы у которых... правильно, коэффициент i=j. 

Давайте выведем формулу, по которой элемент можно отнести к побочной диагонали.
Только не надо мне рассказывать, что i и j изменяются на 1 в разные стороны - один коэффициент увеличивается, другой уменьшается. Как вы это объясните компьютеру? 
  
Надо искать математическую закономерность. Итак: давайте сложим и j каждого из элементов, попавших на побочную диагональ. Какое число получилось? 4? А матрица у нас какого размера? 3*3. Поскольку у нас матрица квадратная - число строк равно числу столбцов, можем говорить "Квадратная матрица размера 3", или просто "матрица размера 3", подразумевая, что в этом случае она - квадратная.

Как связаны числа 4 и 3? Правильно, 4= 3+1. Теперь смотрим на первый элемент матрицы, попавший на эту диагональ. Какие коэффициенты у этого элемента? О! Так это же наши 3 и 1! Которые 3+1=4!

А если у нас матрица будет размером 7? В верхнем правом углу будет стоять элемент первой строки последнего, седьмого столбца. Тогда формула для побочной строки будет 7+1=8.

А если матрица будет размером 9? 9+1=10.

А если размера n?

Для любой матрицы размера n верны следующие утверждения:
  1. Если i=j, то элемент a[i,j] принадлежит ГЛАВНОЙ диагонали.
  2. Если i+j=n+1, то элемент a[i,j] принадлежит ПОБОЧНОЙ диагонали.
Ну а теперь, вооруженные знаниями про диагонали матрицы, напишите сами задачу, в результате которой мы увидим на экране матрицу, где на диагоналях стоят "1" а все остальные элементы - "0". Задайте матрице размер 10.

И, кроме этого, САМОСТОЯТЕЛЬНАЯ РАБОТА:

Введите дополнительную переменную n. В начале программы спросите у пользователя, каков будет размер матрицы. Все расчеты выполняйте относительно n, введенного пользователем. В этой матрице выведите такие картинки:


  1. "Крестик"  
  2. "Окошко"