Информатика. Курс лекций. Громов Ю.Ю - 108 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Cheryl Alice Alice
George Cheryl Bob
Alice George Cheryl
Bob Bob George
4. Настаивать на том, чтобы предшествующий элемент помещался на то же место в списке, бессмысленно. Например,
сделайте предложенные изменения, а затем примените новую программу к списку, все элементы которого одинаковы.
5.
procedure sort(Список)
N ← 1;
while (N < длины Списка) do
{J ← N+1;
while (J ≤ длины Списка) do
{if (элемент в позиции J < элемент в позиции N)
then {поменять местами эти два элемента)
J ← J+1}
N ← N+1}
6. Приведенное ниже решение является неэффективным. Можете ли вы сделать его более эффективным?
procedure sort(Список)
N ← длина Cписка;
while (N > 1) do
{J ← длина Списка;
while (J > 1) do
{if (элемент в позиции J < элемента в позиции J-1)
then {поменять местами эти два элемента}
J ← J–1}
N ← N–1}
Раздел 4.5
1. Первый подсписок состоит из имен, следующих за именем Henry, т.е. Irene, Joe, Karl, Larry, Mary, Nancy и Oliver. Да-
лее идут имена из этого списка, предшествующие имени Larry, т.е. Irene, Joe и Karl. Теперь в очередном цикле поиска иско-
мое имя Joe будет найдено в середине рассматриваемого подсписка.
2. 8, 17
3.
Alice Alice
Carol Bob
Bob Carol
Larry Larry
John John
В итоге будет выполнено четыре вызова процедуры.
4. В результате выполнения процесса список будет отсортирован. Однако его выполнение будет сопровождаться из-
лишней потерей времени, поскольку при первом вызове процедуры первый элемент списка сначала удаляется, а потом воз-
вращается на прежнее место.
5. Будет выполнено несколько вызовов процедуры. При каждом из них элемент будет просто удаляться из списка, а за-
тем возвращаться на прежнее место.
Раздел 4.6
1. Если машина может отсортировать список из 100 имен за секунду, то она способна выполнять
1
/
4
(10 000 – 100) срав-
нений в секунду. Это означает, что каждое сравнение выполняется приблизительно за 0,0004 с. Следовательно, сортировка
списка из 1000 имен (которая в среднем потребует выполнения
1
/
4
(10 000 000 – 1000) сравнений) займет около 100 с, или 1
2
/з
мин.
2. Алгоритм бинарного поиска принадлежит к классу Θ (lgn), алгоритм последовательного поиска – к классу Θ (n), а ал-
горитм сортировки вставками – к классу Θ (n
2
).
3. Класс Θ (lgn) содержит наиболее эффективные алгоритмы, за которыми следуют алгоритмы классов Θ (n), Θ (n
2
) и Θ
(n
3
).
4. Нет. Ответ неправильный, хотя может показаться верным. На самом деле у двух из трех карт обе стороны одинаковы.
Следовательно, вероятность выбора такой карты равна
2
/
3
.
5. Нет. Если делимое меньше делителя, как, например, в дроби
3
/
7
, ответ будет равен 1, хотя он должен быть равен 0.
6. Нет. Если значение переменной X равно 0, а значение переменной Y не равно 0, то полученный ответ будет невер-
ным.
7. Каждый раз, когда выполняется проверка условия прекращения суммирования, утверждение "Sum = 1 + 2 + ... + 1 и I
меньше или равно N" является истинным. Объединяя его с условием прекращения суммирования "I больше или равно N",
мы получим желаемый вывод "Sum = 1 + 2 + ... +N". Поскольку переменная I инициализирована нулем и увеличивается на
каждом шаге цикла, в итоге ее значение обязательно должно достичь значения N.
8. К сожалению, нет. Проблемы, выходящие за рамки управления разработкой аппаратного и программного обеспече-
ния, такие, как механические сбои и электрические помехи, могут оказать влияние на ход вычислений.

Страницы