Что такое алгоритм: различия между версиями

Содержимое удалено Содержимое добавлено
мНет описания правки
м Откат правок Сунприат (обс.) к версии Oleg3280
Строка 102:
 
Докажите, что каждое натуральное число единственным образом представляется в виде суммы неповторяющихся степеней двойки. Подсказка: для данного числа <math>n</math> найдите максимальную степень двойки <math>2^m</math>, которая меньше <math>n</math>. Рассмотрите число <math>n'=n-2^m</math>. Воспользуйтесь [[w:математическая индукция|методом математической индукции]].
{{Акмар}}
{{Конец рамки}}
 
[[Файл:4_2.jpg]]
Строка 122:
 
В компьютерах элементарным объектом является бит. Есть несколько стандартных способов записи чисел (действительных, целых, и целых неотрицательных) в виде последовательности бит фиксированной длины.
{{Акмар}}
{{Конец рамки}}
 
Алгоритм входным данным сопоставляет выходные данные и этим он чем-то похож на обыкновенную функцию. Но главной особенностью алгоритма является то, что он содержит описание того, как это сделать. Функция может быть задана неявно, а алгоритм — нет. Алгоритм описывает, что нужно сделать с входными данными, чтобы получить результат. При этом предполагается, что инструкции алгоритма выполняет исполнитель с ограниченными способностями: собственная память исполнителя конечна, также конечен и чётко зафиксирован набор инструкций, которые он может исполнять. В большинстве классических исполнителей присутствует ''внешняя память'', которая ''в принципе не ограничена''. Например у человека под рукой есть сколь угодно много листов бумаги, уложенных в бесконечный ряд (ячеек памяти), которые он может использовать. Заметьте, что информация о том, что на каком
Строка 178:
 
Докажите, что НОД<math>(a,\;b)=\;</math>НОД<math>(a-b,\;b)</math> для любых неотрицательных целых <math>a</math> и <math>b</math>, таких что <math>a>b</math>.
{{Акмар}}
{{Конец рамки}}
 
{{Рамка}}
Строка 184:
 
Усовершенствуйте вышеприведённый алгоритм, используя то, что НОД<math>(a,\;b)=\;</math>НОД<math>(a\; \bmod\; b, b)</math> при положительных <math>a</math> и <math>b</math> (выражение <math>a\; \bmod\; b</math> означает остаток при делении <math>a</math> на <math>b</math>).
{{Акмар}}
{{Конец рамки}}
 
== Алгоритм вычисления чисел Фибоначчи ==
Строка 224:
 
Сколько раз вызывались вычисления <math>F_2</math> и <math>F_1</math> при вычислении <math>F_6</math>? Нарисуйте дерево рекурсивных вызовов для <math>F_7</math> и определите, сколько раз будут вызваны <math>F_1</math> и <math>F_2</math>. Найдите общую формулу для числа вызовов <math>F_1</math> и <math>F_2</math> при вычислении <math>F_n</math>.
{{Акмар}}
{{Конец рамки}}
 
Пользоваться рекурсивными алгоритмами нужно осторожно, так как они могут быть очень неэффективными с точки зрения времени работы. К сожалению рекурсивные алгоритмы не всегда являются хорошими. Попробуем оценить количество операций, необходимых для того, чтобы вычислить <math>n</math>-й член последовательности Фибоначчи (здесь под операцией мы понимаем строчку в программе). Обозначим это число как <math>T(n)</math>.
Строка 286:
 
Дано четыре стержня. На одном из них 64 кольца́, размеры которых увеличиваются от верхнего к нижнему. Следуя правилам задачи «Ханойские башни» необходимо переместить их на второй стержень. Напишите программу, которая находит минимальное необходимое число операций перекладывания одного кольца́.
{{Акмар}}
{{Конец рамки}}
 
== Примеры простых алгоритмических задач ==