Перебор элементов матрицы

@vetal71 · Регистрация: 24.02.2012

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

Дана матрица A(N*M). Программа должна перебрать все возможные сочетания выбора по 1 элементу в каждой строке и для каждого сочетания выбора посчитать для каждого столбца сумму выбранных элементов.
Пример: матрица 2х3
а11 а12
а21 а22
а31 а32
возможные сочетания
а11,а21,а31
а11,а21,а32
а11,а22,а31
а11,а22,а32
а12,а21,а31
а12,а21,а32
а12,а22,а31
а12,а22,а32
Помогите, может у кого есть идеи как организовать перебор.

@vetal71 · 01.02.2013, 19:22 **[ТС]**

Одиночка,
gorfil
прошу прощения, был в командировке.
цитата из задания
"Дополнительное условие для элементов массива:
1. В случае если все элементы одной какой-либо строки равны нулю, то об этом выводится соответствующее сообщение в конце расчета, а эта строка изымается из следующих расчетов.
2. В случае если в какой-либо строке присутствуют нулевые элементы (но в ней же есть и не нулевые элементы), то такой вариант выбора элементов не рассматривается."
пояснение по п.2.
матрица A:
1 2
3 0
Вариант сочетания 1,0 не учитывается, потому как один элемент равен 0, при условии что в строке второй элемент <> 0 (3 <> 0).
Про массивы B и K речи нет.

Одиночка · 01.02.2013, 20:00

Чтобы выдать сообщение о пустых строках в конце расчёта нужно процедуру Stop записать так:

Delphi

procedure TForm1.Stop;
Var
  i : Integer;
  s : String;
begin
  Label1.Caption := Format('Время проверки: %n  сек.', [(GetTickCount - BeginTickCount)/1000]);
  Label2.Caption := Format('Результат: %d', [Min]);
  Label3.Caption := Format('Кол-во комбинаций: %d', [Z]);
 
  EndCalc := true; // Флаг закраски ячеек
  StringGrid1.Refresh;
 
  s:='';
  For i:=0 To Length(R) Do
  If R[i]=-1 Then
  s:=s+IntToStr(i+1)+', ';
 
  If Length(s)<>0 Then
  Begin
    Delete(s,Length(s)-1,2);
    ShowMessage('В массиве имеются пустые строки: '+s+' !!!');
  End;
 
  Button1.Enabled := true;
  Button2.Enabled := true;
  Button3.Enabled := true;
  Button4.Enabled := true;
end;

а эта строка изымается из следующих расчетов.

Так и сделано. Там сейчас один раз строка просматривается, и если все элементы равны 0 - ставиться отметка в массив "C" (код -1) и в дальнейшем уже просмотр не повторяется. По времени перебор работает, практически столько же, сколько и без этих пустых строк вообще. Поэтому я увеличил возможность размерности массива (до 20). Т.е. если поставишь размерность 15 строк, но из них 6 будут пустыми - будет работать, примерно как и с 9-ю строками.

Вариант сочетания 1,0 не учитывается, потому как один элемент равен 0

Так и сделано. В твоём примере будет выбран вариант 1,3.

А вообще нужно сразу писать задание полностью. А то получается испорченный телефон.

@vetal71 · 02.02.2013, 11:24 **[ТС]**

Одиночка
спасибо за помощь.

Сообщение от Одиночка

А вообще нужно сразу писать задание полностью. А то получается испорченный телефон.

виноват...

Добавлено через 14 часов 17 минут
Одиночка
запутался я в строках и столбцах. тестовый пример не сходится. а можно переделать чтоб M - строка, N - столбец.
тестовый пример:
K A
7 1 2
8 3 4
9 5 6
B 10 11
ответ 86. В прошлом варианте все работало

Одиночка · 02.02.2013, 13:01

В предыдущем варианте как раз и было всё перепутано. В гриде первым индексом идёт столбец, вторым - строка. В массиве - наоброт. А перенос данных был:

Delphi

1	StringGrid1.Cells[i,j]:=IntToStr(A[i,j]);

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

Одиночка · 02.02.2013, 13:07

Хотел твой архив поправить, но не смог его распаковать.

@vetal71 · 02.02.2013, 13:44 **[ТС]**

Сообщение от Одиночка

Хотел твой архив поправить, но не смог его распаковать.

интересно. упакован 7z.
перепаковал в rar.
Perebor.rar
твою версию проверил, вроде правильно считает. сейчас только поменяю местами N и M, т.к. по условию N - столбец, M - строка

@vetal71 · 02.02.2013, 13:55 **[ТС]**

Одиночка
и еще такой вопросик

Pascal

1
2
3

SetLength(eB, M);
  for i := 0 to N - 1 do
    eB[i] := false;

насколько я понял, массив eB - массив для столбцов, размерность у него М, а цикл по строкам

Одиночка · 02.02.2013, 14:08

Да, здесь ошибка. Нужно так:

Delphi

1
2
3

SetLength(eB, M);
  for i := 0 to M - 1 do
    eB[i] := false;

Архив нормально распаковался. Через часик посмотрю.

@vetal71 · 02.02.2013, 14:42 **[ТС]**

Одиночка
что не так

глянь пожалуйста
Perebor.rar

@vetal71 · 02.02.2013, 15:05 **[ТС]**

исправил, считает. но при изменении значений и пересчете ответ уже дает неверный

Одиночка · 02.02.2013, 16:03

Вот исправил все ошибки и вставил самый быстрый вариант перебора. А чтобы он пересчитывал нормально после изменений - нужно было или нажимать "инициализация" перед запуском или перенести очитску массива C - в процедуру Start. И установку значений в массив Be = False - тоже.

@vetal71 · 02.02.2013, 16:31 **[ТС]**

Одиночка
спасибо.
будьмо

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	01.02.2013, 19:22 [ТС]	61
	Одиночка, gorfil прошу прощения, был в командировке. цитата из задания "Дополнительное условие для элементов массива: 1. В случае если все элементы одной какой-либо строки равны нулю, то об этом выводится соответствующее сообщение в конце расчета, а эта строка изымается из следующих расчетов. 2. В случае если в какой-либо строке присутствуют нулевые элементы (но в ней же есть и не нулевые элементы), то такой вариант выбора элементов не рассматривается." пояснение по п.2. матрица A: 1 2 3 0 Вариант сочетания 1,0 не учитывается, потому как один элемент равен 0, при условии что в строке второй элемент <> 0 (3 <> 0). Про массивы B и K речи нет. 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	02.02.2013, 11:24 [ТС]	63
	Одиночка спасибо за помощь. Сообщение от Одиночка А вообще нужно сразу писать задание полностью. А то получается испорченный телефон. виноват... Добавлено через 14 часов 17 минут Одиночка запутался я в строках и столбцах. тестовый пример не сходится. а можно переделать чтоб M - строка, N - столбец. тестовый пример: K A 7 1 2 8 3 4 9 5 6 B 10 11 ответ 86. В прошлом варианте все работало 0

Одиночка 3944 / 1869 / 337 Регистрация: 16.03.2012 Сообщений: 3,880
	02.02.2013, 13:07	65
	Хотел твой архив поправить, но не смог его распаковать. 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	02.02.2013, 13:44 [ТС]	66
	Сообщение от Одиночка Хотел твой архив поправить, но не смог его распаковать. интересно. упакован 7z. перепаковал в rar. Perebor.rar твою версию проверил, вроде правильно считает. сейчас только поменяю местами N и M, т.к. по условию N - столбец, M - строка 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	02.02.2013, 14:42 [ТС]	69
	Одиночка что не так глянь пожалуйста Perebor.rar 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
		1
	Перебор элементов матрицы 17.01.2013, 11:02. Показов 7311. Ответов 71 Метки нет (Все метки) Дана матрица A(NM). Программа должна перебрать все возможные сочетания выбора по 1 элементу в каждой строке* и для каждого сочетания выбора посчитать для каждого столбца сумму выбранных элементов. Пример: матрица 2х3 а11 а12 а21 а22 а31 а32 возможные сочетания а11,а21,а31 а11,а21,а32 а11,а22,а31 а11,а22,а32 а12,а21,а31 а12,а21,а32 а12,а22,а31 а12,а22,а32 Помогите, может у кого есть идеи как организовать перебор. 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	02.02.2013, 15:05 [ТС]	70
	исправил, считает. но при изменении значений и пересчете ответ уже дает неверный 0

@vetal71 0 / 0 / 0 Регистрация: 24.02.2012 Сообщений: 29
	02.02.2013, 16:31 [ТС]	72
	Одиночка спасибо. будьмо 0