Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Программа составления расписания

Автор: Chester 13.03.2004 21:22

Решать задачу за меня никого не прошу, прошу помочь ;) и вообще пора переходить на обсуждени есложных программ smile.gif
Программа не из легких, мне кажется.
Итак, есть список преподавателей (1 препод. ведет 1 предмет), классов. Условия: есть максимальное кол-во часов в которое учитель может работать с таким-то классом в неделю, ограничения по дням недели (может работать только во вторник, или ,например, все дни кроме среды), кол-во часов которое он может работать в одном классе в день (пусть например, 2).
ну там конечно еще условий дофига, но я хотел бы чтобы мне сначала посоветовали, как делать это. Жду идей smile.gif

Автор: Dark 14.03.2004 7:46

Хм, програмно я это не делал ) но хочу попробовать... что получиться - дам
Это я делал тока на Аксесе )

Автор: DI 14.03.2004 15:23

1организовать ввод данных с файла
2использовать массив записей
3для дней недели использовать множество,
4начиная с 1-го дня недели проверяешь всех преподов(если два препода могут работать в этот день выбираешь того который может только вэтот день) по каждому предмету
Млин определённо чё-то забыл.... unsure.gif

Автор: Chester 15.03.2004 17:05

Допустим, ввод данных можно опустить, пусть будет константа.
А как задавать сами условия?

Автор: DI 15.03.2004 18:03

А сколько и какие у тебя условия ?
Думается, для каждого случая по-разному...
В основном при помощи циклов и процедурsmile.gif
У тебя ,наверно, процедура будет похожа на сортировку массива -
пока не будут выполняться все условия она не должна быть закончена.. ph34r.gif

Автор: Chester 16.03.2004 20:42

Условия такие:

Я и хотел делать с помощью массива (array[days,subjects,1..6], число уроков 6) . Только как задавать сами условия, проверку и как сортировать? Мне бы алгоритм узнать.

Автор: Fire_Rage 18.03.2004 10:52

Знаешь, есть такая штука, называется "генетический алгоритм", мне советовали написать с помощью него, правда не знаю, можно ли с его помощью на паскале писать. Вообще мне сказали так напиши все условия для себя и придумай, как их отсеивать, вот и думаю.Помоги мне, пришли на e-mail условия, которые пока надумал, будем вместе писать.

Автор: Chester 23.03.2004 19:02

Знаешь, если бы я знал как хотя бы условия записывать... я вообще не секу в переводе мыслей на компьютерный язык. А как их отсеивать это вообще...
А местные мастера не хотят помогать sad.gif писать много, блин, время жалеют

Автор: Fire_Rage 25.03.2004 11:15

Да мне не нужно, чтобы ты переводил условия сразу на язык, просто напиши их(на русском языке),а думать потом будем.

Автор: trminator 25.03.2004 11:18

Возможно, пройдет метод на динамическом программировании. Будет рекурсивная процедура примерно такого плана:

Код

procedure make_shed;
   if возможно добавить предмет (есть время в учебном плане) then
       for i := 1 to n do
           if i-й учитель свободен в первый же незанятый день,
           begin
               добавить этого учителя (точнее, его предмет)
               make_shed;
               убрать этого учителя, чтобы попытаться сунуть другого
           end;
   else получено расписание -- выйти из всех этих процедур
end;


Фактически тут идет полный перебор всех вариантов =(

А массив с расписанием, может, сделать плоским? (то есть примерно как расписание, которое в школе висит -- двумерная матрица, а не трехмерная =) )

Автор: Guest 30.03.2004 20:12

Fire_Rage
Если ты не заметил, то посмотри пару постингов выше, я писал (как раз над тем постом, где ты говоришь что не писал).
trminator
размерность идет так: по дням недели, по классам, по урокам (сверху я что-то не так написал), то есть 3х мерный получается; не я понимаю, что он на "2х мерной" бумаге как 2х мерный выглядит smile.gif А ты можешь написать примерчик, с несколькими условиями? чтобы не по-русски после IF'ов smile.gif

Автор: trminator 31.03.2004 0:19

Хмм... на стенке в школе расписание вроде не трехмерное висит +) Вот мне и показалось, что двумерное удобнее (прообразом таблицы может служить как раз школьное расписание).

А что касается условий... Сколько часов в неделю может работать учитель -- свойство самого учителя (если будет запись с инфой об учителе, то это -- одно из полей такой записи). А по остальным условиям надо еще репу почесать +)

Автор: Atos 31.03.2004 15:37

Да, действительно, трёхмерная получается... Так и создать трёхмерный массив [1..DayOfWeek, 1..Class,1..MaxLessons] of word. Потом заполнить его номерами учителей - это и будет расписание. В процедуру make_shed передавать его по значению - тогда не придётся "убирать этого учителя, чтобы сунуть другого".
Если расписание составлено - выводить его прямо из процедуры. Передавать в процедуру x, y, z, изначально равные 1 - это координаты текущей заполняемой ячейки. Перед рекурсивном вызовом make_shed делать inc(z) если z<MaxLessons else begin z:=1 ; inc(y); и т.д. Если x=DayOfWeek то расписание составлено.
Вообще, предложенный алгоритм make_shed мне понравился: прост и ясен, как всё гениальное. Сразу ясна становится структура проги, а оптимизировать детали можно по ходу написания.

Автор: trminator 31.03.2004 23:38

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

Автор: Fire_Rage 1.04.2004 10:40

Цитата(Guest @ 30.03.04 13:12)
Fire_Rage
Если ты не заметил, то посмотри пару постингов выше, я писал (как раз над тем постом, где ты говоришь что не писал).

Во-первых, ты написал не все условия(к примеру в тот-то день неможет данный учитель и т.д. и т.п.)
Во-вторых будет 3-хмерный массив-класс, дни недели, и сами уроки на этот денб.
в-третих, я собираюсь делать по генетическому алгоритму.

Автор: Atos 3.04.2004 11:01

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

Да, действительно, я как-то не подумал... Ну, тогда x,y,z передавать по значению. (x,y,z) - как бы граница между заполненной и незаполненной частью массива, причём нам неважно, что незаполненная может быть забита всяким мусором.{может быть, она уже считалась заполненной в процессе рекурсивных вызовов, но мы этого "не помним"}

Chester, напиши все конкретные условия по учителям. Надо будет составить массив записей Teacher, заполнить поля, и уже тогда конкретно прописать кодом условие if i-й учитель свободен в первый же незанятый день

Автор: trminator 4.04.2004 20:55

Можно заводить трезмерный массив не [1..DayOfWeek, 1..Class,1..MaxLessons], а [0..DayOfWeek, 0..Class,0..MaxLessons]. В нулевых элементах можно хранить, сколько дней/классов/уроков уже распланировано. Тогда откат -- просто уменьшение на единицу одного из этих чисел +)

А вообще задача еще интересует автора?

Автор: Chester 6.04.2004 19:07

интересует
руки только что-то не доходят. условия уже пишу, половину накромсал (их не то чтобы очень много), остальное скоро допишу
сюда можно html таблицу вставить? у меня в виде таблички просто

Автор: Atos 7.04.2004 13:36

Можно присоединить к ответу htm- файл, если меньше 50 K.

Автор: imp 7.04.2004 17:06

народ, всем привет smile.gif первый раз здесь. будующая профессия обязывает...может, здесь хоть программировать научусь. rolleyes.gif
а вообще то я надеюсь, что мне кто-нибудь поможет решить задачу, или хотя-бы идею какую подкинет, т.к я только начинаю в это все въезжать, и еще мало что сама понимаю. ближе к делу:
нужно построить модель неупорядоченной таблицы на паскале или фортране

Автор: Catty 8.04.2004 1:07

может тебе лучше новую тему открыть?
ведь тут другую задачу обсуждают! smile.gif

Автор: Atos 8.04.2004 8:41

Цитата
будующая профессия обязывает...может, здесь хоть программировать научусь.

Это уже отлично. Ибо частенько сюда заглядывают челы, не разбирающиеся и не хотящие разобраться в программировании, чтоб им на халяву зачёт сделали.
imp, заведи новую тему. И расскажи конкретнее, что значит неупорядоченная таблица. Это двумерный массив случайных чисел или что-то другое?

Автор: Chester 13.05.2004 23:30

Я вернулся. Как и обещал, с условием: http://betasite.narod.ru/rasp.htm
Жду помощи, указаний, советов. И можно просьбу, чуть побыстрее smile.gif я понимаю, сам провафлял и все такое... зато такую задачу интересную отрыл.
P.S. Это мне не на зачет. чтоб не подумали чего лишнего smile.gif

Автор: BlackShadow 14.05.2004 0:33

Учитыая объём... БрутФорс - самое то!

Автор: Chester 14.05.2004 21:38

в смысле?

Автор: trminator 15.05.2004 22:33

Полный перебор всех вариантов. Что-то похожее на то, что я предложил

Или даже то же самое...

Автор: Chester 17.05.2004 20:37

Понятно. А ты можешь написать пример просчитывания какого-го либо условия?

Автор: Chester 21.05.2004 18:45

А где все? Народу много вроде обсуждало smile.gif

Автор: BlackShadow 21.05.2004 18:51

А обсуждать больше нечего smile.gif Не брутфорс же, в конце концов :D

Автор: Chester 22.05.2004 18:32

Ну так напиши примерчкик условия какого-нибудь средней сложности. Я не могу сразу после массивов,строк понять как это реализуется.

Автор: BlackShadow 24.05.2004 15:29

Перебирает все 5-изначные числа и выводит на экран те, у которых сумма цифр равна 40.

Код

Const
 K=40;

Var
 s:String;

Function Next:Boolean;
Var
 i:Integer;
Begin
 For i:=5 DownTo 1 Do
   If s[i]<'9' Then
   Begin
     Inc(s[i]);
     Break
   End
   Else
     If i = 1 Then
     Begin
       Next:=False;
       Break
     End
     Else
       s[i]:='0'
End;

Function Test:Boolean;
Var
 i,n:Integer;
Begin
 n:=0;
 For i:=1 To 5 Do
   Inc(n,Byte(s[i])-Byte('0'));
 Test:=n=K
End;

Begin
 s:='00000';
 While Next Do
   If Test Then
     WriteLn(s)
End.

Или приблизительно так...

Автор: LinFor 7.09.2004 20:07

ТОВарищи, понимаю, что обсуждалась эта тема давно, но....

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

Автор: Altair 9.09.2004 10:32

Так здесь и будем обсуждать.
Мне кажется эта задача очень интересной.

Автор: LinFor 9.09.2004 16:10

Цитата(Oleg_Z @ 9.09.04 6:32)
Так здесь и будем обсуждать.
Мне кажется эта задача очень интересной.

Мне бы просто хотелось бы более интенсивно пообсуждать данный вопрос, скажем, по аське, благо диал-ап дюже дорогой, чтоб форум читать... А вас эта задача интересует, или вы просто модератор?
PS: Задачка действительно интересная, меня она интересует больше как возможная курсовая работа, нежели производственно. Хотелось бы пообщаться с человеком реально составляющим эти расписания, чтоб узнать нужды и требования.
PS2: Сам я просто программер.

Я конечно модератор, но задача меня эта интересует из-за того, что при ее решении можно использовать генетический алгоритм. Собственно я им интересуюсь. Oleg_Z