Rozwiązywanie arkuszy maturalnych z informatyki

Z podanych rozwiązań należy korzystać dopiero po samodzielnym rozwiązaniu danego zadania w celu sprawdzenia poprawności wyniku. Rozwiązania nie są optymalne (nie zostały sprawdzone z kluczem odpowiedzi, ponieważ na dzień dzisiejszy klucz ten nie został jeszcze opublikowany w Internecie).

 

Poziom podstawowy

 

Zadanie 2. Rozkład liczby (7 pkt)

Rozkładem na czynniki pierwsze liczby całkowitej większej od 1 nazywamy przedstawienie tej liczby w postaci iloczynu czynników pierwszych (liczb pierwszych). Jeżeli dana liczba jest liczbą pierwszą, to w jej rozkładzie występuje tylko ona sama.

Przykłady:

24 = 2 × 2 × 2 × 3

20 = 2 × 2 × 5

19 = 19

  1. Podaj rozkład na czynniki pierwsze następujących liczb całkowitych:

Liczba Rozkład na czynniki pierwsze
63 3 3 7
184 2 2 2 23
277 277

 

  1. Ułóż algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku programowania), który dla liczby całkowitej n  (n  > 1) podaje wszystkie jej czynniki pierwsze występujące w rozkładzie.

Specyfikacja

Dane: liczba całkowita n  (n  > 1)

Wynik: wszystkie czynniki pierwsze liczby n

Przykłady:

Dla n  = 24 poprawnym wynikiem jest 2, 2, 2, 3.

Dla n  =19 poprawnym wynikiem jest 19.

 

Istnieje kilka algorytmów rozkładu na czynniki pierwsze. Na maturze można podać najprostszy z nich, zwany bezpośrednim poszukiwaniem rozkładu na czynniki pierwsze (ang. direct search factorization lub trial division). W algorytmie tym sprawdza się podzielność liczby n  przez kolejne liczby naturalne i  od 2 do pierwiastka z n. Jeśli liczba n  jest podzielna przez daną liczbę i, to liczbę i  wyprowadzimy na wyjście, a za nowe n  przyjmiemy wynik dzielenia i próbę dzielenia będziemy powtarzać dotąd, aż nie będzie to już możliwe. Wtedy przejdziemy do następnego dzielnika. Gdy wykorzystamy wszystkie dzielniki, musimy sprawdzić, czy liczba n  została zredukowana do 1. Jeśli nie, to jest ona równa ostatniemu dzielnikowi, który jest większy od wyliczonego wcześniej pierwiastka z n. Więcej informacji na ten temat znajdziesz tu:

 

Rozkład na czynniki pierwsze metodą próbnych dzieleń
Rozkład na czynniki pierwsze metodą Fermata

 

Lista kroków:

krok 1: g  ← [√n]
krok 2: i 
← 2
krok 3: Jeśli i  > g, to idź do kroku 7
krok 4: Dopóki n  mod i  = 0, to wykonuj:
               Pisz i
               n  ← n  / i
krok 5: i  ← i  + 1
krok 6: Idź do kroku 3
krok 7: Jeśli n  > 1, to pisz n
krok 8: Zakończ

 

Schemat blokowy:

obrazek

 

Program C++:

// Zadanie 2b
// Rozkład na czynniki pierwsze
//-----------------------------

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  unsigned g,i,n;
  cin >> n;
  g = sqrt(n);
  for(i = 2; i <= g; i++)
    while(n % i == 0)
    {
      cout << i << " ";
      n /= i;
    }
  if(n > 1) cout << n;
  cout << endl;
  return 0;
}

 

Program Pascal:

{ Zadanie 2b
  Rozkład na czynniki pierwsze
  ----------------------------}

program rozklad;
var
  g,i,n : cardinal;
begin
  readln(n);
  g := round(sqrt(n));
  for i := 2 to g do
    while n mod i = 0 do
    begin
      write(i,' ');
      n := n div i;
    end;
  if n > 1 then write(n);
  writeln;
end.

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2021 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe