0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
1

Написать алгоритм, который определит максимально возможное количество задач

02.09.2012, 23:52. Показов 1422. Ответов 17
Метки нет (Все метки)

Описание:
Петя и Вася предложили одноклассникам новый способ решения домашнего задания: поскольку каждый из учеников мог быстро решать лишь определённые виды заданий, а другие понимали плохо, то было выдвинуто следующее предложение. Каждый решает одну задачу из тех видов, в которых хорошо разбирается, после чего все ребята собираются и рассказывают друг другу решения.
Имейте в виду, что ребята не могут решать более одной задачи (нет времени), к тому же они не могут решать задачи, которые плохо понимают. Для того, чтобы все ребята не решили одну и ту же задачу, Васе и Пете требуется написать алгоритм, который определит максимально возможное количество задач, которое смогут решить ребята при оптимальном выборе в соответствие с навыками учеников.

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

Входные данные
В первой строке два целых числа N и M (1<=N,M<=50), разделённых пробелом - количество учеников и количество задач соответственно. Далее идёт N строк. В i-й строке содержится не более M целых чисел - номера задач, которые может решить i-й ученик.
Выходные данные
Одно целое число в соответствие с постановкой задачи.
Пример входных данных
Код
4 5
1 2
2
2
2 3 4 5
Пример выходных данных
Код
3
Думал, думал, но никак не знал как обработать входные данные.
Помогите кто-нибудь пожалуйста)
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.09.2012, 23:52
Ответы с готовыми решениями:

Распределить гири на максимально возможное количество пар
Имеются гири с массами 1г, 2г, ...,N г (N &lt;= 10000). Написать алгоритм и программу, распределяющую...

Распределить гири на максимально возможное количество пар
Имеются гири с массами: 1г, 2г,..., N г (N меньше или равно 500000). Написать программу,...

Написать программу, которая определит максимально возможную силу заново сформированного отряда
Для похода на Азерот Оргріму Думхаммеру понадобился еще один отряд. На призыв явились n орков....

Определить максимально возможное количество ферзей, не бьющих друг друга
Нужно написать программу, которая на шахматной доске nxn определяла максимально возможное кол-во...

17
Эксперт С++
4725 / 2546 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
03.09.2012, 06:37 2
v0dka, Вам поможет алгоритм поиска максимального паросочетания в двудольном графе
1
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 13:41  [ТС] 3
valeriikozlov, спасибо за ответ, попробую поискать что это такое и с чем его едят. Но вопрос главный в том, как обработать такие входные данные(каким способом)?
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 16:19 4
v0dka, имеете в виду, как записать в переменные все, что вводится в текстовый файл?) В условие не вчитывался, поэтому во что конкретно (переменная или массив) добавлять неясно.
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 17:13  [ТС] 5
Я вообще не имею понятия как принять правильно такие входные данные.
Пишу сюда, в надежде, что кто-нибудь всё же сталкивался с подобным и знает способ.

Код
4 5
1 2
2
2
2 3 4 5
Первые две переменные говорят сколько учеников и сколько всего задач соответственно, а остальные 4 строки ниже - это 4 разных ученика, которые способны решить заданные номера задач... т.е. максимум цифр может быть задано в данном примере 5, но может быть задано и меньше... короче я не могу понять как это всё обрабатывать, возможно задача неадекватная.
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 17:32 6
v0dka, я над алгоритмом не думал, но задание-то мне понятно
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 20:34  [ТС] 7
BumerangSP, А программу то написать сможешь?
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 20:38 8
v0dka, пока думаю над этим. Мысли появятся - отпишу.
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 20:44  [ТС] 9
BumerangSP, Если даже мысли будут как обработать входные данные, то отписывай.
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 20:58 10
v0dka, данные уже давно обработал. Но все-таки если у меня что-то выйдет, то выложу целиком.
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 21:05  [ТС] 11
BumerangSP, покажи код пожалуйста, даже если он не закончен. Мне как раз обработка данных и нужна. дальше у меня есть план)
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 21:14 12
v0dka, ну, если чем-то поможет. Я просто под свою идею сделал.
Pascal
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
uses crt;
type
 children = record
  zd: set of byte; // задачи, которые умеет решать ученик
 end;
 exercise = record
  kol,num: integer; // количество человек на одну задачу и номер задачи соотв-но
 end;
var a: array [1..50] of children;
    b: array [1..50] of exercise;
    i,j,k,n,m,ii,min,resh: integer;
    s: set of byte;
    input,output: text;
begin
 assign(input,'in.txt');
 reset(input);
 read(input,n);
 readln(input,m);
 ii:=1;
 for i:=1 to n do
  begin
  while not eoln (input) do
    begin
     read(input,k);
     include(a[i].zd,k);
     if not (k in s) then
      begin
        b[ii].num:=k;
       include(s,k);
       inc(ii);
      end;
    end;
   readln(input);
  end;
 close(input);
 
 for i:=1 to m do
  for j:=1 to n do
   if b[i].num in a[j].zd then
    inc(b[i].kol);
 
  for i:=1 to m do
   for j:=1 to m do
    if b[i].kol>b[j].kol then
     begin
      ii:=b[i].kol;
      k:=b[i].num;
      b[i].kol:=b[j].kol;
      b[i].num:=b[j].num;
      b[j].num:=k;
     end;
Данные берутся из текстового файла. В результате в массиве "a" в каждой i-ой строке содержатся те самые номера задач. Тип - множество (проще всего). В массиве "b" располагаются номера задач и их количество.
1
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 21:25  [ТС] 13
BumerangSP, Ну я и сам думал из файла будет полегче. Как-то склонялся к вводу из консоли)
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 21:41 14
v0dka, из файла по идее правильней. И ввод и вывод)
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 22:10  [ТС] 15
BumerangSP, щас твой код поизучаю, вспомню про все записи мож идейка придёт, сам сделаю
0
4299 / 1421 / 463
Регистрация: 16.12.2010
Сообщений: 2,939
Записей в блоге: 3
03.09.2012, 23:44 16
v0dka, это хорошо, если идейка умная будет. А то у меня алгоритм какой-то нелегкий получается)
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
03.09.2012, 23:59  [ТС] 17
BumerangSP, Завтра подумаем ещё... думаю совместно мы решим) Спасибо за поддержку
0
0 / 0 / 0
Регистрация: 02.09.2012
Сообщений: 18
05.09.2012, 01:04  [ТС] 18
Короче, ребята. всем спасибо. Я решил это дело файлами)
А вот и простейший код)
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var
N,M,i,k,schet:longint;
input:text;
s: set of byte;
begin
assign(input,'in.txt');
  reset(input);
  read(input,n);
  read(input,m);
    for i:=1 to n+1 do begin
      while not eoln(input)do begin
      read(input,k);
        if not (k in s) then 
        begin
        include(s,k);
        inc(schet);
        break;
        end;
      end;
      readln(input);
    end;
close(input);
writeln('Всего задач: ',schet);
end.
Подал идею BumerangSP, спасибо ему. Тему можно закрывать
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.09.2012, 01:04
Помогаю со студенческими работами здесь

Вычислите максимально возможное количество человек, которых можно разместить в здании
задание введите два вещественных числа. Меньшее из них соответствует нормативу площади на 1...

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

Вывести максимально возможное количество конфет, которые могут получить игравшие дети
В детском саду готовятся к Новогоднему празднику. Дед Мороз, известный всем своей незаурядностью,...

На прямоугольнике размещено максимально возможное количество квадратов. Найти количество квадратов и площадь незанятой части прямоугольника
1.Даны целые положительные числа A,B,C. На прямоугольнике размером A х B размещено максимально...


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

Или воспользуйтесь поиском по форуму:
18
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru