|
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 |
©2026 mgr Jerzy Wałaszek
|
|
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 |
©2026 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.
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ć \({n = 1 \dots 1000}\), a następnie w trzecim wierszu jest \(n\) podzielników (nie muszą być uporządkowane). |
|
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.
|
C++// 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()) # zbędne w PY
p = input().split()
p = [int(i) for i in p]
# 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 |
JavaScript<html>
<head>
<title>
Liczby podzielne
</title>
</head>
<body>
<div style="overflow-x: auto;"
align="center">
<table
border="0"
cellpadding="4"
style="border-collapse:
collapse">
<tr>
<td nowrap>
<form
name="frm1"
style="text-align: center;
background-color:
#E7E7DA" class="nomargin">
<b><br>
Liczby podzielne</b><br/>
(C)2026 mgr Jerzy Wałaszek
<hr>
<table border="0"
cellpadding="4"
style="border-collapse:
collapse">
<tr>
<td style="text-align:
right">
a =
</td>
<td>
<input
type="text"
name="inp_a"
size="16"
value="-100"
style="text-align:
right">
</td>
</tr>
<tr>
<td style="text-align:
right">
b =
</td>
<td>
<input
type="text"
name="inp_b"
size="16"
value="100"
style="text-align:
right">
</td>
</tr>
<tr>
<td style="text-align:
right">
dzielniki =
</td>
<td>
<input
type="text"
name="inp_d"
size="16"
value="5 12 17"
style="text-align:
right">
</td>
</tr>
</table>
<hr>
<input
type="button"
value="Wykonaj"
name="B3"
onclick="main1()">
<hr>
<b>Wynik:</b>
<div id="out1">.</div>
</form>
</td>
</tr>
</table>
</div>
<script type=text/javascript
language=javascript>
// Liczby podzielne
// Data : 11.03.2008
// (C)2008 mgr Jerzy Wałaszek
//----------------------------
function main1()
{
var a, b, c, i, j, n, t, s, x;
var P = new Array(1000);
a = parseInt(document
.frm1.inp_a.value, 10);
b = parseInt(document
.frm1.inp_b.value, 10);
c = 0;
s = document.frm1.inp_d.value;
s = s.split(' ');
if(s.length>0)
{
n = 0;
for(i = 0; i < s.length; i++)
{
x = parseInt (s[i]);
if(!isNaN (x))
P[n++] = x;
}
if(n)
{
t = "";
for(i = a; i <= b; i++)
for(j = 0; j < n; j++)
if(i % P[j] == 0)
{
t += i+" ";
c++;
if(c == 10)
{
c = 0;
t += "<br>";
}
break;
}
}
else
t = "Złe podzielniki!";
}
else
t = "Brak podzielników!";
document.getElementById("out1")
.innerHTML = t;
}
</script>
</body>
</html>
|
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.
