Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Object Pascal: кроссплатформенные технологии > перебор с возвратом

Автор: GOSHA_BL 8.6.2007, 10:49

заданы целые числа  A1,A2,..,An,An+1 (n<=10)Определить имеется уравнение
A1*X1+A2*X2+...+An*Xn=An+1 хотя бы одно решение при котором каждая из переменных X1,X2,..,Xn
равна 0 или единице. Найти все такие решения.
пример

1*1+2*0+3*0+4*1=5  вывод решения  1 0 0 1
1*0+2*1+3*1+4*0=5  вывод решения  0 1 1 0

нужно решить с помощью перебора с возвратом!!!!
мой текст программы (нужно процедуру 'init' сделать обязательно рекурсивной!!!!)
буду признателен если поможете до воскресенья!
жду ответа как соловей лета smile

Код


uses crt;
const n=4;
Type arr=array[1..n] of byte;
     mas=array[1..n+1] of byte;
var
    b:arr;
    a:mas;
    i,p,j:byte;

Procedure Print(b:arr);
var k,j,i:byte;
begin
for i:=1 to n do write(b[i]:2);
end;

function check(a:mas;b:arr):boolean;
begin
  for i:=1 to n do
   if a[i]*b[i]+a[i]*b[i]+a[i]*b[i]+a[i]*b[i]=a[n+1] then check:=true
                                                     else check:=false;
end;

procedure init;
begin
  for i:=1 to n do b[i]:=0;
  i:=0;
repeat
   if check(a,b) then Print(b)
                 else begin inc(i);
                            p:=1;
                            j:=i;
  while j mod 2 = 0 do begin
                            j:=j div 2;
                            inc(p);
                       end;
    if p<=n then b[p]:=1-b[p];
   end;
until p>n;
  readln;
end;

begin
   for i:=1 to n+1 do a[i]:=i;
   init;
end.

Про теги не забывай ...

Автор: volvo877 8.6.2007, 11:47

Так что-ли?

Код


const
  count = 4;

type
  arr = array[1 .. count] of byte;
  mas = array[1 .. count + 1] of byte;


function check(a:mas;b:arr):boolean;
var i, s: integer;
begin
  s := 0;
  for i := 1 to count do
    s := s + a[i] * b[i];
  check := (s = a[count + 1]);
end;

var
  values: mas;

procedure init(n : integer; mask: arr);
var i: integer;
begin
  if n = 0 then begin
    if check(values, mask) then begin
      for i := 1 to count do write(mask[i]:2);
      writeln;
    end;
  end
  else begin
    mask[n] := 1;
    init(n - 1, mask);
    mask[n] := 0;
    init(n - 1, mask);
  end;
end;

var
  the_arr: arr;
  i: integer;

begin
  for i := 1 to count do begin
    the_arr[i] := 0;
    values[i] := i;
  end;
  values[count + 1] := count + 1;

  init(count, the_arr);
end.

Автор: GOSHA_BL 8.6.2007, 12:06

да вроде так!! Спасибо большое!!
можете ли вы еще краткие комменты про переменные написать а то не совсем ясны переменные.(массив mask и values и the_arr-что там хранится),суть функции check,не очень понятна, как она работает.

Автор: volvo877 8.6.2007, 12:29

То, что у тебя хранилось в массиве A, у меня называется values, то что у тебя было B - это mask...

Цитата(GOSHA_BL @ 8.6.2007, 12:06

)

суть функции check,не очень понятна, как она работает.

Чего не понятно? Находишь суммы всех произведений a[i]*b[i], и проверяешь эту сумму на равенстве с последним элементом массива (там, где хранится сумма).... Поскольку проверка (на равенство) возвращает результат типа Boolean, его сразу можно рассматривать как результат функции, ни к чему добавлять еще один If.

Автор: GOSHA_BL 8.6.2007, 12:58

щас в пошаговом все посмотрел, все понял, еще раз спсибо!!
p.s меня просто эта строча смутла , мытак никогд не писали :(
"check := (s = a[count + 1]);"