• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Modulo z dużą liczbą pierwsza

VPS Starter Arubacloud
+1 głos
295 wizyt
pytanie zadane 20 października 2018 w C i C++ przez detmold Nowicjusz (180 p.)

W tutoriale na temat programowania dynamicznego natknąłem się na jedną niezrozumiała i intrygującą rzecz, może przekopuje że zrodla 

#define MOD 1000000007
​​​​​​Grid[i][j] = (Grid[i][j] + Grid[i-1][j] + MOD)%MOD;

Pytanie brzmi dlaczego tam jest to modulo i co to daje. Link do źródła z całym kodem 

https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/tutorial/

1 odpowiedź

0 głosów
odpowiedź 23 października 2018 przez Noak Mądrala (5,900 p.)
W zadaniach algorytmiczny często proszą o podanie wyniku modulo "jakaś wartość" w przypadku gdy trzeba coś zliczyć. Wynika to z tego, że aby sprawdzić poprawność algorytmu i jego złożoność problemu są duże, a co za tym idzie wyniki też. Dlatego aby nie przepełnić zmiennych stosuje się modulo co zapobiega przepełnieniom.
komentarz 28 października 2018 przez detmold Nowicjusz (180 p.)
dziękuję za odpowiedź, faktycznie ma to sens ale jeszcze jedno nie daje mi spokoju.

Mianowicie w tym zadaniu liczona jest liczba możliwych ścieżek z pozycji (1,1) do pozycji (n.m) przy załozeniu, ze niektóre komórki są zblowkowane. No i teraz jeśli ktoś poda na wejściu liczby wykraczające poza zakres i program zrobi na nich tą operację modulo to jak na moje w wyniku dostanie niepoprawny wynik. Więc jaka jest przewaga tego rozwiązania nad przepełnieniem zmiennych ? W obydwu przypadkach wynik będzie niepoprawny.
komentarz 12 listopada 2018 przez Noak Mądrala (5,900 p.)
Nigdy nie będzie sytuacji, w takich zadaniach, w której na wejściu będą dane przekraczające zakres (chodzi mi o przypadek gdy n,m już wychodzą poza zakres). Dla poprawnie podanych danych wejściowych może zajść sytuacja, w której podczas obliczeń ten zakres zostanie przekroczony. W takim przypadku dostaniemy niepoprawny wynik(gdy tak jak napisałeś wykroczymy poza zakres zmiennych i wykonamy modulo). Dlatego trzeba tak wykorzystywać modulo aby nie dopuścić do tego przepełnienia.

Podobne pytania

0 głosów
0 odpowiedzi 242 wizyt
pytanie zadane 2 kwietnia 2022 w C i C++ przez Krzysztofs1234 Użytkownik (890 p.)
+2 głosów
2 odpowiedzi 382 wizyt
pytanie zadane 19 września 2021 w JavaScript przez Doge Gaduła (3,320 p.)
0 głosów
1 odpowiedź 178 wizyt
pytanie zadane 2 lipca 2020 w Inne języki przez krzysiek852 Nowicjusz (170 p.)

92,454 zapytań

141,262 odpowiedzi

319,090 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...