Автор Тема: Просчет рекурсий и итераций  (Прочитано 1463 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Просчет рекурсий и итераций
« : ДХТаРЫм 03, 2009, 12:33:52 am »
Хотел поинтересоваться существуют ли какие-либо методики для просчета итераций в циклах, если, например циклы вложенные (больше трех). Вот уже сколько раз сталкивался, изобретал различные механизмы (наверное колеса и велосипеды :fool:) чтобы не ошибиться, что где присваивается, что получает приращение и т.п. То таблицы рисовал пастами разных цветов, то рассматривал, напр. крайние случаи  и т.д., но вообще редко получается с первого раза, а бывает и часы уходят (а то и дни на рекурсии). Понимаю, что коммунизм в отдельно маленькой стране не изобрести, вот и хотел спросить, кто какие методики использует.
Когда вы с собой разговариваете, вы получаете информацию?

Оффлайн gigauser

  • Статский советник
  • *****
  • Сообщений: 976
  • Репутация: 20
  • Banned
Re: Просчет рекурсий и итераций
« Ответ #1 : ДХТаРЫм 03, 2009, 02:39:49 am »
делаешь флаг снаружи самого внешнего цикла = 0, на каждой итерации самого внутреннего - инкрементишь, что сложного-то?
Banned

Оффлайн Likyrg

  • .net developer
  • Надворный советник
  • *****
  • Сообщений: 470
  • Репутация: 16
  • Пол: Мужской
Re: Просчет рекурсий и итераций
« Ответ #2 : ДХТаРЫм 03, 2009, 10:53:02 am »
хз, от большого количества вложенных циклов мне помогает доля фукциональности в императивных языках (лямбда-выражения), а рекурсия... просто надо продумать - другого варианта не знаю
лучший способ в чём-то разобраться до конца — это попробовать научить этому компьютер (Кнут)

Оффлайн Alex_cs_gsp

  • Коллежский советник
  • *****
  • Сообщений: 505
  • Репутация: 7
  • Пол: Мужской
  • Нужно все ломать, чтобы строить...
Re: Просчет рекурсий и итераций
« Ответ #3 : ДХТаРЫм 04, 2009, 12:06:43 am »
хз, от большого количества вложенных циклов мне помогает доля фукциональности в императивных языках (лямбда-выражения), а рекурсия... просто надо продумать - другого варианта не знаю
Вот как подумать? Если, например, есть рекурсивная ф-я двоичного поиска со сдвиганием границ:

int BinarySearch(int *Mas, int left_border, int right_border, int key)
{
if(right_border-left_border==1)return -1;
if(Mas[((right_border+left_border)/2)-1]==key)return ((right_border+left_border)/2)-1;
if(Mas[((right_border+left_border)/2)+1]==key)return ((right_border+left_border)/2)+1;
if(Mas[(right_border+left_border)/2]==key)return ((right_border+left_border)/2);

if(Mas[(right_border+left_border)/2]>key)right_border=(right_border+left_border)/2;
else if(Mas[(right_border+left_border)/2]<key)left_border=(right_border+left_border)/2;

BinarySearch(left_border,right_border,key);
}

кто как додумается до строки возвратов, если ничего не было найдено (if(right_border-left_border==1)return -1;)?
Я, например, раньше рассматривал какой-нибудь произвольный случай и потом, вобщем-то начинал думать. Но при этом ашипки неизбежны. Сейчас я пользуюсь буквенным представлением, часто с рассмотрением крайних случаев, напр. для примера выше,

Если какое-либо значение лежит в диапазоне (min,max) то произвольным образом, n раз будет уменьшаться как правая, так и увеличиваться левая граница, и все-таки они где-то встретятся.
Что произойдет, если они встретятся - бесконечная рекурсия. Хорошо, тогда на каком шаге останавливаться? Можно рассмотреть произвольный кусочек X(i), key, X(i+1), X(i+2), где левая граница остановилась на X(i), правая на X(i+2), а key- значение которого не существует. При таком раскладе key меньше среднего X(i+1), тогда X(i+1) станет правой границей и  среднее будет уже X(i), а оно то меньше key, следовательно, это новое среднее X(i) и станет левой границей и вот мы пришли к тому, что было вначале, и получили переполнение стека.  Что будет, если несуществующий key справо? X(i),  X(i+1), key X(i+2). Левой границей станет X(i+1) и повторяется та же история.
Поначалу мне так мыслить достаточно тяжело, поскольку все=равно (ух-ты, это случайно) результат воспринимается на веру. Вот я и хотел узнать кто как, что просчитывает, стационарный ли это процесс, или кто как угодно, есть ли какие-нибудь общие рекомендации и т.п. Я предполагаю, кто давно програмит  тот по опыту ориентируется, а те, у кого его нету, на своих ошибках учатся. Вот я хочу на чужих поучится.

Когда вы с собой разговариваете, вы получаете информацию?