|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Komarov Alexey 2:5020/400 11 Jul 2001 00:15:34
To : All
Subject : Re: Расписание
--------------------------------------------------------------------------------
MS> Hyжно составить pасписание в инститyте, где много пpепадов,
MS> гpyппы
MS> стyдентов и аyдитоpии опpеделенной вместимости. Как это сделать?
Когда то я писал такую штуку. Hо она решается не классическими алгоритмами а
моим собственным
вот его описание
файлы 1-10 это данные для классов 1-10
в них содержится списко предметов. После каждого предмета идет символ #, а
затем количество часов в неделю
алгоритм. (до нельзя кривой,)
берем формируем из файлов расписание. При этом то что в один час попадается
несколько раз один и тот же предмет нам по барабану. Главное составить
массив,
который мы потом будем сортировать.
берем проверяем все предметы по порядку. Если такой предмет в это время уже
есть то от этого предмета идем вниз до конца расписания и ищем такой предмет
которого еще не было в это время. Если нашли - меняем местами.
Естественно к концу расписание обменивать нам становиться нечего и
получаеться
что в одно и тоже время несколько литератур и черт знает чего еще.
в случае если предмет надо бы поменять местами - а менять то его не с чем
идем от этого предмета вверх по расписанию этого класса и ищем предмет с
которым можно было бы махнуться местами. Hашли? проверяем а можно ли
записать
в верх предмет с низу? (то есть строчка, где мы нашли предмет уже
отсортирована
и нам нужно проверить можно ли вставить другой предмет) если можно поменять
эти
два предмета совершенно безболезненно - меняем их местами.
Cheshire Cat
ЗЫ: чуть не забыл: после запуска проги раписание генериться в файл timetabl.
отсюда начинаются файлы. прога и данные..
-----------<file generate.pas>---------
const days:array[1..6] of string[20] =('Понедельник ',
'Вторник ',
'Среда ',
'Четверг ',
'Пятница ',
'Суббота ');
type one_Day=array[1..10] of string[20];
temp=record
name:string[20];
q :byte;
end;
var
tt:array[1..10,1..6] of one_Day;
rt:array[1..40] of temp;
qs:array[1..10,1..6] of byte;
function addspace(s:string;a:byte):string;
begin
while length(s)<a do s:=s+#32;
addspace:=s;
end;
procedure rclass(n:byte);
var
st:string;
ch:char;
fl:file of char;
c:byte;
i,j:integer;
q:word;
begin
for c:=1 to 40 do
begin
rt[c].name:='';
rt[c].q:=0;
end;
c:=1;
st:=chr(n+48);
if st=#58 then st:='10' else st:='0'+st;
assign(fl,st);
reset(fl);
while not eof(fl) do
begin
read(fl,ch);
if ch='#' then
begin
st:='';
ch:=#0;
while (ch<>#13) and (not eof(fl)) do
begin
read(fl,ch);
if ch<>#13 then st:=st+ch;
end;
val(st,rt[c].q,i);
inc(c);
end else if ch<>#10 then rt[c].name:=rt[c].name+ch;
end;
close(fl);
q:=0;
for c:=1 to 40 do q:=q+rt[c].q;
for c:=1 to 6 do qs[n,c]:=q div 6;
for c:=1 to q mod 6 do inc (qs[n,c]);
i:=1;j:=1;c:=1;
while rt[c].name<>'' do
begin
for q:=1 to rt[c].q do
begin
tt[n,j][i]:=rt[c].name;
inc(i);
if i>qs[n,j] then
begin
i:=1;
inc(j);
end;
end;
inc(c);
end;
end;
procedure printf;
var fl:text;
c,b:byte;
class,ct,ct2:string;
day:byte;
cl:byte;
n:byte;
begin
assign(fl,'timetabl');
rewrite(fl);
write(fl,#218);
for c:=1 to 230 do if c mod 21=0 then write(fl,#194) else
write(fl,#196);
writeln(fl,#191);
class:=#179;
for c:=0 to 10 do
begin
str(c,ct);
ct:=ct+' класс';
if c=0 then ct:='';
ct2:='';
for b:=1 to (20-length(ct)) shr 1 do ct2:=#32+ct2;
ct2:=ct2+ct;
while length(ct2)<>20 do ct2:=ct2+#32;
class:=class+ct2+#179;
end;
writeln(fl,class);
for day:=1 to 6 do
begin
write(fl,#195);
for c:=1 to 230 do if c mod 21=0 then write(fl,#197) else
write(fl,#196);
writeln(fl,#180);
for n:=1 to 10 do
begin
class:=#179;
if n=1 then class:=class+days[day] else
class:=class+addspace('',20);
class:=class+#179;
for cl:=1 to 10 do class:=class+addspace(tt[cl,day][n],20)+#179;
writeln(fl,class)
end;
end;
write(fl,#192);
for c:=1 to 230 do if c mod 21=0 then write(fl,#193) else
write(fl,#196);
writeln(fl,#217);
close(fl);
end;
procedure make_tabl;
var
temp:string[20];
c,dc,nc:byte;
day,cl2,class,n,day2,n2:word;
sflag:boolean;
begin
for day:=1 to 6 do
begin
for n:=1 to 10 do
begin
for class:=1 to 10 do
begin
for cl2:=class-1 downto 1 do
begin
sflag:=false;
if (tt[class,day][n]=tt[cl2,day][n]) and (tt[class,day][n]<>'')
then
begin
for day2:=1 to 6 do
begin
for n2:=1 to 10 do
begin
if (day2-1)*10+n2>(day-1)*10+n then
begin
if (tt[class,day2][n2]<>'') then
begin
sflag:=true;
for cl2:=class-1 downto 1 do
if (tt[class,day2][n2]=tt[cl2,day][n]) then
begin
sflag:=false;
break;
end;
if sflag then
begin
temp:=tt[class,day2][n2];
tt[class,day2][n2]:=tt[class,day][n];
tt[class,day][n]:=temp;
break;
end;
end;
end;
if sflag then break;
end;
if sflag then break;
end;
if not sflag then
begin
for day2:=1 to 6 do
begin
for n2:=1 to 10 do
begin
if (day2-1)*10+n2<(day-1)*10+n then
begin
if (tt[class,day2][n2]<>'') then
begin
sflag:=true;
for cl2:=class-1 downto 1 do
if (tt[class,day2][n2]=tt[cl2,day][n]) then
begin
sflag:=false;
break;
end;
if sflag then
begin
for cl2:=1 to 10 do
begin
if tt[class,day][n]=tt[cl2,day2][n2] then
begin
sflag:=false;
break;
end;
end;
end;
if sflag then
begin
temp:=tt[class,day2][n2];
tt[class,day2][n2]:=tt[class,day][n];
tt[class,day][n]:=temp;
break;
end;
end;
end;
if sflag then break;
end;
if sflag then break;
end;
end;
if not sflag then
begin
nc:=10;
if (day=6) and (class=3) then
day:=6;
for c:=1 to 6 do
if qs[class,c]<nc then
begin
nc:=qs[class,c];
dc:=c;
end;
inc(qs[class,dc]);
inc(nc);
tt[class,dc][nc]:=tt[class,day][n];
tt[class,day][n]:=' ';
end;
break;
end;
end;
end;
end;
end;
end;
var c:byte;
begin
for c:=1 to 10 do rclass(c);
make_tabl;
printf;
end.
-----------<end of file generate.pas>-----------
Далее идут входные данные.
-----------<file 01.pas>---------
Математика #3
Русский Язык #3
Литература #3
Физкультура #1
Рисование #1
Музыка #1
-----------<end of file 01.pas>---------
-----------<file 02.pas>---------
Математика #3
Русский Язык #2
Литература #2
Физкультура #1
Рисование #2
Музыка #1
Труд #2
-----------<end of file 02.pas>---------
-----------<file 03.pas>---------
Математика #4
Русский Язык #2
Литература #2
Физкультура #2
Рисование #2
Музыка #2
Труд #2
-----------<end of file 03.pas>---------
-----------<file 04.pas>---------
Математика #5
Русский Язык #2
Литература #1
Физкультура #2
Рисование #2
Музыка #1
Труд #2
История #2
-----------<end of file 04.pas>---------
-----------<file 05.pas>---------
Алгебра #2
Геометрия #2
Русский Язык #1
Литература #1
История #2
Физкультура #1
Рисование #1
Музыка #1
Труд #2
-----------<end of file 05.pas>---------
-----------<file 06.pas>---------
Алгебра #2
Геометрия #2
Русский Язык #1
Литература #3
Физкультура #2
Труд #2
Физика #2
Биология #2
-----------<end of file 06.pas>---------
-----------<file 07.pas>---------
Алгебра #4
Геометрия #2
Русский Язык #1
Литература #1
Физкультура #1
Труд #2
Физика #2
Биология #2
Физика #2
-----------<end of file 07.pas>---------
-----------<file 08.pas>---------
Алгебра #2
Геометрия #2
Русский Язык #1
Литература #1
Физкультура #1
Труд #2
Физика #3
Биология #1
Физика #2
Ин. Яз #2
-----------<end of file 08.pas>---------
-----------<file 09.pas>---------
Алгебра #2
Геометрия #2
Литература #2
Физкультура #1
Труд #2
Физика #2
Биология #3
Химия #3
Физика #2
Ин. Яз #2
Информатика #2
-----------<end of file 09.pas>---------
-----------<file 10.pas>---------
Алгебра #3
Геометрия #1
Литература #1
Физкультура #1
Труд #2
Физика #2
Биология #1
Физика #2
Ин. Яз #2
Информатика #2
Химия #3
Астрономия #2
ОБЖ #2
-----------<end of file 10.pas>---------
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
