Jan 2016
11 / 40
Jan 2016
Feb 2023
narbej
Jan '16
2

Pięknie i może, ale czy poprawnie? Policzyłeś ręcznie i sprawdziłeś wink
Zobacz jak to pięknie robi: http://ideone.com/GYbvnO255
Ustawienie cout << setprecision(1000); spowoduje Ci tylko wyświetlenie odpowiedniej ilości cyfer, ale wcale nie znaczy, że będą to dokładne wartości. Przy long doble, gdzieś tak 20 znaczących [o ile dobrze pamiętam[ a reszta to śmieci, a dodatkowo, przy niektórych kombinacjach danych i tak sypie wartościami po przecinku. Autor zadania zapewnia, że wynik nie będzie większy od 1 000 000 000 [typ int wystarcz] ale po drodze pewnie pojawiają się w twoim algorytmie, przekłamania [błędy zaokrągleń zmiennoprzecinkowych].
A duże wartości możesz zobaczyć i sprawdzić np tu: http://www.wolframalpha.com/input/?i=binomial+%28+1000%2C+12%2998 wpisując w pomarańczową ramkę dowolne wartości [ale pewnie bez przesady], taki sobie po[d]ręczny kalkulator.
Dwumian to liczba całkowita, a licząc na typie double, czy long double uzyskasz jakiś wynik przybliżony, dla małych wartości z bardzo małym [pomijalnym] błędem dla ogromnych z dużym. Mam na myśli ilość cyfr znaczących.

PS
Na pocieszenie, pewien bloger, autor kilku ciekawych kursów programowania, prowadzący interesujący i wartościowy blog ale nie pozbawiony błędów. Międy innymi przedstawia swój program do liczenia wielkiech liczb fibonacciego i niestety też z tym samym, co twój, błędem.

vojtass
Jan '16
1

Dzięki wielkie za odpowiedzi!

Tak sądziłem, że ten typ double coś kręci, już mi ktoś kiedyś napomknął o tym przybliżaniu gdzieś tam za przecinkiem. Od dłuższego czasu próbuję więc ominąć duże liczby, staram się współpracować z mniejszymi, i do tej pory wykombinowałem coś takiego: http://ideone.com/LTJL6b82 (tak, w kodzie jest funkcja newton_triangle, pomyliłem się, ten trójkąt w istocie nazywa się trójkątem Pascala oczywiście)

Program opiera się na zależności trójkąta Pascala, gdzie każdy wyraz poza skrajnymi powstaje przez dodanie do siebie dwóch bezpośrednio nad nim, oraz z zależności, że dla k > n/2 --> k = n - k; liczy na samych intach, więc przybliżenie wyeliminowane, rozmiar kodu i programu też zmniejszony, ale doszedł mi teraz problem z czasem wykonania programu (za duży)... macie jakieś wskazówki może, jak jeszcze inaczej to wykonać? Jak tu ukrócić ten czas?

narbej
Jan '16

Funkcje rekurencyjne mają to do siebie, że są łatwiejsze do napisania, ale często taki algorytm jest dużo wolniejszy od iteracjyjnego. Tutaj dochodzi do wielokrotnego liczenia tych samych wartości. Np popatrz:
(20, 10) = (19, 9) + (19, 10)
(19 , 9) = (18, 8) + (18, 9); (19, 10) = (18, 9) + (18, 10)
(18, 8) = (17, 7) + (17, 8); (18, 9) = (17, 8) + (17, 9); drugi raz (18, 9) = (17, 8) + (17, 9); (18, 10) = (17, 9) + (17, 10)
.........itd
Czy pomysł z trójkątem jest w takim razie zły? Nie, pod warunkiem, że wcześniej obliczysz wartości i zapiszesz w tablicy dwuwymiarowej [preprocesing]. Potem już od razy będziesz mógł odczytywać wartości (n, k) bezpośrednio z tablicy. Jakie wymiary tej tablicy? Z treści zadania wynika, że wierszy musi być n <= 1000, ale czy kolumn też aż tyle?

Druga metoda, to liczenie dwumianu iteracyjnie i aby nie przekroczyć zakresu na zmianę odpowiednio mnożyć i dzielić. Odpowiednio, bo musimy dzielić całkowicie [bez reszty]. Dzięki temu uda się "utrzymać" w zakresie long long - przy założeniach z zadania. [Algorytm np na wikipedi]

PS
Nazwy zmiennych zwyczajowo coś znaczą. Np i, j - zmienne pętli, indeksy tablic. x, y, z --> układ kartezjański i wartości na osiach. itd Dlatego twoją funkcję jeżeli już, to napisałbym raczej jakoś tak, chociaż i tak to nie zmienia faktu - nadal jest tle.
i

int PascalTriangle (int n, int k){
    if (n == k || k == 0) return 1;
    if(k > (n >> 1)) k = n - k;
    if ( k == 1) return n;
        return PascalTriangle (n-1, k-1) +  PascalTriangle

(n-1, k);
}

vojtass
Jan '16

Dzięki znów za odpowiedź, to mi dużo da, zaraz siadam do pracy i pokombinuje w tym kierunku!

A co do tych zmiennych, gdzieś słyszałem, że bezpieczniej jest inaczej nazwać zmienne, które wykorzystuje funkcja na potrzeby własne, nie do końca jestem w stanie teraz podać sensowne powody tego założenia, więc nie będę się kłócić, ale podejrzewam, że wiesz na ten temat co nieco, mógłbyś jakoś się odnieść do tego? Z góry dziękuje! ^^

vojtass
Jan '16

Skorzystałem z liczenia iteracyjnego, program po raz kolejny wykonuje obliczenia dokładnie, szybko, tym razem jednak mam błędną odpowiedź. Poważnie, nie wiem czy ja nie jestem czasem za głupi na to zadanie stuck_out_tongue nie mogę się doszukać błędu.

Wstawiam kod: http://ideone.com/jJCNaF117

narbej
Jan '16
2
narbej

Sorry, że cytuję sam siebie, ale proszę sprawdź, czy rzeczywiście tak napisałem wink No może wcześniej nie pogrubiłem i nie wystarczająco uwypukliłem, więc się tym nie przejmuj. I chodzi tylko o jedną zmienną tego typu, w, reszta jest ok. Po prostu, w tym algorytmie, mimo naprzemiennego mnożenia i dzielenia jednak czasami wychylamy się troszkę ponad inta, dla danych takich jak w zadaniu.

PS
Co do nazewnictwa. Funkcja, lokalnie używa swoich zmiennych lokalnych, więc może chyba
sobie je lokalnie nazywać jak chce? Po prostu nie wierz [albo wież] bezgranicznie we wszystko co gdzieś usłyszysz czy przeczytasz, póki sam osobiście tego nie sprawdzisz. Więc mi oczywiście też nie wink

vojtass
Jan '16
1

Może nie jest tak, że bezgranicznie wierzę, po prostu ufam lepszym od siebie, skoro są w stanie wyjaśnić mi multum zagadnień, czemu w tym mają się mylić stuck_out_tongue prawda jest taka, że i tak większość rzeczy człowiek i tak uczy się na błędach, jak ja w tej chwili ^^ z drugiej strony jednak, czemu w takim razie kompilator nie wyrzuca mi błędu u mnie na komputerze, ale sędzia doskonale wie, że w którejś tam iteracji zmienna wypada poza zakres? Myślałem, że dla niego liczy się tylko poprawność wyjścia

PS. Kod przeszedł (dzięki long long) bez problemu, dzięki wielkie!

PSS. Dobra, mój błąd, po prostu nie dobrałem takiego wejścia żeby pojawił się problem który opisałeś - dla niektórych dwumianów faktycznie wynik jest błędny mimo tego, że prawidłowy końcowy wynik zawiera się w przedziale podanym przez autora.

sig
Jan '16

Podejrzewam że chodzi o to, że zmienna lokalna "przykryje" globalną, i przy 2 zmiennych o tej samej nazwie (lokalnej i globalnej) nie będziesz miał z tej funkcji dostępu do globalnej. Będziesz też musiał zastanawiać się czy w danym miejscu ta zmienna jest globalna czy też lokalna. Generalnie zalecam nazywanie zmiennych zgodnie z tym co w nich przechowujesz, wtedy nie powinno być tego typu problemów, a kompilator i tak zamieni je na adresy pamięci więc długość nazw nie ma najmniejszego wpływu na działanie programu.

2 months later
eriq2207
Mar '16

Witam.

Przejrzałem wszystkie tematy związane z zadaniem, próbowałem różnych zestawów danych jednak mój program cały czas wyrzuca "błąd wykonania".
Jeżeli ktoś miałby czas spojrzeć na kod i stwierdzić co w nim jest nie tak to byłbym wdzięczny.

Link do kodu: https://ideone.com/TmxyVB74

Z góry dzięki :slight_smile:

5 months later
karol1ch
Sep '16

Witam. Ponownie muszę zwrócić się do Was z prośbą o pomoc choć tym razem nie do końca dotyczącą kodu.
Sędzia wyrzuca mi błąd SIGFPE czyli coś złego dzieje się z działaniami, a ja nie mam pojęcia co i będę wdzięczny za pomoc.
Na wszelki wypadek dołączam też mój kod :slight_smile:
ideone28

vojtass
Sep '16

Problem wynika ze sposobu liczenia. Zobacz - sposób jest dobry, ale weź pod uwagę, że gdy do funkcji silnia() jako argument wstawisz 1000 to nie wiem czy long long będzie w stanie uciągnąć taką liczbę. :slight_smile: dodatkowo posługując się tak ogromnymi liczbami, wykonując potem operacje dzielenia narażasz się na błąd przybliżenia wynikający ze sposobu zapisu liczb w programowaniu

4 months later
prynio
Feb '17

Stworzyłem do tego zadania bardzo prosty kod, z czego byłem bardzo dumny. W code::blocks działa niezawodnie, sprawdzałem dla wielu przykładów ręcznie. Ale sędzia tego nie uznaje. Jakieś uwagi co poszło nie tak?

Kod:
https://ideone.com/pfwLJe71

prynio
Feb '17

Ale w zadaniu jest założenie "Dla liczb całkowitych n i k, 0 <= k <= n <= 1000", a w Twoim drugim przykładzie k>n i jeśli się nie mylę, to nie da się wyznaczyć takiego dwumianu.

krystian01
Feb '17

W tym zadaniu kombinatoryka się kłania :wink: Poczytaj o symbolu Newtona(kombinacje bez powtórzen). Sam wzór niestety nie wystarczy. Będziesz musiał coś wykminić.

prynio
Feb '17

Dla 25 25 działał dobrze, ale Twój poprzedni przykład pokazał słabość kodu. Nie wiem czemu, ale dla n=0 wykonywał pętle for (int j=n; j>(n-k); j--) x*=j; chociaż tak na logikę powinien zerwać ją przed pierwszym wykonaniem. W każdym razie dodałem "ręcznie" wyjątek w postaci if (n==0)cout<<x<<endl; i już mi zaliczyło.

Także bardzo dziękuję za pomoc!

narbej
Feb '17

No, nono, w takim razie wielki szacunek :wink: I za dodanie wyjątku i za zrobienie tego ręcznie, jestem pełen podziwu i uznania :wink:

A na ideone.com, można i należy wkleić nie tylko kod programu, ale i testy, abyś i Ty mógł sobie potestować i aby inni też widzieli, że testowałeś: https://ideone.com/9DN2Ui37 <-- tu niestety twoja stara wersja kodu, bez wstawionego ręcznie wyjątku.

PS
Tak na marginesie, dwumian (1000 3) == dwumian (1000 997), o czym przeczytałbyś i w opisie dwumian'a i w tym wątku, gdybyś czytał.

prynio
Feb '17

Dzięki, nie zauważyłem że można tam dodawać testy. Na pewno skorzystam

To akurat wiem, ale nie bardzo rozumiem jak się ma do tematu. Mogłem zamienić (0 x) na (x x), jeśli to masz na myśli, ale w sumie wyszłoby na to samo co dodanie automatycznego wyniku "1" dla każdego n=0.