задачка

[MrXaK]

В-общем задачка... желательно написать на си... с моей школьной олимпиады... пишу в сокращении что должна делать...

сопоставить N учеников c M учителями всеми способами ( N >= M)... то есть типа перебор... только я не совсем понял как писать... кто поможет буду очень рад...



и ещё... если в файле строка первая типа 13 2 3 то fscanf(F, "%d %d", a, b) обработает её? или придётся fgets() и потом посимвольно atol()?

Comments

[Vj_o-oy]

прочитаются первые 2 числа.

[MrXaK]

Vj_o-oy

ок... в принципе как я и думал... это хорошо )) осталась задача ))

[Vj_o-oy]

MrXaK второе: кол-во вариантов - C(N,M) т.е. N!/((N-M)!*M!). Оно же кол-во сочетаний.

ну а перебор то:

#define M

#define N



struct TEACHER

{

char * Students[N];

char Name[80];

int StudCount;

}

TEACHER Teachers[M];

char * Students[N];



void SetStudents( int StudLeft, int CurrTeacher, TEACHER teachers[M] );

int main

{

/*

Читаешь откуда влупится эти массивы и т.п. мутотень

*/

SetStudents( N, 0, Teachers );

return 0;

}

void SetStudents( int StudLeft, int CurrTeacher, TEACHER teachers[M] )

{

/* M-CurrTeacher - кол-во оставшихся преподов. всем нужно минимум по одному

ученику */



if( CurrTeacher = M && StudLeft == 0 ) // если всех всем роздали, то выводим список

{

for( unsigned i=0; i<M; i++ )

{

printf( "\n%s\n", teachers[i].Name );

unsigned j=0;

while( j<teachers[i].StudCount )

{

printf( "\n%s", teachers[i].Students[j] );

j++;

}

}

return;

}



// Начинается раздача слонов

for( unsigned i=N-StudLeft; i<N-(M-CurrTeacher); i++)

{

// По очередни выделяем этому преподу доп учеников и смотрим, сколько в этом раскладе достанется последнему

teachers[CurrTeacher].Students[teachers[CurrTeacher].StudCount++]=Students[i];

// Смотрим, как можно раскидать студентов по остальным преподам

SetStudents( StudLeft-1, CurrTeacher+1, teachers );

}

}



________



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

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

Ессно контролируется то, чтобы на каждого попало минимум по одному ученику

N-(M-CurrTeacher) - показывает учеников вплоть до какого нужно раздавать, чтобы всем преподам достался объект мучений.

N-StudentsLeft - номер ученика, которого делим



Алгоритм рекурсивный. глубина рекурсии - M.



орфографию и т.п. проверь, т.к. я прямо сюды и выписывал, без проверки в среде.

[MrXaK]

Vj_o-oy

хм... подставляем N = 3, M = 2? получаем 3!/(3-2)!*2! = 3... а их 6... может я конечно условие не так дописал... но для N=3, M=2 получаем пары

у1 - п1 п1 п2 п1 п2 п2

у2 - п1 п2 п1 п2 п1 п2

у3 - п2 п1 п1 п2 п2 п1

т. е. 6 пар... а по формуле как уже посчитал, получается 3... ещё 3 пары куд-то деваются... (у - ученики, п - преподы)

я когда думал как решать тоже думал что формула как для сочетаний будет... только неполучилось...

[Vj_o-oy]

такс, значит в формуле наврал. Для двух преподов у меня получилось кол-во вариантов - сумма биномиальных коэффициентов, за вычетом крайних (которые по 1).

Не заморачивайся с формулой Тут статистика нужна. Все варианты распределений - невозможные варианты. Ну на вскидку кол-во вариантов (проверил на паре тройке значений) M^N. Варианты - которых не может быть: для 2х преподов - всего 2. для 3х преподов: 3+кол-во вариантов для остальных распределений (по 2). Итого получаем.

Кол-во тех вариантов, которые устраивают: M^N - Сумма(M^n, nС[1;N-1])

[MrXaK]

Vj_o-oy

хм... ясна... спасиба... в принципе терь прогу сам подправлю... пасиба за помощь...

[zw0rk]

Что-то не тянет на олимпиадную задачку

[MrXaK]

in_Tegrity

олимпиада школьная...

на городской сложнее были...

а на областной прошлогодней как мне рассказывали, были те же что на городской, только с одним отличием - работа с огромными данными... то есть вот даже эта задача чтобы число M и N такие большие что не влезают в long int... и т. п.