Practical examples
Task 1
Determine the smallest even number and the greatest odd number in an integer sequence.
TIP
- Partition the sequence into two sets: even and odd numbers. Partitioning PoA
- Find the maximum in the odd set. Maximum selection PoA
- Find the minimum in the even set. Minimum selection PoA
Input
Postcondition
Implementation
c#
int cnt = 0;
for (int i = 0; i < numbers.Length; i++){
if (numbers[i] % 2 == 0){
even[cnt] = numbers[i];
cnt++;
} else {
odd[i - cnt] = numbers[i];
}
}
int maxOdd = odd[0];
for (int i = 1; i < odd.Length; i++){
if (odd[i] > maxOdd){
maxOdd = odd[i];
}
}
int minEven = even[0];
for (int i = 1; i < even.Length; i++){
if (even[i] < minEven){
minEven = even[i];
}
}Task 2
We know the birth year of N friends. Write an algorithm that gives how many of them are of the same age.
TIP
- Count the number of friends born in each year. Multiset transformation PoA
- Find the maximum in the resulting multiset. Maximum selection PoA
Input
Postcondition
Where U is a set of unique birth years. After Set transformation PoA
Implementation
c#
int cnt = 0;
for (int i = 0; i < friends.Length; i++){
int j = 0;
while (j < cnt && friends[i].birthyear != R[j].birthyear){
j++;
}
if (j == cnt){
R[cnt].birthyear = friends[i].birthyear;
R[cnt].count = 1;
cnt++;
} else {
R[j].count++;
}
}Task 3
The water temperature was measured at N locations of Lake Balaton for M days. List the days with the highest temperatures that mostly deviate from the average for the whole period.
TIP
- Calculate the average temperature for the period. Sequence calculation PoA
- Transform the sequence into deviations from the average. Copy PoA
- Select maximum deviation. Maximum selection PoA
- Select days with maximum deviation. Multiple item selection PoA
Input
Postcondition
Implementation
c#
double avg = 0;
for (int i = 0; i < measurements.Length; i++){
avg += measurements[i].temp;
}
avg /= measurements.Length;
double[] deviations = new double[measurements.Length];
for (int i = 0; i < measurements.Length; i++){
deviations[i] = measurements[i].temp - avg;
}
double maxDev = deviations[0];
for (int i = 1; i < deviations.Length; i++){
if (deviations[i] > maxDev){
maxDev = deviations[i];
}
}
int cnt = 0;
for (int i = 0; i < deviations.Length; i++){
if (deviations[i] == maxDev){
days[cnt] = measurements[i].day;
cnt++;
}
}