[bordeaux]

Czy ktoś może mi w łopatologiczny sposób wytłumaczyć dlaczego to działa? Metoda oblicza resztę z dzielenia liczby s (w zapisie dwójkowym) przez p:

 public static int reszta(String s, int p) {
 int result = 0;
 for (int i = 0; i < s.length(); i++) {
 int cyfra = s.charAt(i) - '0';
 result = (result*2 + cyfra) % p;
 }
 return result;
 }

#programowanie #algorytmy #matematyka #matura z informatyki ( ͡° ʖ̯ ͡°)

[Pablo_Dlugosz-00]

@bordeaux: o jezu co

[wytrzzeszcz]

@bordeaux: wyglada jak dzielenie w slupku

[heheherbatnik]

@bordeaux: bosze, nie używaj polskich nazw dla zmiennych ( ͡° ʖ̯ ͡°)

[bordeaux]

@heheherbatnik: Skopiowałem z informatora, parę godzin przed maturą nazewnictwo zmiennych to ostatnia rzecz na którą zwracam uwagę XD

[kosa1410]

@bordeaux: mam wrażenie że dodaje kolejne reszty z dzielenia (z poprzedniego kroku + reszta z liczby z danej pozycji) co krok.

[deryt]

@bordeaux:
Po pierwsze funkcję length() wywołujesz mnóstwo razy. Przesuń przed pętlę (w dodatkowej zmiennej) bo to nieoptymalne.

Więc cały ten kod który wkleiłeś bez " % p"...
Jak się przyjrzysz dokładnie, to jest to zamiana liczby na system dziesiętny.

I w tej pętli dodajemy " % p", czyli wszystko robimy modulo p.
(Dzięki temu result nie wychodzi poza p, czyli działamy na małych liczbach, czyli jest sprytne.)
I już.

[WhirPool]

@bordeaux: Kod rozumiem, ale dlaczego ten algorytm faktycznie podaje dobre wartości nie mam pojęcia. Siedziałem nad tym 20 min i nic. Podejrzewam, że jest gdzieś dowód matematyczny do tego, ale już nie chce mi się szukać bo wystarczająco dużo czasu straciłem :D

[bordeaux]

@WhirPool: Już wiem. Schemat Hornera, kolejne cyfry to współczynniki w wielomianie (1/0)x^n+(1/0)n^(n-1)+..., gdzie x = 2

[WhirPool]

@bordeaux: Dzięki ;)