Liczby KN, ilosc liczb fibonacciego w danym przedziale ...

KHR · Post autor: **KHR** » 16 sie 2005, o 01:13

Witam serdecznie,

Mimo usilnych prob nie potrafie sobie poradzic z dwoma zadaniami z kombinatoryki, byc moze dla niektorych wydadza sie smieszne jednak ja spedzilem duzo czasu i nie potrafilem wpasc na ten "genialny sposob" ich rozwiazania.

Zad. 1

Zadanie to pochodzi z serwisu mianowicie:

Rozważmy liczby zawierające dokładnie N cyfr, zapisane w systemie K.
Liczbę nazwiemy KN-poprawną, jeśli w jej zapisie w systemie K nie wystąpią dwa sąsiadujące ze soba zera.

Na przykład:
1010230 jest poprawną 7-cyfrowa liczbą KN (n=7, k=4)
1000198 nie jest poprawną liczbą KN (sąsiadujące zera)
0121235 nie jest 7-cyfrową, lecz 6-cyfrową liczbą KN (n=7, k=7).

Pytanie: Ile jest liczb KN poprawnych dla danego K i N.

O ile poprzednie zadanie potrafie zaczac (kombinowalem z wariacjami z powtorzeniami) o tyle zadanie drugie (pochodzace z ksiazki "Wyzwania programistyczne") nie potrafie nawet zaczac ...

Zad. 2

Ile jest liczb fibonacciego w danych przedziale .

PS: Moim celem nie jest nabicie sobie punktow na OPSS tylko nauczenie sie czegos wiec prosze mnie nie krytykowac ze wystawiam zadanie z konkursu.

PS2: Mile widziane bylo by napisanie jak doszliscie do tego rozwiazania a nie podanie gotowej odpowiedzi. (a jeszcze lepsze bylo by wytlumaczenie "tak na zdrowy rozsadek" bo w ten sposob cos mi zostanie w glowie i bede potrafil byc moze zrobic podobne zadania)

PS3: Kombinatoryki nie przerabialem jeszcze w szkole (ale rozumiem podstawowe pojecia zwiazane z tym dzialem matematyki

wiec prosilbym o opis w miare zrozumialy dla laika.

pozdr.
Karol H.

g · Post autor: g » 16 sie 2005, o 01:44

drugie jest banalne, jak sie zna wzor Bineta.

KHR · Post autor: **KHR** » 16 sie 2005, o 02:06

g pisze:drugie jest banalne, jak sie zna wzor Bineta.

Ehh ... dzieki to wystarczylo, a moze masz tez jakas blyskotliwa podpowiedz do Zad 1 ?

półpasiec · Post autor: **półpasiec** » 16 sie 2005, o 02:27

w szkole raczej nie dowiesz sie niczego co pomoze ci w rozwiazaniu tego zadania, wez poszukaj czegos o rekurencji, to i tak jest juz bardzo duza podpowiedz
i nie mam pojecia na co zdrowy rozsadek do tego zadania

KHR · Post autor: **KHR** » 16 sie 2005, o 03:07

Reksio pisze:w szkole raczej nie dowiesz sie niczego co pomoze ci w rozwiazaniu tego zadania, wez poszukaj czegos o rekurencji, to i tak jest juz bardzo duza podpowiedz
i nie mam pojecia na co zdrowy rozsadek do tego zadania

O ktorym zadaniu mowisz ? Jesli o pierwszym to nie wiem w czym by mi mogla pomoc rekurencja, a co do drugiego zastanawiam sie czy nie mozna zrobic tego bardziej elegancko.

_el_doopa · Post autor: **_el_doopa** » 16 sie 2005, o 03:34

ostatnio tez tam duzo wysylam ...
o tak wygladal moj program jak chcesz wiedziec w c++

Kod: Zaznacz cały

   1.
      #include<stdio.h>
   2.
       
   3.
      main()
   4.
      {
   5.
      int K,N;
   6.
      scanf("%d
%d",&N,&K);
   7.
      int tab[N+1];
   8.
      tab[0]=1;
   9.
      tab[1]=K-1;
  10.
      for(int i=2;i<N+1;i++)
  11.
      {
  12.
      tab[i]=(K-1)*(tab[i-1]+tab[i-2]);
  13.
      }
  14.
      printf("%d
",tab[N]);
  15.
      }
  16.
       
  17.

wiem z autopsji ze czytanie cudzych programow jest kosmicznie trudne i zazwyczaj nie da sie zrozumiec idei zwlaszca jak ktos nie robi wciec ani komentarzy
wiec przedstawiam jak do tego doszedlem
oznaczmy przez a_N ilosc KN poprawnych liczb
wiemy ze a_0=1 (zbior pusty)
a_1=K-1
i teraz patrzysz na koncowa cyfre poprawna liczba KN moze konczyc sie zerem albo nie
1)jesli nie konczy sie zerem to ostatnia cyfra moze byc jedna z K-1 a wczesniejsze musza tworzyc poprawna K(N-1) liczbe
2) jelsi konczy sie zerem to przedostatnia cyfra musi byc jedna z K-1 a wczesniejsze tworza poprawna liczbe K(N-2)
w takim razie a_N=(K-1)*a_(N-1)+(K-1)*a_(N-2)
znajac takie cos
a_0=1
a_1=K-1
a_N=(K-1)*a_(N-1)+(K-1)*a_(N-2)
oczywiscie moznaby wyprowadzic jakis wzor ogolny ale w informatyce zwykle bardziej oplacalny jest rekurencyjny czyli taki w ktorym nastepny zalezy od poprzedniego

napisalem ci kufa szmata cale rozwiazanie wiec jakbys mogl wcisnac pomogl taki przycisk na dole to bylbym wdzieczny

btw zajebiscie by bylo jakby mi ktos mowil jak robic zadania jakie struktury danych sa efektywne itp. niestety do wsyztskiego musze dochodzic sam a OI sie zacznie juz w pazdzierniku...

KHR · Post autor: **KHR** » 16 sie 2005, o 08:49

_el_doopa pisze:ostatnio tez tam duzo wysylam ...
oczywiscie moznaby wyprowadzic jakis wzor ogolny ale w informatyce zwykle bardziej oplacalny jest rekurencyjny czyli taki w ktorym nastepny zalezy od poprzedniego

Zadanie jest stricto z kombinatoryki wiec liczylem na teki "genialny" pomysll z wzorem.

napisalem ci kufa szmata cale rozwiazanie wiec jakbys mogl wcisnac pomogl taki przycisk na dole to bylbym wdzieczny

bez komentarza

btw zajebiscie by bylo jakby mi ktos mowil jak robic zadania jakie struktury danych sa efektywne itp. niestety do wsyztskiego musze dochodzic sam a OI sie zacznie juz w pazdzierniku...

ja sie nie wybieram na zadne OI ...

półpasiec · Post autor: **półpasiec** » 16 sie 2005, o 11:29

ty pizdzielcu jebany nie dosc ze ci pomogl napisal ci wiadomosc chyba z 3 tys znakow to nawet nie chcesz zrobic o co cie poprosil, jak nie zrobisz tego to bana dostaniesz
i jesli ktos ci mowi ze to z czegos wyjdzie to nie wal glupich napisow 'nie wiem w czym to mialoby pomoc', tylko idz sie kurwa dowiedz lec na google albo do biblioteki co ty myslisz ze laske nam robisz ze ci pomagamy

g · Post autor: g » 16 sie 2005, o 21:26

ahaha :DD dwa razy jeblem jak stalem

ed - co ci sie na mozg rzucilo ze ci na tych dunych punkcikach zalezy?

no normalnie beton roku "dawaj punkta" buehehe

pizdzielec jebany - musze sobie zapamietac

temat roku jak dla mnie

chociaz swoja droga Reksio ma racje. nie wyjezdzalbys z taka maniera. nie prosil cie zebys mu possal tylko zebys kliknal w jedno miejsce (jakkolwiek durnowato by to nie brzmialo :D).

Arek · Post autor: **Arek** » 16 sie 2005, o 23:36

ahaha D dwa razy jeblem jak stalem

nie Ty jeden....

ed - co ci sie na mozg rzucilo ze ci na tych dunych punkcikach zalezy? no normalnie beton roku "dawaj punkta" buehehe

wlasnie... jak chcesz modem zostać, to powiedz... coś wykombinujemy

temat roku jak dla mnie

Ano własnie.. czytaliśmy tak sobie z liu ten temat i myślimy co tu robić, kogo karać itd, no ale w sumie wakacje są, temat zabawny, więc czemu nie

chociaz swoja droga Reksio ma racje. nie wyjezdzalbys z taka maniera. nie prosil cie zebys mu possal tylko zebys kliknal w jedno miejsce (jakkolwiek durnowato by to nie brzmialo ).

ano... w sumie

g - sorry, ze Cie tak cytuje...

liu · Post autor: **liu** » 16 sie 2005, o 23:39

[...] nie prosil cie zebys mu possal [...]

[...] myslisz ze laske nam robisz [...]

Eh, chlopaki, to nie forum erotyczne:D