开发者

What does this algorithm do?

Got an exam tomorrow and one of the practice question asks what this algorithm written in pseudocode does. Can anyone help?

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


The algorithm takes an array of integers (sorted or unsorted) and outputs the number of items in the same array with an index higher than the current position and that are larger than the current index positions value.

For example

manually sorted array of ascending integers :

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));
    }

}

would give the output

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

for a manually sorted array of descending integers :

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

the output is :

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

for an array of integers all the same :

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

the output would be

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


Here's helping you help yourself and pass your exam: What do you think it does? If you pass it A = [1, 2, 3] and n = 3, what happens? If you pass it A = [3, 2, 1, 0] and n = 3, what happens? Could you code it up in Java/JavaScript/C#/Python/Erlang and see what happens yourself?


For each number in the array, this algorithm finds the count of numbers to its right that form a consecutive sequence of numbers greater than or equal to this number.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜