Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера +3 задачи

@Serg3010 · Регистрация: 20.12.2009

Author24 — интернет-сервис помощи студентам

Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).
N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий по- рядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.
Ввести три числа а,b,с. 1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c]. 2). Можно ли представить число а таким образом, чтобы k а = х[1] * x[2] * ... * x[k] = П x[i], i>=1, i=1 где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует. Ввести три числа а,b,с.
1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c].
2). Можно ли представить число а таким образом, чтобы
k
а = х[1] * x[2] * ... * x[k] = П x[i], i>=1,
i=1
где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм
находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует.
На олимпиаду прибыло N человек. Некоторые из них знакомы меж- ду собой.Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомо- го)..

Надеюсь на помощь...

Добавлено через 48 минут
Был бы рад хотя бы за одну решенную задачу...

Добавлено через 49 минут
Могу предложить рублей 50 за задачу))

Добавлено через 1 час 53 минуты
Есть предлжения?

Добавлено через 19 часов 56 минут
Ну???

@Serg3010 · 12.06.2010, 18:33 **[ТС]**

есть кто?

Добавлено через 19 часов 37 минут
Решите хотя бы одну

@Audetore · 21.04.2013, 19:35

Могу помочь с 4 :
Для решения задачи достаточно определить, является ли связным граф, определяемый матрицей смежности, элементы которой а[i,j] равны 1, если люди с номерами i и j знакомы и равны 0 иначе. Граф называется связным, если существует путь между любыми парами его вершин. Понятно, что путь между вершинами i и j в таком графе и определяет возможную последовательность знакомств, позволяющих познакомить людей с номерами i и j.
Для определения связности графа можно воспользоваться методом поиска в ширину, который состоит в следующем.
На начальном этапе в очередь помещается некоторая начальная вершина, например вершина с номером 1.
На каждой из следующих итераций (пока очередь не пуста) выполняются следующие действия:
- извлекается вершина из очереди;
- определяются вершины, ей смежные и которые в очереди еще не были, и помещаются в очередь.
Если в результате таких действий все вершины побывали в очереди (а для этого удобнее подсчитывать количество вершин, там побывавших), то граф связен, иначе не связен. Для маркировки вершин, побывавших в очереди, можно использовать массив размера N с элементами 0 и 1.

Добавлено через 14 минут

Pascal

uses crt;
type man = record
  acq: integer; //значения у людей
  friends: set of byte;  //список знакомств каждого
  flag: boolean; //отметка уже познакомившихся
 end;
 
var a: array [1..100] of man;
    i,j,k,n: integer;
begin
 write('Количество человек: ');
 readln(n);
 for i:=1 to n do //присваиваем людям числа
  begin
   write('A[',i,']= ');
   readln(a[i].acq);
   if a[i].acq>=n then
    begin
     writeln('Всех перезнакомить нельзя');
     halt;
    end;
  end;
 for i:=1 to n do //начинаем перебор
  begin
   k:=0;
   if a[i].acq=0 then //если человеку нужно выполнить 0 знакомств
    begin
     a[i].flag:=true; // свою миссию он выполнил, помечаем
     continue;
    end; //иначе
   for j:=1 to a[i].acq+k do // для i-го человека заводим знакомства, равные его числу
    if j=i then
     inc(k)
    else
    if not (j in a[i].friends) then // j-го человеку еще нет в списке знакомств i-го человека
     begin
      dec(a[j].acq); //у j-го человека отмечаем тоже состоявшееся знакомство 
      include(a[i].friends,j); //добавляем j-го человека в список друзей i-ому
     end;
   if a[i].acq=0 then //если человеку осталось выполнить 0 знакомств
    a[i].flag:=true; //свою миссию он выполнил, помечаем
  end;
 k:=0;
  for i:=1 to n do //сравниваем количество знакомств между всеми людьми
   for j:=1 to n do
    if a[i].friends=a[j].friends then
     inc(k);
   if k=n then
    writeln('Всех перезнакомить возможно')
   else
    writeln('Всех перезнакомить нельзя');
end.

Вот что-то придумал, делал в соответствии с заданием. Выходит, всех познакомить можно будет только в том случае, если у каждого i-го элемента значение будет n-1. Т.к. сам с собой человек уже знаком.
Например, массив из 4 элементов, у каждого значение = 3. В этом случае можно любого i-uго человека можно познакомить с остальными тремя людьми. Даже при условии, что предыдущие уже знакомы. Правда, я сделал так, что если, например, один человек должен познакомиться с 3 людьми и выполняет это действие, то другие люди, с которыми он не знаком, могут знакомиться с ним. Ему это ничего не дает, а вот другим прибавляет одно знакомство.
В остальных как-то не очень

@Serg3010 0 / 0 / 0 Регистрация: 20.12.2009 Сообщений: 14
		1
	Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера +3 задачи 10.06.2010, 19:38. Показов 3618. Ответов 2 Метки нет (Все метки) Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину). N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий по- рядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей. Ввести три числа а,b,с. 1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c]. 2). Можно ли представить число а таким образом, чтобы k а = х[1] * x[2] * ... * x[k] = П x[i], i>=1, i=1 где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует. Ввести три числа а,b,с. 1). Представить a в виде суммы минимального числа целых слагаемых x[i], каждое из которых лежит на отрезке [b,c]. 2). Можно ли представить число а таким образом, чтобы k а = х[1] * x[2] * ... * x[k] = П x[i], i>=1, i=1 где b<=x[i]<=c, х[i], а, в, с - целые. Лучшим считается алгоритм находящий такое представление с наименьшим числом множителей. Предусмотреть вариант, когда такого представления не существует. На олимпиаду прибыло N человек. Некоторые из них знакомы меж- ду собой.Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомо- го).. Надеюсь на помощь... Добавлено через 48 минут Был бы рад хотя бы за одну решенную задачу... Добавлено через 49 минут Могу предложить рублей 50 за задачу)) Добавлено через 1 час 53 минуты Есть предлжения? Добавлено через 19 часов 56 минут Ну??? 0

@Serg3010 0 / 0 / 0 Регистрация: 20.12.2009 Сообщений: 14
	12.06.2010, 18:33 [ТС]	2
	есть кто? Добавлено через 19 часов 37 минут Решите хотя бы одну 0

	21.04.2013, 19:35

Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера +3 задачи

Решение