python - zbiór zadań cke zad. 59.1

Question

Mam problem z zadaniem:

Sprawdziłem treść i odpowiedź kilka razy i mimo wszystko wychodzi mi zły wynik, ma być 144, a wychodzi 47.

Poniżej zamieszczam kod, proszę o pomoc, bo nie mam pojęcia czy błąd jest w rozumowaniu czy w którymś warunku.

import math


def Rozklad(liczba):
    k = 2
    czynniki = []
    # rozklad na czynniki pierwsze
    while (k < round(math.sqrt(liczba))):
        if liczba % k == 0:
            # jezeli czynnik jest nieparzysty to go dodajemy do listy
            if k % 2 == 1:
                czynniki.append(k)
            # w przeciwnym wypadku funkcja zwraca falsz
            else:
                return False
            liczba /= k
        else:
            k += 1
    # skoro maja byc 3 rozne czynniki to sprawdzamy to poprzez utowrzenie zbioru
    czynniki2 = set(czynniki)
    if len(czynniki2) == 3:
        return True


wynik = 0
with open("liczby.txt") as file:
    liczby = file.read().splitlines()
    for liczba in liczby:
        liczba = int(liczba)
        if Rozklad(liczba):
            wynik += 1
    print(wynik)

 

Answer 1

Twój pomysł jest z grubsza dobry, ale pomija jeden szczegół. Nie uwzględniasz przypadku, gdy liczba którą rozkładasz ma czynnik pierwszy większy od jej pierwiastka.

Np. dla liczby 105 Twój program sprawdzi, że dzieli się przez 3 i po podzieleniu zostanie Ci 35. Potem wyjdzie, że 35 dzieli się przez 5 i zostanie 7. I teraz będziesz sprawdzał czy 6 dzieli 7, ale 6 jest większe od pierwiastka z 7, więc pętla się zakończy. No i wyszło na to, że pominęliśmy 7.

Tak wygląda poprawny kod:

import math
 
def Rozklad(liczba):
    k = 2
    czynniki = []
    # rozklad na czynniki pierwsze
    while (k * k <= liczba):
        if liczba % k == 0:
            # jezeli czynnik jest nieparzysty to go dodajemy do listy
            if k % 2 == 1:
                czynniki.append(k)
            # w przeciwnym wypadku funkcja zwraca falsz
            else:
                return False
            liczba /= k
        else:
            k += 1

    if liczba > 1:
        czynniki.append(liczba)
    # skoro maja byc 3 rozne czynniki to sprawdzamy to poprzez utowrzenie zbioru
    czynniki2 = set(czynniki)
    if len(czynniki2) == 3:
        return True

    else:
        return False
 
 
wynik = 0
with open("liczby.txt") as file:
    liczby = file.read().splitlines()
    for liczba in liczby:
        liczba = int(liczba)
        if Rozklad(liczba):
            wynik += 1
    print(wynik)

Dodatkowo zmieniłem warunek w pętli na k*k <= liczba, żeby uniknąć działania na liczbach zmiennoprzecinkowych.

Comments

Jeżeli mogę zapytać, czemu nigdzie nie jest wspomniane o tek kwestii? Też robiłem to zadanie i miałem tą samą sytuację co autor.

Gdy wynik nie był poprawny popatrzyłem jeszcze na implementacje rozkładu na czynniki np: http://www.algorytm.edu.pl/algorytmy-maturalne/rozklad-na-czynniki.html czy https://eduinf.waw.pl/inf/utils/010_2010/0212.php . Wynik dalej był ten sam czyli jakby nie uwzględniał wymienionej przez Ciebie sytuacji. Mógłbyś mi to jakoś wyjaśnić - bo trochę mi się zrobił mętlik w głowie od tego :)

---

Wydaje mi się, że algorytmy, które podałeś są poprawnie zaimplementowane. Więc albo gdzieś indziej masz błąd w kodzie, albo ewentualnie błąd mozę wynikać z tego, że te algorytmy korzystają z sqrt(). Ogólnie lepiej unikać liczb zmiennoprzecinkowych więc zamiast:

x = sqrt(n)
while(n > 1 && k <= x)

ja bym napisał:

x = n
while(n > 1 && k*k <= x)

---

To ja może w takim razie wstawię swój kod. Każdy krok starałem się opisać tak jak ja to rozumiem. Zauważyłem że po wykonaniu głównej pętli niektóre liczby są większe niż 1, nie za bardzo mam pojęcie czemu tak się dzieje. Jeśli chodzi o wynik końcowy to otrzymuję 53, jeśli na końcu dodam warunek 

if liczba > 1:
    czynnik_licz += 1

wynik końcowy jest bliski poprawnemu - otrzymuję 113 a w wynikach jest 114

def czynniki(liczba):
    #stworz kopie liczby do warunku w petli
    kopia = liczba
    #ustaw czynnik na 2
    czynnik = 2
    #zainicjuj liczbe roznych czynnikow jako 0
    czynnik_licz = 0

    while liczba > 1 and czynnik*czynnik <= kopia:
        # jezeli liczba jest podzielna przez czynnik
        if liczba % czynnik == 0:
            #jezeli czynnik parzysty to nie spelnia warunkow zwracaj False
            if czynnik % 2 == 0:
                return False
            #dopoki liczba jest podzielna przez czynnik dziel ja przez czynnik
            while liczba % czynnik == 0:
                liczba = int(liczba / czynnik)
            #jezeli czynnik spelnil warunki dodaj go do liczby czynnikow
            czynnik_licz += 1
        #zwieksz czynnik o 1
        czynnik += 1

    #jezeli liczba roznych czynnikow to 3 zwroc True
    if czynnik_licz == 3:
        return True
    return False

 

---

A to dziwne, bo uruchomiłem Twój program dodałem to:

if liczba > 1:
    czynnik_licz += 1

i wychodzi mi 114. Tu jest kod:

def czynniki(liczba):
    #stworz kopie liczby do warunku w petli
    kopia = liczba
    #ustaw czynnik na 2
    czynnik = 2
    #zainicjuj liczbe roznych czynnikow jako 0
    czynnik_licz = 0
 
    while liczba > 1 and czynnik*czynnik <= kopia:
        # jezeli liczba jest podzielna przez czynnik
        if liczba % czynnik == 0:
            #jezeli czynnik parzysty to nie spelnia warunkow zwracaj False
            if czynnik % 2 == 0:
                return False
            #dopoki liczba jest podzielna przez czynnik dziel ja przez czynnik
            while liczba % czynnik == 0:
                liczba = int(liczba / czynnik)
            #jezeli czynnik spelnil warunki dodaj go do liczby czynnikow
            czynnik_licz += 1
        #zwieksz czynnik o 1
        czynnik += 1

    if liczba > 1:
        czynnik_licz += 1
 
    #jezeli liczba roznych czynnikow to 3 zwroc True
    if czynnik_licz == 3:
        return True
    return False

f = open("liczby.txt")
res = 0

for line in f:
    if czynniki(int(line)):
        res+=1

print(res)

---

Pobrałem dane od nowa, teraz się zgadza. Jednak dalej nurtuje mnie ta sprawa czemu muszę dodać ten warunek 

 if liczba > 1:
        czynnik_licz += 1

skoro jeśli w głównej pętli powinienem dojść do 1. Wygląda na to że brakuje dzielenia, tylko gdzie? Bo o ile dobrze rozumiem algorytmy podane wyżej przeze mnie również uwzględniają warunek że liczba może mieć czynnik większy od jej pierwiastka

---

To brakujące dzielenie w głównej pętli wynika z tego, że w tej pętli przeglądasz tylko dzielniki od 2 do sqrt(n). A skoro liczba może mieć co najwyżej jeden dzielnik większy od sqrt(n) to musisz sprawdzić if'em czy ten dzielnik tam jest.

W pierwszym algorytmie tutaj: http://www.algorytm.edu.pl/algorytmy-maturalne/rozklad-na-czynniki.html nie ma tego dodatkowego if'a bo nie jest potrzebny. Tam petla przechodzi po wszystkich dzielnikach. Natomiast w tych pozostałych kodach ten if już jest

---

Dzięki za poświęcony czas, teraz wszystko rozumiem, wszystkie moje wątpliwości zostały rozwiane 

Answer 2

Twój kod w części rozkładania na czynniki pierwsze nie uwzględnia, że 2 również może być dzielnikiem.  Według kodu do listy dzielników dołączane są tylko liczby nieparzyste. Kod ma też problemy z wyliczaniem ostatniego dzielnika.

Można to rozwiązać np tak (tylko fragment funkcji 'Rozklad' - petla while, reszta tzn. zmienne, tworzenie seta i końcowy id zostało):

    while (liczba>1 and k <= math.sqrt(liczba)):
        while(liczba%k == 0):
            czynniki.append(k)
            liczba /= k
        k +=1
    if liczba>1:
        czynniki.append(liczba)

sprawdzać dopóki liczba jest większa od 1 i aktualnie sprawdzany dzielnik jest mniejszy od pierwiastka z tej liczby. Drugi warunek ogranicza sprawdzanie zakresu - wiadomo, że dzielnik nie będzie większy od pierwiastka z liczby. Póżniej sprawdzanie w pętki kolejnych dzielników tzn sprawdzanie dla 2 jeżeli da się podzielić bez reszty to dzielisz i po podzieleniu przez 2 znowu sprawdzasz czy nadal jest podzielna jeżeli tak, to znowu powtarzasz dla 2 i robisz to dopóki dzielenie jest możliwe, jeżeli nie jest przechodzisz do następnej liczby. Jeżeli po tej operacji tzn zakończeniu pętli liczba nie bedzie 1 to ją dodajesz jako ostatni dzielnik.

Comments

Tylko że nie ma sensu uwzględniać dwójek, gdyż w zadaniu chodziło o znalezienie liczb, które posiadają 3 nieparzyste czynniki pierwsze. Autor pytania miał całkiem dobry pomysł, aby od razu zwracać False, gdy znajdzie jakąkolwiek dwójkę w rozkładzie.

---

Masz racje - zasugerowałem, się tym, że w tabelce 2 są wypisane, mój błąd.