Skip to content

Practical examples ​

Task 1 ​

Determine the smallest even number and the greatest odd number in an integer sequence.

TIP

  1. Partition the sequence into two sets: even and odd numbers. Partitioning PoA
  2. Find the maximum in the odd set. Maximum selection PoA
  3. Find the minimum in the even set. Minimum selection PoA

Input ​

numbers[1..]∈Rn

Postcondition ​

cnt=∑i=1length(numbers){1if numbers[i] is even0otherwiseeven[1..cnt]={ numbers[i] | numbers[i] is even }i=1length(numbers)odd[1..length(numbers)−cnt]={ numbers[i] | numbers[i] is odd }i=1length(numbers)maxOdd=maxi=1length(odd)odd[i]minEven=mini=1length(even)even[i]

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

  1. Count the number of friends born in each year. Multiset transformation PoA
  2. Find the maximum in the resulting multiset. Maximum selection PoA

Input ​

Tfriend=(name×birthyear)n∈N+friends[1..n]∈Tfriendn

Postcondition ​

cnt=∑i=1length(friends){1if  ∄j (1≤j<i):friends[i].birthyear=friends[j].birthyear0otherwiseU[1..cnt]=⋃i=1length(friends){ friends[i].birthyear | friends[i].birthyear∉U }

Where U is a set of unique birth years. After Set transformation PoA

R[1..cnt].birthyear=U[1..cnt]R[1..cnt].count=⋃i=1length(friends){ ∑j=1length(friends){1if friends[j].birthyear=R[i].birthyear0otherwise }

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

  1. Calculate the average temperature for the period. Sequence calculation PoA
  2. Transform the sequence into deviations from the average. Copy PoA
  3. Select maximum deviation. Maximum selection PoA
  4. Select days with maximum deviation. Multiple item selection PoA

Input ​

Tmeasurement=(loc×day×temp)measurements[1..]∈Tmeasurementn

Postcondition ​

avg=∑i=1length(measurements)measurements[i].templength(measurements)∀i (1≤i≤length(measurements)):deviations[i]=measurements[i].temp−avgmaxDev=maxi=1length(deviations)deviations[i]cnt=∑i=1length(deviations){1if deviations[i]=maxDev0otherwisedays[1..cnt]=⋃i=1length(deviations){ measurements[i].day | deviations[i]=maxDev }

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