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

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

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

(a + b)² = a² + 2ab + b<sup>2

(a + b)3 = a3 + 3a2b + 3ab2 + b3</sup>

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

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

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

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

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

Теперь давайте сформулируем вывод на языке информатики. 

Пусть каждый элемент треугольника обозначается как 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 степени, сверив с рисунком выше.

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

И еще одна подсказка.

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

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

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

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

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

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

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

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

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

Решение:

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

  В I туре Интернет-олимпиады по программированию n учеников все задачи решили верно, но время выполнения у всех было разным: 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. Осталось только вывести результат в соответствующий файл.

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

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

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

Задачи районной олимпиады по программированию. 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, и "Рекурсия" в математике и программировании.

Процедуры и функции в Паскале - 1

Процедуры и функции в Паскале - 2

Процедуры и функции в Паскале - 3

Рекурсия в программировании - 1

Рекурсия в Паскале - 2

Рекурсия в Паскале - 3

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

Задачи районной олимпиады по программированию. Разбор задачи 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.

Занятие 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. Посчитать суммарный трудовой стаж.

Занятие 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. Если находится несовпадение - d увеличивается на 1. В итоге я смогу даже сказать, сколько конкретно несовпадений в фразе, если они есть. В этой программе я не делала сброса при первом же несовпадении, но вы можете это сделать.
• f, g - традиционные переменные типа TEXT для организации работы с файлами ввода и вывода.

С переменными разобрались. Теперь - ход работы:

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

В процессе мы считаем количество элементов, не являющихся пробелами.

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

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

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

Занятие 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 и им подобные пары считать повторяющимися).

Занятие 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 в разные стороны - один коэффициент увеличивается, другой уменьшается. Как вы это объясните компьютеру? 

  

Надо искать математическую закономерность. Итак: давайте сложим i и 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. "Окошко"