Inne, zadanie nr 4804

Autor	Zadanie / Rozwiązanie
tasia postów: 17	2016-09-18 13:51:56 ile jest liczb trzycyfrowych o sumie cyfr równej 9? Jeśli wypisze sobie wszystkie przypadki to bedę ich miała 45.Czy istnieje jakaś inna metoda wyliczenia ?

janusz78 postów: 820	2016-09-18 16:26:22 Musimy znaleźć liczność (moc) zbioru $\left\{ \overline{abc}: a+b+c = 9\wedge a \geq 1\right\}.$ Innymi słowy musimy obliczyć liczbę rozwiązań naturalnych równania $ a + b + c = 9 \wedge a\geq 1.$ Liczba ta jest równa liczbie kombinacji z powtórzeniami $ {9 + 3 -1\choose 9} = {11\choose 9} = 55.$ Program R choose(11,9) [1] 55

tumor postów: 8070	2016-09-19 09:00:22 Możemy na zadanie spojrzeć tak: Mamy 9 jednostek do podziału na 3 cyfry, to mniej więcej tak, jakby 9 jabłek podzielić na 3 grupy. Podzielmy - wstawiając pomiędzy jabłka dwie gruszki. Mamy zatem w rzędzie 11 owoców i wybieramy, które dwa są gruszkami, z tym jednym zastrzeżeniem, że NIE jest gruszką owoc pierwszy. Wobec tego wynikiem jest ${10 \choose 2}$, co równe 45 (no i chyba jasne, układ w jjgjjjjjjjg oznacza liczbę 270 etc) wybieramy zatem, powtórzę, 2 z 10, a nie z 11 (Janusz pomija warunek a>0). --- Inaczej myślimy o tym rekurencyjnie. Niech S(3,9) oznacza ilość liczb 3-cyfrowych o sumie cyfr 9 (ale dopuśćmy, że liczby te zaczynają się od 0). Ogólnie S(n,k) to ilość liczb n-cyfrowych o sumie cyfr k (gdy dopuszczamy rozpoczynanie się od 0) Oczywiście wtedy S(3,9)=S(2,9)+S(2,8)+S(2,7)+...+S(2,1)+S(2,0) (odpowiednio: pierwszą cyfrą może być 0 lub 1 lub 2 lub... lub 8 lub 9) Dość jasne jest też, że S(2,9)=S(1,9)+S(1,8)+...S(1,1)+S(1,0)=10 i dla k<9 podobnie S(2,k)=S(1,k)+S(1,k-1)+...+S(k,0)=k+1 Zatem S(3,9)=10+9+...+1=55, jak to liczy Janusz, no ale przypominam, że tu liczby mogą się zaczynać od 0. Jeśli chcemy mieć pierwszą cyfrę dodatnią, to musimy odjąć S(2,9) czyli te przypadki, gdzie sumą dwóch ostatnich cyfr było 9. S(3,9)-S(2,9)=55-10=45 Dla dużych liczb podejście rekurencyjne jest wolne, gdy liczy człowiek, ale szybkie, gdy maszyna.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj