Ханойская башня, или один замечательный алгоритм - История изменений

User2 в 13:58, 31 октября 2012

2012-10-31T13:58:20Z

User16 в 20:04, 5 сентября 2012

2012-09-05T20:04:51Z

← Предыдущая		Версия 20:04, 5 сентября 2012
Строка 91:		Строка 91:
	<u></u>'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] аудио-, видеоклипы и мультимедиа '''		<u></u>'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] аудио-, видеоклипы и мультимедиа '''
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фотографии, картинки		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фотографии, картинки
-	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] графики, таблицы, схемы	+	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] [http://school.xvatit.com/index.php?title=%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F,_%D0%B8%D0%BB%D0%B8_%D0%BE%D0%B4%D0%B8%D0%BD_%D0%B7%D0%B0%D0%BC%D0%B5%D1%87%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC._%D0%93%D1%80%D0%B0%D1%84%D0%B8%D0%BA%D0%B8,_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B,_%D1%81%D1%85%D0%B5%D0%BC%D1%8B графики, таблицы, схемы]
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] юмор, анекдоты, приколы, комиксы		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] юмор, анекдоты, приколы, комиксы
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] притчи, поговорки, кроссворды, цитаты		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] притчи, поговорки, кроссворды, цитаты

User16 в 09:30, 29 июня 2012

2012-06-29T09:30:41Z

User16 в 16:00, 7 апреля 2012

2012-04-07T16:00:58Z

← Предыдущая		Версия 16:00, 7 апреля 2012
Строка 3:		Строка 3:
	'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''		'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''

		+	<br> <br>

-	<br>	+	'''                  § 4.12. Ханойская башня, или один замечательный алгоритм'''<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы:

-	~~'''&nbsp~~;                                          § 4.12. Ханойская башня, или один замечательный алгоритм'''<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, ~~следуя законам Брамы:~~	+	1) диски можно перемещать с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху.

-	~~1) диски можно перемещать~~ с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, ~~сужающейся кверху~~.	+	Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».

-	~~Когда все 64 диска будут перенесены с одного~~ стержня на ~~другой~~, ~~наступит конец света»~~.	+	Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.<br> <br>[[Image:16-03-017.jpg]]<br><br>Если башня состоит из одного диска, то она переносится за один ход: 1->3.

-	~~Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n~~ дисков ~~со стержня 1 на стержень 3, используя промежуточный стержень~~ 2 ~~и соблюдая законы Брамы.<br>~~&~~nbsp~~;~~<br>карт <br><br>Если башня состоит из одного диска~~, ~~то она переносится за один ход: 1-~~>3.	+	Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3.

-	~~Башня~~ из ~~двух~~ дисков ~~переносится за три хода~~: 1—>2, 1—>3, 2—>3.	+	Для переноса башни из трех дисков потребуется уже семь ходов: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Обратите внимание, за первые три хода мы переносим башню из двух верхних дисков на второй промежуточный стержень. Затем переносим самый большой диск с первого стержня на третий и еще раз проделываем хорошо знакомую нам операцию: переносим башню из двух дисков на третий диск.

-	Для переноса башни из трех дисков потребуется уже семь ходов: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Обратите внимание, ~~за первые три хода мы переносим~~ башню из ~~двух верхних~~ дисков ~~на второй промежуточный стержень. Затем переносим самый большой диск~~ с первого стержня на третий ~~и еще раз проделываем хорошо знакомую нам операцию~~: ~~переносим башню из двух дисков на третий диск.~~	+	Следовательно, чтобы перенести башню из четырех дисков с первого стержня на третий, необходимо действовать по плану:

-	Следовательно, чтобы перенести башню из четырех дисков с первого стержня на третий, необходимо действовать по плану:	+	1) перенести башню из трех верхних дисков с первого стержня на второй (7 ходов);<br>2) самый большой диск перенести с первого стержня на третий (1 ход);<br>3) перенести башню из трех дисков со второго стержня на третий (7 ходов).
-		+
-	1) перенести башню из трех верхних дисков с первого стержня на второй (7 ходов);<br>2) самый большой диск перенести с первого стержня на третий (1 ход);<br>3) перенести башню из трех дисков со второго стержня на третий (7 ходов).	+

	Всего на перенос потребуется 15 ходов.		Всего на перенос потребуется 15 ходов.

-	Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.	+	Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.

-	Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>'''Вопросы и задания'''<br><br>1. Проведите необходимые вычисления и заполните следующую таблицу:<br>	+	Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>'''Вопросы и задания'''<br><br>1. Проведите необходимые вычисления и заполните следующую таблицу:<br>

	{\| cellspacing="1" cellpadding="1" border="1" style="width: 330px; height: 234px;"		{\| cellspacing="1" cellpadding="1" border="1" style="width: 330px; height: 234px;"
	\|-		\|-
-	\|    Число дисков	+	\|    Число дисков
	\|     Число ходов		\|     Число ходов
	\|-		\|-
-	\|    7	+	\|    7
	\|		\|
	\|-		\|-
-	\|    8	+	\|    8
	\|		\|
	\|-		\|-
-	\|    9	+	\|    9
	\|		\|
	\|-		\|-
-	\|    10	+	\|    10
	\|		\|
	\|-		\|-
-	\|    20	+	\|    20
	\|     1 048 575		\|     1 048 575
	\|-		\|-
-	\|    21	+	\|    21
	\|		\|
	\|-		\|-
-	\|    30	+	\|    30
	\|		\|
	\|-		\|-
-	\|    31	+	\|    31
	\|		\|
	\|-		\|-
-	\|    39	+	\|    39
	\|		\|
	\|-		\|-
-	\|    40	+	\|    40
	\|     1 099 511 627 775		\|     1 099 511 627 775
	\|}		\|}

-	<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?	+	<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?

	3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br><br><br>		3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br><br><br>

User16 в 18:20, 10 ноября 2011

2011-11-10T18:20:03Z

← Предыдущая		Версия 18:20, 10 ноября 2011
Строка 66:		Строка 66:
	<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?		<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?

-	3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение Калькулятор. <br><br><br><br><br>	+	3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br><br><br>

	<br>		<br>

User16 в 18:19, 10 ноября 2011

2011-11-10T18:19:18Z

← Предыдущая		Версия 18:19, 10 ноября 2011
Строка 2:		Строка 2:

	'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''		'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''
		+

	<br>		<br>

-	§ 4.12. Ханойская башня, или один замечательный алгоритм<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы:~~<br><br>~~1) диски можно перемещать с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху.~~<br><br>~~Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».~~<br><br>~~Эта древняя легенда положена в основу задачи о Ханойской башне: переместить п дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.<br> <br>карт <br><br>Если башня состоит из одного диска, то она переносится за один ход: 1->3.~~<br><br>~~Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3.~~<br><br>~~Для переноса башни из трех дисков потребуется уже семь ходов: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Обратите внимание, за первые три хода мы переносим башню из двух верхних дисков на второй промежуточный стержень. Затем переносим самый большой диск с первого стержня на третий и еще раз проделываем хорошо знакомую нам операцию: переносим башню из двух дисков на третий диск.~~<br><br>~~Следовательно, чтобы перенести башню из четырех дисков с первого стержня на третий, необходимо действовать по плану:~~<br><br>~~1) перенести башню из трех верхних дисков с первого стержня на второй (7 ходов);<br>2) самый большой диск перенести с первого стержня на третий (1 ход);<br>3) перенести башню из трех дисков со второго стержня на третий (7 ходов).~~<br><br>~~Всего на перенос потребуется 15 ходов. ~~<br><br>~~Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.~~<br><br>~~Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. Алгоритм решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>Вопросы и задания<br><br>1. Проведите необходимые вычисления и заполните следующую таблицу:<br>~~<br>табл<br><br>~~Число дисков    Число ходов~~<br><br>7~~    ~~<br>8~~    ~~<br>~~9   ~~ <br>~~10   ~~ <br>~~20    1 048 575~~<br>21~~    ~~<br>30~~    ~~1 073 741 823<br>~~31   ~~ <br>~~39   ~~ <br>~~40    1 099 511 627 775~~<br>~~<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?~~<br><br>~~3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение Калькулятор. <br><br><br><br><br>	+	'''                                           § 4.12. Ханойская башня, или один замечательный алгоритм'''<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы:
		+
		+	1) диски можно перемещать с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху.
		+
		+	Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».
		+
		+	Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.<br> <br>карт <br><br>Если башня состоит из одного диска, то она переносится за один ход: 1->3.
		+
		+	Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3.
		+
		+	Для переноса башни из трех дисков потребуется уже семь ходов: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Обратите внимание, за первые три хода мы переносим башню из двух верхних дисков на второй промежуточный стержень. Затем переносим самый большой диск с первого стержня на третий и еще раз проделываем хорошо знакомую нам операцию: переносим башню из двух дисков на третий диск.
		+
		+	Следовательно, чтобы перенести башню из четырех дисков с первого стержня на третий, необходимо действовать по плану:
		+
		+	1) перенести башню из трех верхних дисков с первого стержня на второй (7 ходов);<br>2) самый большой диск перенести с первого стержня на третий (1 ход);<br>3) перенести башню из трех дисков со второго стержня на третий (7 ходов).
		+
		+	Всего на перенос потребуется 15 ходов.
		+
		+	Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.
		+
		+	Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>'''Вопросы и задания'''<br><br>1. Проведите необходимые вычисления и заполните следующую таблицу:<br>
		+
		+	{\| cellspacing="1" cellpadding="1" border="1" style="width: 330px; height: 234px;"
		+	\|-
		+	\|    Число дисков
		+	\|     Число ходов
		+	\|-
		+	\|    7
		+	\|
		+	\|-
		+	\|    8
		+	\|
		+	\|-
		+	\|    9
		+	\|
		+	\|-
		+	\|    10
		+	\|
		+	\|-
		+	\|    20
		+	\|     1 048 575
		+	\|-
		+	\|    21
		+	\|
		+	\|-
		+	\|    30
		+	\|
		+	\|-
		+	\|    31
		+	\|
		+	\|-
		+	\|    39
		+	\|
		+	\|-
		+	\|    40
		+	\|     1 099 511 627 775
		+	\|}
		+
		+	<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?
		+
		+	3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение Калькулятор. <br><br><br><br><br>

	<br>		<br>

User16: Новая страница: «Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханой...»

2011-11-10T10:32:57Z

Новая страница: «<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханой...»

Новая страница

<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханойская башня, или один замечательный алгоритм</metakeywords>

'''[[Гипермаркет знаний - первый в мире!|Гипермаркет знаний]]>>[[Информатика|Информатика ]]>>[[Информатика 6 класс|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''

 

§ 4.12. Ханойская башня, или один замечательный алгоритм Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы: 1) диски можно перемещать с одного стержня на другой только по одному; 2) нельзя класть больший диск на меньший; 3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху. Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света». Эта древняя легенда положена в основу задачи о Ханойской башне: переместить п дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.   карт Если башня состоит из одного диска, то она переносится за один ход: 1->3. Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3. Для переноса башни из трех дисков потребуется уже семь ходов: 1->3, 1->2, 3->2, 1->3, 2->1, 2->3, 1->3. Обратите внимание, за первые три хода мы переносим башню из двух верхних дисков на второй промежуточный стержень. Затем переносим самый большой диск с первого стержня на третий и еще раз проделываем хорошо знакомую нам операцию: переносим башню из двух дисков на третий диск. Следовательно, чтобы перенести башню из четырех дисков с первого стержня на третий, необходимо действовать по плану: 1) перенести башню из трех верхних дисков с первого стержня на второй (7 ходов); 2) самый большой диск перенести с первого стержня на третий (1 ход); 3) перенести башню из трех дисков со второго стержня на третий (7 ходов). Всего на перенос потребуется 15 ходов. Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: 15 + 1 + 15 = 2 • 15 + 1 = 31. Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д. Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. Алгоритм решения задачи «Ханойская башня» — пример рекурсивного алгоритма. Вопросы и задания 1. Проведите необходимые вычисления и заполните следующую таблицу: табл Число дисков    Число ходов 7     8     9     10     20    1 048 575 21     30    1 073 741 823 31     39     40    1 099 511 627 775 2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа? 3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение Калькулятор. 

 

''Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. — 3-е изд., испр. и доп. — М.: БИНОМ. Лаборатория знаний, 2005. — 208 с.: ил.''

 

'''Содержание урока'''
'''[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] конспект урока'''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] опорный каркас
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] презентация урока
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] акселеративные методы
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] интерактивные технологии

'''Практика'''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] задачи и упражнения
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] самопроверка
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] практикумы, тренинги, кейсы, квесты
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] домашние задания
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] дискуссионные вопросы
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] риторические вопросы от учеников

'''Иллюстрации'''
'''[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] аудио-, видеоклипы и мультимедиа '''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] фотографии, картинки
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] графики, таблицы, схемы
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] юмор, анекдоты, приколы, комиксы
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] притчи, поговорки, кроссворды, цитаты

'''Дополнения'''
'''[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] рефераты'''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] статьи
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] фишки для любознательных
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] шпаргалки
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] учебники основные и дополнительные
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] словарь терминов
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] прочие
''''''
Совершенствование учебников и уроков
'''[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] исправление ошибок в учебнике'''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] обновление фрагмента в учебнике
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] элементы новаторства на уроке
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] замена устаревших знаний новыми

'''Только для учителей'''
'''[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] идеальные уроки '''
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] календарный план на год
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] методические рекомендации
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] программы
[[Image:1236084776 kr.jpg|10x10px|1236084776 kr.jpg]] обсуждения

'''Интегрированные уроки'''


 

Если у вас есть исправления или предложения к данному уроку, [http://xvatit.com/index.php?do=feedback напишите нам].

Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - [http://xvatit.com/forum/ Образовательный форум].

← Предыдущая		Версия 13:58, 31 октября 2012
Строка 1:		Строка 1:
	<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханойская башня, или один замечательный алгоритм, калькулятор, алгорим, таблица</metakeywords>		<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханойская башня, или один замечательный алгоритм, калькулятор, алгорим, таблица</metakeywords>

-	'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> ~~Ханойская башня, или один замечательный алгоритм'''~~	+	'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы:
-		+
-	~~<br> <br>~~	+
-		+
-	~~'''                  § 4.12.~~ Ханойская башня, или один замечательный алгоритм'''<br><br>Одна из древних легенд гласит: «В непроходимых джунглях недалеко от города Ханоя есть храм бога Брамы. В нем находится бронзовая плита с тремя алмазными стержнями. На один из стержней бог при сотворении мира нанизал 64 диска разных диаметров из чистого золота. Наибольший диск лежит на бронзовой плите, а остальные образуют пирамиду, сужающуюся кверху. Это башня Брамы. Работая день и ночь, жрецы храма переносят диски с одного стержня на другой, следуя законам Брамы:	+

	1) диски можно перемещать с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху.		1) диски можно перемещать с одного стержня на другой только по одному;<br>2) нельзя класть больший диск на меньший;<br>3) нельзя откладывать диски в сторону, при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды, сужающейся кверху.
Строка 65:		Строка 61:
	''<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?''		''<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?''

-	''3. Для того чтобы переместить башню из 64 дисков, при безошибочной [http://xvatit.com/busines/ '''работе'''] потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. ~~<br><br>~~<br><br><br>	+	''3. Для того чтобы переместить башню из 64 дисков, при безошибочной [http://xvatit.com/busines/ '''работе'''] потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br>

	<br>		<br>
Строка 71:		Строка 67:
	''Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. — 3-е изд., испр. и доп. — М.: БИНОМ. Лаборатория знаний, 2005. — 208 с.: ил.''		''Босова Л. Л. Информатика: Учебник для 6 класса / Л. Л. Босова. — 3-е изд., испр. и доп. — М.: БИНОМ. Лаборатория знаний, 2005. — 208 с.: ил.''

-	~~<br>~~ <br>	+	<br>

	'''<u>Содержание урока</u>'''		'''<u>Содержание урока</u>'''
-	~~<u></u>~~'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] конспект урока'''	+	'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] конспект урока'''
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] опорный каркас		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] опорный каркас
-	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] презентация урока	+	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] [http://school.xvatit.com/index.php?title=%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F,_%D0%B8%D0%BB%D0%B8_%D0%BE%D0%B4%D0%B8%D0%BD_%D0%B7%D0%B0%D0%BC%D0%B5%D1%87%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC._%D0%9F%D1%80%D0%B5%D0%B7%D0%B5%D0%BD%D1%82%D0%B0%D1%86%D0%B8%D1%8F_%D1%83%D1%80%D0%BE%D0%BA%D0%B0 презентация урока]
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] акселеративные методы		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] акселеративные методы
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] интерактивные технологии		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] интерактивные технологии
Строка 89:		Строка 85:

	'''<u>Иллюстрации</u>'''		'''<u>Иллюстрации</u>'''
-	~~<u></u>~~'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] аудио-, видеоклипы и мультимедиа '''	+	'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] аудио-, видеоклипы и мультимедиа '''
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фотографии, картинки		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фотографии, картинки
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] [http://school.xvatit.com/index.php?title=%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F,_%D0%B8%D0%BB%D0%B8_%D0%BE%D0%B4%D0%B8%D0%BD_%D0%B7%D0%B0%D0%BC%D0%B5%D1%87%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC._%D0%93%D1%80%D0%B0%D1%84%D0%B8%D0%BA%D0%B8,_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B,_%D1%81%D1%85%D0%B5%D0%BC%D1%8B графики, таблицы, схемы]		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] [http://school.xvatit.com/index.php?title=%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F,_%D0%B8%D0%BB%D0%B8_%D0%BE%D0%B4%D0%B8%D0%BD_%D0%B7%D0%B0%D0%BC%D0%B5%D1%87%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC._%D0%93%D1%80%D0%B0%D1%84%D0%B8%D0%BA%D0%B8,_%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D1%8B,_%D1%81%D1%85%D0%B5%D0%BC%D1%8B графики, таблицы, схемы]
Строка 96:		Строка 92:

	'''<u>Дополнения</u>'''		'''<u>Дополнения</u>'''
-	~~<u></u>~~'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] рефераты'''	+	'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] рефераты'''
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] статьи		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] статьи
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фишки для любознательных		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] фишки для любознательных
Строка 103:		Строка 99:
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] словарь терминов		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] словарь терминов
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] прочие		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] прочие
-	~~'''<u></u>'''~~	+
	<u>Совершенствование учебников и уроков		<u>Совершенствование учебников и уроков
	</u>'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] исправление ошибок в учебнике'''		</u>'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] исправление ошибок в учебнике'''
Строка 111:		Строка 107:

	'''<u>Только для учителей</u>'''		'''<u>Только для учителей</u>'''
-	~~<u></u>~~'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] идеальные уроки '''	+	'''[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] идеальные уроки '''
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] календарный план на год		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] календарный план на год
	[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] методические рекомендации		[[Image:1236084776 kr.jpg\|10x10px\|1236084776 kr.jpg]] методические рекомендации

← Предыдущая		Версия 09:30, 29 июня 2012
Строка 1:		Строка 1:
-	<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханойская башня, или один замечательный алгоритм</metakeywords>	+	<metakeywords>Гипермаркет Знаний - первый в мире!, Гипермаркет Знаний, Информатика, 6 класс, Ханойская башня, или один замечательный алгоритм, калькулятор, алгорим, таблица</metakeywords>

	'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''		'''[[Гипермаркет знаний - первый в мире!\|Гипермаркет знаний]]>>[[Информатика\|Информатика ]]>>[[Информатика 6 класс\|Информатика 6 класс]]>> Ханойская башня, или один замечательный алгоритм'''
Строка 11:		Строка 11:
	Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».		Когда все 64 диска будут перенесены с одного стержня на другой, наступит конец света».

-	Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.<br> <br>[[Image:16-03-017.jpg]]<br><br>Если башня состоит из одного диска, то она переносится за один ход: 1->3.	+	Эта древняя легенда положена в основу задачи о Ханойской башне: переместить n дисков со стержня 1 на стержень 3, используя промежуточный стержень 2 и соблюдая законы Брамы.<br> <br>[[Image:16-03-017.jpg\|550px\|задачи о Ханойской башне]]<br><br>Если башня состоит из одного диска, то она переносится за один ход: 1->3.

	Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3.		Башня из двух дисков переносится за три хода: 1—>2, 1—>3, 2—>3.
Строка 23:		Строка 23:
	Всего на перенос потребуется 15 ходов.		Всего на перенос потребуется 15 ходов.

-	Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами алгоритм решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.	+	Рассуждая аналогичным образом, сосчитаем число ходов, необходимых для переноса башни из пяти дисков: <br><br>15 + 1 + 15 = 2 • 15 + 1 = 31.<br><br>Для башни из 6 дисков получаем: 2 • 31 + 1 = 63 и т. д. <br><br>Рассмотренный нами '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» обладает одним удивительным свойством: в ходе его выполнения для башни, состоящей из n колец, мы используем алгоритм для чуть более простой ситуации — переноса башни, состоящей из n - 1 кольца. В свою очередь, в алгоритме для башни из n - 1 кольца используется этот же алгоритм для n - 2 колец и т. д.

-	Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>'''Вопросы и задания'''<br><br>1. Проведите необходимые вычисления и заполните следующую таблицу:<br>	+	Прием, когда некоторый процесс описывается через самого себя, называется рекурсией. '''[[Что такое алгоритм\|Алгоритм]]''' решения задачи «Ханойская башня» — пример рекурсивного алгоритма.<br><br>'''Вопросы и задания'''<br><br>''1. Проведите необходимые вычисления и заполните следующую '''[[Табличные модели\|таблицу]]''':''<br>

	{\| cellspacing="1" cellpadding="1" border="1" style="width: 330px; height: 234px;"		{\| cellspacing="1" cellpadding="1" border="1" style="width: 330px; height: 234px;"
Строка 63:		Строка 63:
	\|}		\|}

-	<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?	+	''<br>2. Назовите числа: 1048 575,1073 741823,1 099 511627 775. Что это за числа?''

-	3. Для того чтобы переместить башню из 64 дисков, при безошибочной работе потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br><br><br>	+	''3. Для того чтобы переместить башню из 64 дисков, при безошибочной [http://xvatit.com/busines/ '''работе'''] потребуется 18 446 744 073 709 551 615 перекладываний. Сколько уйдет на это времени, если считать, что на одно перекладывание уходит одна секунда? Для выполнения вычислений используйте приложение '''''[[Конспект уроку на тему «Робота з Калькулятором і вікнами»\|Калькулятор]]'''. <br><br><br><br><br>

	<br>		<br>