Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Problem nr 1W przedziale <a, b> liczb całkowitych należy wyszukać wszystkie liczby podzielne przez jedną z liczb z zadanego zbioru P. |
W przypadku ogólnym stosujemy podejście pierwsze, czyli generujemy wszystkie kolejne liczby z przedziału <a, b> i sprawdzamy, czy dzielą się bez reszty przez jedną z liczb z zadanego zbioru. Jeśli tak, wyprowadzamy je na wyjście.
Kolejne liczby z przedziału <a, b> podzielne przez jeden z podzielników w P.
K01: Dla i = a, a+1,…,b: ; przechodzimy przez kolejne wykonuj kroki K02…K03 ; liczby z przedziału <a,b> K02: Dla j = 0,1,…,n-1: ; sprawdzamy, czy liczba i dzieli się wykonuj kroki K03…K05 ; przez jeden z podzielników z tablicy P. K03: Jeśli i mod P[j] ≠ 0, ; nie dzieli się, następny podzielnik to następny obieg pętli K02 K04: Pisz i ; dzieli się, wypisz liczbę i K05: Następny obieg pętli K01 ; przerywamy pętlę K02
K06: Zakończ
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program spodziewa się w pierwszym
wierszu liczb a i b.
W drugim wierszu należy podać
|
Dane przykładowe (przekopiuj
do schowka i wklej do okna konsoli): -100 100 3 5 12 17 |
Pascal// Liczby podzielne // Data : 11.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; const MAXP = 1000; var a, b, i, j, n : longint; P : array [0..MAXP-1] of longint; begin readln(a,b); readln(n); for i := 0 to n - 1 do read(P[i]); readln(); // Koniec wiersza danych for i := a to b do for j := 0 to n - 1 do if i mod P[j] = 0 then begin write (i,' '); break; end; writeln; end. |
// Liczby podzielne // Data : 11.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> using namespace std; const int MAXP = 1000; int main() { int a, b, i, j, n, P[MAXP]; cin >> a >> b >> n; for(i = 0; i < n; i++) cin >> P[i]; for(i = a; i <= b; i++) for(j = 0; j < n; j++) if(i % P[j] == 0) { cout << i << " "; break; } cout << endl; return 0; } |
BasicConst MAXP = 1000 Dim As Integer a,b,i,j,n,P(MAXP-1) Open Cons For Input As #1 Input #1,a,b,n For i = 0 To n - 1 Input #1,P(i) Next For i = a To b For j = 0 To n - 1 If i Mod P(j) = 0 Then Print i;" "; Exit For End If Next Next Print Close #1 End |
Python (dodatek)# Liczby podzielne # Data : 02.02.2024 # (C)2024 mgr Jerzy Wałaszek #---------------------------- # odczyt i przygotowanie danych arr = input().split(" ") a = int(arr[0]) b = int(arr[1]) n = int(input()) p = input().split(" ") for i in range(n): p[i] = int(p[i]) # obliczenia for i in range(a,b+1): for j in range(n): if not(i % p[j]): print(i, end=" ") break print() |
Wynik: |
-100 100 3 5 12 17 -100 -96 -95 -90 -85 -84 -80 -75 -72 -70 -68 -65 -60 -55 -51 -50 -48 -45 -40 -36 -35 -34 -30 -25 -24 -20 -17 -15 -12 -10 -5 0 5 10 12 15 17 20 24 25 30 34 35 36 40 45 48 50 51 55 60 65 68 70 72 75 80 84 85 90 95 96 100 |
Problem można rozwiązać podejściem drugim, tzn. wyznaczając kolejne liczby podzielne przez jeden z podzielników z tablicy P. Wystarczy zauważyć, iż liczby te będą wielokrotnościami swoich podzielników. Zatem dla każdego podzielnika wyznaczamy najmniejszą wielokrotność zawartą w przedziale <a, b>. Następnie z tych wielokrotności wybieramy najmniejszą i przesyłamy na wyjście. Jeśli w trakcie szukania najmniejszej liczby trafimy na taką, która została już wysłana na wyjście, to zamieniamy ją na jej następną wielokrotność. Operację kontynuujemy dotąd, aż najmniejsza liczba przekroczy kraniec b przedziału. Poniżej przedstawiamy szczegółowy algorytm tego rozwiązania.
Kolejne liczby z przedziału
K01: Dla i = 0,1,…,n–1: wykonuj kroki K02…K03 K02: Jeśli P[i] < 0, ; ujemne podzielniki zamieniamy to P[i] ← -P[i] ; na dodatnie K03: Jeśli a < 0, to ; wyznaczamy pierwszą wielokrotność V[i] ← (a div P[i])×P[i] ; podzielnika P[i] inaczej V[i] ← ((a+P[i]-1) div P[i])×P[i] K04: s ← a-1 ; s zapamiętuje wysłaną na wyjście liczbę. ; Nadajemy jej wartość niemożliwą K05: minv ← MAXZ ; wśród wielokrotności V szukamy najmniejszej K06: Dla i = 0,1,…,n–1: wykonuj kroki K07…K08 K07: Jeśli V[i] = s, ; jeśli trafimy na wysłaną już wielokrotność, to V[i] ← V[i]+P[i] ; to obliczamy kolejną K08: Jeśli V[i] < minv, ; zapamiętujemy najmniejszą z wielokrotności to minv ← V[i] K09: s ← minv ; zapamiętujemy w s znalezioną najmniejszą z wielokrotności K10: Jeśli s > b, ; jeśli jest ona poza przedziałem <a,b>, to kończymy to zakończ K11: Pisz s ; inaczej wyprowadzamy s i kontynuujemy pętlę K12: Idź do kroku K05
Algorytm wygląda na dłuższy niż w pierwszej wersji. Jednakże działa on efektywniej, ponieważ w pętli głównej nie wykonujemy dzieleń, a jedynie dodawania oraz pętla ta nie wykonuje pustych przebiegów – przy każdym obiegu wyprowadzana jest jedna liczba. Korzyści ujawnią się szczególnie przy dużym przedziale <a, b> oraz znacznej różnicy pomiędzy dzielnikami.
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program spodziewa się w pierwszym
wierszu liczb |
Dane przykładowe (przekopiuj do schowka i
wklej do okna konsoli)
-100 100 3 5 12 17 |
Pascal// Liczby podzielne - wersja 2 // Data : 12.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; const MAXZ = 2147483647; const MAXP = 1000; var a, b, i, n, s, minv : longint; P, V : array [0..MAXP-1] of longint; begin readln(a, b); readln(n); for i := 0 to n-1 do begin readln(P[i]); if P[i] < 0 then P[i] := -P[i]; if a < 0 then V[i] := (a div P[i]) * P[i] else V[i] := ((a + P[i] - 1) div P[i]) * P[i]; end; s := a - 1; while true do begin minv := MAXZ; for i := 0 to n-1 do begin if V[i] = s then inc(V[i],P[i]); if V[i] < minv then minv := V[i]; end; s := minv; if s > b then break; write (s, ' '); end; writeln; end. |
// Liczby podzielne - wersja 2 // Data : 12.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> using namespace std; const int MAXZ = 2147483647; const int MAXP = 1000; int main() { int a, b, i, n, s, minv; int P[MAXP], V[MAXP]; cin >> a >> b >> n; for(i = 0; i < n; i++) { cin >> P[i]; if(P[i] < 0) P[i] = -P[i]; if(a < 0) V[i] = (a / P[i]) * P[i]; else V[i] = ((a + P[i] - 1) / P[i]) * P[i]; } s = a - 1; while(true) { minv = MAXZ; for(i = 0; i < n; i++) { if(V[i] == s) V[i] += P[i]; if(V[i] < minv) minv = V[i]; } s = minv; if(s > b) break; cout << s << " "; } cout << endl; return 0; } |
Basic' Liczby podzielne - wersja 2 ' Data : 12.03.2008 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- Const MAXZ = 2147483647 Const MAXP = 1000 Dim As Integer a, b, i, n, s, minv Dim As Integer P(MAXP), V(MAXP) Input a, b Input n For i = 0 To n-1 Input P(i) If P(i) < 0 Then P(i) = -P(i) If a < 0 Then V(i) = (a \ P(i)) * P(i) Else V(i) = ((a + P(i) - 1) \ P(i)) * P(i) End If Next s = a - 1 Do minv = MAXZ For i = 0 To n - 1 If V(i) = s Then V(i) += P(i) If V(i) < minv Then minv = V(i) Next s = minv If s > b Then Exit Do Print s;" "; Loop Print End |
Python (dodatek)# Liczby podzielne - wersja 2 # Data : 13.02.2024 # (C)2024 mgr Jerzy Wałaszek # ---------------------------- Maxz = 2147483647 v = [] p = [] arr = input().split(" ") a = int(arr[0]) b = int(arr[1]) n = int(input()) for i in range(n): p.append(int(input())) if p[i] < 0: p[i] = -p[i] if a < 0: v.append((a // p[i]) * p[i]) if v[i] < a: v[i] += p[i] # korekcja !!! else: v.append(((a + p[i] - 1) // p[i]) * p[i]) s = a - 1 while True: minv = Maxz for i in range(n): if v[i] == s: v[i] += p[i] if v[i] < minv: minv = v[i] s = minv if s > b: break print(s, end=" ") print() |
Problem nr 2W przedziale <a, b> liczb całkowitych wyszukać wszystkie liczby podzielne przez każdą z liczb z zadanego zbioru P liczb względnie pierwszych. |
Jeśli liczba ma być podzielna przez każdy z podzielników, to również musi być podzielna przez ich iloczyn. Zatem w podejściu 1 obliczamy iloczyn kolejnych podzielników, a następnie w pętli przebiegającej przez kolejne liczby z przedziału <a,b> sprawdzamy, czy są one podzielne przez ten iloczyn. Jeśli tak, to wyprowadzamy je na wyjście.
W podejściu drugim obliczamy najmniejszą wielokrotność iloczynu podzielników, która wpada w przedział <a, b> (patrz powyżej – rozwiązanie alternatywne). Następnie w pętli dopóki wielokrotność jest mniejsza lub równa b, wyprowadzamy ją na wyjście i obliczamy następną dodając iloczyn podzielników.
W ramach ćwiczeń proponuję czytelnikom samodzielne utworzenie algorytmów oraz na ich podstawie odpowiednich programów.
Problem nr 3W przedziale <a, b> liczb całkowitych wyszukać wszystkie liczby niepodzielne przez żadną z liczb z zadanego zbioru P. |
Stosując pierwsze podejście przebiegamy przez kolejne liczby w przedziale <a, b>. Każdą liczbę sprawdzamy na podzielność przez podzielniki z P. Jeśli któryś z nich dzieli liczbę, to przechodzimy do następnej liczby w <a, b>. Jeśli żaden nie dzieli liczby, liczbę wyprowadzamy na wyjście.
Kolejne liczby z przedziału <a, b> niepodzielne przez żaden z podzielników w tablicy P.
K01: Dla i = a,a+1,…,b: ; pętla przebiegająca przez wykonuj kroki K02…K04 ; kolejne liczby z <a,b> K02: Dla j = 0, 1, …, n - 1: ; pętla sprawdzająca podzielność wykonuj krok K03 ; przez dzielniki z P K03: Jeśli i mod P[j] = 0, ; jeśli jakiś dzielnik dzieli i, to następny obieg pętli K01 ; przechodzimy do następnej liczby K04: Pisz i ; jeśli żaden dzielnik nie dzieli i, wyprowadzamy je K05: Zakończ
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program spodziewa się w pierwszym wierszu liczb a i b. W drugim wierszu należy podać n = 1…1000, a następnie w n wierszach kolejne podzielniki (nie muszą być uporządkowane). |
Dane przykładowe (przekopiuj do schowka i
wklej do okna konsoli): -100 100 4 2 3 5 7 |
Pascal// Liczby niepodzielne // Data : 12.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- program prg; const MAXP = 1000; var a, b, i, j, n : longint; P : array [0..MAXP-1] of longint; t : boolean; begin readln(a, b); readln(n); for i := 0 to n - 1 do readln(P[i]); for i := a to b do begin t := true; for j := 0 to n - 1 do if i mod P[j] = 0 then begin t := false; break; end; if t then write (i,' '); end; writeln; end. |
// Liczby niepodzielne // Data : 12.03.2008 // (C)2020 mgr Jerzy Wałaszek //---------------------------- #include <iostream> using namespace std; const int MAXP = 1000; int main() { int a, b, i, j, n, P[MAXP]; bool t; cin >> a >> b >> n; for(i = 0; i < n; i++) cin >> P[i]; for(i = a; i <= b; i++) { t = true; for(j = 0; j < n; j++) if(i % P[j] == 0) { t = false; break; } if(t) cout << i << " "; } cout << endl; return 0; } |
Basic' Liczby niepodzielne ' Data : 12.03.2008 ' (C)2020 mgr Jerzy Wałaszek '---------------------------- Const MAXP = 1000 Dim As Integer a, b, i, j, n, P(MAXP), t Input a, b Input n For i = 0 To n - 1: Input P(i): Next For i = a To b t = 1 For j = 0 To n - 1 If i Mod P(j) = 0 Then t = 0 Exit For End If Next If t Then Print i;" "; Next Print End |
Python (dodatek)# Liczby niepodzielne # Data : 03.02.2024 # (C)2024 mgr Jerzy Wałaszek # ---------------------------- p = [] arr = input().split(" ") a = int(arr[0]) b = int(arr[1]) n = int(input()) for i in range(n): p.append(int(input())) for i in range(a, b + 1): t = True for j in range(n): if not (i % p[j]): t = False break if t: print(i, end=" ") print() |
Wynik: |
-100 100 4 2 3 5 7 -97 -89 -83 -79 -73 -71 -67 -61 -59 -53 -47 -43 -41 -37 -31 -29 -23 -19 -17 -13 -11 -1 1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.