Tip na algoritmus – Pascal – Fórum – Programujte.com

Pěkný podvečer,
kamarád mě prosil o pomoc a já zjistil, že toho moc nezmůžu. Tak se ptám tady. Vymýšlí program, který by doplnil následující člen zadané posloupnosti - jistě to znáte z IQ testů, zadají vám řadu čísel a domyslete to poslední. Nenapadá mě efektivní algoritmus.
Jediné, co mě napadlo, je postupně testovat typy posloupností (např. jedná-li se o přičítání čísla, násobení atp.). kombinací je ovšem mnoho - nenapadá někoho něco efektivnějšího?
Nejde mi o vlastní kód, sháním nápad, Děkuji.

Hmm, možná nalézt pro danou posloupnost generující funkci http://en.wikipedia.org/wiki/Generating_function, z ní spočítat n-tou derivaci v bodě 0, a to by měl být n-tý člen posloupnosti. Nicméně látka je to složitá.

Dále viz. například http://kam.mff.cuni.cz/~eva/kg/gf.pdf.

Tahle úloha už z principu na počítači řešit nejde. Vždyť v IQ testech jde právě o to - rozpoznat pravidla posloupnosti. Tedy potřeba najít algorimus. Počítače nejsou od toho, aby nacházely algoritmy, ale aby prováděly algoritmy. Samozřejmě bys mohl zkusit udělat jakousi kuchařku, program, který dokáže identifikovat několik typů posloupností, ale v praxi by to bylo na nic, protože možností, podle kterých může být posloupnost sestavena, je nekonečně mnoho.
Není ale naopak problém napsat program, jestli zadané číslo může být členem nějaké dříve definované posloupnosti. Např. program, který zjistí, zda je zadaná hodnota členem Fibonacciho posloupnosti, zda je to prvočíslo, zda je to součet dvou předchozích prvočísel, atd.

To Laaca : No počkat počkat, kamarád si to vybral z nějakého seznamu úloh, a ten program má obtížnost asi 7 z dvanácti, to by nemusel být tak složitý? Pravda je, že na všechny posloupnosti to opravdu napasovat asi nepůjde... Takže říkáte udělat několik testovacích procedur?

pokud se nemylim tak toto je uloha z nejake nedavne sady korespondencniho seminare z informatiky - KSI.
zadani ulohy vicemene vybizelo k heuristickemu reseni ulohy, tedy zavest do programu co nejvice predpisu a podle tech pak doplnovat (To Laaca : takhle velice casto postupuje clovek. a kdyz jsme u ulohy pocitacu, rika ti neco termin geneticke algoritmy?). ovsem je taky treba rict ze pokud je rada zadana vyctem prvku, pak jeji predpis nemusi byt jednoznacny.

teoreticky se da podle jednoducheho pravidla k jakekoli rade vygenerovat predpis ktery ji pasuje - napr. pro radu {3,5,7}, ktera by mela odpovidat prepisu n=2*x + 1, se da pouzit i predpis n=||sgn(x-1)|-1|*3 + ||sgn(x-2)|-1|*5 + ||sgn(x-3)|-1|*7. ten viditelne pasuje jen teto casti rady - ale to je presne to o co nam jde. reseni je to sice nechutne, ale teoreticky zadani odpovida - ovsem podle techto predpisu jsou vsechny nasledujici cleny 0).

ale jinak bych jako smysluplne reseni videl ony usirevem navrhnute generujici funkce).

To Garret Raziel : podle me je nadavka se spenatem docela originalni a dobra).

a proc je tohle vlastne v sekci pascal?

To tmi : jj, ty generující funkce jsou myslím nejlepší. Ony ty posloupnosti v IQ testech nikdy nejsou náhodné, vždy to má nějaký jednoduchý/složitý řád.

To Osiris : ale cela ta uloha je z principu dost spatna - totiz pokud je posloupnost zadana konecnym poctem prvku, tak teoreticky pro ni muze byt vice navzajem ruznych predpisu (a tim nemyslim jen ten psychoidni kterej sem popsal ja))...

tmi napsal:
To Osiris : ale cela ta uloha je z principu dost spatna - totiz pokud je posloupnost zadana konecnym poctem prvku, tak teoreticky pro ni muze byt vice navzajem ruznych predpisu (a tim nemyslim jen ten psychoidni kterej sem popsal ja))...

To Osiris : jasne -> ale pak uz je mozna lepsi pouzit heuristiku zalozenou na prave ty podmnozine ruznych zakladnich posloupnosti (a ten predpis najit treba metodou nejmensich ctvercu nebo nejak podobne)

tmi napsal:
To Osiris : jasne -> ale pak uz je mozna lepsi pouzit heuristiku zalozenou na prave ty podmnozine ruznych zakladnich posloupnosti (a ten predpis najit treba metodou nejmensich ctvercu nebo nejak podobne)

to all.......................dekuji za oslobodeni mysle!off