помогите разобраться в заданиях, задания на поиск в глубину Опции

[maksimla]

поиск в глубину обратный метод
Первое задание
Напишите идею решение рюкзака задание. Задание рюкзака. Есть n вещей, пронумерованы от 1 до n.
Каждая вещь имеет свою ценность ki и массу m (1<=i<=n).
Найдите самое ценное (если есть несколько то любой из них) вещие набор , которых общая масса не превышала max (со всеми i max>=mi).

Вот такая задачка. Скажите тут все эти данные откуда берутся с клавиатуры вводятся ?
Вещи называются как то или просто вещи 1, 2 и так далее?
Тут надо несколько вещей самых ценных написать в ответе или одну вещь ?
Как все это сделать методом поиска в глубину обратным методом?

То выходит если так то очень просто сперва сортируешь ценности вещь каждую в порядке уменьшения потом выводишь вещь самую ценную проверяешь на max и тогда выводишь на экран или если несколько вещей надо вывести то когда отсортируешь то тогда вещь сравнивается и постоянно прибавляется вес еще тех вещей до тех пор пока не превысят потом назад делаешь шаг и тогда на экран выводишь вещи самые ценные.


Второе задание
Есть n домино косточек(пластинок если на русском кажется так). Напишите функцию

 dlinnij(n: skolko; 
var A: plostinka): skolko 

, которая нашла длиннейший сложены по правилам домино ( домино пластинки соединяются по одинаковым очкам по сторонам ) длину цепочки.Может иметь внутриние процедуры и (или) функции.
Используйте такие общее типы

type skolko=1..28; 
     plostinka = array [0..6, 0..6] of boolean; 

А тут зачем тип boolean?
а тут что с клавиатуры вводится ?
тут как то надо сделать перебором с двух сторон подставлять пластинки как то наверное может объясните?

мне эти задания надо до 8 сделать этого месяца
и еще вот это задание подсчет чисел
но чего то все молчат там сейчас

[Unconnected]

Вот такая задачка. Скажите тут все эти данные откуда берутся с клавиатуры вводятся ?
Вещи называются как то или просто вещи 1, 2 и так далее?
Тут надо несколько вещей самых ценных написать в ответе или одну вещь ?
Как все это сделать методом поиска в глубину обратным методом?

Вот "мы" то откуда знаем?

Найдите самое ценное (если есть несколько то любой из них) вещие набор , которых общая масса не превышала max (со всеми i max>=mi).

Вещие - это что?

Сообщение отредактировано: Unconnected - 3.03.2009 13:37

[Lapp]

Сдается мне, что задача о рюкзаке решалась на Форуме... Поищи.
Что касается способа ввода - если он не оговорен жестко в задании, то выбери сам, какой тебе нравится. Я бы организовал текстовый файлик, пожалуй. Типа так:


100 (максимальный вес)
2 5 (вес и ценность вещи)
3 8
10 1

Завершать чтение можно по признаку конца файла.

[maksimla]

на форуме набрал в поиске рюкзак выдала пару тем таких по там не какого решения не было.
а как это так можно Завершать чтение можно по признаку конца файла.? я чего то такого не знаю можете написать как это так сделать ?
и я не представляю как потом будет считаться это

[maksimla]

я так вот что сделал только незнаю то или нето вывел на экран

program kuprine;
var d,r:text;
m,k:array [1..1000] of integer;
max,n,i,l:integer;
{procedure vda( f,g:integer);
begin
writeln('kk');
end;   }
begin
 assign(d, 'duom.TXT');
  assign(r, 'rez.TXT');
  reset(d);
  rewrite®;
  read(d,max);
  read(d,n);
  for i:=1 to n do
  readln(d,m[i],k[i]);
  for i:=1 to n-1 do
  if k[i]<k[i+1] then
     begin l:=k[i]; k[i]:= k[i+1]; k[i+1]:=l; l:=m[i]; m[i]:=m[i+1]; m[i+1]:=l; end;
     writeln(m[1],' ',k[1]);
     
  readln;
end.

Добавлено через 18 мин.
или вот так надо было

program kuprine;
var d,r:text;
m,k:array [1..1000] of integer;
max,n,i,l,z:integer;
{procedure vda( f,g:integer);
begin
writeln('kk');
end;   }
begin
 assign(d, 'duom.TXT');
  assign(r, 'rez.TXT');
  reset(d);
  rewrite®;
  read(d,max);
  read(d,n);
  for i:=1 to n do
  readln(d,m[i],k[i]);
  for i:=1 to n-1 do
  if k[i]<k[i+1] then
     begin l:=k[i]; k[i]:= k[i+1]; k[i+1]:=l; l:=m[i]; m[i]:=m[i+1]; m[i+1]:=l; end;
     z:=0;
     i:=0;
   for i:=1 to n do
   if m[i]+z<=max then
   begin
    z:=z+m[i] ;
     writeln(m[i],' ',k[i]);
     end;
     
  readln;
end.

но я непредставляю как это сделать пошаговым методом (поиск в глубину) обьесните что надо сделать как?
и что выводится на экран или в файл записыватя

[maksimla]

вот в процедуру записал еще я

program kuprine;
type masiv=array[1..100] of integer;
var d,r:text;
m,k:masiv;
max,n,i,l:integer;
procedure vda( m,k:masiv; i:byte);
begin
for i:=1 to n-1 do
if k[i]<k[i+1] then
begin l:=k[i]; k[i]:= k[i+1]; k[i+1]:=l; l:=m[i]; m[i]:=m[i+1]; m[i+1]:=l; end;
write(r,m[1],' ',k[1])

end;
begin
  assign(d, 'duom.TXT');
  assign(r, 'rez.TXT');
  reset(d);
  rewrite®;
  read(d,max);
  read(d,n);
   for i:=1 to n do
    readln(d,m[i],k[i]);
    i:=1;
     vda(m,k,i);
close(d);
close®;
end.

а в пошаговую процедуру незнаю как и даже в рекурсивную процедуру незнаю я помогите обесните

Добавлено через 3 мин.
это вот сделал рекурсию кажется но не то наверное

program kuprine;
type masiv=array[1..100] of integer;
var d,r:text;
m,k:masiv;
max,n,i,l:integer;
procedure vda( m,k:masiv; i:byte);
begin
if m[i]<=max then write(r,m[i],' ',k[i])
else vda(m,k,i+1);
end;
begin
  assign(d, 'duom.TXT');
  assign(r, 'rez.TXT');
  reset(d);
  rewrite®;
  read(d,max);
  read(d,n);
   for i:=1 to n do
    readln(d,m[i],k[i]);
    for i:=1 to n-1 do
if k[i]<k[i+1] then
begin l:=k[i]; k[i]:= k[i+1]; k[i+1]:=l; l:=m[i]; m[i]:=m[i+1]; m[i+1]:=l; end;
    i:=1;
     vda(m,k,i);
close(d);
close®;
end.

[maksimla]

вот нашел в интернете задание про дамено я но программа какаето сложная как для меня
можете обеснить или упростить и обеснить мне ее?
и эта программа на поиск в глубину?

{ Задача "Домино",решение:А.Никитина,Самара }
{$M $C000,0,650000}
const max = 28;
maxtime = 60;
tl :longint = (maxtime*18); {чутьменьше 60сек }
yes :boolean = false; {флаг выхода, если ужеестьцепочкаиз n}
var m :array [0..6,0..6] of boolean;
n :byte; {кол-вокостяшекнавходе, 1..28}
cep,best :array [1..max*2] of byte; {цепочка/память }
p,maxlen :integer; { указатель нахвостцепочки/длинамакс.цеп. }
jiffy :longint absolute $0040:$006C; {секундомер,точнеетикомер }

procedure ReadData; { начальные установкиисчитываниеданных }
var i,a,b : byte;
begin
tl:=jiffy + tl;
p:=1; maxlen:=0;
assign(input,'d.in'); reset(input);
fillchar(cep,sizeof(cep),0);
fillchar(m,sizeof(m),false);
readln(n);
for i:=1 to n do begin
readln(a,b);
m[a,b]:=true; m[b,a]:=true;
end;
close(input);
end;

procedure WriteResults; {записьрезультата }
var i : integer;
begin
assign(output,'d.out'); rewrite(output);
writeln(maxlen div 2);
if (maxlen>1) then begin
i:=1;
while (i<pred(maxlen)) do begin
write(best[i],best[i+1],':');
inc(i,2);
end;
write(best[pred(maxlen)],best[maxlen]);
end;
close(output);
end;
{ более длинная цепочказапоминаетсявмассиве best }
procedure s_cep;
begin
if (p-1>maxlen) then begin
move(cep,best,p-1);
maxlen:=p-1;
yes:=(maxlen div 2=n);
end;
end;
{ сущеуствует лиещеподходящиекостяшки? }
function exist(k:integer):boolean;
var i : integer;
begin
i:=0; while (i<=6) and not(m[k,i]) do inc(i);
exist:=(i<=6);
end;
{построениецепочек }
procedure make_cep(f:integer);
var s:integer;
begin
if (yes) or (tl-jiffy<=0) then exit; {пораостановиться?}
if (m[f,f]) then begin {исключениепозволяетулучшитьперебор}
m[f,f]:=false; {убираемкостяшку }
cep[p]:=f; cep[succ(p)]:=f; inc(p,2); {идеяисключения -Савин}
if exist(f) then make_cep(f) else s_cep;
dec(p,2);
m[f,f]:=true; {возвращаемкостяшку }
end else
for s:=0 to 6 do {стандартныйбэк-трекинг}
if (m[f,s]) then begin
m[f,s]:=false; m[s,f]:=false; {убираемкостяшку }
cep[p]:=f; cep[succ(p)]:=s; inc(p,2);
if exist(s) then make_cep(s) else s_cep;
dec(p,2);
m[f,s]:=true; m[s,f]:=true; {возвращаемкостяшку }
end;
end;

var i:integer;
begin
ReadData;
for i:=0 to 6 do make_cep(i);
WriteResults;
end.

[Unconnected]

Может, ещё и условие приложишь к ней?

[maksimla]

ну и могу условие приложить там но это условие было в первом сообшении
Второе задание
Есть n домино косточек(пластинок если на русском кажется так). Напишите функцию

dlinnij(n: skolko;
var A: plostinka): skolko

, которая нашла длиннейший сложены по правилам домино ( домино пластинки соединяются по одинаковым очкам по сторонам ) длину цепочки.Может иметь внутриние процедуры и (или) функции.
Используйте такие общее типы

type skolko=1..28;
plostinka = array [0..6, 0..6] of boolean;



А тут зачем тип boolean?
а тут что с клавиатуры вводится ?
тут как то надо сделать перебором с двух сторон подставлять пластинки как то наверное может объясните?

Сообщение отредактировано: maksimla - 4.03.2009 20:10

[Unconnected]

В условие я не вникал (не понял, блин!), а про Boolean - это наверное какие точки нарисованы на половинках костяшки домино..

[maksimla]

какие точки нарисованы не понел тут же графики нету.
вот что там было написано откуда я взял программу задание написано

{ Берутся случайных N костяшек из одного набора домино (1<=N<=28). }
{ Задача состоит в том, чтобы образовать из этих N костяшек самую длинную }
{ цепочку, состыковывая их по правилам домино частями сравным количеством }
{точек. }
{ }
{ Входные данные: Входной файл с именем "D.IN"содержит информациюо }
{ наборе костяшек. 1-ястрока -количество костяшек. }
{ 2-я и последующие строки - парные наборы точек (числа разделены }
{ пробелом). В каждой строке записана пара точек,указанной на одной }
{ костяшке. Количество пар соответствует числу из первой строки. }
{ Выходные данные: результаты работы программы записываются в файл "D.OUT".}
{ 1-я строка содержит длину максимальной цепочки костяшек. 2-ястрока }
{ содержит пример такой цепочки, при этом пары (цифры)на костяшках }
{ записываются без пробелов, подряд, а между костяшками в цепочке ставится }
{двоеточие. }
{ Пример входного файла:Пример выходного файла: }
{ 5 5 }
{ 1 2 56:62:21:13:36 }
{ 1 3 }
{ 2 6 }
{ 3 6 }
{ 5 6 }

вот так надеюсь что понятно тут.

а мне немножко попроще
мне надо найти цепочку самых длинных и записать результат длины цепочки

[Lapp]

на форуме набрал в поиске рюкзак выдала пару тем таких по там не какого решения не было.

Странно. Вот здесь, задача номер 5: Переборные Алгоритмы

а как это так можно Завершать чтение можно по признаку конца файла.? я чего то такого не знаю можете написать как это так сделать ?
и я не представляю как потом будет считаться это

Вот так:

var
  Item: array[1..m] of record
    Weight,Price: integer
  end;

...
  ReadLn(Sack);
  n:=0;
  while not EoF(f) do begin
    Inc(n);
    with Item[n] do ReadLn(f,Weight,Price)
  end;

По окончании цикла в n будет количество вещей, а в массиве Item - их параметры. Только надо следить, чтоб за данными во входном файле не было ничего, даже пустых строк.

Сообщение отредактировано: Lapp - 5.03.2009 12:43

[maksimla]

да точно а мне такого в поиске недало наверное плохо искать умею я
вот задачу о рюкзаке мне немношко надо изменить будит и все зделано задачка будет

а о домино задачку можете подробнее обеснить и по возможности упростить
спасибо

[maksimla]

а там неправильная 5)задача о рюкзаке :
Условие :
Дано - максимальный вес рюкзака. Дано n предметов имеющих свой вес и стоимость. Определить максимальную стоимость груза, вес которого не превышает максимального веса рюкзака.

а там вводишь такие данные
всего 2 придмета
макс груз 10
вес
2
5
цена
10
11
выдает ответ
50
это ведь неправильно должен был по решению выдать 21 или я чего то не понел а?

[Vinchkovsky]

Определить максимальную стоимость груза, вес которого не превышает максимального веса рюкзака.

5 предметов, которые стоят "10" и весят "2" как раз и составят "максимальную стоимость"=50, внимательно условие прочитайте

[maksimla]

а при чем тогда еще 11 надо ввести или еще дополнительную надо ввести?
и тогда что ли перепутаны нам слова на английском вес и цена ?