Zadanie 5 - zbiór zadań maturalnych informatyka

Question

Witam, natknąłem się na prawdopodobnie kolejny błąd w zbiorze zadań maturalnych z informatyki od CKE. W odpowiedziach na j = 2 w tabeli jest odpowiednio 1 i 1. Moja odpowiedź natomiast to 2 i 0. Czy mógłby ktoś spojrzeć na to świeżym okiem i wskazać dobrą odpowiedź?

Answer 1

Tym razem wygląda na to, że odpowiedź mają poprawną. Przepisałem ten algorytm do C++. Poniżej zamieszczę kod wraz z odpowiedzią.

#include <iostream>
using namespace std;
int main()
{
  const int n = 6;
  int A[ n + 1 ] = {0,12,4,3,10,5,11};

  for( int j = n - 1; j >= 1; j-- )
  {
      int x = A[ j ];
      int p = j;
      int k = n + 1;
      cout << "j = " << j << endl;
      
      int licznikK = 0;
      int licznikP = 0;
      while( k - p > 1 )
      {
          int i = (p+k)/2;
          if( x <= A[i] )
          {
            k = i;
            licznikK++;
          }
          else
          {
            p = i;
            licznikP++;
          }
      }
      cout << "k " << licznikK << " razy" << endl;
      cout << "p " << licznikP << " razy" << endl;
      cout << "-------------------------" << endl;
      for( int i = j; i <= p - 1; i++ )
      {
          A[ i ] = A[ i + 1 ];
      }
      A[ p ] = x;
  }
}

Wynik programu jest następujący:

j = 5
k 1 razy
p 0 razy
------------------------------------
j = 4
k 1 razy
p 1 razy
------------------------------------
j = 3
k 2 razy
p 0 razy
------------------------------------
j = 2
k 1 razy
p 1 razy
------------------------------------
j = 1
k 0 razy
p 3 razy
------------------------------------

Zawsze jak masz wątpliwości, to spróbuj przepisać algorytm z pseudokodu na znany Ci język programowania. Można poćwiczyć dobrze się przy tym bawiąc.

Pozdrawiam :-)

Comments

Tak, rzeczywiście popełniłem błąd po drodze porównując do złego x'a. Dziękuję za pomoc.