Jak powinienem zoptymalizować ten kod?

Odpowiedz Nowy wątek
2019-04-25 15:53
0

Napisałem dobrze działający, ale wydaje mi się że niezbyt dobry kod więc proszę o poradę jak mógłbym go ulepszyć, z góry przepraszam za rozmiar.

Zadanie 2 (20 punktów diament AGH)Liczbę pierwszą będącą palindromem nazywamy “palindromem pierwszym”. Liczbę nazywamy “super palindromem pierwszym” jeżeli podczas odrzucania parami skrajnych cyfr, do końca pozostaje ona palindromem pierwszym. Na przykład, liczba 373929373 jest super-palidromem pierwszym bo 373929373, 7392937, 39293, 929, 2 są palindromami pierwszymi. Początkowymi super palindromami pierwszymi są: 2, 3, 5, 7, 11, 131, 151. Proszę napisać program, który wylicza ile jest super palindromów pierwszych mniejszych od zadanej liczby n.
Wejście: Wpisz jedna liczbę naturalną n.
Wyjście: program powinien wypisać jedną liczbę będącą rozwiązaniem.
Przykład: Dla danych wejściowych: 200 -poprawną odpowiedzią jest: 7.

public class Main {
public static void main(String[] args) {
//wczytanie liczby
Scanner s = new Scanner(System.in);
int n = s.nextInt();

    int pal=0;
    for(int i=2; i<n; i++) {
        pal = zwiekszLiczbePal(i, pal);
    }
    System.out.println("Liczba super-palindromów to: "+pal);
}
private static int zwiekszLiczbePal(int i, int pal){
    int copy = i;
    while (czyLp(i) && czyPal(i) && i > 11) {
        int dlugosc = dl(i);
        i = oddziel(i, dlugosc);
    }

    if (i <= 11 && czyLp(i) && i!=0) {
        //dla sprawdzenia - System.out.println(copy);
    return pal+1;
    }
    return pal;
}
//oddziela indeksy np. 3253 == 25
private static int oddziel(int x, int size){
    int[] liczba = new int[size];
    int rev=0;
    for(int y=0; y<size; y++) {
        liczba[y] = x % 10;
        x /= 10;
    }

        for (int i = size-2; i >=1; i--) {
            rev = rev * 10 + liczba[i];
        }
        return rev;
    }

    //czy liczba pierwsza
 private static boolean czyLp(int x){
    for(int i=2; i*i<=x; i++){
        if(x%i==0)return false;
    }
    return true;
}

//czy palindrom
private static boolean czyPal(int x){
    int copy = x, rev=0;
    while(x>0){
        rev = rev*10 + x % 10;
        x/=10;
    }
    return rev == copy;
}

//oblicza dlugosc liczby
 private static int dl(int x){
    int counter=0;
    while(x>0){
        x/=10;
        counter++;
    }
    return counter;
}

}

Pozostało 580 znaków

2019-04-25 17:01
1

Po 1, na przyszłość zwróć uwagę na formatowanie kodu.
Po 2, na przyszłość daj jakieś normalne tagi i temat...
Po 3, rozwiązanie optymalne, ztablicowane odpowiedzi:

    public static Integer superPalindromeAmount(int max) {
        int[] superPalindromes = 
                {
                        2, 3, 5, 7, 
                        11, 
                        131, 151, 353, 373, 727, 757, 929, 
                        11311, 31513, 33533, 37273, 37573, 39293, 71317, 93739, 97579, 
                        1335331, 3315133, 3392933, 7392937, 9375739, 
                        373929373, 733929337
                };
        return IntStream
                .of(superPalindromes)
                .filter(i -> i < max)
                .boxed()
                .collect(Collectors.toList())
                .size();
    }

Po 4, jak dojść do tego rozwiązania? Otóż bierzesz wszystkie superpalindromy pierwsze o zadanej długości (wychodzisz od znanych o długości 1 i 2) i patrzysz czy jak dodasz z przodu i z tyłu taką samą nieparzystą cyfrę to czy powstanie liczba pierwsza:

    IntStream
        .range(1, 100)
        .boxed()
        .flatMap(i -> calculateSuperPalindromes(i).stream())
        .sorted(BigInteger::compareTo)
        .collect(Collectors.toList())

    public static List<BigInteger> calculateSuperPalindromes(Integer n) {
        if(n == 1) {
            return Arrays.asList(new BigInteger("2"),new BigInteger("3"),new BigInteger("5"),new BigInteger("7"));
        } else if(n == 2) {
            return Arrays.asList(new BigInteger("11"));
        } else {
            return calculateSuperPalindromes(n - 2)
                    .stream()
                    .flatMap(i -> Stream.of("1","3","5","7","9")
                            .map(s -> s + i.toString() + s)
                            .map(BigInteger::new))
                    .filter(bi -> bi.isProbablePrime(1))
                    .collect(Collectors.toList());
        }
    }

Po 5, ty na siłe po kolei sprawdzasz wszystkie liczby, czy są palindromami i czy są pierwsze, to jest mega nieoptymalne. Kluczem do optymalnego podejścia które dałem w pkt 4 jest zauważenie że wszystkie palindromy o długości np. 8 możemy znaleźć wychodząc od palindromów o długości 6 i dodająć z przodu i z tylu tą samą cyfre i sprawdzając czy jest pierwsza. Zauważ że w moim programie nigdzie nie sprawdzam czy liczba jest palindromem, bo zamiast tego sam konstruuje liczby które wiem że są palindromami.

W skrócie twoje rozwiązanie jest nieoptymalne bo działa w czasie O(N) gdzie N jest liczbą która sprawdzasz, moje rozwiązanie z pkt 4 działa w złożoności O(log(n)) ponieważ jest zależne od długości liczby N. A rozwiązanie z pkt 3 działa w złożoności N(1) bo ztablicowałem wszystkie odpowiedzi. (Dla uproszczenia obliczania złożoności zakładam że sprawdzenie czy liczba jest pierwsza odbywa się w czasie stałym)

edytowany 4x, ostatnio: Noozen, 2019-04-25 17:19
Btw, amount jest do rzeczowników niepoliczalnych (np. amount of water) - powinieneś mieć count. - Patryk27 2019-04-25 18:12

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0