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.
Algorytm wyznaczania liczb
podzielnych przez zadane czynniki
Wejście:
a : początek przedziału; a ∈ C.
b : koniec przedziału; b ∈ C,
a < b.
n : liczba podzielników; n ∈ N.
P : tablica, której kolejne elementy są podzielnikami;
P[i] ∈ C;
i = 0, 1, …, n - 1.
Wyjście:
Kolejne liczby z przedziału <a, b> podzielne przez
jeden z podzielników w P.
Elementy pomocnicze:
i : przebiega przez kolejne liczby w przedziale
<a, b>;
i ∈ C.
j : przebiega przez numery kolejnych podzielników
w P; j ∈ N.
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
Przykładowe programy
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 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;
} |
Basic
Const 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
|
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.
Algorytm wyznaczania liczb podzielnych przez zadane
czynniki
Wejście:
a : początek przedziału, a ∈ C.
b : koniec przedziału, b ∈ C.
n : liczba podzielników, n ∈ N.
P : tablica, której kolejne elementy są podzielnikami.
P[i] ∈ C;
i = 0, 1, …, n-1.
Numeracja elementów od zera.
Wyjście:
Kolejne liczby z przedziału <a, b> podzielne
przez jeden z podzielników w P.
Elementy pomocnicze:
i : przebiega przez indeksy podzielników w P; i ∈ C.
s : liczba przesłana na wyjście; s ∈ C.
minv : minimalna wartość wielokrotności podzielników
z P;
minv ∈ C.
V : tablica wielokrotności podzielników. Elementy ∈ C.
Numeracja elementów od zera zgodna z numeracją P.
MAXZ : największa wartość całkowita.
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.
Przykładowe programy
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
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. |
C++
// 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()
|
