- #1

evinda

Gold Member

MHB

- 3,836

- 0

I am looking at the following exercise:

We say that a sequence of numbers $A=(a_1,a_2, \dots, a_n) , n \geq 3$, is strictly alternating if for each $i$, with $2 \leq i \leq n-1$, one of the following conditions stands:

- $a_{i-1}< a_i$ and $a_i>a_{i+1}$

$$$$ - $a_{i-1}>a_i$ and $a_i<a_{i+1}$

For example, the sequences $(2,10,5,6,3,11,-1,7,4)$ and $(2,-7,4,3,6,0,33,2)$ are alternating, but the sequnce $(5,6,7,3,4,-2,7,10)$ isn't.

Design an algorithm, that, given an alternating sequence of numbers $A$, executes at most $\lceil \frac{n}{2} \rceil$ comparisons, in order to calculate the minimum element of $A$. Justify your answer.

I wrote the following code:

Code:

```
#include <stdio.h>
int main()
{
int n,i,min,position_min;
printf("Give n: \n");
scanf("%d",&n);
while (n<3){
printf(" Give an other value for n: \n");
scanf("%d", &n);
}
int A[n];
for (i=0; i<n; i++){
printf("Give the value of the %dth position of the array: \n",i+1);
scanf("%d",&A[i]);
}
min=A[0];
position_min=0;
if (A[1]<min) {
min=A[1];
position_min=1;
}
for (i=position_min+2; i<n; i+=2){
if (A[i]<min){
min=A[i];
position_min=i;
}
}
printf("min=%d \n ",min);
return 0;
}
```

So, we need $2 \left ( \frac{n-\text{position_min}-2+1}{2} \right )=n-\text{position_min}-1$ comparisons..But.. we don't need $\lceil \frac{n}{2} \rceil$ comparisons, at the algorithm I wrote.. (Sweating)

How could I do it otherwise?