сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Тре­уголь­ни­ком Пас­ка­ля на­зы­ва­ют бес­ко­неч­ную тре­уголь­ную таб­ли­цу чисел, у ко­то­рой на вер­ши­не и по бокам стоят еди­ни­цы, а каж­дое число внут­ри равно сумме двух сто­я­щих над ним чисел. Так, на­при­мер, тре­тья стро­ка тре­уголь­ни­ка (1, 2, 1) со­дер­жит два не­чет­ных числа и одно чет­ное. Сколь­ко чет­ных чисел со­дер­жит­ся:

а)  в стро­ке с но­ме­ром 256?

б)  в стро­ке с но­ме­ром 200?

Спрятать решение

Ре­ше­ние.

Будем за­ме­нять в тре­уголь­ни­ке не­чет­ные числа еди­ни­ца­ми, а чет­ные ну­ля­ми. При этом каж­дое число внут­ри по-преж­не­му оста­ет­ся рав­ным сумме сто­я­щих над ним чисел, если при­нять, что 0 плюс 0=1 плюс 1=0, 1 плюс 0=0 плюс 1=1. Рас­смот­рим струк­ту­ру тре­уголь­ни­ка по­дроб­нее. Тре­уголь­ник, сфор­ми­ро­ван­ный пер­вы­ми во­се­мью стро­ка­ми, обо­зна­чим T8. В стро­ке 9 всего две еди­ни­цы (по бокам), осталь­ные  — нули. С этой стро­ки и вниз далее идет фор­ми­ро­ва­ние двух тре­уголь­ни­ков T8, ко­то­рые «встре­ча­ют­ся друг с дру­гом» в стро­ке 16. На­чи­ная со стро­ки 17 и ниже, об­ра­зо­вы­ва­ют­ся два тре­уголь­ни­ка T16, ко­то­рые, в свою оче­редь, «встре­ча­ют­ся» в стро­ке 32. Со стро­ки 33 и ниже фор­ми­ру­ют­ся два тре­уголь­ни­ка T32 и т. д. Таким об­ра­зом, стро­ки, чей номер пред­став­ля­ет собой сте­пень двой­ки, со­сто­ят толь­ко из еди­ниц. По­это­му в стро­ке 256 чет­ных чисел нет.

Об­ра­тим­ся те­перь к стро­ке 200. По­нят­но, что, после стро­ки 128 (сте­пень двой­ки), идет фор­ми­ро­ва­ние «с нуля» двух оди­на­ко­вых тре­уголь­ни­ков. Стро­ки с но­ме­ром 72 в этих новых тре­уголь­ни­ках как раз и со­дер­жат­ся в стро­ке 200 ис­ход­но­го (боль­шо­го) тре­уголь­ни­ка, т. к. 200=128 плюс 72. Зна­чит, еди­ниц в стро­ке 200 вдвое боль­ше, чем еди­ниц в стро­ке с но­ме­ром 72. В свою оче­редь еди­ниц в стро­ке 72 вдвое боль­ше, чем в стро­ке 8 (рас­смот­реть тре­уголь­ни­ки, фор­ми­ру­ю­щи­е­ся после стро­ки 64). Ко­ли­че­ство же 1 в стро­ке 8 можно под­счи­тать не­по­сред­ствен­но  — их 8 штук. Зна­чит, в стро­ке 200 их 32, осталь­ные 168  — нули.

 

Ответ: а) 0; б) 168.


Аналоги к заданию № 7577: 7589 7580 Все