Pomożecie zrobić taki program w Pythonie ?
Napisz program, który wyświetla największych 25 trzycyfrowych liczb naturalnych podzielnych przez 7 lub 9. Każda liczba powinna być wyświetlana w oddzielnej linii.
Napisałem coś takiego, ale to nie do końca jest to co chciałbym uzyskać. Jestem początkujący.
for x in range(100, 208):
if x % 7 == 0 or x % 9 == 0:
print(x)
No weź sobie xrange zamiast range żeby jechać od największej zamiast od najmniejszej. Oprócz tego pewnie chcesz zacząć od 999 zamiast 208 - nie wiem skąd Ci się to zrodziło. Warunek wygląda okej. No a jak wypisać w nowej linii to sobie przecież sprawdzisz.
Korzystam z wersji python 3, w dwójce jest xrange
No to sobie sprawdź jak zrobić range żeby iterować od większej do mniejszej.
Ewentualnie jakby Ci się nie chciało szukać to masz link: https://stackoverflow.com/questions/4294082/decreasing-for-loops-in-python-impossible
Coś w tym stylu:
numbers = [ x for x in range(999,99,-1) if x % 7 == 0 or x % 9 == 0][:25]
for number in numbers:
print(number)
Jeśli masz kłopoty z ogarnięciem "o co w tym biega", małe wyjaśnienie:
range(999,99,-1)
range w Pythonie ma postać (start, stop, step). Step, po polsku krok może być ujemny.
[ x for x in range(999,99,-1) if x % 7 == 0 or x % 9 == 0]
tzw. list comprehension (https://docs.python.org/3.6/tutorial/datastructures.html). Zastępuje kilka linii kodu jedną.
[:25]
Chyba wiadomo, tradycyjny slicing.
Jest też inna metoda. Robisz jak na początku (tylko z range (999,99,-1)), przed pętlą dodajesz zmienną, w której przechowujesz ilość wypisanych liczb (np. counter = 0), w pętli zwiększasz z każdym wypisanym x jej wartość o 1, a jak osiągnie 25 - wychodzisz z pętli.
Rozwiązanie powyższego kolegi jest jak najbardziej dobre i pythonowe, niemniej przy dużych zakresach, modulo (i pierwiastkowanie, tutaj akurat nie ma, ale tak na przyszłość) to jest coś czego należy unikać gdy zależy ci na prędkości.
Ja polecam trochę się zastanowić nad problemem i zrobić to 'metodą sito-podobną':
zakres_gorny = 208 #Jeśli chcesz wszystkie trzycyfrowe, to dajesz największą w zakresie - 999
zakres_dolny = 100
#Zbiory domyślnie są nieuporządkowane, ale póki ich nie złączymy, nie jest nam to potrzebne. Dodatkowo później wyeliminują nam duplikaty przy sumie zbiorów.
zbior1 = {iter*7 for iter in range(zakres_dolny//7, zakres_gorny//7)} # @Edit - błąd dałem //9 zamiast //7
#Podwójny slash dzieli bez reszty zmiennoprzecinkowej (też polecam unikać, ale w tym przypadku używamy tego 2 razy, nie za każdym razem w pętli.
zbior2 = {iter*9 for iter in range(zakres_dolny//9, zakres_gorny//9)}
lista = sorted( zbior1 | zbior2 )[-25:] #Zwraca nam posortowaną listę 25 największych elementów.
del zbior1; del zbior2;
print(lista) #Wyrzuca nam ostatnie 25 elementów
#A jeśli chcesz w osobnych liniach, to iteracja:
for item in lista:
print(item)
Oczywiście to przykład napisany na szybko, ale i tak powinien działać szybciej, pomimo sortowania.
Przy takim zakresie to niewiele zmieni, ale jakby zakres zawierał na przykład 10**6 elementów, już byłoby gorzej, ale wtedy przydałaby się dedykowana klasa przechowująca wartości typu bool ('array' lub 'bytearray') służąca za słownik posortowany :p. Wtedy mniej konwersji byłoby potrzebne, i pamięci tak dużo nie jadło :D.
@Edit - w kodzie zrobiłem błąd: dałem //9 zamiast //7 w zbiorze1
Oto szybkie, idiomatyczne rozwiązanie (szybsze od pozostałych oraz bardziej Pythonowe):
import itertools
def najwpodzielne(limit, p, q, count):
return list(itertools.islice(filter(lambda x: x%p == 0 or x%q == 0, range(limit, 0, -1)), 0, count))
W szczególności, nawet jeśli limit = 10**8888, rozwiązanie to wciąż działa błyskawicznie, w przeciwieństwie do dwóch pozostałych.
Poza tym, podejście Guaza ( @Guaz ) jest na tyle zbyteczne, że operuje na tak wielkich zbiorach (rzędu limit/p), podczas gdy tak naprawdę użycie zbiorów w tym zadaniu jest całkowicie niepotrzebne - w każdych kolejnych pq liczbach całkowitych (p i q są względnie pierwsze), dokładnie p+q-1 dzięki się przez jedno z nich. Wobec tego, poprawnym rozwiązaniem jest rozważyć jedynie zbiór {0, 1, ..., pq}, wyznaczyć w nim wielokrotności p lub q (np metodą [0] + sorted(list(range(p, p*q, p))+list(range(q,p*q,q))), następnie wybierać z tej kolekcji pierwsze count liczb, poczynając od limit (mod p*q), idąc w dół, pamiętając o cyklicznej strukturze tej listy. Nie da się osiągnąć lepszej złożoności, gdyż liczba operacji jest proporcjonalna do rozmiaru listy, którą należy utworzyć. (pomijam preprocessing), ale też można założyć że (p+q)*log(p+q), czyli czas sortowania jest sporo mniejszy niżcount).
def podzielnosc(gorny, i, j, count):
return sorted( {_ for _ in range(floor(gorny/i)*i, gorny-i*(count+1), -i)} |
{_ for _ in range(floor(gorny/j)*j, gorny-j*(count+1), -j)})[-count:]
Jedyne rozwiązanie bez itertools które udało mi się napisać o zbliżonej prędkości funkcji @enedil do zadanego problemu.
Przy dużej ilości elementów wybieranych (np. poniżej 999999, 150 elementów) albo dla dużych dzielnych (typu dzielone przez 33 lub 83) działa szybciej, jednak dla zadanej ilości elementów o małych dzielnikach zdecydowanie będzie lepsza funkcja napisana przez enedila :).
Oczywiście zarówno mój jak i enedila nie odfiltrują wartości poniżej dolnego zakresu - bo go tutaj nie ma, więc jeśli ktoś chce wszystko w zakresie podzielne przez jedną i drugą liczbę, nadal lekko zrefatoryzowane zbiory będą lepsze.
def podzielnosc(gorny, dolny, i, j):
return sorted( {_ for _ in range(floor(gorny/i)*i, dolny, -i)} |
{_ for _ in range(floor(gorny/j)*j, dolny, -j)})
Kombinacja dwóch powyższych, gdzie może wystąpić zarówno dolny zakres jak i ilość elementów:
def podzielnosc(gorny, dolny, i, j, ilosc):
return sorted( {_ for _ in range(floor(gorny/i)*i, max((gorny-i*(count+1), dolny)), -i)} |
{_ for _ in range(floor(gorny/j)*j, max((gorny-j*(count+1), dolny)), -j)})[-ilosc:]
Jeśli ktoś by potrzebował najszybszy sposób do zadanej ilości elementów, to najszybsza wersja jest w komentarzu pod postem enedila, to tylko zmiana warunków, ale to zajmuje najwięcej czasu w jego funkcji ;P. Dlatego z tą zmianą może się wykonać nawet kilkukrotnie nim wykona się którykolwiek z powyższych.
A na grzyba ten filter?
def najwpodzielne(limit, p, q, count):
return list(itertools.islice((x for x in range(limit, 0, -1) if not x%p or not x%q), 0, count))
1.7 x szybciej. Chociaż takie optymalizowanie Python'a to trochę dla sportu :)