Strona: [  << <   1 2   > >>  ]  z  2     
Autor Temat: funkcja Ackermanna
andrey
Łódź



Typ: neutral
Postów: 295
Zarejestrowany: Mar 2003
funkcja Ackermanna

Witam,
Zastanawiam sie nad mozliwosci napisania funkcji ackermana w VB, Sama postac rekurencyjna nie jest trudna do osiagniecia mnie zastanawia postac iteracyjna. Jak by wygladala? Moze ktos sie juz zetknal z takim problemem?
Pozdrawiam
Andrzej


_____________________________________________
http://www.carbondesign.pl/ - rowery poziome, trójkołówce, handbike-i, tuning, akcesoria

13-11-2004 01:40
Pokaż profil andrey  Wyślij email do andrey   Odwiedź stronę andrey       3078613
Chudy
[TLHW]Wiktor



Typ: moderator
Postów: 574
Zarejestrowany: Aug 2002

Hmm... Mam wrażenie jakbyś pisał językiem naukowym, za wiele z tego niestety nie rozumiem. Może ktoś mi wyjaśni ?


_____________________________________________
Projekt "Thunder Cannons" nadchodzi...

13-11-2004 15:59
Pokaż profil Chudy  Wyślij email do Chudy   Odwiedź stronę Chudy       1220895
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Rekurencyjnie rzeczywiście nie jest trudno, ale przy m = 4 w VB jest już "Out of stack space" .
Taka forma wyglada tak:
Function Ackermann(m As Long, n As Long)
    If (m < 0) Or (n < 0) Then Exit Function
   
    If m = 0 Then
        Ackermann = n + 1
    ElseIf n = 0 Then
        Ackermann = Ackermann(m - 1, 1)
    Else
        Ackermann = Ackermann(m - 1, Ackermann(m, n - 1))
    End If
End Function


Natomiast jeśli chodzi o formę iteracyjną, to jedyne co mi przychodzi do głowy, to metoda najbardziej klasyczna - użycie stosu...

Z tym, że nigdy nie przerabiałem rekurancji na iteracje, a na dodatek nie znam funkcji Ackermanna, więc tego nie zrobię...

[Post edytowany dnia 13-11-2004 16:18 przez marcin_an]


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

13-11-2004 16:01
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
andrey
Łódź



Typ: neutral
Postów: 295
Zarejestrowany: Mar 2003

Witam,
Wlasnie tez sie zastanawialem nad stosem ale czy uda sie to VB? Chyba niekoniecznie? Spotkales sie juz z kodem funkcji ackermanna zapisanej iteracyjnie w jakims innym jezyku moze byc w C/C++?

Chudy wcale nie mowie wyjatkowo naukowym jezykiem: Jezeli interesuje cie ta funkcja zerknij tutaj:
* http://www.brainyencyclopedia.com/encyclopedia/a/ac/ackermann_function.html#Use%20as%20benchmark
* http://www.modulaware.com/mdlt08.htm

Pozdrawiam
Andrzej


_____________________________________________
http://www.carbondesign.pl/ - rowery poziome, trójkołówce, handbike-i, tuning, akcesoria

13-11-2004 16:19
Pokaż profil andrey  Wyślij email do andrey   Odwiedź stronę andrey       3078613
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Implementacja stosu w VB jest banalna (kilka linii kodu), mogę napisać, tylko podaj dla jakiego typu danych ma on być..
A z iteracyjnym zapisem w innym jezyku się nie spotkałem. Przed chwilką znalazłem zapis rekurencyjny w C++, ale to już nas chyba w tym przypadku nie interesuje...

[Post edytowany dnia 13-11-2004 17:06 przez marcin_an]


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

13-11-2004 17:05
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Pozostaje jeszcze jeden problem - w czym przechować wynik, jeśli jako m podamy np. 4? Tego podstawowe zmienne VB już nie przechowają w żaden sposób..
Patrząc na te strony, które podałeś zauważyłem, że dla m<4 da się to zrobić liniowo, z prostego wzoru, więc jeśli i tak nie możemy przechować wyników dla m>=4, to może poprostu funkcja nie będzie ich obsługiwała?

[Post edytowany dnia 13-11-2004 17:10 przez marcin_an]


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

13-11-2004 17:09
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Posiedziałem nad tym i udało mi się przekształcić na inną formę. Nie jest to już postać rekurencyjna z programistycznego punktu widzenia (przynajmniej na pierwszy rzut oka tego nie widać), ale iteracyjna też jeszcze nie:
Private m_stack As New Stack
Private n_stack As New Stack
Private j_stack As New Stack

Public Function Ackermann(m As Currency, n As Currency) As Currency
    Dim tm As Currency, tn As Currency
    Dim ta As Currency
   
    tm = m: tn = n
   
ackermann_entry:
    If tm = 0 Then
        ta = tn + 1
    ElseIf tn = 0 Then
        m_stack.Push tm: n_stack.Push tn: j_stack.Push 1
        tm = tm - 1: tn = 1: ta = 0
        GoTo ackermann_entry
n0return:
        tm = m_stack.Pop: tn = n_stack.Pop
    Else
        m_stack.Push tm: n_stack.Push tn: j_stack.Push 2
        tn = tn - 1: ta = 0
        GoTo ackermann_entry
nmereturn0:
        tm = m_stack.Pop: tn = n_stack.Pop
        m_stack.Push tm: n_stack.Push tn: j_stack.Push 3
        tm = tm - 1: tn = ta: ta = 0
        GoTo ackermann_entry
nmereturn1:
        tm = m_stack.Pop: tn = n_stack.Pop
    End If
    Select Case j_stack.Pop
        Case 1: GoTo n0return
        Case 2: GoTo nmereturn0
        Case 3: GoTo nmereturn1
    End Select
    Ackermann = ta
End Function


Jak widać, tak naprawdę jest to inny zapis tego, co podałem wcześniej, tyle, ze teraz własnoręcznie obsługuję stos i mogę swobodnie wykonać 32767 zagłębień bez ryzyka, że dostanę "Out of stack space". Funkcję sprawdziłem dla (m,n) nal.do [0;3]x[0;5], porównałem wyniki z tym, co jest w tabelce i dla tych przedziałów się zgadza, a wykonuje się bardzo szybko. Dla (m,n)=(4,0) również działa prawidłowo. A(4,1) nie sprawdzałem, bo chociaż w teorii dałoby się to zrobić, to czas wykonywania byłby zbyt długi (w ciągu 6 minut na Celeronie872;192SDRAM;Win98SE mu się nie udało). A(4,2) i wyższych nawet nie próbowałem sprawdzać, ze względu na wynik, który w zabisie binarnym miałby co najmniej 8kB... o wymaganym rozmiarze stosu nawet nie będę myślał.

Wysuwam taki wniosek:
W tej postaci nie da się pod VB zapisać algorytmu obliczającego funkcje Ackermana dla argumentów spoza wspomnianego przedziału w rozsądnym czasie, a napisanie jej wiąże się ze zdefiniowaniem własnych procedur liczących (dodawanie/odejmowanie) dla liczb o rozmiarach wielu kilobajtów.
Natomiast temat wersji iteracyjnej pozostaje otwarty. Narazie nie znalazłem takiego zapisu dla innego języka.

---
Jeśli chodzi o obiekt Stack to może to być dowolna implementacja stosu obsługująca push/pop i typ zmiennych Currency jako argument. Ja napisałem taką klasę:
Private nData() As Currency
Private nItems As Integer

Public Sub Push(nVal As Currency)
    nItems = nItems + 1
    ReDim Preserve nData(nItems - 1) As Currency
    nData(nItems - 1) = nVal
End Sub

Public Function Pop() As Currency
    If nItems = 0 Then Exit Function
    Pop = nData(nItems - 1)
    nItems = nItems - 1
    If nItems > 0 Then ReDim Preserve nData(nItems - 1) As Currency
End Function



_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

14-11-2004 08:30
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

I krótkie uzupełnienie, które byćmoże zamknie toą dyskusję:
Przejrzałem trochę stron i wygląda na to, że ta funkcja wogóle nie ma szukanej przez nas postaci . Co nie znaczy wcale, że jej nie ma - może poprostu narazie jej nie odkryto .


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

14-11-2004 08:39
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
losmac
"profesorek"




Typ: neutral
Postów: 758
Zarejestrowany: May 2003

Na pierwszy rzut oka nie jest możliwe wykonanie funkcji Ackermann w formie iteracyjnej, ponieważ wynik samej funkcji zależy od niej samej (mam nadzieję, że to jest jasne).
Zauważcie, że dla:
-> m=3, n=1 funkcja aż 106 razy wywołuje się rekurencyjnie
-> m=3, n=2 funkcja aż 541 razy wywołuje się rekurencyjnie
-> m=3, n=3 funkcja aż 2432 razy wywołuje się rekurencyjnie
-> aż boję się myśleć jeśli jeden z argumentow funkcji przyjmie wartość >=4

Wniosek:
...???...


_____________________________________________
POSTULATY STARUSZKA:
1) Ludzie, dbajcie o polszczyznę!!!
2) Ludzie, zadawajcie kompletne pytania, a nie rzucacie ochłapy i trzeba się domyślać o co chodzi!!!

Powodzenia
Maciej Łoś

14-11-2004 12:41
Pokaż profil losmac  Wyślij email do losmac   Odwiedź stronę losmac  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Niezupełnie. Wiele (jeśli nie większosć) funkcji rekurencyjnych można przedstawić iteracyjnie, ale podobno funkcja Ackermanna jest własnie przykłądem takiej, której się nie da.
Próbowałem dla (m,n) = (4,1)... powinno wyjść 65 tysięcy z kawałkiem, ale się nie doczekałem wyniku, chociaż funkcja chodziła ponad 6 minut... po 6 minutach at wynosiło około 6000, czyli można zgadywać, że do 65k doszłoby po ponad godzinie, jeśliby się stos nie przepełnił.


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

14-11-2004 13:40
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Widzę, że jestem osobą najbardziej zainteresowaną tym wątkiem nawet bardziej niż jego autor .

Przechodząc do konkretnych spraw:
Rozpisałem sobie naszą funkcję na zależności międzykomórkowe i nie dosć, ze od razu złapałem jak wygląda, to już widzę, gdzie jest problem z iteracją .

Wynik mojej pracy dla argumentów ze zbioru [0;10]x[0;10] będzie dostępny do 21.11.2004 tutaj (format archiwum do wyboru, w środku .xls Excela 2000):
http://www.enter.net.pl/www/marcin_an/ackermann.rar [2.14kB]
http://www.enter.net.pl/www/marcin_an/ackermann.zip [2.38kB]
http://www.enter.net.pl/www/marcin_an/ackermann.7z [1.91kB]

Jak widać (a jeśli nie widać, to patrz: wcześniejszy akapit), w zerowym wierszu wynik da się obliczyć wprost, wystarczy dodać 1 do indeksu kolumny. Teraz dopiero zaczynają się problemy. Każdy element z zerowej kolumny ma wartość taką jak sąsiad w jego prawym-górnym rogu. Niby nic trudnego, przecież to prosta zależność. I tu się zgadzam - jest prosta, jeśli tylko zna się wartość tego sąsiada . A jaka ona jest? Dla wszystkich komórek oprócz zerowego wiersza i kolumny zależność jest, mówiąc bardzo obrazowo (niematematycznie) taka:
Z wiersza znajdującego się nad komórką bierzemy wartość z kolumny o indeksie równym wartości komórki po lewej omawianej komórki.
Zatem mamy funkcję, która nie dość, że odwołuje się sama do siebie, to jeszcze wyznacza sobie indeksy komórek z argumentami dla siebie na podstawie siebie .

Przyjrzałem się też, jak powstaje wartość dla danej komórki. A powstaje ona w miarę prosto:
Dla przykładu weźmy komórkę [5,5]. Funkcja w kolejnych odwołaniach do siebie będzie schodziła na coraz wyższe wiersze jednocześnie wyznaczając sobie kolejne indeksy kolumn. Wreszcie dojdzie do wiersza 0 i komórki x, z której pobierze stałą już wartość (tzn. nie stałą, ale obliczaną wprost ze stałej) i radośnie wróci tą samą drogą do omawianej komórki. Koniec.

Wnioski, które wysnułem:
Obserwują, jak funkcja wyznacza sobie kolejne komórki zauważyłem co jest potrzebne do ich wyznaczenia. Mianowicie - komórka z lewej i wiersz pod spodem. A to oznacza, że potrzebujemy wiersze pod spodem wyznaczone do odpowiednich miejsc i wiersz, w którym jest nasza komórka wypełniony do tej komórki. Takie wypełnienie da się zrobić iteracyjnie. A to oznacza, że chociaż funkcja Ackermanna nie ma postaci w pełni iteracyjnej (jest podawana jako przykład funkcji, która ma tylko postać rekurencyjną), to byćmoże ("byćmoże" podkreślam podwójnie) da się zrobić funkcję częściowo iteracyjną. Największy problem, ktory powstaje, jest - gdzie znajdują się końce poszczególnych wierszy dla danej komórki. Na to pytanie odpowiedzi narazie nie znam. Jedyne, co przychodzi mi narazie do głowy to segmentowe uzupełnianie wierszy w razie potrzeby (wolno nam przecież). To nadal jest w dużej mierze rekurancja, ale byćmoże o wiele wydajniejsza od zapisu prostego.

---

Do osób, które czytały poprzednią wersję tego posta: wkradł się tam mały błąd przy odczycie indeksów (zamieniłem je miejscami) i z tego powodu wyszedł taki potworek, który w rzeczywistości chodziłby w nieskończoność .
Uproszczona wersja funkcji Ackermanna dla VB narazie też jest usunięta ze wzgledu na to, że jest jeszcze szansa załatwienia jej w inny sposób . Jeśli jednak ktoś ją chce - podam.


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

14-11-2004 17:30
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Popatrzyłem, popatrzyłem i uważam, że da się stworzyć algorytm, który będzie działał na zasadzie iteracyjnego uzupełnienia wierszy do komórki, która jest nam potrzebna do obliczenia komórki w następnym wierszu. Jednak i tak dla każdej kolejnej wyznaczanej komórki trzeba będzie wyznaczać kolejne itd, czyli niewiele zyskujemy, bo całość nadal będzie się opierała na zagłębianiu w kolejne poziomy.
Natomiast nie mam zamiaru się dalej nad tym zastanawiać z następujących powodów:
- ze wzgledu na wartości jakie przybiera funkcja, i tak niemiałbym jak sprawdzić algorytmu
- tworzenie tablicy zawierającej dane pochłaniałoby ogromne ilości zasobów, których nie tylko nie mam ja, ale sądzę, że narazie nikt nie ma. Trzeba poczekać, aż ktoś wynajdzie skuteczny i wymagajacy niewiele pamięci zapis dużych liczb.
- algorytm nie wnosiłby bardzo znaczącej poprawy w prędkości, za to zżerałby dużo więcej zasobów
- nie widzę praktycznego zastosowania dla funkcji Ackermanna, oprócz benchmarków, ale one wymagają właśnie wersji rekurencyjnej.
--
koniec
--


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

15-11-2004 00:36
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
andrey
Łódź



Typ: neutral
Postów: 295
Zarejestrowany: Mar 2003

Witaj marcin_an,
Dziękuję za odpowiedź i to jaką. Przepraszam ale przez ostatni czas nie było mnie w sieci i nie wiedziałem co sie dzieje zaraz wezme sie do analizy tego co przedstawileś. Wracając do stwierdzenia, że istnieje funkcja o postaci rekurencyjnej której nie da się przedstawić w postaci iteracyjnej to podobno udowodniono , że każdy proces rekurencyjny da się zastąpić procesem iteracyjnym.
Mówiłeś też coś o uproszczonej wersji tejże funkcji w VB byłbym też zainteresowany.
Pozdrawiam i bardzo dziękuję.
Andrzej

[Post edytowany dnia 15-11-2004 02:41 przez andrey]


_____________________________________________
http://www.carbondesign.pl/ - rowery poziome, trójkołówce, handbike-i, tuning, akcesoria

15-11-2004 01:35
Pokaż profil andrey  Wyślij email do andrey   Odwiedź stronę andrey       3078613
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Zastanawiałem sie nad jeszcze jedną możliwością:
Wiemy, że funkcja Ackermana w kolejnych "krokach" dochodzi wreszcie do zerowego wiersza. Gdyby za każdym przejściem pętli zagłębiać się o jeden poziom, az osiągnie się wiersz o indeksie 0, moznaby to uznać za iterację. Ale nie wiem, czy jest to wykonalne, spróbuję to zrobić wieczorem (siedze teraz na uczelni, nie mam VB i niezbyt dobrą atmosferę do pracy (nawet muzyki nie ma )).

Jesli jednak udowodniono, to byłoby ciekawe, bo podobno rzczywiscie istnieją funkcje, których nie da się przedstawić iteracyjnie. No chyba, że coś się zmieniło ostatnio, a ja o tym nic nie wiem.

Uproszoczona wersja to tak naptawdę niemalże przeniesienie tabelki wartości A(m,n) dla m nal.do. [0;3] oraz par (4;0), (4;1) i (5;0). Niezbyt efektowne, ale zwazywszy na potrzeby - całkiem wystarczajace (chyba, ze rzeczywiscie potrzebujesz policzyć np. A(4,2) i otrzymać ośmiokilobajtowa liczbę ).
Spróbuje tutaj przedstawić jej kod, ale możliwe, że gdzieś zrobię błąd (brak edytora pod reką):

Function Ackermann(m As Long, n As Long) As Long
    If (m < 0) Or (n < 0) Then Exit Function

    Select Case m
    Case 0: If n < 2147483646 Then Ackermann = n + 1
    Case 1: If n < 2147483645 Then Ackermann = n + 2
    Case 2: If n < 1073741821 Then Ackermann = 2 * n + 3
    Case 3: If n < 28 Then Ackermann = 2^n * 8 - 3
    Case 4:
        Select Case n
        Case 1: Ackermann  = 65533
        Case 0: Ackermann = 13
        End Select
    Case 5:
        If n = 0 Then Ackermann = 65533
    End Select
End Function


W szczególności nie jestem pewien wartości w warunkach chroniących przed przepełnieniem zmiennej wyniku.


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

15-11-2004 15:07
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
andrey
Łódź



Typ: neutral
Postów: 295
Zarejestrowany: Mar 2003

Witam,
Zastanawiałem się właśnie nad tym samym. Muszę ci powiedzieć, że twoja tabela w excelu bardzo ulatwia wszelkie rozważania. Dla swoich potrzeb ja zmodyfikowałem dopisując wartości w części pól. Zastanawiałem się nad jedną dużą pętlą while aby zmniejszać włąśnie te kolejne wiersze do zera, ale niby miała by "m" przejść ale co do tego nie jestem przekonany. Zastanawiałem się nad Głębokością rekursji i ilością wewnętrznych wywołań. Wiem, że w postaci iteracyjnej nie ma raczej mowy o głębokości rekursji ale zastanawiam się nad zliczaniem ilości wywołań tych skoków strukturalnych GoTo.

Dzisiaj będę raczej późno w domu więc zajrzę tu koło 23.
Pozdrawiam
Andrzej


_____________________________________________
http://www.carbondesign.pl/ - rowery poziome, trójkołówce, handbike-i, tuning, akcesoria

15-11-2004 19:18
Pokaż profil andrey  Wyślij email do andrey   Odwiedź stronę andrey       3078613
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Dzisiaj ten problem chodzi za mną od rana . Do tej pory udało mi się stwierdzić, że nie da się zejśc wprost do zerowego wiersza i wypełnić go pętlą, bo żeby to zrobić... musimy wiedzieć, która jego komórka nam będzie potrzebna, a tego nie będziemy wiedzieli dopuki nie wypełnimy wiersza pod nim. Z kolejnym wierszem sytuacja się powtarza itd. To chyba wyklucza formę iteracyjną.. Zanim przejdę dalej, dorzucę jedną uwagę - do 3 wiersza włącznie wartosć komórki możemy ustalić na podstawie numeru jej indeksu, więc nie ma potrzeby schodzenia do wiersza zerowego. To może trochę ułatwić sprawę (ale nie bardzo). Przechodząc dalej: wpadłem na jeszcze jeden pomysł. Przypuśćmy, że mamy komórkę (m,n). Co możemy w tej chwili powiedzieć?
1) Żeby ustalić jej wartość będą nam potrzebne wartości z wierszy < m.
2) Potrzebna nam wartość na pewno będzie miała indeks kolumny większy od indeksu kolumny naszej komórki.
3) Potrzebne nam będą wartości wszystkich komórek po jej lewej stronie, czyli z tego samego wiersza i o indeksie kolumnowym mniejszem od jej własnego.
4) Żadna z komórek po jej lewej stronie ani pod nią nie będzie się odnosiła do komórki o indeksie kolumnowym większym niż ona sama.
Wynikają z tego następujące fakty:
(1) i (2): W pewnym momencie obliczeń potrzebne nam będą wszystkie komórki o adresach ze zbioru [0;0]x[m-1;n+1]
(3): W pewnym momencie będą nam potrzebne komórki o adresach [m;0]x[m:n-1]
(4): Narazie pozostaje tylko wskazówką.

Z pkt 1-3 wynika, które komórki na pewno będą nam potrzebne. Powiemy, że w jakiś sposób je sobie zaznaczamy, zapisujemy, wrzucamy na listę... żeby wiedzieć, że i tak to musimy obliczyć. To można uznać za etap I.

Przejdźmy do etapu II.
Ponieważ nie możemy iść od dołu w górę - idźmy od góry w dół. Wiersz 0 pomińmy, bo on wyznacza się wprost ze wzoru i nie ma sensu przechowywać nigdzie wartości jego komórek. Zacznijmy od wiersza 1. Możemy bez problemu wyliczyć w pętli kolejne jego komórki, aż do n+1 włącznie (kolumna następna po tej, w której jest nasza najważniejsza, "szukana" komórka). Etap II narazie przerywamy.

Etap III: Przechodzimy do wiersza o indeksie 2. Wyznaczamy tyle komórek, ile możemy - czyli do momentu, gdy któraś z komórek nie zacznie "domagać się" wartości z komórki wiersza 1, ale nie obliczonej jeszcze kolumny. Jeśli na taką trafimy, to dodajemy sobie do listy, że musimy wyliczyć wszystkie komórki od (1,n+1) do (1,x2) włącznie, gdzie x2 to kolumna, z której potrzebujemy wartość.
Przechodzimy do wiersza 3 i powtarzamy to wszystko. potem wykonujemy te same czynności dla wszystkich wierszy aż do m (włączajać w to także sam wiersz m). Gdy to skończymy - powtarzamy cały etap II i III od początku i tak w kółko, aż dojdziemy do naszej komórki. Ponieważ tego wcześniej nie zaznaczyłem - kolejne uzupełniania wierszy zaczynamy od komórki o indeksie kolumnowym o 1 większym od ostatnio uzupełnionej w tym wierszu. Przeciez poprzednie i tak mamy już uzupełnione w poprzednich przebiegach .

Teraz uwagi na temat tego rozwiązania
1) Trzeba skonstuować dobry system przechowywania adresów potrzebnych nam komórek, tak, by procedury wypełniajace wiersze mogły łatwo i szybko "dowiedzieć się", co wogóle mają wypełniać. Przy milionach adresów może się okazać, że nie bedzie im łatwo skompletować informacje na ten temat .
2) Gdzieś w opisie stwierdziłem, że trzeba zapisać adresy wszystkich komórek aż do tej potrzebnej. Można zauważyć, że nie jest to potrzebne, bo "idziemy po wierszach", czyli wystarczy nam informacja od kąd do kąd mamy wypełniać. To znacząco zmniejsza nam ilość przechowywanych adresów.
3) Pamięć operacyjna przeciętnego komputera nie będzie w stanie przechowywać potrzebnych danych - w szczególności wyników obliczeń. Już dla A(5,2) potrzeba - co często już wspominałem - ponad 8 kilobajktów pamieci.. wymagania te drastycznie rosną. Proponuję zatem zorganizowanie "pamieci danych" np. na dysku.
4) Zauważmy, ze po uzupełnianiu w danym wierszu dane z poprzedniego uzupełniania są nam już poprostu niepotrzebne (żadna z komórek nie będzie się już do nich odwoływała - wraz ze wzrostem indeksu kolumnowego szybko rośnie numer kolumny komórki z pobieranymi danymi). Można je usunąć, co zwolni miejsce dla kolejnych wartości. Potrzeby i tak będą rosły w zastraszającym tempie, ale wolniej niż bez tego.
5) Nie słyszałem o języku programowania, który byłby w stanie używać własnych zmiennych o tak wielkich rozmiarach. Dlatego trzebaby było stworzyć własny typ zmiennych i procedury do jego obsługi. Na szczęście musimy tylko dodawać i odejmować. To też się da zrobić prostą pętlą .


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

15-11-2004 22:42
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

6) ooo.. zauważyłem, że to chyba właśnie jest forma iteracyjna. Czy się mylę?

7) Pomysł wymaga jeszcze dużo pracy.
8) Wciągnęło mnie to .


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

15-11-2004 22:44
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
andrey
Łódź



Typ: neutral
Postów: 295
Zarejestrowany: Mar 2003

Witaj marcin_an,
Kurczę zaskoczyłeś mnie bardzo! Teraz muszę dokładnie przeanalizować twoją propozycję rozwiazania problemu.  Robi się coraz ciekawiej aż mam mały dreszczyk emocji ;-) Ostatnio delikatnie przerabiam kod który zasugerowałeś (mam na myśli ten używający stosu do przechowywania danych) Jest to dość powolny sposób zauważylem że na Pentium III 850 Mhz i 128 MB Ramu funkcja ackerman z m =4 i n = 1 wykonywała sie ponad 30 minu bez rezultatu. Nie chciało mi się dłużej czekać więc wyłączyłem program ale Ackerman z m = 3 i n = 10 wykonywał się coś koło 16 minut.

Mnie też wciągnęło to strasznie.
Pozdrawiam
Andrzej

[Post edytowany dnia 15-11-2004 23:55 przez andrey]


_____________________________________________
http://www.carbondesign.pl/ - rowery poziome, trójkołówce, handbike-i, tuning, akcesoria

15-11-2004 23:02
Pokaż profil andrey  Wyślij email do andrey   Odwiedź stronę andrey       3078613
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

Zostawię program na noc i zobaczę jaki da mi wynik.

Co do mojej propozycji: to narazie chyba tylko nakreslenie tego, jak taka procedura powinna działać. Ale jeśli będzie działać, to będzie też miała niewątpliwą przewagę nad swoją rekurencyjną poprzedniczką - nie będzie wykonywała kilkaset razy tych samych kroków . A jesli mowa o wykonywaniu tych samych kroków - dlaczego nie zapisać otrzymanych już liczb w tablicy i zamiast wykonywać tysiące razy to samo... poprostu pobrać już wyznaczoną wartość? Może coś przeoczyłem, ale to powinno znacznie przyspieszy działanie. Postaram się to jutro napisać (mówię tutaj o wersji, która widnieje na forum ).

[Post edytowany dnia 16-11-2004 00:12 przez marcin_an]


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

15-11-2004 23:39
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
marcin_an
Forumowicz




Typ: neutral
Postów: 1265
Zarejestrowany: Mar 2004

No i muszę cię jednak zmartwić. Przegląałem znowu strony o funkcji Ackermanna i okazuje sie, że chyba jednak ma ona postać iteracyjną... więc pewnie niczego nowego tu nie odkryjemy . Nadal nie znalazłem konkretnego kodu, ale obawiam się, że to jednak kwestia czasu...
Ale sam pomysł implementacji choćby wczesniejszej wersji (tej pół-rekurencyjnej) w VB jest ciekawy .

---

I dobra wiadomość:
Na Celeronie872 w 16 minut policzył A(3,10) i wyszła prawidłowa wartość .
A(4,1) liczy już od ponad 10 godzin. Szkoda, że nie dodałem do kodu robienia statystyk... może dostalibyśmy z tego jakieś ciekawe dane (np. maksymalnym użyciu stosu, które w tej chwili sięga 700 poziomów, ale nie wiem, czy nie wykorzystywał już więcej...).

---

Kolejne uzupełnienie:
Wykorzystał ponad 700 - w tej chwili jest ponad 24000 poziomów w stosie..

---

No i po 15 godzinach pracy stos przekroczył 32767 poziomów i zrobiło się przepełnienie .

[Post edytowany dnia 16-11-2004 15:16 przez marcin_an]


_____________________________________________
Jedzonko dla Google'a:
Forum na temat Visual Basic, C, C++, Pascal, Programowanie, API, PHP, VBA, VB.NET, QBasic, VBScript, Komputery
Moja strona o wszystkim

16-11-2004 00:03
Pokaż profil marcin_an  Wyślij email do marcin_an   Odwiedź stronę marcin_an  
Wszystkich odpowiedzi: 25 :: Maxymalnie na stronę: 20
Strona: [  << <   1 2   > >>  ]  z  2