С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
#1

Пример, подтверждающий что не любую итерацию можно заменить рекурсией - C++

05.10.2010, 23:36. Просмотров 4277. Ответов 45
Метки нет (Все метки)

Как известно(по некоторым источникам ) любую рекурсию можно представить в виде цикла, но не наоборот. Так вот, надо придумать пример, который будет наглядно показывать , что итеративный вариант единственно возможный в данном случае.
Я по этому поводу пока ничего вразумительного предположить не могу ..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2010, 23:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Пример, подтверждающий что не любую итерацию можно заменить рекурсией (C++):

Sleep(8000) - что значит? На что можно заменить в борланд с++? - C++
Не распознаёт Sleep(8000) . Если за комментировать пишет что f заданно но не используется. Как исправить? ...

на что можно заменить функцию? - C++
#include <vcl.h> #include <iostream.h> #include <iomanip.h> float yearzp(float z); //описание функции годовая 3/п const int m=20;...

Как можно найти итерацию, на которой происходит "access violation reading location"? - C++
Ситуация такая что имеется функция которая вызывается в цикле около 1 млн. раз, в какой-то из итераций выскакивает исключение "access...

Заменить любую группу пробелов одним - C++
помогите пожалуйста с лабой. необходимо сжать строку , заменив любую группу пробелов одним пробелом.Исходную строку и результат вывести...

из питона можно сделать что то вроде интерпритатора на любую ос ? - Python
со своим кодом(кодом питона), если да как это делается хотябы "направление"

Доказать, что любую целочисленную денежную сумму, большую 7 руб., можно выплатить без сдачи - C#
Доказать, что любую целочисленную денежную сумму, большую 7 руб., можно выплатить без сдачи трешками и пятерками. Для заданного числа n>7...

45
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
11.10.2010, 10:49 #31
Цитата Сообщение от easybudda Посмотреть сообщение
Вы, если знаете пример, когда итерацию нельзя рекурсией заменить, покажите - нам тоже интересно. А так - метафизика какая-то...
Ну или пусть объяснит, что имеет в виду, а мы там и сами додумаем
0
Евгений М.
1036 / 977 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
11.10.2010, 10:49 #32
Цитата Сообщение от KBAC Посмотреть сообщение
Как известно(по некоторым источникам) любую рекурсию можно представить в виде цикла, но не наоборот.
Эти источники говорят, что существует задача, которую можно решить рекурсивным методом, но невозможно (или пока не найден способ) решить итерационным методом.
Я правильно понял? Если да, то поделитесь с источниками. Там должен быть либо конкретный пример либо задача, которую можно решить рекурсией, но надо решить итерационным методом. Пока мне кажется, что источник - недостоверный.
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
11.10.2010, 11:16 #33
Евгений М.,
Видимо "некоторые источники" - препод вроде того, который говорил, что for на while не заменяется...
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
11.10.2010, 11:18 #34
Цитата Сообщение от silent_1991 Посмотреть сообщение
for на while
заменяется, как и наоборот. Но обе эти замены - наглядные пособия, как делать не надо. Поэтому в нормальных прогах ни один из этих циклов на другой не заменяется.
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
11.10.2010, 11:20 #35
taras atavin,
Спасибо, в той теме мы ТСу примерно так и ответили. Но препод-то настаивал, что не заменяется. Потому я и привёл здесь этот пример...
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
11.10.2010, 11:23 #36
Цитата Сообщение от Евгений М. Посмотреть сообщение
Я правильно понял
Наоборот. Имеется в виду существование задачи, которую можно решить иттеративно, но нельзя рекурсивно. Если задрать размерность, а память ограничить, то так оно и есть. Например, на слабых компах задача вычисления определителя матрицы 130*130 иттеративно через приведение к треугольнйо решается элементарно, а рекурсивно через разложение по строке не решается вовсе.
0
Patch
2277 / 492 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
11.10.2010, 11:31 #37
Цитата Сообщение от taras atavin Посмотреть сообщение
Например, на слабых компах задача вычисления определителя матрицы 130*130 иттеративно через приведение к треугольнйо решается элементарно, а рекурсивно через разложение по строке не решается вовсе.
А рекурсивно, через приведение к треугольной?
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
11.10.2010, 11:32 #38
taras atavin,
Опять же, я здесь это уже озвучивал, мне кажется, имеется ввиду "можно ли решить вообще", а не "решить на конкретной машине или с конкретными условиями".
0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
12.10.2010, 14:24  [ТС] #39
Так, вот что я почерпнул из ТВП:

(1)Тезис Тьюринга: "Всякий алгоритм может быть реализован на машине Тьюринга"
Доказательства этому утверждению НЕТ и НЕ может быть, т.к. само понятие алгоритма является неточным, неформальным.
(2)далее по Тьюрингу: Если для некоторой функции существует маш. Тьюринга, которая эту функцию правильно вычисляет, то эта функция называется вычислимой.
(3)по Чёрчу :
каждая стандартно заданная частично рекурсивная функция(ЧРФ) вычислима путем применения процедуры механического характера.
ЧРФ - множество всех арифметических рекурсивных функций.

по- моему, доказано только как быть не с арифметическими функциями ? или наверно для машины- то таковых НЕ существует ?

Добавлено через 3 минуты

Не по теме:

как оно туда ответилось 0_0

0
KBAC
1 / 1 / 0
Регистрация: 10.05.2010
Сообщений: 72
13.10.2010, 18:22  [ТС] #40
Так, вот что я почерпнул из ТВП:

(1)Тезис Тьюринга: "Всякий алгоритм может быть реализован на машине Тьюринга"
Доказательства этому утверждению НЕТ и НЕ может быть, т.к. само понятие алгоритма является неточным, неформальным.
(2)далее по Тьюрингу: Если для некоторой функции существует маш. Тьюринга, которая эту функцию правильно вычисляет, то эта функция называется вычислимой.
(3)по Чёрчу :
каждая стандартно заданная частично рекурсивная функция(ЧРФ) вычислима путем применения процедуры механического характера.
ЧРФ - множество всех арифметических рекурсивных функций.

по- моему, доказано. только как быть не с арифметическими функциями ? или наверно для машины- то таковых НЕ существует ?
0
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
18.10.2010, 18:46 #41
Если я не ошибаюсь то такую задачку ты сможешь реализовать только рекурсивно но не итеративно:

На шахматной доске стоит на какой либо клетке конь и нужно пройти по всем клеткам доски без повторов.
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
18.10.2010, 18:55 #42
Любую рекурсию можно заменить на цикл. Просто нужно для организации подобия рекурсивных вызовов применить стек
0
danfox
0 / 0 / 0
Регистрация: 05.10.2010
Сообщений: 10
18.10.2010, 21:47 #43
ты уверен что возможно решить данную задачу итеративно?
0
Nameless One
Эксперт С++
5777 / 3427 / 255
Регистрация: 08.02.2010
Сообщений: 7,448
19.10.2010, 04:44 #44
danfox, прочитай еще раз мое предыдущее сообщение. В качестве примера итеративной реализации рекурсивного алгоритма с помощью стека смотри вот этот пост. Также можешь погуглить статью "Реализация рекурсивных алгоритмов на основе автоматного подхода"
0
taras atavin
3570 / 1754 / 91
Регистрация: 24.11.2009
Сообщений: 27,567
19.10.2010, 05:38 #45
Любая рекурсия при исполнении всёравно превращается в неявный цикл.
0
19.10.2010, 05:38
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2010, 05:38
Привет! Вот еще темы с ответами:

Объяснить пример с рекурсией - C (СИ)
#include<stdio.h> void gg(int a,int b) { int i=0; if(a==20) return; printf("%d\n",a); printf("%d\n",b); gg(a+1,b-1); ...

Доказать, что любую денежную сумму, большую 7 руб, можно выплатить без сдачи трешками и пятерками - C (СИ)
в общем программа сделанная, но выдает такую ошибку: "function 'fdiv' should have a prototype". объясните новичку в чем проблема. #...

Доказать что любую целочисленную денежную сумму ,большую 7 руб. можно выплатить без сдачи трёшками и пятёрками. - Pascal ABC
1.Доказать что любую целочисленную денежную сумму ,большую 7 руб. можно выплатить без сдачи трёшками и пятёрками.Для данного n>7 найти...

Заменить цикл рекурсией - C (СИ)
Дана функция. float result(double x1, double e) { double x2; float temp; x2 = x1; Ufunction = function; Ufunction1 =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
45
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.