Member 14048071 Ответов: 2

Сколько сравнений делает этот алгоритм?

Я наткнулся на экзаменационный вопрос с приведенным ниже алгоритмом в псевдокоде. В вопросах спрашивается: "сколько сравнений производится, если n равно 10?"

Algorithm sort
Declare A(1 to n)
n = length(A)
for i = 1 to n
    for j = 1 to n-1 inclusive do
        if A[i-1] > A[i] then
swap( A[i-1], A[i] )
        end if
    next j
next i


Что я уже пробовал:

Цитата:
Схема маркировки говорит, что это 100, но я думаю, что это неправильно, и думаю, что это 90. Каковы мнения людей?

CPallini

Вы отдаете себе отчет в том, что A[i-1] является ли доступ за пределами границ, когда i = 1 ?

Member 14048071

Будет ли это вне пределов досягаемости? Я думаю, что это будет 0? Таким образом, доступ к первому элементу массива.

CPallini

Первый элемент массива-это A[1], за Declare A(1 to n).

2 Ответов

Рейтинг:
2

OriginalGriff

Зависит от того, вы можете получить 72, 80, 81 или 90. Но, вероятно, не 100.
Простой способ узнать это: попробуйте!

int n = 10;
int count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 72
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j < n - 1; j++)
        count++;
Console.WriteLine(count);            // 80
count = 0;
for (int i = 1; i < n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 81
count = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n - 1; j++)
        count++;
Console.WriteLine(count);            // 90
Я сам? Учитывая, что один из ваших циклов конкретно относится к "инклюзивному", а другой-нет, я бы пошел с 81 ...

Rob Philpott

Да, инклюзивный бит-это странно, не так ли? Можно предположить, что это означает более высокую границу массива, но это может относиться и к нижней из них. И начиная с 1 звучит как то, что сделал бы "человек VB". Ах милый.

OriginalGriff

Я всегда думаю, что циклы начинаются с инклюзивной нижней границы (иначе зачем указывать "i = 1" или "j = 1"?)
Но включение "инклюзивного" в один цикл действительно как бы исключает другой ... плохо спроектированный. Вполне может быть VB :смех:

Member 14048071

Я думаю, что это то, что бросает меня. Я думаю, что это было написано программистом VB.

Member 14048071

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

OriginalGriff

На самом деле все это чушь собачья ... :смеяться:

Member 14048071

Это официальная документация от экзаменационной комиссии.

OriginalGriff

Но это не мешает ему быть немного дерьмовым, не так ли? :)

Рейтинг:
1

CPallini

Вы правы, так оно и есть 90 сравнения, если n является 10.
(предполагая, что "включительно" применимо к обоим циклам).