Ilość możliwych liczb

Ziemniak1990 · Post autor: **Ziemniak1990** » 3 cze 2009, o 13:37

Nie mogę sobie poradzić z zadaniem...w sumie to problemem, bo nie muszę tego zrobić na żadne zajęcia, tylko dla siebie.

Ile może być liczb o N cyfrach, w których zera ze sobą nie sąsiadują ( zer może być dowolna liczba )?

Potrzebował bym raczej listę kroków lub jakieś nakierowanie niż ostateczny wzór. Z góry dziękuje.

abc666 · Post autor: **abc666** » 3 cze 2009, o 15:04

Chyba najłatwiej będzie policzyć liczbę dowolnych liczb o N cyfrach a potem odjąć od tego liczbę tych w których zera sąsiadują. Można też liczyć od razu ale chyba policzyć te niepasujące będzie łatwiej. W obu przypadkach powinieneś otrzymać zależność rekurencyjną tzn. przy rozważaniu liczby N cyfrowej trzeba wziąć liczbę z przypadku liczby o długości N-1 i dodać do tego przypadki które dochodzą przy jednej cyfrze więcej. Oczywiście zawsze doklejasz liczbę z jednej strony, (proponuje z prawej, omijamy problemy ze zliczaniem liczb z zerami wiodącymi). Był podobny temat o ciągach 116497.htm . W nim praktycznie jest odpowiedź jednak trzeba właśnie policzyć niemożliwe przypadki itp.

Jak gdzieś się zatniesz to napisz gdzie oraz najlepiej przedstaw swój tok rozumowania.

Ziemniak1990 · Post autor: **Ziemniak1990** » 3 cze 2009, o 15:54

Rozpatrywałem to podobnie.
Najpierw liczyłem ile jest liczb o N cyfrach, to nie jest trudne.
Po tym sprawdzałem ile jest liczb, w których występują 2 zera i ze sobą sąsiadują o odejmowałem od całości. Potem 3 itd, az do N-1. Ale klopot mam z policzeniem, czy wyznaczeniem ilości takich sąsiadujących zer ze sobą. w przypadku, przykładowo N = 8, przy 3 zerach sprawa się komplikuje i nie mogę sobie poradzić.

abc666 · Post autor: **abc666** » 3 cze 2009, o 17:41

Lepiej będzie to robić "od dołu", zaczynamy (dokładamy cyfry z prawej strony)

\(\displaystyle{ N=1}\) - 10 liczb \(\displaystyle{ \{1,2,3,4,5,6,7,8,9,0\}}\)
\(\displaystyle{ N=2}\) - mamy \(\displaystyle{ 9 \cdot 10}\) liczb, do każdej cyfry oprócz 0 możemy dodać dowolną cyfrę
\(\displaystyle{ N=3}\) - mamy \(\displaystyle{ 80 \cdot 10}\) znów dodajemy każdą z cyfr tam gdzie nie ma zer na końcu, mamy jeszcze 9 liczb do których możemy na koniec dopisać nie-zero więc mamy w sumie \(\displaystyle{ 80 \cdot 10 + 9}\) lub wyraźniej \(\displaystyle{ (90-10) \cdot 10+9}\),
\(\displaystyle{ N=4}\) - mamy \(\displaystyle{ 809}\) liczb z poprzedniej sytuacji, trzeba się zastanowić ile jest z zerami, ponieważ na końcu nie może być dwóch zer więc od razu zauważamy że zawsze mamy 10 liczby z zerami na końcu, do nic nie możemy dodać zera, mamy więc \(\displaystyle{ (809-10) \cdot 10}\) no i do tego 9 liczby z zerami na końcu do których możemy dodać cyfry 1-9 więc w sumie mamy \(\displaystyle{ (809-10) \cdot 10+9}\)

Zauważyłeś już wzór ogólny? Jeśli nie rozpisz sobie \(\displaystyle{ N=5}\) a jeśli tak to napisany wzór trzeba udowodnić indukcyjnie. Potem można się pokusić o wyznaczenie wzoru jawnego.

Ziemniak1990 · Post autor: **Ziemniak1990** » 4 cze 2009, o 12:37

Mam jeszcze tylko jedno pytanie. Czy w przypadku N = 3, gdy sprawdzamy na początku do ilu liczb możemy dopisać tę trzecią cyfrę, nie będzie ich 81, zamiast 80?

\(\displaystyle{ \lbrace 1,2,3,4,5,6,7,8,9\rbrace}\) na pierwszej pozycji i

\(\displaystyle{ \lbrace 1,2,3,4,5,6,7,8,9\rbrace}\) na pozycji drugiej

No i w sumie jak tak liczę na palcach, to tych liczb 2 cyfrowych z 0 na końcu jest 9:

\(\displaystyle{ \lbrace 10,20,30,40,50,60,70,80,90\rbrace}\)

\(\displaystyle{ (90-9) \cdot 10 + 9 \cdot 1\cdot 9}\)

no, chyba, że po prostu źle zrozumiałem cały zabieg...

abc666 · Post autor: **abc666** » 4 cze 2009, o 12:46

Masz, rację, pomyliłem się, powinno być 81 i dalej też inne liczby wyjdą ale idea ta sama cały czas

Ziemniak1990 · Post autor: **Ziemniak1990** » 4 cze 2009, o 13:12

Tak, już wszystko wiem. Dzięki wielkie, nie wpadł bym na pomysł dokładania cyfr po kolei, więc bardzo pomogłeś.

Jeszcze w Twoim algorytmie się pomyliłeś mówiąc że takich liczb z zerami na końcu zawsze jest 9. Jest ich zawsze 9 razy więcej niż poprzednio.

Klikam, że pomogłeś:)

abc666 · Post autor: **abc666** » 4 cze 2009, o 13:49

ah racja, zapomniałem że mamy coraz więcej liczb z takim samym końcem