Nie wszędzie działający program.

Witam ponownie.

Miałem napisać program ,który po podaniu ilości kul ogółem i ilości losowanych , wyrzuca ilość możliwych kombinacji losowania. Napisałem i działa dobrze ,lecz "urządzenie sprawdzające" orzeka błąd uruchomienia. Nie mam pojęcia do czego może mieć problem ,bo na moim kompilatorze testowałem go wiele razy i kłopotu nie było. Oto kod:

http://wklej.org/id/1932055/

Z góry dzięki za pomoc :)

1. Silnia rekurencyjnie? o_O
2. Liczenie ilości kombinacji za pomocą rekurencyjnych silni :D :D :D
   Cały kod jest do wyrzucenia. Zresztą wpisz sobie tam jakąś liczbę większą niż 30 i już będziesz miał złe wyniki. Nie, to nie działa dobrze. Ani trochę.

Jakie są zakresy danych na te liczby? Bo jak są wystarczająco duże to w ogóle na tej twojej bieda-silni dostajesz stackoverflow przez wielokrotne rekurencje i stąd błąd wykonania.

Przecież ci już odpisałem: http://4programmers.net/Forum/1223829
Jakiego słowa nie rozumiesz?

Dragon , zrobiłem według Twojej rady ,ale najpewniej kulawo :/ Podmieniłem dużą silnie tak aby zamiast liczyć 40! liczyła kilka ostatnich wyrazów co działa jak skracanie silni nad i pod kreską ułamkową. Niezbyt wiedziałem co zrobić gdy wartość K będzie spora i właśnie dla takich danych program ni działa :/

I gdzie jest to co niby zrobiłeś według mojej rady?

int nk=(n-k)+1;
long long int suma=nk;
while(nk<n){
suma=suma*(nk+1);
nk=nk+1;
}

nk -pierwsza liczba nie skrócona z silnią niżej czyli na górze 40! na dole 35! zatem nk=36 - póki nk<40 będzie mnożyło 363738 do 40 włącznie.
Bardzo możliwe ,że coś mi nie wyszło . Z góry wybaczcie ,bo z waszej perspektywy totalny nieogar ,a ja po prostu miałem rok przerwy w programowaniu i popełniam dużo głupich błędów :(.

PRosze :
http://stackoverflow.com/questions/27697636/newtons-binomial-doesnt-work-for-bigger-numbers
http://stackoverflow.com/questions/3537360/calculating-binomial-coefficient-nck-for-large-n-k

Newton's Binomial to znaczy symbol newtona. Skopiuj sobie kod z drugiego i zobacz czy działa.

#include <cstdint>
#include <iostream>
#include <algorithm>
using namespace std;

uint64_t newton(uint64_t n,uint64_t k)
  {
   k=min(k,n-k);
   uint64_t mul=1;
   for(uint64_t i=1;i<=k;++i,--n) mul=(mul*n/i);
   return mul;
  }

int main()
  {
   unsigned n,k;
   while(cin>>n>>k) cout<<newton(n,k)<<endl;
   return 0;
  }

Jeżeli nie chcesz by zbyt szybko doszło do przepelnienia to zastosuj programowanie dynamiczne. Algorytm wynika z własności:

Newton(n, k) = Newton(n-1, k-1) + Newton(n-1, k)
Newton(n, 0) = Newton(n, n) = 1

Stablicuj raz obliczone wartości, aby nie liczyć niepotrzebnie.

Edit: Ok, ktoś wyżej juz zapodał linki do tego sposobu.

Mi nie działa , ale jeśli Tobie działa to zapewne wina mojego syfnego kompilatora. No nie będę prosił o rozpisanie tego na podstawowy c++ bo nie chcę męczyć. Jeśli nie masz nic przeciwko możesz w punktach opisać co dokładnie po kolei ma robić program ,to sam pokombinuję. Z mojej perspektywy problem tkwi w zbyt wielkich liczbach przez co moje pomysły są do bani.

@nalik

O widziałem taki sposób u kogoś z mojej grupy ćwiczeniowej. Spróbuję może się uda :)

Brakuje podstawowej informacji, jak duże może być n? Stosowany algorytm trzeba uzależnić od dopuszczalnej wielkości n. W Javie (typ long jest signed i 8-bajtowy, maksymalna wartość 9 223 372 036 854 775 807):

• algorytm @_13th_Dragon'a daje poprawne wyniki dla n<=60,
• algorytm @nalik'a daje poprawne wyniki dla n<=66, ale działa kilkaset razy wolniej, a jeśli nie tablicuje się uzyskanych wyników, to już w pobliżu n = 33 nie nadaje się do użytku.
  Jeśli n mogą być jeszcze większe to trzeba korzystać z typu BigInteger.