border=0

Rekursive funksjes

Foar fierdere konsideraasje sille wy in oantal definysjes nedich hawwe. Tink derom dat der twa sets binne X en Y.

As guon eleminten fan 'e set X oansluten binne mei unike definiearre eleminten fan' e set Y, dan sizze se dat in dielfunksje fan X oant Y oanbean wurdt.

De opset fan dy eleminten fan 'e set X, dy't oerienige eleminten yn Y hawwe, wurdt it domein fan' e definysje fan 'e funksje neamd, en de set fan dy eleminten fan Y, dy't oerienkomme mei de eleminten fan X, wurdt de set fan wearden fan' e funksje neamd.

As it domein fan in funksje fan X oant Y oerienkomt mei de set X, dan wurdt de funksje oeral definiearre.

It earste idee om in krekte definysje fan in algoritme oan te meitsjen dy't basearre is op it begryp fan in rekursive funksje dat is dat alle gegevens (fansels diskrete) mei natuerlike nûmers yn in bepaald nûmerssysteem kodearre wurde kinne en dan alle transformaasje wurde ferlege ta in ôfdieling fan komputearjende operaasjes, en it resultaat fan de ferwurking sil ek wêze in integer wêze. By dizze oanpak wurdt elke algorithm dat unifoarm is foar in beskate numerike funksje har wearde wearde, en har elemintêre stappen binne de gewoane arithmetyk en logyske operaasjes. Soksoarte funksjes wurde rekkenberamd neamd .

Tink derom dat der in klasse fan funksjes fan type y ( x 1, x 2 , ..., x n ) binne dy't funksjes binne dat alle arguminten fan 'e funksje x 1 , ..., x n binne integer, en de wearde fan' e funksje y wurdt ek as integer útdrukt. Mei oare wurden wurde funksjes beskôge as har arguminten en wearden diskrete binne.

In funksje y ( x 1 , x 2 , ..., x n ) wurdt effektyf ferwurde neamd as der in algoritme is dat syn wearde berekkene wurde kin út de bekende wearden fan 'e arguminten.

Sûnt it begryp fan in algoritme yn dizze definysje is yn in yntuitive sin nommen, wurdt it begryp fan in effektyf komputerbere funksje yntuitysk. Yn 'e oergong fan algoritme nei komputerbere funksjes ûntstiet lykwols ien tige wichtige omstannichheid. De set fan prosessen dy't de betingsten befetsje 1 - 5 fan klausel 7.1 en, dêrom, falle ûnder de yntuitive begryp fan in algoritme, is tige wiidweidich en net hiel sichtber. Yn tsjinstelling ta it opstellen fan komputerbere funksjes foar hiel ferskillende fersteaningen fan prosessen dy't de opsleine betingsten befetsje, wie itselde as itselde en, boppedat, maklik yn 'e gewoane wiskundige termen beskreaun. Dit krekt beskreaun set fan numerike funksjes, dy't oerienkomt mei de opset fan alle komputerbere funksjes mei it breedste ynsjoch fan 'e algoritme, dy't al bekend binne, wurdt de opset fan rekrektive funksjes neamd.

Elke algoritmyske model, wêrûnder rekkurzele funksjes, moat soargje foar it fêststellen fan 'e elemintêre stappen fan' e algoritme en metoaden foar it opstellen fan har in gewoane sesje fan transformaasjes dy't de nedige sekere fan data ferwurkjen leverje. Yn it rekursive model binne sokke "elemintêre stappen" de saneamde simpelste numerike funksjes S 1 , 0 n en I m n, in kombinaasje fan dy't hieltyd mear komplekt boude en wurde as folget:

S1 ( x ) = x + 1 - dit is in inkele (dat is, it hat ien argumint) direkte folgjende funksje;

· 0 n ( x 1 , x 2 ..... x n ) = 0 - dit is in n- plak funksje, identysk identysk as nul;

· Ik m n ( x 1 , ..... x n ) = x m (1 ≤ m ≤ n; n = 1, 2, ...) is de n-plakfunksje fan 'e identike werhelling fan' e wearde fan ien fan har arguminten.

De neikommende ienfâldige funksjes binne oeral definiearre en yntuitysk komputerber. Operaasjes binne boppe harren definiearre (hjirnei wurde se as operators neamd ), mei it eigendom dat har applikaasje op funksjoneel, yn 'e yntuitive sin komputer is, nije funksjes generearret, dy't ek wierskynlik rekkenber binne yn' e yntuitive sin. De partielfunksjes dy't kinne krije mei help fan dizze operators fan 'e ienfâldige funksjes wurde diels rekursyf neamd. De hypoteze fan 'e tsjerke is dat de klasse fan diels rekurvende funksjes op dizze manier oanbe>

Wy draaie no nei de behanneling fan operators dy't de transformaasje fan de ienfâldige funksjes leverje.

Superposysje fan dielfunksjes

Lit myn lokale funksjes wêze

wurde ferfongen yn 'e n-plakfunksje g (x 1 , ..., x n ). It resultaat is in n-plakfunksje .

Se sizze dat de funksje h is fan 'e funksjes g, f 1 , ..., fn troch superposysje (of troch subsydzje) ûntfongen. Sykynlik is sokke subtiltyken as neamd: S n + 1 (g, f 1 , ..., f n ), wêrby't de ynskrift hjirboppe it tal funksjes as arguminten ferfange.

As wy de funksjes g, f 1 , ..., f n berekkenje kinne dan de funksje h wurde ek berekkene. It is ek dúdlik dat as alle funksjes g, f 1 , ..., f n oeral oantsjutte binne, dan is de funksje h ek oeral definiearre. As de funksjes g, f 1 , ..., f n yntuktysk komputer binne, dan sil de funksje h intuitysk komputerber wêze .





Sjoch ek:

Foarbyld 4.6

Algemiene oanpak

Algoritmyske Postmasine

Foarbyld 9.5

Foarbyld 7.9

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info