Poradnik dla na100latek!!!

Temat: Rekurencyjny algorytm na pierwiastek
On 2004-12-03, Marcin (OSI) wrote:


| Witam,
| Potrzebuje rekurencyjny algorytm na znajdowanie pierwiastka kwadratowego.

ja zrobilem cos takiego:
jest to przyklad w C++

exp(1/x * log(y));

powyzsza linia pozwala wyliczyc pierwiastek n-tego stopnia z danej liczby
rzeczywistej gdzie:
x - stopien pierwiastka
y - liczba pierwiestkowana


Ladne, tylko ze najpierw trzeba umiec logarytmowac i podnosic liczby do
niecalkowitych poteg.


wynik zwracany jest typu float.


O, to ciekawe, bo moje exp() i log() zwracaja double.


ponizej masz definicje rownierz w C++ funkcji log() uzytej wczesniej


              również ---^^^^^^^^


float log(float x,float y)
{ float wynik=-1;
 float pot=0;

if (y==1) wynik = 0;
while (pot <= y)
{
wynik++;
pot = potega(x,wynik);
}
return wynik;
}

czy ta funkcja do konca dobrze liczy sam logarytm nie wiem bo to ppisal moj
kumpel i do konca sam nie wiem czy dobrze liczy.


A ile to bedzie log(10, 31.6)?


Ciekawe jest to ze wynik pierwistkowania jest dobry bo sam sprawdzalem
wielokrotnie na liczbach rzeczywistych,  calkowitych i na roznych
wartosciach stopnia pierwiastka.


Chyba nie przy uzyciu tej funkcji log(), ktora przytoczyles.


Źródło: topranking.pl/1276/rekurencyjny,algorytm,na,pierwiastek.php


Temat: Rekurencyjny algorytm na pierwiastek


Witam,
Potrzebuje rekurencyjny algorytm na znajdowanie pierwiastka kwadratowego.


ja zrobilem cos takiego:
jest to przyklad w C++

exp(1/x * log(y));

powyzsza linia pozwala wyliczyc pierwiastek n-tego stopnia z danej liczby
rzeczywistej gdzie:
x - stopien pierwiastka
y - liczba pierwiestkowana
to sa tylko przykladowe nazwy zmiennych mozesz je zmienic wedlug uznania
wynik zwracany jest typu float.

ponizej masz definicje rownierz w C++ funkcji log() uzytej wczesniej

float log(float x,float y)
{ float wynik=-1;
 float pot=0;

if (y==1) wynik = 0;
while (pot <= y)
{
wynik++;
pot = potega(x,wynik);


}
return wynik;
}


czy ta funkcja do konca dobrze liczy sam logarytm nie wiem bo to ppisal moj
kumpel i do konca sam nie wiem czy dobrze liczy.
Ciekawe jest to ze wynik pierwistkowania jest dobry bo sam sprawdzalem
wielokrotnie na liczbach rzeczywistych,  calkowitych i na roznych
wartosciach stopnia pierwiastka.

Mam nadzieje ze sie przyda.

Pozdrawiam


Źródło: topranking.pl/1276/rekurencyjny,algorytm,na,pierwiastek.php


Temat: rekurencja
Witam grupowiczow

Mam dosc banalny problem a jednak prosze o pomoc.Z gory dzieki.

Stworzya algorytm i zapisac go za pomoc? programu obliczaj?cy potege danej
liczby
w sposob rekurencyjny. wskazówka:

potega(x,n) = potega(x,n/2)*2 dla n parzystych
oraz
potega(x,n) = x*potega(x,n-1) dla n nieparzystych

Podrawiam


Źródło: topranking.pl/1280/rekurencja.php


Temat: PYTANIE????!


On Tue, 14 Dec 1999, Irek wrote:
Czy ktoś potrafi mi sensownie wytłumaczyć czym różnią się algorytmy
iteracyjne i rekurencyjne (może być na przykładzie)


Najprosciej przedlozyc to na przykladzie silni albo potegi o wykladniku
naturalnym. Przesledz przebieg takich oto fragmentow programu:

Function Silnia_Iteracyjnie(X : Word) : Word;
Var
  Temp : Word;
  Count : Byte;
Beg
  Temp:=1;
  For Count:=1 To X Do Temp:=Temp*Count;  
  Silnia_Iteracyjnie:=Temp;
End;

Function Silnia_Rekurencyjnie(X : Word) : Word;
Begin
  If X=1 Then Silnia_Rekurencyjnie:=1
    Else Silnia_Rekurencyjnie:=Silnia_Rekurencyjnie(X-1);
End;

Podstaw sobie za X jakas mala liczbe i przesledz w mysli albo na kartce
przebieg funkcji.

Pozdrawiam,
Michal


Źródło: topranking.pl/1301/79,pytanie.php


Temat: FFT - modyfikacja


Czy istnieje jakaś modyfikacja algorytmu FFT (Fast Fourier
Transform),
która nie zakładałaby, że ilość próbek jest potęgą dwójki?


Mało prawdopodobne, bo ww. ograniczenie wynika z rekurencyjnego
dzielenia tablicy na pół w trakcie pracy algorytmu


Wiem, że można dopełnić ciąg próbek odpowiednią ilością zer,
ale widmo, które powstaje przy takim podejściu jest inne, niż
te, które powstaje bez dodawania zer i z wykorzystaniem zwykłej FT


Widmo nie będzie takie same, bo jak dodasz do funkcji fragment, będący
funkcją stałą, to w oczywisty sposób zmieniasz funkcję, którą chcesz
analizować. Spróbuj użyć interpolacji do funkcji wejściowej tak, aby
dopasować ilość próbek do magicznego 2^N


Źródło: topranking.pl/1407/fft,modyfikacja.php


Temat: FFT - modyfikacja


| Czy istnieje jakaś modyfikacja algorytmu FFT (Fast Fourier
Transform),
| która nie zakładałaby, że ilość próbek jest potęgą dwójki?

Mało prawdopodobne, bo ww. ograniczenie wynika z rekurencyjnego
dzielenia tablicy na pół w trakcie pracy algorytmu


Próbowałem w przypadku tablicy o nieparzystej długości dzielić na pół
wszystko poza ostatnim elementem ale nie doszedłem do niczego co by było
n*log(n) :-(
Myślałem że ktoś może też tak próbował i mu się udało.


| Wiem, że można dopełnić ciąg próbek odpowiednią ilością zer,
| ale widmo, które powstaje przy takim podejściu jest inne, niż
| te, które powstaje bez dodawania zer i z wykorzystaniem zwykłej FT

Widmo nie będzie takie same, bo jak dodasz do funkcji fragment, będący
funkcją stałą, to w oczywisty sposób zmieniasz funkcję, którą chcesz
analizować.


No tak.


Spróbuj użyć interpolacji do funkcji wejściowej tak, aby
dopasować ilość próbek do magicznego 2^N


Albo zamiast interpolacji (nie wniosłaby jakichś śmieci do widma?), dodać
odpowiedniej
długości (powiedzmy d) początkowy wycinek wejściowego ciągu - po prostu
powtórzyć
dane aż będzie 2^n. Zaznaczam, że nie sprawdzałem tego :-)

pzdr.
MŚ.


Źródło: topranking.pl/1407/fft,modyfikacja.php


Temat: arcsinx
Adam 'aimsoft' Michalski napisał:


Jak najprościej rozwinąć w szereg potęgowy funkcję arcsinx? Chodzi mnie o
to, żeby dostać 'zwartą' postać, tzn.  nie wypisać kilka wyrazów lecz
napisać wzór ogólny z użyciem znaku sumy. Rozwijam w otoczeniu zera. Tak czy
inaczej przydałoby się znać wzór ogólny na k-tą pochodną funkcji arcsinx. I
właśnie (przechodzę do sedna sprawy) z tym mam problem. Rozpisałem sobie
kilka pochodnych ale jakoś nie widzę ładnej zależności, która mógłbym
następnie indukcyjnie wykazać...


Ależ proszę :

Problem jest dosyć prosty :
Pierwsza pochodna to 1/(1-x^2)^(1/2)
Kolejne pochodne to w mianowniku kolejne potęgi 3/2, 5/2, 7/2 itd
a w liczniki pochodne wewnętrzne.
Dla parzystych n w liczniku wszystkie 'x' są w nieparzystych potegach -dla x=0
pochodna jest równa zeru.
Dla nieparzystych n w liczniku wszystkie 'x' są w parzystch potęgach ( oraz
wyraz wolny !). wystarczy więc zająć się tylko zmianą wartosci wyrazu wolnego i
to wszystko

Algorytm jest więc taki:
1. Wszystkie parzyste pochodne w otoczeniu zera są równe zero
2. Dla nieparzystych n oblicz iloczyn m = 1*3*5....*(n-2)
   Pochodna w punkcie x=0 jest równa m^2, a kolejny wyrazy w rozwinięciu
   na szereg wynosi m^2/n!
   Mozesz również kolejne wyrazy obliczyc rekurencyjnie
    a(1)=1 ;  a(n) = a(n-2) *(n-2)^2/((n-1)*n)

 marian otremba


Źródło: topranking.pl/1842/arcsinx.php


Temat: TAAA... Linux gorszy?
On 23 Aug 1999 09:24:47 GMT, =?ISO-8859-2?Q?Rados=B3aw?= Gancarz

<fea@zeus.polsl.gliwice.plwrote:
A jeśli procedura trzyma zmienne lokalne w rejestrach właśnie (dosyć
często spotykane) ? Ciekawe, gdzie je przechowasz ?


W klasycznej rekurencji zmienne lokalne sie raczej dziedzicza z
poziomu na poziom i nie ma potrzeby ich mnozyc - taka natura
rekurencji...

Gdzieś je trzeba trzymać w wielu nietrywialnych algorytmach...
(Tak, wiem, są Sparce z rejestrami zawiniętymi w kółeczko, ale to
jeszcze mniej miejsca niż na stosie.)


Trzeba. tyle ze akurat w rekurencyjnych nie trzeba - natomiast natura
rekuencji jest w zasadzie nieograniczona glebokosc (a nieograniczonego
stosu poki co nie ma...). czyli warto zauwazyc ten fakt i zrezygnowac
z pamietania zbednych glupot - inaczej stack overflow...

Bredzisz. Da się bez sięgania prawą ręką do lewego ucha zrobić
rekurencję =język pozwala na rekurencję.


Zrob w Borland pascalu. on pozwala. tyle ze wywolanie rekurencyjne
traktuje jak zwykle i marnuje stos na potege - tylko nie pisz mi ze
dolozysz obsluge bledu przepelnienia stosu bo po pierwsze w asemblerze
zrobic mozna wszystko co sie chce, po drugie i tak w koncu ci miejsca
zabraknie...
[...]

Każda   rekurencja   jest   "rekurencją  inaczej"  jak  Ci  braknie  pa­
mięci/prądu/etc. ;-P


No wiec wlasnie dobrze zaimplementowana rekurencja jest odporna na
brak pamieci - obszar zarezerwowany dla funkcji przy pierwszym wolaniu
moze wystarczyc dla wszystkich kolejnych wywolan. Tyle ze rozwiazanie
tego nie jest trywialne, zwlaszcza jak funkcja poza soba sama ine
funkcje wola... Pradu zabraknac moze i bez rekurencji. jedyne czego
kazdej implementacji algorytmu rekurencyjnego zabraknac moze niehybnie
to czas :-((

Nieprawda (przynajmniej dla Pascala). BP nie trzymał na stosie rejestrów
(oprócz BP) - trzymał tam zwykłe ramki (parametry, zmienne lokalne,  ad­
res powrotu). Inna sprawa, że stos miał tylko w porywach do 64kB.


A ja o czyms innym pisalem? Wlasnie zmienne lokalne, adres powrotu -
dla kazdego wolania osobno, calkiem zbednie... I rekurencja dosyc
szybko sie konczy.

Źródło: topranking.pl/1330/taaa,linux,gorszy.php


Temat: Wyznacznik macierzy w c,


Lucas wrote:
Czesc wszystkim.
Mam prosbe czy ma ktos moze rekurencyjny algorytm obliczania
wyznacznika macierzy w c. Najlepiej jak by byl na tablicach
dynamicznych. Z gory dzieki.
Lukasz


Wyznacznik macierzy mozna obliczyc metoda rekurencyjna.
Przykladowo, jesli macierz jest dana jako:

A =

a11 a12 a13
a21 a22 a23
a31 a32 a33

to jej wyzncznik mozna obliczyc tak:

det(A) =  1*a11*A11 + (-1)*a12*A12 + 1*a13*A13

A11, A12, A13 to podwyznaczniki, które w tym przypadku liczy sie
nastepujaco:

A11 = a22*a33 - a23*a32
A12 = a21*a33 - a23*a31
A13 = a21*a32 - a22*a31

W ogólnym przypadku podwyznacznik A(i,j) jest
wyznacznikiem macierzy (minorem), która powstaje
z macierzy A przez skreslenie wiersza "i" i kolmny "j",
czyli u nas A11 jest wyznacznikiem takiej macierzy [A11]:

[A11] =

a22 a23
a32 a33

Ogólny wzór na wyznacznik macierzy A jest
dany jako:

det(A) = sum{ (-1)^(i+j)*a(i,j)*A(i,j) }

dla ustalonego "i" oraz j=1..n
lub dla ustalonego "j" oraz i = 1..n

Przy czym:

a(i,j) - element i,j macierzy
A(i,j) - podwyznacznik i,j (minor)
(-1)^(i+j) - minus jeden do potegi "i"plus "jot" :-)

Twoi zadaniem byloby wiec :

1. Sprawdzic jaki jest rzad macierzy, jesli jest n=1 to
    znaczy ze do procedury przyslano liczbe, i te liczbe trzeba zwrócic.
2. Jesli rzad macierzy jest n1, to w petli, np. dla j=1..n ukladasz
    mniejsze macierze (minory) i wysylasz je po kolei do procedury
   obliczajacej wyznacznik (robidsz rekurencje).

W pseudokodzie to bedzie mniej wiecej tak:

procedure det(A)

  n = rzad_macierzy(A);
  if(n==1) {
    return A[1,1];
  }

  // ELSE
  sum = 0;
  for(j=1..n) {
    A1j = A[ 2..n,  1..j-1..j+1..n ]
   sum = sum+det(A1j);
  }
  return sum;
end procedure det

Mniej wiecej tak... ;)


Źródło: topranking.pl/1406/wyznacznik,macierzy,w,c.php


Temat: Szybkie potegowanie


Stanislaw Sidor <elcom@kr.onet.plwrote:


: Zwracam sie z pytaniem: czy ktos zna szybki algorytm potegowania wyrazenia
: typu x^n gdzie x jest rzeczywiste a n calkowite (dla jezyka C) i na ogol wieksze
: od 6.
: Oczywiscie mozna mnozyc x n razy w petli lub mnozyc n/2 x i pomnozyc przez
: siebie uzyskane produkty a pozniej ewentualnie pomnozyc to przez x (jesli n
: bylo nieparzyste).
: Mozna tez tworzyc produkty czastkowe x^2, x^4 itd aby pozniej je
: zastosowac.

I to jest wlasciwa droga, a dokladniej - potegi tworzysz na biezaco
zgodnie z bitami wykladnika. To naprawde jest szybko, bo dla long int n
bedziesz mial co najwyzej 32 mnozenia. A to niewiele.

Czasem nieco szybszy jest rekurencyjny algorytm ktory:
1) jesli n jest pierwsze, to x^n=x*x^(n-1)
2) jesli n=pq to x^n=(x^p)^q, oba potegowania robimy powyzszym algorytmem.

Przy czym, dla prostego przypadku potegowania liczb rzeczywistych
to nie radze nawet probowac - te dwa zaoszczedzone mnozenia nie zrownowaza
komplikacji w programie.

: Chodzi mi o optymalizacje czasowa takiego dzialania, a co sie z tym wiaze
: nie zawsze zgrabny zapis w C jest czasowooptymalny.

Oj, optymalizowac to to trzeba w assemblerze. A w C mozesz sprobowac:

   wyn=1.0
   temp=x
   while (n0)
    {
     if ( (n&1) = 1) wyn*=temp;
     temp*=temp;
     n | 1
    }

lub
  temp=1
  mask=0x80000000 // n 32 bit
  for (i=0; i < 32; i++)
   {
     temp*=temp;
     if ( (n&mask) != 0)  temp*=x;
   }

to drugie w assemblerku znacznie ladniej by wyszlo, jeszcze jakby
usunac poczatkowe puste mnozenia  (1*1)

J.


Źródło: topranking.pl/1407/szybkie,potegowanie.php