Раздел 4. 6.docx

Раздел 4. 6

1.  Если машина может отсортировать список из 100 имен за секунду, то она способна выполнять ¹/₄ (10 000 – 100) срав- нений в секунду. Это означает, что каждое сравнение выполняется приблизительно за 0,0004 с. Следовательно, сортировка списка из 1000 имен (которая в среднем потребует выполнения ¹/₄ (10 000 000 – 1000) сравнений) займет около 100 с, или 1²/з мин.

2.  Алгоритм бинарного поиска принадлежит к классу Q (lgn), алгоритм последовательного поиска – к классу Q (n), а ал- горитм сортировки вставками – к классу Q (n²).

3.  Класс Q (lgn) содержит наиболее эффективные алгоритмы, за которыми следуют алгоритмы классов Q (n), Q (n²) и Q

(n³).

4.  Нет. Ответ неправильный, хотя может показаться верным. На самом деле у двух из трех карт обе стороны одинаковы.

Следовательно, вероятность выбора такой карты равна ²/₃.

5.  Нет. Если делимое меньше делителя, как, например, в дроби ³/₇, ответ будет равен 1, хотя он должен быть равен 0.

6.   Нет. Если значение переменной X равно 0, а значение переменной Y не равно 0, то полученный ответ будет невер-

ным.

7.  Каждый раз, когда выполняется проверка условия прекращения суммирования, утверждение "Sum = 1 + 2 + ... + 1 и I

меньше или равно N" является истинным. Объединяя его с условием прекращения суммирования "I больше или равно N", мы получим желаемый вывод "Sum = 1 + 2 + ... +N". Поскольку переменная I инициализирована нулем и увеличивается на каждом шаге цикла, в итоге ее значение обязательно должно достичь значения N.

8.   К сожалению, нет. Проблемы, выходящие за рамки управления разработкой аппаратного и программного обеспече- ния, такие, как механические сбои и электрические помехи, могут оказать влияние на ход вычислений.