Что делает этот алгоритм? - PullRequest
Новая
       1

Что делает этот алгоритм?

0 голосов
/ 28 января 2011

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

Algorithm ???  
Input A: Array of Integers; n: Integer;  
Variables i, c: Integers;  

Begin 
    for i:=0 to n-1 do  
        c:=1;  
        while ((i+c)<n) and (A[i]<A[i+c]) do
           c:=c+1;
        od
        output(i,A[i],c-1);
    od
End

Ответы [ 3 ]

2 голосов
/ 28 января 2011

Алгоритм принимает массив целых чисел (отсортированных или не отсортированных) и выводит количество элементов в одном массиве с индексом, превышающим текущую позицию и , которые превышают текущее значение позиции индекса.

Например,

отсортированный вручную массив восходящих целых чисел: 

public static void main(String[] args){
    // stores an array of integers
    int [] myArray = {0,1,2,3};
    // assuming the length of array is n
    int n = myArray.length;
    // counter variables
    int i,c;
    // starting from array index 0 to the length of the array
    for(i=0;i<(n);i++){
        c = 1;
        while(((i+c)<n) && (myArray[i]<myArray[i+c])){
            c++;
        }
        System.out.println("index value..."+i+", myArray value..."+myArray[i]+", number of items in array with index greater than current with values greater than current..."+(c-1));
    }

}

даст вывод 

index value...0, myArray value...0, number of items in array with index greater than current with values greater than current...3
index value...1, myArray value...1, number of items in array with index greater than current with values greater than current...2
index value...2, myArray value...2, number of items in array with index greater than current with values greater than current...1
index value...3, myArray value...3, number of items in array with index greater than current with values greater than current...0

для отсортированного вручную массива по убываниюцелые числа: 

int [] myArray = {10,9,8};

вывод: 

index value...0, myArray value...10, number of items in array with index greater than current with values greater than current...0
index value...1, myArray value...9, number of items in array with index greater than current with values greater than current...0
index value...2, myArray value...8, number of items in array with index greater than current with values greater than current...0

для массива целых чисел: 

int [] myArray = {1,1,1};

вывод будет 

index value...0, myArray value...1, number of items in array with index greater than current with values greater than current...0
index value...1, myArray value...1, number of items in array with index greater than current with values greater than current...0
index value...2, myArray value...1, number of items in array with index greater than current with values greater than current...0
1 голос
/ 28 января 2011

Вот что поможет вам помочь себе и сдать экзамен: Как вы думаете, что это делает? Если вы передадите его A = [1, 2, 3] и n = 3, что произойдет? Если вы передадите его A = [3, 2, 1, 0] и n = 3, что произойдет? Не могли бы вы написать код на Java / JavaScript / C # / Python / Erlang и посмотреть, что произойдет самостоятельно?

1 голос
/ 28 января 2011

Для каждого числа в массиве этот алгоритм находит количество чисел справа от него, которые образуют последовательную последовательность чисел, большую или равную этому числу.

...