Biorąc pod uwagę dużą liczbę pozytywną maksymalnie 1000 cyfr. Musisz dowiedzieć się, czy liczba jest podzielna przez 17, czy nie. Znam algorytm, który mówi, pomnóż ostatnią cyfrę przez 5 i odejmij od pozostałej liczby, jeśli wynikowa liczba jest podzielna przez 17, wtedy liczba jest podzielna przez 17. Czy istnieje bardziej skuteczna metoda?podzielny przez 17?
Co można zrobić, jest iteracyjne ciągu cyfr, śledzenie bieżącej wartości Modulo 17. Gdy dojdziesz do końca, jeśli aktualna wartość modulo 17 wynosi zero, to jest wielokrotnością 17; inaczej, nie.
Na przykład, jeśli liczba jest "12345" (? Zakładam, że masz ten numer zapisany na sznurku po przecinku), a następnie kroki są:
0(0 * 10 + 1) mod 17 → 1(1 * 10 + 2) mod 17 → 12(12 * 10 + 3) mod 17 → 4(4 * 10 + 4) mod 17 → 10(10 * 10 + 5) mod 17 → 3tak 12345 mod 17 jest 3: 12345 nie jest podzielna przez 17.
(Oczywiście, z 12345 można po prostu napisać 12345 mod 17 na początek, ale z dużą liczbą, powyższe podejście pozwala nam przetwarzać tylko trochę na raz, co jest wygodne, ponieważ oznacza to, że wszystkie nasze liczby są małe na tyle, aby zmieścić natywne 32- lub 64-bitowe procesory.)
Biorąc pod uwagę, że mówimy tutaj o programach komputerowych, wykonanie maksymalnie 1000 iteracji prostego algorytmu jest dość szybkie.
To prawda, jeśli każda iteracja to O (1); ale jeśli dobrze rozumiem OP, myślę, że każda iteracja to O (n). – ruakh
Jak wskazuje ruakh, każda iteracja będzie się zmniejszać w czasie działania w przybliżeniu liniowo, co oznacza, że pełne 1000 iteracji będzie zbliżone do O (N^2) w czasie pracy. – Seph
Odejmowanie dwucyfrowej liczby od N-cyfrowej nie jest O (N) w przeciętnym przypadku. Oczywiście podejście do ruaków jest jeszcze lepsze. –
Inny wariant. 10 to -1 mod 17.
Weź więc pierwsze 8 cyfr, zamień na liczbę, a% 17, aby uzyskać pozostałą modę 17. Następnie powtórz z następnymi 8 cyframi, z wyjątkiem tego, że odejmujesz liczbę czas. Następnie dodaj kolejne 8 cyfr, itd.
Powoduje to mniejszą liczbę konwersji łańcuchowych-> liczbowych i mniej operacji mod 17.
To prawda, że będzie to wymagać mniejszej liczby operacji mod-17, ale tak naprawdę nie jest prawdą, że będzie wymagało mniejszej liczby konwersji ciągów do liczb: oba wymagają konwersji każdej cyfry z postaci znakowej do postaci całkowitej, dokładnie jeden raz, i oba obejmują taka sama liczba mnożeń przez 10. Nie musisz też brać "pierwszych 8 cyfr", chyba że liczba jest dokładnie 8 \ * n cyfr dla pewnej liczby całkowitej * n *. Na przykład, jeśli liczba ma 21 cyfr, musisz zacząć od pierwszych 5 cyfr, a następnie 8 kolejnych, a następnie 8 ostatnich. – ruakh
@ruakh przez "pierwsze 8" Miałem na myśli "ostatnie 8". Myślałem o tym jako o liczbie, a nie o łańcuchu. Mój błąd. – btilly
Ach, to ma więcej sensu. Nie mogłem już wcześniej wyliczyć, co rozumiesz przez "odjąć numer tym razem", ale teraz widzę. :-) – ruakh
Przestań się martwić o "bardziej skuteczną metodę". ** Wdrożenie ** tego, co wiesz, jak to zrobić, a następnie ** zmierzyć ** czy jest wystarczająco wydajny. –
To brzmi dla mnie bardzo wydajnie ... pojedyncze operacje odejmowania i mnożenia/modowania na liczbach o długości zaledwie kilku cyfr brzmią bardzo szybko. – hackartist
O ile nie pominę czegoś w opisie algorytmu, nie zawsze będzie działać. Spróbuj na przykład na 34. –