Witam wszystkich.
Jak w tytule, zmagam się z zadaniem wyznaczenia sumy \(\displaystyle{ n}\) kolejnych cyfr po przecinku rozwinięcia dziesiętnego liczby \(\displaystyle{ \sqrt{m} }\).
Jest to 3 zadanie z konkursu "O Diamentowy Indeks AGH 2018/19".
Będę wdzięczny za wszelkie podpowiedzi jak do tego podejść - problem gubienia dokładności w C++ wydaje mi się nie do obejścia
suma n cyfr po przecinku pierwiastka z m
-
- Użytkownik
- Posty: 7
- Rejestracja: 14 gru 2020, o 17:51
- Płeć: Kobieta
- wiek: 17
- Lokalizacja: Paraguay
suma n cyfr po przecinku pierwiastka z m
Ostatnio zmieniony 20 kwie 2022, o 20:52 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
- Użytkownik
- Posty: 7
- Rejestracja: 14 gru 2020, o 17:51
- Płeć: Kobieta
- wiek: 17
- Lokalizacja: Paraguay
Re: suma n cyfr po przecinku pierwiastka z m
Załóżmy że musimy obliczyć 100 cyfr po przecinku liczby \(\displaystyle{ \sqrt{2} }\) i mamy ich już 99.
Nazwijmy upragnioną cyfrę \(\displaystyle{ x}\).
Korzystając z wymienionego wyżej algorytmu:
\(\displaystyle{ c \ge (20p + x) \cdot x}\)
wszystko super, tyle że \(\displaystyle{ p = \sqrt{2} \cdot 10 ^{99} }\)
Zarówno \(\displaystyle{ c}\), jak i \(\displaystyle{ p}\) są o wiele za duże żeby przechować je w jakiejkolwiek zmiennej liczbowej.
Nie istnieje żaden sposób wyznaczania pierwiastka, który pozwalałby "zapomnieć" wcześniejsze cyfry, lub przynajmniej je skompresować?
Ps.: Można zapisać te liczby jako string i wykonywać wszystkie operacje matematyczne ręcznie ale mam nadzieje że istnieje prostsze rozwiązanie.
Nazwijmy upragnioną cyfrę \(\displaystyle{ x}\).
Korzystając z wymienionego wyżej algorytmu:
\(\displaystyle{ c \ge (20p + x) \cdot x}\)
wszystko super, tyle że \(\displaystyle{ p = \sqrt{2} \cdot 10 ^{99} }\)
Zarówno \(\displaystyle{ c}\), jak i \(\displaystyle{ p}\) są o wiele za duże żeby przechować je w jakiejkolwiek zmiennej liczbowej.
Nie istnieje żaden sposób wyznaczania pierwiastka, który pozwalałby "zapomnieć" wcześniejsze cyfry, lub przynajmniej je skompresować?
Ps.: Można zapisać te liczby jako string i wykonywać wszystkie operacje matematyczne ręcznie ale mam nadzieje że istnieje prostsze rozwiązanie.
Ostatnio zmieniony 21 kwie 2022, o 18:55 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Symbol mnożenia to \cdot.
Powód: Symbol mnożenia to \cdot.
-
- Użytkownik
- Posty: 128
- Rejestracja: 5 lip 2015, o 14:48
- Płeć: Mężczyzna
- Lokalizacja: nie wiem
- Podziękował: 11 razy
- Pomógł: 24 razy
Re: suma n cyfr po przecinku pierwiastka z m
A czy autorzy raczyli podać jakieś ograniczenia? Bo równie dobrze można przyjąć, że \(\displaystyle{ n= 10^{10 ^{10 ^{...} } } }\) i wtedy to już w ogóle mamy problem Jeśli natkniesz się na rozwiązanie akceptowalne przez autorów to wrzuć tu proszę, jestem ciekaw co sobie tam założyli.
-
- Użytkownik
- Posty: 7
- Rejestracja: 14 gru 2020, o 17:51
- Płeć: Kobieta
- wiek: 17
- Lokalizacja: Paraguay
Re: suma n cyfr po przecinku pierwiastka z m
\(\displaystyle{ 1 \le m \le 10 ^{8} }\)
\(\displaystyle{ 1 \le n < 100}\)
czyli suma maksymalnie 99 cyfr po przecinku
\(\displaystyle{ 1 \le n < 100}\)
czyli suma maksymalnie 99 cyfr po przecinku
-
- Użytkownik
- Posty: 128
- Rejestracja: 5 lip 2015, o 14:48
- Płeć: Mężczyzna
- Lokalizacja: nie wiem
- Podziękował: 11 razy
- Pomógł: 24 razy
Re: suma n cyfr po przecinku pierwiastka z m
No to nie jest tak źle, nie podałeś innych ograniczeń co do kodu więc najwygodniej będzie Ci chyba wykorzystać tę bibliotekę
Kod: Zaznacz cały
https://gmplib.org
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Re: suma n cyfr po przecinku pierwiastka z m
Nie znam takiego - miałem na myśli algorytm działający na trzymanych w tablicy liczbach stucyfrowych z ręcznie zaprogramowanymi operacjami arytmetycznymi, bo w końcu jest to zadanie konkursowe. Gdyby wystarczyło używać typów wbudowanych, problem stałby się trywialny.Corvette653 pisze: ↑21 kwie 2022, o 18:28Nie istnieje żaden sposób wyznaczania pierwiastka, który pozwalałby "zapomnieć" wcześniejsze cyfry, lub przynajmniej je skompresować?