Delphi P-ичный Перебор

sima12

New member
14.12.2012
2
0
#1
Подскажите пожалуйста, как можно реализовать данное задание, используя p-ичный перебор.
В доску вбито N гвоздей (N<=20). Расстояния между соседними гвоздями
-натуральные числа, записанные в текстовый файл по одному в каждой строке.
Веревка длины L. Веревку нужно разрезать на несколько частей так, чтобы
каждой частью можно было связать какие-либо два соседних гвоздя и никакие два гвоздя не
были связаны более одного раза. На привязывание веревки к гвоздю уходит Р единиц
длины. Ввод P и L с клавиатуры. Вывод в текстовый файл все возможные
варианты соединения гвоздей частями веревки. Каждый вариант записать в виде строки,
состоящей из чисел 1, 2, 3, :, N (номера гвоздей), между которыми стоят пробелы (гвозди не
связаны) или знаки минус (гвозди связаны). Например, при N=4, L=19, P=1 и расстояниях между гвоздями 5, 10, 17 выходной
файл
может иметь вид:
1-2-3 4
1 2 3-4
Код:
[code]program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;
const n=20;
type mas = array [0..n] of integer;
var dv:mas;

procedure plus(ko:integer);
var i:integer;
begin
i:=ko;
while dv[i]=1 do
begin
dv[i]:=0;
dec(i);
end;
dv[i]:=1;
end;


var f,f1:TextFile; P,l,l1,i,j,per,g,m,k,ko,ind:integer;
ss,xx: array of integer;
b,a:boolean; str:string;
begin
assign(f,'input.txt'); assign(f1,'output.txt');
reset(f); rewrite(f1); SetLength(ss,19);
i:=0;
while not EOF(f) do
begin
readln(f,per);
ss[i]:=per;
inc(i);
end;
k:=i+1;m:=i;a:=false;
SetLength(ss,m); SetLength(xx,m);
ko:=trunc(exp((m)*ln(2)));
write('dlina verevki L='); readln(L); write('dlina na gvozd P='); readln(P);
for i:=0 to n do dv[i]:=0;
writeln('Vozmozhnie varianti:'); writeln;
repeat
l1:=l; ind:=0;
For j:=1 to m do
begin
if dv[j]=1 then
begin
if (l1-ss[j-1]-2*p)>=0 then
begin
b:=true;
l1:=l1-ss[j-1]-2*p;
xx[j-1]:=1;
end else begin b:=false;ind:=1; end;
end;
end; str:='';
if (b=true) and (l1=0) and (ind<>1) then
begin
for k:=0 to m do
begin
str:=str+IntToStr(k+1);
if (dv[k+1]=1) and (xx[k]=1) then str:=str+'-' else str:=str+' ';
end;
end;
if (str<>'') then
begin
writeln(f1,str);
writeln(str);a:=true;
end;
plus(m);
until dv[0]=1;
if not a then writeln('Net takix variantov!');
readln;
close(f);close(f1);

end.[code=delphi]
В данной реализации меня смущает (l1-ss[j-1]-2*p)
 

sinkopa

Well-known member
17.06.2009
344
4
#2
В данной реализации меня смущает (l1-ss[j-1]-2*p)
Что именно Вас смущает? :)
l1 - остаток веревки после предыдущего "обрезания"
ss[j-1] - расстояние между гвоздями.
2*p - длина куска веревки, требуемая чтобы обернуть через 1-й и 2-й соседние гвозди и завязать.
По моему тут все логично...
 

sima12

New member
14.12.2012
2
0
#3
Работает не всегда правильно(!
А если я оборачиваю 1 ый гвоздь длиной p и 2ой так же, а потом получается, что я снова 2ой оборачиваю длиной p, не разрывая верёвки и далее третий, разумно ли это ?
 

sinkopa

Well-known member
17.06.2009
344
4
#4
Работает не всегда правильно(!
А если я оборачиваю 1 ый гвоздь длиной p и 2ой так же, а потом получается, что я снова 2ой оборачиваю длиной p, не разрывая верёвки и далее третий, разумно ли это ?
Как это "не разрывая верёвки"?... :)
Выражение
Код:
l1:=l1-ss[j-1]-2*p;
это собственно и есть "процесс отрезания веревки"...
Думаю "глюк" надо в другом месте ловить.
Меня вот лично другое "смущает"...
1) Вижу цикл: for i:=0 to n do dv:=0;... НЕ вижу (может слепой? :D ) чтобы в dv хоть одна единичка хоть раз попала в коде...

2) Гвозди "связанные" уже у Вас как помечаются? xx[j-1]:=1; - так? я правильно понял? я чего-то не вижу чтобы после SetLength(xx,m); этот массив у Вас нулями инициализировался... Там в нем всякий мусор может быть (не только нули).

3) Я не знаю что у Вас в "input.txt" лежит, но..
(1) вот это SetLength(ss,19);
(2) потом в цикле ss:=per; inc(i);
(3) потом m:=i; SetLength(ss,m);
Это хорошо если из "input.txt" меньше 19 строчек читается... а если больше?