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

Тема в разделе "Pascal and Delphi", создана пользователем sima12, 16 дек 2012.

  1. sima12

    sima12 New Member

    Регистрация:
    14 дек 2012
    Сообщения:
    2
    Симпатии:
    0
    Подскажите пожалуйста, как можно реализовать данное задание, используя 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
    Код (Delphi):
    [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)
     
  2. sinkopa

    sinkopa Well-Known Member

    Регистрация:
    17 июн 2009
    Сообщения:
    344
    Симпатии:
    9
    Что именно Вас смущает? :)
    l1 - остаток веревки после предыдущего "обрезания"
    ss[j-1] - расстояние между гвоздями.
    2*p - длина куска веревки, требуемая чтобы обернуть через 1-й и 2-й соседние гвозди и завязать.
    По моему тут все логично...
     
  3. sima12

    sima12 New Member

    Регистрация:
    14 дек 2012
    Сообщения:
    2
    Симпатии:
    0
    Работает не всегда правильно(!
    А если я оборачиваю 1 ый гвоздь длиной p и 2ой так же, а потом получается, что я снова 2ой оборачиваю длиной p, не разрывая верёвки и далее третий, разумно ли это ?
     
  4. sinkopa

    sinkopa Well-Known Member

    Регистрация:
    17 июн 2009
    Сообщения:
    344
    Симпатии:
    9
    Как это "не разрывая верёвки"?... :)
    Выражение
    Код (Delphi):
    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 строчек читается... а если больше?
     
  5. sima12

    sima12 New Member

    Регистрация:
    14 дек 2012
    Сообщения:
    2
    Симпатии:
    0
    Спасибо большое за помощь!
     
Загрузка...
Похожие Темы - Delphi ичный Перебор
  1. cybert
    Ответов:
    0
    Просмотров:
    90
  2. Shouldercannon
    Ответов:
    0
    Просмотров:
    151
  3. antares
    Ответов:
    0
    Просмотров:
    432
  4. Луиза
    Ответов:
    0
    Просмотров:
    294
  5. avizer
    Ответов:
    5
    Просмотров:
    726

Поделиться этой страницей