Programowanie na II IPB: Gimnazjum

Poniżej publikujemy zadania programistyczne dla uczniów szkół podstawowych (klasy 4-6), które obowiązywały na II Informatycznym Pucharze Beskidów. Identyczną treść dostali uczestnicy, w dniu konkursu. Miłych ćwiczeń.

SITO ERATOSTENESA

Liczby pierwsze to liczby naturalne większe od 1, które dzielą się bez reszty tylko przez 1 i przez samą siebie. Liczbami pierwszymi są na przykład 2, 3, 5, 7, 11, ... ale nie 4 (bo dzieli się dodatkowo przez 2) ani 6 (dzieli się przez 2 i 3).

Uwaga: 1 nie jest liczbą pierwszą. Najmniejszą liczbą pierwszą jest 2!

Liczby pierwsze mają duże znaczenie między innymi w szyfrowaniu.

Algorytm wyszukiwania liczb pierwszych podał Eratostenes z Cyreny (ur. 276 p.n.e., zm. 194 p.n.e), grecki matematyk, astronom, filozof, geograf i poeta. Oczywiście nie był to algorytm przeznaczony dla komputerów, gdyż wtedy jeszcze nie istniały. Algorytm ten dzisiaj nazywany jest "sitem Eratostenesa" i polega na odsiewaniu liczb, które nie są pierwsze.

Jeżeli chcemy znaleźć wszystkie liczby pierwsze z przedziału od 2 (pamiętamy, że 1 nie jest liczba pierwszą) do np. 200, to kolejne kroki algorytmu przedstawiają się następująco:
  1. Wypisujemy wszystkie liczby z przeszukiwanego zakresu, tj. 2, 3, 4, 5, ..., 200.
  2. Znajdujemy najmniejszą liczbę - czyli 2 i zaznaczamy ją w jakiś sposób. Jest to liczba pierwsza.
  3. Następnie wykreślamy wszystkie wielokrotności tej liczby, czyli 2, 4, 6, 8,...
  4. Znajdujemy najmniejszą niewykreśloną i niezaznaczoną liczbę - znowu jest to liczba pierwsza, a więc zaznaczamy ją.
  5. Następnie wykreślamy jej wielokrotności.
  6. Kroki 4 i 5 powtarzamy aż do momentu, kiedy nie ma już nic do wykreślenia.
  7. W efekcie niewykreślone pozostały wszystkie liczby pierwsze z przeszukiwanego zakresu.
Zadanie:
Skonstruuj program, który wyświetli wszystkie liczby pierwsze z zakresu od A do B. Liczby A i B podawane są przez użytkownika programu, przy czym A i B mogą przyjmować wartości od 1 do 30000.

BAGAŻ PODRĘCZNY

Jesteś na zagranicznej wycieczce. Kupiłaś/kupiłeś mnóstwo prezentów dla koleżanek i kolegów z klasy. Jednakże przed powrotem okazuje się, że do samolotu możesz zabrać tylko część prezentów, gdyż bagaż podręczny nie może ważyć więcej niż N kilogramów.

Zbuduj program, który pomoże Ci wybrać te prezenty, które zapakujesz do bagażu podręcznego. Każdy z prezentów ma swoją wagę i cenę (podawaną przez użytkownika programu). Celem programu jest wybranie prezentów tak, aby ich łączna waga nie przekraczała N kilogramów, a ich wartość była możliwie jak największa.

Łączna liczba zakupionych prezentów jest nie większa niż 12. Maksymalna waga bagażu podręcznego N podawana jest przez użytkownika programu.

Popularne posty z tego bloga

Podsumowanie II Informatycznego Pucharu Beskidów

Podsumowanie I Informatycznego Pucharu Beskidów

Ruszają zapisy do III IPB