matura informatyka

Question

Witam przygotowywuję się do matury z informatyki i postanowiłem zrobić sobie zadania z ubiegłych lat arkusze z zadaniami znalazłem, ale nie do wszystkich mogę znaleźć odpowiedź czy wiecie może gdzie mogę znaleźć odpowiedzi do zadań z matury z informatyki  także tych z przed 2015 r.

Jeśli nie da się już ich znaleźć czy mógł by mi ktoś powiedzieć ile wynosi odpowiedź do tego zadania mi wychodzi 13 ale nie jestem pewien.

Liczbami półpierwszymi nazywamy liczby, które są iloczynem dwu liczb pierwszych. Przykład: 34 jest liczbą półpierwszą, ponieważ 34 = 2 * 17 95 jest liczbą półpierwszą, ponieważ 95 = 5 * 19 699 jest liczbą półpierwszą, ponieważ 699 = 3 * 233 841 jest liczbą półpierwszą, ponieważ 841 = 29 * 29 Wykonaj poniższe polecenia: a) Sprawdź, czy poniższe liczby są półpierwsze. Dla tych które są, wpisz ich rozkład na czynniki pierwsze, dla pozostałych wpisz słowo „NIE.

W pliku liczby.txt umieszczono w kolejnych wierszach 500 całkowitych liczb dodatnich, z których każda ma co najwyżej 6 cyfr. Napisz program, za pomocą którego otrzymasz wszystkie liczby półpierwsze z pliku liczby.txt. Otrzymane wyniki zapisz w pliku zadanie5.txt. Przy ocenie Twojego programu będą przyznawane punkty za złożoność zastosowanego przez Ciebie algorytmu. Niżej są dane.

 https://megawrzuta.pl/download/247a0805f0046910c254cadc04d2b568.html

 

#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>

using namespace std;

void sito(vector<bool> &pierwsze,int r) {

    for (int i = 2; i <= r; i++) {
        if (pierwsze[i]) {
            for (int j = i*2; j <= r; j+=i) {
                pierwsze[j] = false;
            }
        }
    }

}

int main() {

    const int r = 999999;

    vector <int> liczby;
    vector <bool> pierwsze(r+1,true);
    vector <int> pomoc;

    pierwsze[0] = pierwsze[1] = false;

    ifstream plik("liczb.txt");

    if ( ! plik.is_open() ) return 1;
    while (!plik.eof())
    {
        int p;
        plik >> p;
        liczby.push_back(p);
        cout << p << "\n";
    }
    plik.close();

    sito(pierwsze,r);

    for (int i = 2; i <= r; i++) {
        if (pierwsze[i]) pomoc.push_back(i);
    }

    int ile = 0;

    for (int i = 0; i < 500; i++) {
        if (!pierwsze[liczby[i]]) {
            int lewy = 2; int prawy = pomoc.size()-1;
            while (lewy <= prawy && pomoc[lewy] * pomoc[prawy] != liczby[i]) {
                if (pomoc[lewy] * pomoc[prawy] < liczby[i]) lewy++;
                else if (pomoc[lewy] * pomoc[prawy] > liczby[i]) prawy--;
            }
            if (lewy <= prawy) {
                ile++;
                cout << liczby[i] << " " << pomoc[lewy] << " " << pomoc[prawy] << "\n";
            }
        }
    }

    cout << ile << "\n";

    return 0;
}

 

Comments

Weź to edytuj i wrzuć gdzieś link z tymi danymi. W dodatku gdzie tutaj jest pytanie? Gdzie Twój kod, w którym masz problem lub który chciałbyś, by ktoś sprawdził? Nie po to mamy tyle możliwości, by korzystać z tych najbardziej prymitywnych, to jest wklejenia pięciuset linii danych w poście...

---

dobrze ale mógłbyś mi podpowiedziać jak wstawić osobno link z tymi danymi

---

Poszukaj jakiegoś darmowego hostingu plików. Ten plik pewnie niewiele waży, więc taki w zupełności wystarczy. Kod możesz wkleić bezpośrednio na forum opcją "Dodaj lub zaktualizuj bloczek kodu".

---

Dziękuję za pomoc edytowałem i wrzuciłem kod

Answer 1

Trochę popatrzyłem i algorytm nie jest do końca dobry. Nawet w treści zadania masz, że 34 spełnia warunki zadania, bo jest iloczynem 2*17. Jednakże jeśli do pliku, na przykład w miejsce pierwszej wartości wstawimy 34, to nie zostanie owa wartość wypisana na ekranie, tak więc algorytm jest nieprawidłowy. 
W dodatku zmień warunek 

for (int i = 2; i <= r; i++)

na taki:
 

for (int i = 2; i <= sqrt(r); i++)

Działa tak samo, ale jest o wiele mniej obliczeń. 

Zapewne błędne zliczanie wynika z Twojego pomysłu na algorytm, to jest:
 

for (int i = 0; i < 500; i++) {
        if (!pierwsze[liczby[i]]) {
            int lewy = 2; int prawy = pomoc.size()-1;
            while (lewy <= prawy && pomoc[lewy] * pomoc[prawy] != liczby[i]) {
                if (pomoc[lewy] * pomoc[prawy] < liczby[i]) lewy++;
                else if (pomoc[lewy] * pomoc[prawy] > liczby[i]) prawy--;
            }
            if (lewy <= prawy) {
                ile++;
                cout << liczby[i] << " " << pomoc[lewy] << " " << pomoc[prawy] << "\n";
            }
        }
    }

 

Ogółem na Twoim miejscu zmieniłbym również ilość liczb pierwszych, jakie sprawdzasz. W warunkach zadaniach masz powiedziane, że są to liczby maksymalnie sześciocyfrowe oraz szukamy jednocześnie liczb, które są iloczynami dwóch liczb pierwszych. A to oznacza, że najmniejszym dzielnikiem szukanych liczb jest 2. Oczywiście nie dla każdej liczby dwa będzie dzielnikiem, ale jeśli podzielimy liczbę pół-pierwszą przez liczbę większą od 2, to otrzymamy liczbę mniejszą od tej samej liczby podzielonej przez 2. 
Aby było jaśniej dam przykład: 
100/2 = 50, ale już 100/3 = 33 i 1/3. Wobec tego jeśli mianownik rośnie, to wynik maleje. 
Wobec powyższej uwagi szukałbym w Twoim algorytmie sita liczb nie większych niż (999999/2). 
Dodam, że ta mała zmiana Twojej zmiennej r na r = (999999/2) przyspieszyła wykonanie programu (u mnie) o jakieś 0.3 sekundy, więc możesz sobie wyobrazić, jak dużo mniej działań zostało wykonanych 

 

EDIT: No dobra, poszperałem Trochę i już wiem, gdzie masz błąd. 
Mianowicie:
 

int lewy = 2; int prawy = pomoc.size()-1;

Niby nic takiego, prawda? Tyle, że potem odwołujesz się do pomoc[lewy]. Wobec tego nie dopuszczasz w ogóle możliwości, że jedną ze składowych iloczynu liczby jest 2 lub 3. 

Comments

Dziękuję za pomoc i chyba znalazłem błąd ponieważ do zmiennej lewy przypisuję wartość 2 pomyliłem się i musiałem pomyśleć że zacznę wtedy od liczby 2 ale zacznę wtedy od liczby znajdującej się w zmiennej pomoc[2] pomijając niektóre liczby w tym 2 więc zapewne dlatego przykład z 34 nie działa. Mógłby mi jeszcze pan wyjaśnić dlaczego 

for (int i = 2; i <= sqrt(r); i++) 

to działa z góry dziękuję za pomoc

---

Przepraszam nie zauważyłem tego fragmentu

Niby nic takiego, prawda? Tyle, że potem odwołujesz się do pomoc[lewy]. Wobec tego nie dopuszczasz w ogóle możliwości, że jedną ze składowych iloczynu liczby jest 2 lub 3.

---

O widzisz, znaleźliśmy ten sam błąd.

---

@milosz123, Nie zauważyłeś, bo byłeś szybszy o dosłownie 4 sekundy w swojej wypowiedzi 

---

Mógłby mi pan jeszcze objaśnić dlaczego ten fragment kodu działa 

for (int i = 2; i <= sqrt(r); i++) 

 

---

@milosz123, Próbowałem dowodzić, ale to nie takie proste. Nie mogę również znaleźć żadnego konkretnego twierdzenia - a takowe na pewno istnieje. Postaram się czegoś poszukać w czasie wolnym 

Answer 2

Uważam, że Twój algorytm ma trochę zbyt skomplikowany sposób działania. IMHO lepiej jest tutaj zastosować kontener std::set, który będzie przechowywał posortowane liczby pierwsze oraz std::vector do przechowywania podanych liczby do sprawdzenia.

Następnie dla każdej liczby n z kontenera std::vector sprawdzamy czy jest ona podzielna przez którąś z liczb pierwszych znajdujących się w std::set. Jeżeli dla liczby n istnieje taka liczba ( np. p ) to sprawdzamy czy istnieje liczba pierwsza n/p znajdująca się w zbiorze std::set. Jeżeli tak - to liczba n jest pół pierwsza.

Tutaj masz przykład kodu ( C++17 )

#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;

bool isPrime( int number )
{
    if( number == 2 ) return true;
    if( number % 2 == 0 || number < 2 ) return false;
    for( int i {3} ; (i*i)<=number ; i+=2 ) if( number % i == 0 ) return false;
    return true;
}

auto createSetWithPrimeNumbers( int maximum )
{
    set<int> container;
    for( auto i {0} ; i<=maximum/2 ; ++i ) if( isPrime(i) ) container.insert(i);
    return container;
}

int main()
{
    ifstream file {"dane.txt"};
    vector<int> data { istream_iterator<int>{file} , {} };

    const auto primes = createSetWithPrimeNumbers( *max_element(data.cbegin(),data.cend()) );

    for( const auto& number : data )
    {
         for( const auto& prime : primes )
         {
             if( prime>number/2 ) break;
             if( number%prime == 0 )
             {
                 if( primes.find(number/prime) != primes.end() )
                 {
                     cout << "Number " << number << " is semiprime" << endl;
                     break;
                 }
             }
         }
    }

    return 0;
}