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

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

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

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