Я не понимаю рекурсию (чтобы понять рекурсию)

итерацию тоже нет... :-)
 
DE Deep Blue Sea #19.11.2008 21:13
+
-
edit
 

Deep Blue Sea

опытный
★☆
Вопрос к знатокам, мне нужно спрограммировать Regula Farsi - метод получения координаты пересечения графика функции с абсциссой в C++...
Причем два раза: в варианте с итерацией do - while и с рекурсией.

Принцип таков, выбираю левую и правую границу интервала, где я ищу нулевую точку. Если продукт функций обеих границ меньше нуля, то у меня там есть 0-точка. Если нет, то ухожу из программы...

Выбираю точность, с которой я ищу эту точку...

Потом провожу линию между обеими функциями границ и вычисляю точку пересечения этой линии с абсциссой. Смотрю на функцию этой точки и сравниваю ее модуль с моей точностью поиска. Если модулъ менъше точности, выдаю ответ, если нет, то эту точку пересечения я беру за новую левую или правую границу и повторяю процесс по-новой, до тех пор, пока моя аппроксимация не достигнет уровня точности, который я задал...

Сейчас программка работает, но выдает дебилъные результаты, спроситъ некого... С++ (м)учим всего 2 месяца.

Я извиняюсь за возможную неточность в терминах. После 9-го класса я математику учил исключительно на немецком...
Прикреплённые файлы:
RegulaF.C (скачать) [1,98 кбайт, 118 загрузок] [attach=124916]
 
 
Carpe noctem, quam minime credula postero  3.0.43.0.4
+
-
edit
 

Balancer

администратор
★★★★☆
На Питоне, как наследнике Бейсика :)

Рекурсия:
code python
  1. #!/bin/env python
  2. # coding: utf-8
  3.  
  4. precision = 1e-5
  5.  
  6. def sign(n):
  7.     if(n > 0): return 1;
  8.     elif(n < 0): return -1;
  9.     else: return n;
  10.  
  11. def solve(func, left_bound, right_bound):
  12.     middle_point = (left_bound + right_bound) / 2
  13.  
  14.     # Сразу проверяем выход из рекурсии по достижению результата
  15.     if abs(left_bound - right_bound) < precision:
  16.         return middle_point
  17.  
  18.     # теперь надо узнать, где у нас пересечение, слева или справа
  19.     # по разные стороны пересечения знак функции будет разный:
  20.     if sign(func(left_bound)) == sign(func(middle_point)):
  21.         # тогда пересечение правее средней точки:
  22.         return solve(func, middle_point, right_bound)
  23.     else:
  24.         return solve(func, left_bound, middle_point)
  25.  
  26. print solve(lambda x: x*x-1.0, 0.0, 3.0)

>>> 0.999999046326

Цикл:
code python
  1. #!/bin/env python
  2. # coding: utf-8
  3.  
  4. precision = 1e-5
  5.  
  6. def sign(n):
  7.     if(n > 0): return 1;
  8.     elif(n < 0): return -1;
  9.     else: return n;
  10.  
  11. def solve(func, left_bound, right_bound):
  12.     middle_point = (left_bound + right_bound) / 2
  13.     while abs(left_bound - right_bound) > precision:
  14.         middle_point = (left_bound + right_bound) / 2
  15.  
  16.         # теперь надо узнать, где у нас пересечение, слева или справа
  17.         # по разные стороны пересечения знак функции будет разный:
  18.         if sign(func(left_bound)) == sign(func(middle_point)):
  19.             # тогда пересечение правее средней точки:
  20.             left_bound = middle_point
  21.         else:
  22.             right_bound = middle_point
  23.  
  24.     return middle_point
  25.  
  26. print solve(lambda x: x*x-1.0, 0.0, 3.0)


>>> 1.00000190735

Во втором случае немного неуклюже (дважды считаем среднюю точку вначале) while вместо do-while, т.к. второго в Питоне нет :)
 
RU Balancer #20.11.2008 00:20  @Deep Blue Sea#19.11.2008 21:13
+
-
edit
 

Balancer

администратор
★★★★☆
A.K.> Сейчас программка работает, но выдает дебилъные результаты, спроситъ некого... С++ (м)учим всего 2 месяца.

У тебя:

Где в обеих функция вычисление f_von_xn?

Где в них же вычисления новых границ?

...

В общем, я бы за такое двойку поставил :D
 
DE Deep Blue Sea #16.01.2009 17:19
+
-
edit
 

Deep Blue Sea

опытный
★☆
Так. Проблемы в той же программе, что и в начале топика, но программа в значителъной степени доработана и исполъзованы классы. Никто толком ничего помочь не смог, так как никто ничего толком не понял. В моей программе использованы куски кода из образцового решения задачи. Когда запустил сам образец он выдал те же самые сообщения об ошибке, что и моя версия. Т.е. проф навалил дроф... на мой вопрос ответил "нету времени этим заниматься"...

Программа в идеале спрашивает сначала степень многочлена, затем отделъные коэффициенты. После чего она выдает таблицу значений от -1 до 1.

Параллелъно она считает количество выполненных циклов и обрывает программу, если их болъше положенного. Под конес она выдает данные счетчика и саму точку пересечения с абсциссой.

Из-за ошибки таблица получается неверная (описано внизу для многочлена x³ + 1 у которого Nullstelle ну никак не в начале координат).

Версия 5 программы без классов работала на ура... Версия 6... И теперь мне ее надо дополнить до версии 7 с новыми функциями, но если уже база глючная...

компиллируется g++ -o nullstelle Main.C Polynom.C

Вот ошибка:

deepblueseaDeepBlueSea:~/Übungen/6$ ./nullstelle
Programm zur Auswertung eines Polynoms mit dem Horner Schema
Geben Sie den Polynomgrad n ein: 3
Geben Sie den 3. Koeffizenten ein: 1
Geben Sie den 2. Koeffizenten ein: 0
Geben Sie den 1. Koeffizenten ein: 0
Geben Sie den 0. Koeffizenten ein: 1

x p(x)
-1.00000 0.00000
-0.90000 -0.24390
-0.80000 -0.39040
-0.70000 -0.45990
-0.60000 -0.47040
-0.50000 -0.43750
-0.40000 -0.37440
-0.30000 -0.29190
-0.20000 -0.19840
-0.10000 -0.09990
-0.00000 -0.00000
0.10000 0.10010
0.20000 0.20160
0.30000 0.30810
0.40000 0.42560
0.50000 0.56250
0.60000 0.72960
0.70000 0.94010
0.80000 1.20960
0.90000 1.55610
1.00000 2.00000
Schritt : 1
Schritt : 2
Das Polynom hat eine Nullstelle bei ungefaehr (nan, )
  • glibc detected *** ./nullstelle: double free or corruption (fasttop): 0x0000000000b6b010 ***
  • ======= Backtrace: =========
    /lib/libc.so.6[0x7f3a8f617938]
    /lib/libc.so.6(cfree+0x76)[0x7f3a8f619f86]
    ./nullstelle[0x401480]
    ./nullstelle[0x400f20]
    /lib/libc.so.6(__libc_start_main+0xe6)[0x7f3a8f5bc466]
    ./nullstelle[0x400c29]
    ======= Memory map: ========
    00400000-00402000 r-xp 00000000 08:08 2122192 /home/deepbluesea/Übungen/6/nullstelle
    00601000-00602000 r--p 00001000 08:08 2122192 /home/deepbluesea/Übungen/6/nullstelle
    00602000-00603000 rw-p 00002000 08:08 2122192 /home/deepbluesea/Übungen/6/nullstelle
    00b6b000-00b8c000 rw-p 00b6b000 00:00 0 [heap]
    7f3a88000000-7f3a88021000 rw-p 7f3a88000000 00:00 0
    7f3a88021000-7f3a8c000000 ---p 7f3a88021000 00:00 0
    7f3a8f59e000-7f3a8f707000 r-xp 00000000 08:05 466982 /lib/libc-2.8.90.so
    7f3a8f707000-7f3a8f906000 ---p 00169000 08:05 466982 /lib/libc-2.8.90.so
    7f3a8f906000-7f3a8f90a000 r--p 00168000 08:05 466982 /lib/libc-2.8.90.so
    7f3a8f90a000-7f3a8f90b000 rw-p 0016c000 08:05 466982 /lib/libc-2.8.90.so
    7f3a8f90b000-7f3a8f910000 rw-p 7f3a8f90b000 00:00 0
    7f3a8f910000-7f3a8f926000 r-xp 00000000 08:05 467005 /lib/libgcc_s.so.1
    7f3a8f926000-7f3a8fb26000 ---p 00016000 08:05 467005 /lib/libgcc_s.so.1
    7f3a8fb26000-7f3a8fb27000 r--p 00016000 08:05 467005 /lib/libgcc_s.so.1
    7f3a8fb27000-7f3a8fb28000 rw-p 00017000 08:05 467005 /lib/libgcc_s.so.1
    7f3a8fb28000-7f3a8fbac000 r-xp 00000000 08:05 467016 /lib/libm-2.8.90.so
    7f3a8fbac000-7f3a8fdab000 ---p 00084000 08:05 467016 /lib/libm-2.8.90.so
    7f3a8fdab000-7f3a8fdac000 r--p 00083000 08:05 467016 /lib/libm-2.8.90.so
    7f3a8fdac000-7f3a8fdad000 rw-p 00084000 08:05 467016 /lib/libm-2.8.90.so
    7f3a8fdad000-7f3a8fe9e000 r-xp 00000000 08:05 1542548 /usr/lib/libstdc++.so.6.0.10
    7f3a8fe9e000-7f3a9009e000 ---p 000f1000 08:05 1542548 /usr/lib/libstdc++.so.6.0.10
    7f3a9009e000-7f3a900a5000 r--p 000f1000 08:05 1542548 /usr/lib/libstdc++.so.6.0.10
    7f3a900a5000-7f3a900a7000 rw-p 000f8000 08:05 1542548 /usr/lib/libstdc++.so.6.0.10
    7f3a900a7000-7f3a900ba000 rw-p 7f3a900a7000 00:00 0
    7f3a900ba000-7f3a900d9000 r-xp 00000000 08:05 466962 /lib/ld-2.8.90.so
    7f3a902b6000-7f3a902b9000 rw-p 7f3a902b6000 00:00 0
    7f3a902d3000-7f3a902d8000 rw-p 7f3a902d3000 00:00 0
    7f3a902d8000-7f3a902d9000 r--p 0001e000 08:05 466962 /lib/ld-2.8.90.so
    7f3a902d9000-7f3a902da000 rw-p 0001f000 08:05 466962 /lib/ld-2.8.90.so
    7fff982c4000-7fff982d9000 rw-p 7ffffffea000 00:00 0 [stack]
    7fff983fe000-7fff983ff000 r-xp 7fff983fe000 00:00 0 [vdso]
    ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
    Aborted
    Прикреплённые файлы:
    Main.C (скачать) [702 байт, 82 загрузки] [attach=133635]
     
    Polynom.C (скачать) [1,9 кбайт, 95 загрузок] [attach=133636]
     
     
    Carpe noctem, quam minime credula postero  3.0.53.0.5
    DE Deep Blue Sea #16.01.2009 17:20  @Deep Blue Sea#16.01.2009 17:19
    +
    -
    edit
     

    Deep Blue Sea

    опытный
    ★☆
    header
    Прикреплённые файлы:
    Polynom.h (скачать) [562 байт, 94 загрузки] [attach=133637]
     
     
    Carpe noctem, quam minime credula postero  3.0.53.0.5
    +
    -
    edit
     

    carlos

    опытный

    Длинное и нудное лирическое отступление, многабукав. Читать не обязательно - здесь автор пытается убедить себя и читателей, что он не полный м---к и дебил. :-)

     [показать]


    Суть. Visual Basic 6. Нужно прошерстить некую директорию Input, включая все ее вложенные поддиректории, выбрать файлы и произвести с ними некие манипуляции. Ну пусть, для примера - надо имена всех обнаруженных файлов записать в текстовый файл.

    Объект командная кнопка для запуска сканирования директории Input:

    code text
    1. Private Sub Command1_Click()
    2. Dim InputDirName As String 'переменная для хранения пути к директории Input
    3. InputDirName = "C:\input\"
    4. ScanDir InputDirName
    5. End Sub


    Подпрограмма ScanDir:

    code text
    1. Sub ScanDir(Dirname As String)
    2. Dim X As Long
    3. Dim FileName As String 'переменая для хранения имени элемента
    4. X = FreeFile
    5. FileName = Dir(Dirname, vbDirectory) 'получаем первый элемент содержимого директории
    6. Do While FileName <> "" 'начало цикла
    7. If FileName <> "." And FileName <> ".." Then 'игнор текущей директории и вышестоящих директорий
    8. 'если элемент - не директория, то
    9. If (GetAttr(Dirname & FileName) And vbDirectory) <> vbDirectory Then
    10. 'ioe?uoea eoiaiaiai oaeea ia caienu
    11. Open App.Path & "\itog.txt" For Append As #X
    12. Print #X, FileName
    13. Close #X
    14. Else
    15. 'иначе (т.е. если элемент - директория) запускаем рекурсивно ScanDir в этой вложенной директории
    16. Dirname = Dirname & "\" & FileName
    17. ScanDir Dirname
    18. End If
    19. End If
    20. FileName = Dir() 'получаем следующий элемент
    21. Loop 'конец цикла
    22. End Sub


    Причем если без этого куска с рекурсией:

    code text
    1. Else
    2. Dirname = Dirname & "\" & FileName
    3. ScanDir Dirname


    - то все работает, в файле itog.txt создается список файлов из директории Input, но без сканирования поддиректорий. А надо, чтобы их тоже проверять.

    И как быть этому человеку? :-)
     4.04.0
    +
    +1
    -
    edit
     

    Mishka

    модератор
    ★★☆
    carlos> И как быть этому человеку? :-)
    Проблема в том, что используется ф-ция Dir(Dirname, vbDirectory) и Dir() — эта ф-ция имеет внутреннее состояние — с параметрами вызвал — установил что-то, без параметров — продвинулся. Когда в рекурсивном вызове ты ещё раз её вызываешь, то контескт (внутреннее состояние) лошаемшь новой установкой. А по возвращении для того контектса уже всё исчерпано и, соответственно, ничего обходить больше не получается. Выхода два:
    1. Сохранять контекст в локальной переменной (не знаю, позволяет ли Васец это делать).
    2. Организовать очередь LIFO или FIFO и добавлять в неё полный путь директории (Dirname & "\" & FileName) при этом в директорию не лезть, пока не прошёл полностью все файлы (файлы печатаются, а директории собираются в очередь). Очередь глобальна или передаётся параметром с правом модификации. FIFO или LIFO будет только отличать порядок обхода. Если надо по уровням иерархии слева на право, то FIFO.
     6.06.0

    Mishka

    модератор
    ★★☆
    VB - List All The Files In A Directory-VBForums — есть примерчик примерно такой же, как твой, но с использованием системных ф-ций
    Private Declare Function FindFirstFile Lib "kernel32" Alias "FindFirstFileA" (ByVal lpFileName As String, lpFindFileData As WIN32_FIND_DATA) As Long
    Private Declare Function FindNextFile Lib "kernel32" Alias "FindNextFileA" (ByVal hFindFile As Long, lpFindFileData As WIN32_FIND_DATA) As Long
    Private Declare Function GetFileAttributes Lib "kernel32" Alias "GetFileAttributesA" (ByVal lpFileName As String) As Long
    Private Declare Function FindClose Lib "kernel32" (ByVal hFindFile As Long) As Long

    Которые контекст имеют (lpFindFileData) в качестве параметра, а значит это можно объявить локальной переменной и хранить на каждом витке рекурсии своё, не мешаю чужому.
     6.06.0

    carlos

    опытный

    Mishka> Когда в рекурсивном вызове ты ещё раз её вызываешь, то контекст (внутреннее состояние) ломаешь новой установкой. А по возвращении для того контекста уже всё исчерпано и, соответственно, ничего обходить больше не получается.

    Черт, мог бы и сам догадаться. Читал же про Dir с параметром и без.

    Спасибо! :)
     4.04.0

    в начало страницы | новое
     
    Поиск
    Настройки
    Твиттер сайта
    Статистика
    Рейтинг@Mail.ru