пятница, 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 степени, сверив с рисунком выше.

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

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

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

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

Комментариев нет:

Отправить комментарий