Учёба идёт полным ходом......

перваки уже задрали со своими паскалевскими лабами. для этого есть всякие rsdn.ru, forum.sources.ru итд

а критиковать тебя препод будет.

ух ты, сердитый какой )))

Хех, симпатично - у меня такая же тема для OB, только заместо fbpanel, pypanel и adesklets :)

Which font you're using, man? It's pretty nice. It looks like old dos fonts. Where can I download it?

Где найти хорошие темы для OB?

terminus

Музыкальный винигрет - зачёт:) Лаба - максимум "зачёт", но не "5" (чего только троекратное "k+1" стОит:))

2KirG0FF: Terminus

2Stalwart: http://themes.freshmeat.net/browse/1087/ ну и http://www.google.ru/search?q=openbox+themes

если первый раз в рекурсию передать 1 то будет трекратное k - 1, правда в другом месте :)

> 2KirG0FF: Terminus

Thanx a lot.

>если первый раз в рекурсию передать 1 то будет трекратное k - 1, правда в другом месте :)

А локальные переменные ещё не проходили значит?:)

>А локальные переменные ещё не проходили значит?:)

ты это имеешь в виду ?

procedure perm(k : integer);
var
    i, lk : integer;
begin
    lk := k + 1;
    if k = n then output(res, k)
    else for i := 1 to n - k do begin
    	res[lk] := del;
	perm(lk);
	add(res[lk]);
    end;
end;

как-то это не хорошо по-моему в рекурсивных процедурах лишнии переменные объявлять, они ведь стек кушают...

Симпатично, вот только шрифты сделаны так, что как буд-то двоятся.

>Симпатично, вот только шрифты сделаны так, что как буд-то двоятся.

? ....

Может это от слишком долгого смотрения в монитор ?

>ты это имеешь в виду ?

Угу:) Только я обычно предпочитаю

lk:=Succ(k);

>lk:=Succ(k);

OK, а что со стеком ?

>OK, а что со стеком

1) Не вижу тип для n, поэтому не могу знать максимальную глубину рекурсии

2) Если бережём стек для рекурсии, то и i, и lk нужно винести в глобальные ИМХО

1) Не вижу тип для n, поэтому не могу знать максимальную глубину рекурсии

n <= 30, хотя для перестановок 30 эл. у меня наверное даже винта не хватит :)

2) Если бережём стек для рекурсии, то и i, и lk нужно винести в глобальные ИМХО

стек, не бережём, просто имхо это в принципе нехорошо, хотя можно сделать локальную lk, неверное сделаю ) , а i глобальной никак нельзя объявить, она в рекурсии используется.

кстати, не подскажешь где можно поискать алгоритмы генерации перестановок с трудоёмкостью n! ? Мне мой немного громоздким кажется, но лучше я найти не смог ...

>> Симпатично, вот только шрифты сделаны так, что как буд-то двоятся.

> Может это от слишком долгого смотрения в монитор ?

Нет. Просто буквы сделаны как бы с тенью (типа выпуклые). Вот только смотрится это хорошо только вблизи, чуть дальше так получается, как буд-то нерезко.

Значок флага в трее это что?

>Значок флага в трее это что?

fbxkb

>а i глобальной никак нельзя объявить, она в рекурсии используется

Сорри, проглядел:) Но lk можно ведь завести глобальную?:)

А k и n после ввода где проверяется?

>Сорри, проглядел:) Но lk можно ведь завести глобальную?:)

ага, действительно можно, что-то я туплю сёдня ))

>А k и n после ввода где проверяется?

нигде, предпологается что введённые данные корректны

> стек, не бережём, просто имхо это в принципе нехорошо, хотя можно ? > сделать локальную lk, неверное сделаю )

Тогда уже лучше статическую локальную. Что-бы не засорять пространство имен.

>нигде, предпологается что введённые данные корректны

Слишком много необоснованных предположений:) а ещё и k<n должно быть, кажется, иначе цикл хрен знает куда заведёт:) надо бы и это проверять:)

>Тогда уже лучше статическую локальную.

В паскале? Каким образом? Я запамятовал, может через "типизированную константу" это и можно? но всё равно её лишний раз инициализировать нужно:)

>Что-бы не засорять пространство имен.

Оно и так "засорено"

>а ещё и k<n должно быть, кажется, иначе цикл хрен знает куда заведёт:) надо бы и это проверять:)

для генерации сочетаний да, k должен быть меньше n, но на скрине этого куска кода не видно, а в процедуре которая генерирует перестановки k у меня просто измеряет глубину рекурсии. Когда прцедура вызывается первый раз k = 0, и как только k достигает n алгоритм входит из рекурсии на шаг назад.

>Когда прцедура вызывается первый раз k = 0, и как только k достигает n алгоритм входит из рекурсии на шаг назад.

Это не спасёт:) Угадай, сколько шагов рекурсии произойдёт прежде чем k станет равно n, если k>n

>Это не спасёт:) Угадай, сколько шагов рекурсии произойдёт прежде чем k станет равно n, если k>n

n + 1 и на n + 1 - м шаге результат вычислений запишется в файл, после чего рекурсия пойдёт обратно.

>n + 1 и на n + 1 - м шаге результат вычислений запишется в файл, после чего рекурсия пойдёт обратно.

Не факт. Но спорить не стану:)

>Не факт. Но спорить не стану:)

шаг k-й, k=n :
    выполняется эта строчка :
    if k = n then output(res, k) 
    выход процедуру с k=(n-1)

возврат там где стрелочка:
    procedure perm(k : integer);
    var
        i : integer;
    begin
        if k = n then output(res, k)
        else for i := 1 to n - k {k = n-1; n-k = n-(n-1) = 1} do begin
    	    res[k + 1] := del; 
->	    perm(k + 1);     {i уже = 1 следовательно цикл исполняется }
	    add(res[k + 1]); {последний раз                            } 
        end;
    end;

после этого рекурсия вернётся к шагу где k=n-2 ну и дальше начнёт 
туда-сюда бегать пока не выполнится n! раз 

Я же сказал: не спорю:) Если k и n - знаковые - так и будет, а если беззнаковые - не получится. Потому и спрашивал про их тип:)

Спасибо, f0rk, ты показал мне, что и с прозрачностью в терминале можно нормально работать ;)

Любая рекурсия сводится к итерации.
А посему 2 совета:
1. Избавься от рекурсии вообще
2. Посмотри на implementation of next_permutation() in
/usr/include/c++/<version>/bits/stl_algo.h

======= Begin Of Example =========
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

using namespace std;

int main()
{
typedef vector<int> Vec;
Vec vec(10, 0);
for (size_t i = 0; i < vec.size(); ++i) {
vec[i] = i;
}
size_t i = 0;
while (next_permutation(vec.begin(), vec.end())) { ++i; }
cout << "Performed " << i << " permutations" << endl;
copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, " "));
cout << endl;
return 0;
}
======= End of Example ===========

xxx@yyy:~/src/tests/STL/perm$ g++ -O2 main.C
xxx@yyy:~/src/tests/STL/perm$ time ./a.out
Performed 3628799 permutations
0 1 2 3 4 5 6 7 8 9

real 0m0.124s
user 0m0.112s
sys 0m0.000s

-- Nick

музыка - пять, скрин - пять... ничего лишнего...

хы-хы

паскаль - язык будущего :))) фсем фтыкать в паскаль...

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

Лаба на паскале! Когда это было! Спасибо, поностальгировал :))

>переменные стек не кушают а кушают просто память как и в нерекурсивных функциях

Как ты себе это представляешь? Тебе же надо полностью сохранять/восстанавливать состояние процедуры/функции.

Хорошо! ;-)

>Симпатично, вот только шрифты сделаны так, что как буд-то двоятся.

Я кстати это в первую очередь откючил - четкие шрифты рулят

оффтоп: мне вот интересно, почему в универах преподают паскаль, а не си

2 Ubnormal (*) (24.11.2005 22:14:13)

> С тем же успехом можно сказать что лишний раз 1 прибавлять в рекурсивных функциях нехорошо - это ведь ресурсы CPU кушает.
_Лишний_ раз что-то делать в любом случае плохо.

> локальные переменные стек не кушают
Локальные переменные исключительно на стеке и живут

> стек кушают передаваемые функции параметры
Частично правда. Размер stack-frame существенно больше чем int.
Но я думаю Вы совсем не это имели ввиду...

-- Nick

2 yuko (*) (25.11.2005 7:43:41)
> оффтоп: мне вот интересно, почему в универах преподают паскаль, а не си
Ну это где как... Для меня паскаль закончился в СШ. Эх.. Давно это было :)

-- Nick

Вот это я понимаю, вот это чел! Хвастаться не треками (много ли их на экране поместится?), а сразу списком исполнителей! :) А что внутри Irish?

> оффтоп: мне вот интересно, почему в универах преподают паскаль, а не си

универы надо грамотные выбирать:
у нас был сначала ассемблер, потом си, потом си++

> кстати, не подскажешь где можно поискать алгоритмы генерации перестановок с трудоёмкостью n! ?

Ну ты даешь, парень!
Это же классика - Кнут тебе в помощь.
Можешь еще на algolist.manual.ru сходить...

> паскаль - язык будущего :))) фсем фтыкать в паскаль...

Кто отключил установку анабиоза?!
Он всего четверть века промариновался - ему еще лежать и лежать...

Просветите тёмного: это что за консольный проигрыватель такой?

>>Тогда уже лучше статическую локальную.

>В паскале? Каким образом? Я запамятовал, может через "типизированную константу" это и можно? но всё равно её лишний раз инициализировать нужно:)

Ну и что? Один раз. Это будет намного лучше чем новая автоматическая переменная в каждой следующей итерации рекурсии.