ile jest liczb co m-nty i n-ty krok

[Ox16]

Mam określoną ilość liczb \(\displaystyle{ 0..k}\)
ile może byc liczb ktore sa podzielne przez \(\displaystyle{ m}\) i \(\displaystyle{ n}\).

Próbowałem znaleźć jakiś algorytm kiedy będą się powtarzac odleglosci pomiedzy wykreslanymi liczbami, ale poległem.

przyklad:
\(\displaystyle{ m=3, n=5, k}\) powiedzmy \(\displaystyle{ 50}\)
wynik \(\displaystyle{ 23}\)
odleglosci to
\(\displaystyle{ 3\ 2\ 1\ 3\ 1\ 2\ 3\ |\ 3\ 2\ 1\ 3\ 1\ 2\ 3\ |\ 3\ 2\ 1\ 3\ 1\ 2\ 3\ |\ 3\ 2}\)
czy istnieje jakiś sposób by wyznaczyc po jakim czasie szablon bedzie się powtarzać?

[kropka+]

Algorytm nie jest tu potrzebny a wynik dla \(\displaystyle{ k=50}\) to \(\displaystyle{ 24}\) (bo zero jest podzielne przez każdą liczbę). Jeśli dobrze zrozumiałam, to masz po kolei \(\displaystyle{ k+1}\) liczb całkowitych: \(\displaystyle{ 0,1,2,3,...,k}\) i chcesz wiedzieć ile spośród tych liczb jest podzielnych przez \(\displaystyle{ m}\) lub \(\displaystyle{ n}\).
Jest ich

\(\displaystyle{ \left[ \frac{k}{m} \right] +\left[ \frac{k}{n} \right] -\left[ \frac{k}{m \cdot n} \right] +1}\)

gdzie \(\displaystyle{ \left[ a \right]}\) oznacza część całkowitą liczby \(\displaystyle{ a}\)
W naszym przykładzie

\(\displaystyle{ \left[ \frac{50}{3} \right] +\left[ \frac{50}{5} \right] -\left[ \frac{50}{3 \cdot 5} \right] +1=16+10-3+1=24}\)

[Ox16]

Algorytm nie jest tu potrzebny...

\(\displaystyle{ \left[ \frac{k}{m} \right] +\left[ \frac{k}{n} \right] -\left[ \frac{k}{m \cdot n} \right] +1}\)

Dobrze zrozumiałaś przykład.
Choć mi wyszło \(\displaystyle{ 24}\) (ja zapomniałem o zerze )
\(\displaystyle{ 0\ 3\ 5\ 6\ 9\ 10\ 12\ 15\ 18\ 20\ 21\ 24\ 25\ 27\ 30\ 33\ 35\ 36\ 39\ 40\ 42\ 45\ 48\ 50}\)

dla jasnosci:

Kod: Zaznacz cały

#!/usr/bin/env ruby
# encoding: utf-8
i = 0
51.times {|k|
if ((k % 3) == 0) || ((k % 5) == 0) then
 print "#{k} " ; i+=1
end }
puts ; puts i

lub prościej pomińmy zero

Kod: Zaznacz cały

#!/usr/bin/env ruby
k = 50; m = 3; n = 6
puts (1..k).select {|j| ((j % m) == 0) || ((j % n) == 0) }.size

a co będzie jeśli to będzie \(\displaystyle{ m=3, n = 6}\) ? Twój sposób się załamie.

Dlaczego dodajesz \(\displaystyle{ 1}\)? A jak bede miał wiecej zmiennych \(\displaystyle{ m,n,o...}\) to mam dużo kombinacji.

[kropka+]

a co będzie jeśli to będzie \(\displaystyle{ m=3, n = 6}\) ? Twój sposób się załamie.

Dlaczego dodajesz \(\displaystyle{ 1}\)? A jak bede miał wiecej zmiennych \(\displaystyle{ m,n,o...}\) to mam dużo kombinacji.

Masz rację, zamiast \(\displaystyle{ m \cdot n}\) powinna być najmniejsza wspólna wielokrotność \(\displaystyle{ NWW(m,n)}\), czyli

\(\displaystyle{ \left[ \frac{k}{m} \right] +\left[ \frac{k}{n} \right] -\left[ \frac{k}{NWW(m,n)} \right] +1}\)

Dodaję 1, bo uwzględniam, że zero też jest podzielne.
Dla większej liczby dzielników poczytaj o zasadzie włączeń i wyłączeń.