С Новым годом! Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
1

Рекурсия с возвратом на бутылках) Подайте идею!

22.11.2012, 14:13. Показов 1757. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Люди добрые, прошу помощи, не для себя, для друга своего))))
по инету ходит олимпиадная задачка которую 3му курсу решили дать как домашнюю работу, сделать ее надо до завтра..
везде описание есть, решения конечно нет)
"По двум конвейерам двигаются молочные бутылки(один заполняет, другой закупоривает). Для каждой бутылки известно время заполнения и закупоривания. Найти расстановку бутылок, при которой время обработки минимально. "
создан файл содержащий n - количество бутылок и времена заполнения и закупоривания.
эти времена записаны в массивы X и Y размерностью n.
как быть с этими расстановками и рекурсией с возвратом? как это вообще работает?)
хоть какой-то псевдокод, чтобы было понятно в какую сторону лезть)
примерно ясно что надо как-то, прибавляя к сумме очередное Xi проверять, может если прибавим Xj время будет меньше... но тут еще Y. в общем непонятно)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Блог
22.11.2012, 14:13
Ответы с готовыми решениями:

Подайте идею
Вот задача: Задача Bracket. В сложных математических выражениях приходится иногда ставить много...

Рулетка - Подайте идею пожайлусто
Вот фото: Подайте пожалуйста идею как можно было бы сделать чтоб крутилась рулетка с...

Подайте идею для сайта
вот :

Подайте пожалуйста идею математического проекта
Доброго времени суток. Подкиньте пожалуйста идеи программ, связанные с математикой. Уровня 4го...

7
3944 / 1869 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
22.11.2012, 20:26 2

Не по теме:

Сейчас обдумываю. Зайдите позже.


Если файлы есть - выложите.
0
0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
22.11.2012, 20:35  [ТС] 3
входной файл
10 //N
15 //X1
20 //Y1
10 //X2
60 //Y2
40 //и т д
10
10
20
90
10
90
80
50
30
20
70
60
60
40
40

код:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
var X,Y:array of integer;//массивы времени   заполнения(X) и закупоривания(Y)
    n,i,sumX,sumY:integer;
    fin,fout: textfile;
begin
   AssignFile(fin, 'input.txt');//связываем файл с именем
   reset(fin);//подготавливаем для чтения
   readln(fin,n); //считываем количество бутылок и устанавливаем размерность массивов
   setlength(X,n);
   setlength(Y,n);
   i:=0;
   while(not eof(fin)) do
   begin
     readln(fin,X[i]);
     readln(fin,Y[i]);
     i:=i+1;
   end;
   closefile(fin); //закрываем файл
 
   readln;
end.

ну и все... дальше ступор
0
3944 / 1869 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
22.11.2012, 20:36 4
Вообще, предполагаю, что бутылки закупориваются после заполнения. Т.е. они должны двигаться по одному конвейеру, а автоматы должны стоять друг за другом. Так или нет?

Не по теме:

Страница сама не обновляется. Поэтому, нужно обновлять самому, чтобы увидеть выложенный ответ.

0
0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
22.11.2012, 20:48  [ТС] 5
так! получается что если время закупорки следующей бутылки больше чем заполнение предыдущей то мы теряем время и данная расстановка не оптимальна!
0
3944 / 1869 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
23.11.2012, 02:46 6
Описание я уже нашел. Только немного подумал.
Если бы время закупорки было прямо пропорционально времени налива - тогда всё проще - сортируем в порядке убывания времён. Буду думать дальше. А вы заходите позже, обдумаю - напишу функцию.

Добавлено через 5 часов 54 минуты
Вот, кажется так:
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils, Windows;
 
Type
  MyArr = Array Of Integer;
Var
  X,Y : MyArr; //массивы времени заполнения(X) и закупоривания(Y)
    Z : MyArr; //Массив текущего порядка
    R : MyArr; //Массив результирующего порядка
   mm : Integer; //Минимальное время пропуска всех бутылок
 
    n : Integer;
  fin : TextFile;
 
//----------------------------------------------------------
// Времена на момент обращения к процедуре
// Tw - Время заполнения,
// Tz - Время нужное ещё на закупоривание.
// ii - порядковый номер следующей бутылки (на конвейер).
//----------------------------------------------------------
Procedure MnM(Tw,Tz,ii:Integer);
var
  i,k,t : Integer;
begin
  For i:=0 To n-1 Do
  if (Z[i]>ii) Or (Z[i]=0) then
  Begin
    Z[i]:=ii;
    k:=X[i]-Tz; //Время ожидания тек. бут. под закупоривание после заполнения
    t:=Y[i];
    If k<0 Then
    //Если закрытие предыдущих длится дольше наполнения текущей
    Begin
      t:=t-k;
      k:=0;
    End;
 
    k:=Tw+k+X[i]; //Время заполнения бутылок до текущей включительно
 
    If ii<n Then
    MnM(k,t,ii+1) Else
    If (k+t)<mm Then
    Begin
      mm:=k+t;
      For k:=0 To n-1 Do
      R[k]:=Z[k]; //Запоминаем последовательность меньшего результата
    End;
    Z[i]:=0;
  End;
End;
 
Var
  i,j : Integer;
begin
  //Если после переключения русские буквы показываются неверно,
  //следует открыть системное меню консольного окна - щелчком мыши в левом
  //верхнем углу окна консоли и выбрать:
  //Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
  SetConsoleCP(1251);
  SetConsoleOutputCP(1251);
 
  AssignFile(fin, 'input.txt');//связываем файл с именем
  Reset(fin); //подготавливаем для чтения
  ReadLn(fin,n); //считываем количество бутылок и устанавливаем размерность массивов
  SetLength(X,n);
  SetLength(Y,n);
  SetLength(Z,n);
  SetLength(R,n);
  i:=0;
  While(Not Eof(fin)) Do
  Begin
    Readln(fin,X[i]);
    Readln(fin,Y[i]);
    i:=i+1;
  End;
  CloseFile(fin); //закрываем файл
 
  //Перебираем варианты...
  mm:=MaxInt;
 
  For i:=0 To n-1 Do
  Begin
    For j:=0 To n-1 Do Z[j]:=0;
    Z[i]:=1;
    MnM(X[i],Y[i],2);
  End;
 
  //Выдаём результирующую последовательность...
  For i:=0 To n-1 Do
  Z[R[i]-1]:=i+1;
  // Здесь в массиве R - порядковые номера каждой бутылки
  // исходной последовательности в конечной последовательности:
  // 1-я - 4-ой, 2-1, 3-3, ... 10-я - 6-ой. (первая идёт четвёртой, вторая...)
  // В массиве Z - номера бутылок исходной последовательности в порядке их
  // выставления на конвейер: 1-ой - 8-я, 2-5, 3-3, ... 10-й - 7-я.
  // (первой идёт восьмая, второй...)
 
  WriteLn('Бутылки должны выставляться в следующей последовательности:');
  For i:=0 To n-1 Do
  WriteLn(Z[i]);
 
  WriteLn('Полное время разлива : ',mm);
 
  //Запишем в файл...
  AssignFile(fin, 'ouput.txt');//связываем файл с именем
  Rewrite(fin); //подготавливаем для записи
 
  For i:=0 To n-1 Do
  Begin
    WriteLn(fin,X[Z[i]-1]);
    WriteLn(fin,Y[Z[i]-1]);
  End;
 
  CloseFile(fin); //закрываем файл
 
  ReadLn;
  //Освободим память массивов
  Finalize(X);
  Finalize(Y);
  Finalize(Z);
  Finalize(R);
end.
Вложения
Тип файла: txt input.txt (82 байт, 12 просмотров)
Тип файла: txt ouput.txt (80 байт, 13 просмотров)
1
0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
23.11.2012, 10:59  [ТС] 7
Огромное спааааасибо! жажду выразить благодарность в виде небольшого пополнения счета если пришлете свой номер телефона!))))))

Добавлено через 8 минут
и еще хотелось бы услышать совет тоже по поводу рекурсии. )
дан файл с двоичными числами. надо перевести из в 10ю сс. и составить бинарное дерево: ключи - эти числа. информационное поле - путь к вершине. например:
6 (6)
4 (6->4) 9(6->9)
2 (6->4->2) 11 (6->9->11)


вот код:

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
type
  T_item = String; // здесь может быть любой тип
  P_Node = ^T_Node;
  T_Node = record
             info: T_item;
             key: integer;
             left, right: P_Node;
           end;
  var root: P_Node; // корень дерева
      fin,fout: textFile;
      n,m,dec,kPrev:integer;
      binStr,strByte:string;
 
 
// вспомогательная процедура
procedure PrintKey(t: P_Node);
begin
  write(t^.key: 5);
  write('/');
  write(t^.info);
end;
 
 
// обход сверху вниз     К-Л-П
procedure preorder(t: P_Node);
begin
  if t <> nil
    then begin
      PrintKey(t);  // обработать корневой узел
      preorder(t^.left);// обойти левое поддерево в нисходящем порядке
      preorder(t^.right);//обойти правое поддерево в нисходящем пор-ке
    end;
end;
 
// вставка элемента в дерево (рекурсивная процедура)
procedure InsertInTree(var t: P_Node; k: Integer; str:String);
begin
  if t = nil // если найдено место для нового узла
    then begin
           new(t); // распределяем память
           t^.left := nil; // устанавливаем пустые ссылки для левого и
           t^.right := nil; // правого поддеревьев
           t^.key := k; // заполняем ключевое поле
           t^.info := str;
         end // then
{иначе определяем, в каком поддереве узла t должен располагаться элемент с таким ключом}
    else
    begin str:=str+t^.info; //записываем путь к вершине
    if k <= t^.key // если новый ключ меньше или равен текущему
           then InsertInTree(t^.left, k,str) // вставим в левое поддерево
           else InsertInTree(t^.right, k,str); // а иначе – в правое
    end;
end;
 
 
function bin2dec(s:string):integer;      //  функция перевода числа из 2 СС в 10
var x,i:integer;
begin
  x:=0;
  for i:=1 to length(s) do
  begin
     x:=x+ord(s[i])-ord('0');
     if i<length(s) then x:=x*2;
   end;
   bin2dec:=x;
end;
 
function dec2bin(x:integer):string;            //из 10 в 2 сс
var s:string;
begin
  s:='';
  while x>0 do
  begin
     s:=chr(ord('0')+x mod 2)+s;
     x:=x div 2;
  end;
dec2bin:=s;
end;
 
begin
assignFile(fin,'input.txt'); //связываем файл с именем
reset(fin);  //открываем для чтения
readln(fin,n);      //считываем количество целых чисел в файле
readln(fin,m); //и количество бит
kPrev:=0;
while not eof(fin) do
begin
  readln(fin,binStr); //считываем число в двоичном представлении
  dec:=bin2dec(binStr); //переводим в 10ю сс
  strByte:=IntToStr(dec)+'-->';
  InsertInTree(root, dec,strbyte); //вставляем вершину с заданным ключом и инф полем
  kPrev:=dec;
end;
preorder(root); //root - корень дерева в котором ключи - числа заданные в файле и переведенные в 10ю сс
//а инф поле - путь к вершине
closeFile(fin);
readln;
end.
в процедуре вставки в дерево заполняется инф.поле. но видимо из-за того что пробегается много уровней рекурсии(туда +возврат) в инф.поле неверно записывается путь... можете запустить посмотреть и посоветовать как же этого избежать...
0
3944 / 1869 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
24.11.2012, 16:18 8
Вот исправил всё. Немного подправил, чтобы отображение было получше. С деревьями работал очень мало, поэтому быстро не получилось.
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
program Project2;
 
{$APPTYPE CONSOLE}
 
uses
  SysUtils;
 
type
  T_item = String; // здесь может быть любой тип
  P_Node = ^T_Node;
  T_Node = record
             info: T_item;
             key: integer;
             left, right: P_Node;
           end;
  var root: P_Node; // корень дерева
      fin: textFile;
      n,m,dec:integer;
      binStr,strByte:string;
 
 
// вспомогательная процедура
procedure PrintKey(t: P_Node);
begin
  writeln;
  write(t^.key: 5);
  write('/');
  write(t^.info);
end;
 
// обход сверху вниз        К-Л-П
procedure preorder(t: P_Node);
begin
  if t <> nil then
  begin
    PrintKey(t);  // обработать корневой узел
    preorder(t^.left);// обойти левое поддерево в нисходящем порядке
    preorder(t^.right);//обойти правое поддерево в нисходящем пор-ке
  end;
end;
 
// вставка элемента в дерево (рекурсивная процедура)
procedure InsertInTree(var t: P_Node; k: Integer; str:String);
begin
  if t = nil Then
  // если найдено место для нового узла
  begin
    new(t); // распределяем память
    t^.left := nil; // устанавливаем пустые ссылки для левого и
    t^.right := nil; // правого поддеревьев
    t^.key := k; // заполняем ключевое поле
    t^.info := str;
  end else
  {иначе определяем, в каком поддереве узла t должен располагаться элемент с таким ключом}
  begin
    str:=t^.info+'-->'+IntToStr(k); //записываем путь к вершине
    if k <= t^.key then
    // если новый ключ меньше или равен текущему
    InsertInTree(t^.left, k,str) // вставим в левое поддерево
    else InsertInTree(t^.right, k,str); // а иначе – в правое
  end;
end;
 
function bin2dec(s:string):integer;      //  функция перевода числа из 2 СС в 10
var x,i:integer;
begin
  x:=0;
  for i:=1 to length(s) do
  x:=(x Shl 1)+ord(s[i])-ord('0');
  Result:=x;
end;
 
function dec2bin(x:integer):string;            //из 10 в 2 сс
var s:string;
begin
  s:='';
  while x>0 do
  begin
    s:=chr(ord('0')+(x And 1))+s;
    x:=x Shr 1;
  end;
  Result:=s;
end;
 
Var
  i,j : Integer;
begin
  assignFile(fin,'input.txt'); //связываем файл с именем
  reset(fin);    //открываем для чтения
  readln(fin,n); //считываем количество целых чисел в файле
  readln(fin,m); //и количество бит
  root:=Nil;
  For i:=1 To n Do
  begin
    If eof(fin) then Break;
    readln(fin,binStr); //считываем число в двоичном представлении
    j:=Pos(' ',binStr); //В файле после пробела число в десятичной сс для наглядности
    If j=0 Then j:=Length(binStr)+1;
    If (j-1)>m Then j:=m+1; //Ограничение по количеству бит
    binStr:=Copy(binStr,1,j-1);
 
    dec:=bin2dec(binStr); //переводим в 10ю сс
    strByte:=IntToStr(dec);
    InsertInTree(root, dec,strbyte); //вставляем вершину с заданным ключом и инф полем
  end;
  preorder(root); //root - корень дерева в котором ключи - числа заданные в файле и переведенные в 10ю сс
  //а инф поле - путь к вершине
  closeFile(fin);
  readln;
end.
но видимо из-за того что пробегается много уровней рекурсии(туда +возврат) в инф.поле неверно записывается путь
Как вы говорите "рекурсии(туда +возврат)" здесь нет. Здесь происходит переход либо в левое поддерево, либо в правое. А по нахождении конца - записывается новый элемент. У вас и правда путь записывался неверно, потому, что на каждом уровне дерева к предыдущему пути добавлялся ещё путь к текущему узлу.
Delphi
1
str:=str+t^.info;
Т.е. путь к предыдущему узлу + путь к текущему узлу, который также включает путь к предыдущему узлу.
Кроме того такой красивый путь по нисходящей или восходящей - не получится. Почему покажу на примере:
Код
  363/363
  182/363-->182
    7/363-->182-->7
    2/363-->182-->7-->2
  341/363-->182-->341
  602/363-->602
  558/363-->602-->558
  526/363-->602-->558-->526
  942/363-->602-->942
  954/363-->602-->942-->954
Это отчёт по вводу чисел. Первые 4 идут по убыванию - здесь всё нормально. Следующий идёт сначала в левое поддерево до узла 182. А в этом узле добавляется правый подузел, поскольку новый ключ больше ключа узла. Поэтому путь получается сами видите какой.
1
24.11.2012, 16:18
BasicMan
Эксперт
19315 / 2622 / 84
Регистрация: 17.02.2009
Сообщений: 10,364
Блог
24.11.2012, 16:18
Помогаю со студенческими работами здесь

Подайте идею, как защитить видео
Есть сервис с видео-материалами, доступ к которым предоставляется только если у человека есть...

Подайте идею как реализовать мысль
Доброго времени суток! вопрос вот такого вида. идет подсчет строковых показателей на Количество...

Подайте идею для исправления знаков препинания
Всем привет. Задача: Создать программу, которая будет исправлять такой текст: Привет , меня...

Рекурсия с возвратом
Помогите пожалуйста,не понимаю, как тут использовать рекурсию. Найти маршрут обхода конем...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru