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

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

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

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

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

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

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

7
 Аватар для Одиночка
3944 / 1869 / 337
Регистрация: 16.03.2012
Сообщений: 3,880
22.11.2012, 20:26

Не по теме:

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


Если файлы есть - выложите.
0
0 / 0 / 0
Регистрация: 22.11.2012
Сообщений: 5
22.11.2012, 20:35  [ТС]
входной файл
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
Вообще, предполагаю, что бутылки закупориваются после заполнения. Т.е. они должны двигаться по одному конвейеру, а автоматы должны стоять друг за другом. Так или нет?

Не по теме:

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

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

Добавлено через 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  [ТС]
Огромное спааааасибо! жажду выразить благодарность в виде небольшого пополнения счета если пришлете свой номер телефона!))))))

Добавлено через 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
Вот исправил всё. Немного подправил, чтобы отображение было получше. С деревьями работал очень мало, поэтому быстро не получилось.
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;
Т.е. путь к предыдущему узлу + путь к текущему узлу, который также включает путь к предыдущему узлу.
Кроме того такой красивый путь по нисходящей или восходящей - не получится. Почему покажу на примере:
Code
1
2
3
4
5
6
7
8
9
10
  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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
24.11.2012, 16:18
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru