Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Просьба пояснить код программы

Автор: Sideful 25.10.2007 21:24

ситуация такая

есть задача, условие которой - вывести на экран все перестановки чисел от 1 до n, без повторов

есть полностью рабочий код, но с одним небольшим, но существенно непонятным моментом

огромная просьба пояснить, каким образом строятся и выводятся на экран подстановки

ниже привожу код программы, часть требующую пояснения выделяю жирным шрифтом

program perestanovki;
uses crt;
const maxN=100;
type massiv=array[1..maxN] of integer;
type proverka=array[1..maxN] of boolean;
var
b,n,c:integer;
    w:massiv;
    a:proverka;
    otvet:char;

{ !!! начало непонятного кода !!! }

procedure print(a,b:integer;q:proverka);
var i,j:integer;
    otv:char;
begin
 b:=b+1;
 for i:=1 to a do
   begin
    if q[i]=false then
      begin
        w[b]:=i;
        q[i]:=true;
        print(a,b,q);
        q[i]:=false;
      end;
   end;
 if b=a then
  begin
   for j:=1 to a do write(w[j]);
   writeln;
  end;
end;

{ !!! конец непонятного кода !!! }

begin
 clrscr;
 b:=0;
 c:=0;
 repeat
  write('vvedite natural''noe chislo: ');
  readln(N);
  if n>maxN then writeln('chislo ne doljno prevyshat'' ',maxN);
  if n<=0 then writeln('chislo doljno byt'' polojitel''nym');
 until (n<=maxN) and (n>0);

 print(n,b,a);
 write('complete.. press any key..');
 readkey;
end.

заранее спасибо!

Автор: volvo 25.10.2007 21:33

Цитата
часть требующую пояснения выделяю жирным шрифтом
Жирным шрифтом не выйдет - выделяй комментариями...

Автор: Sideful 25.10.2007 21:41

готово smile.gif

Автор: volvo 25.10.2007 22:07

Обычный переборный алгоритм с возвратом: для того, чтобы перебрать все комбинации, используется массив чисел и массив Boolean-ов, который показывает, задействовано ли уже число в соответствующей позиции, или еще нет...

Перед изменением элемента помечаем его, как задействованный, далее - рекурсивный вызов самой процедуры Print (в которой заполнение продолжается, пока не будут использованы ВСЕ числа), после возврата из рекурсии - снимаем отметку о том, что данный элемент задействован (т.е, возвращаемся к первоначальному состоянию).

Для того, чтобы понять это - надо понимать, что такое рекурсия, и как она работает... Ты это знаешь?

Автор: Sideful 25.10.2007 22:22

Ну как я понимаю, есть исходный массив чисел, на его основе строим подобные ему массивы, но с иным расположением элементов.

То есть у нас есть исходный массив, на его основе формируем новый, используя все элементы исходногоsmile.gif

Но это только в моем понимании..

Еще одно для меня неясно.. в коде есть цикл с условиев for i:=1 to a

но переменная a же объявлена как логическая

каким же образом идете перебор?

p.s.: спасибо за отзывчивостьsmile.gif

Автор: volvo 25.10.2007 22:40

Цитата
но переменная a же объявлена как логическая
Не путай локальные переменные с глобальными... В данном случае у тебя A - локальная переменная типа Integer, которая перекрывает глобальный массив Boolean-ов...

Автор: Sideful 25.10.2007 22:53

тогда понятно

спасибо огромное за помощьsmile.gif