IPB
ЛогинПароль:

> ВНИМАНИЕ!

Прежде чем задать вопрос, смотрите FAQ.
Рекомендуем загрузить DRKB.

> реализуемо ли
.helga
сообщение 1.01.2007 22:55
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 26
Пол: Женский

Репутация: -  1  +


Реализуемо ли это в Делфи??


1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице
2 Найти наименьший из элементов, через которые не проходит ни одна прямая
3 Вычесть его из всех элементов, через которые не проходят прямые
4 Прибавить его ко всем элементам, лежащим на пересечении прямых
5 Элементы, через которые проходит только одна прямая, оставить неизменными


 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
Bokul
сообщение 3.01.2007 0:23
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 117
Пол: Мужской
Реальное имя: Богдан

Репутация: -  11  +


Цитата
здесь можно вычеркнуть 4 столбца. А у тебя вычеркивается 2 столбца и 3 строки, так?

yes2.gif
Цитата
А я - всегда вертикальную... Но что с этим делать - не придумала.

Положится на судьбу и воспользоваться random-ом
Цитата
Жду твой вариант...

Добавил функцию, которая ищет количество безнулевых строк/столбцов в зависимости от передаваемого флага: true для столбца.
Также улучшил (имхо) читабельность главного цикла.

uses crt;
const
n=5;
ar:array[1..n,1..n] of byte=((0,1,0,1,0),
(1,0,1,1,1),
(1,0,0,1,0),
(0,1,1,1,1),
(1,0,0,1,0));
Type
TElement=record
info:byte;
checked:boolean;
end;
TRes=record
ind,n:byte;
end;
Var mas:array[1..n,1..n] of TElement;

procedure init;
var i,j:byte;
begin
for i:=1 to n do
for j:=1 to n do
begin
mas[i,j].info:=ar[i,j];
mas[i,j].checked:=false;
end;
end;

function GetMax(isLine: boolean):TRes;
var i,j,max:byte;
res:TRes;
value: TElement;
begin
max:=0;
res.n:=0;
res.ind:=0;
for i:=1 to n do
begin
for j:=1 to n do begin
if isLine then value := mas[i, j] else value := mas[j, i];
if (value.info=0) and (value.checked=false) then inc(max);
end;
if max>res.n then
begin
res.n:=max;
res.ind:=i;
end;
max:=0;
end;
GetMax:=res;
end;

function GetWithoutZero(IsColumn:boolean):byte;//<--Новая!!!
var i,j:byte; res:byte; b:boolean; value:TElement;
begin
res:=0;
for i:=1 to n do
begin
b:=false;
for j:=1 to n do
begin
if IsColumn then value:=mas[j,i] else value:=mas[i,j];
if (value.info=0) and (value.checked=false) then
b:=true
end;
if not(b) then
inc(res);
end;
GetWithoutZero:=res;
end;



procedure CrossColumn(num:byte);
var i:byte;
begin
for i:=1 to n do
mas[i,num].checked:=true;
end;

procedure CrossLine(num:byte);
var i:byte;
begin
for i:=1 to n do
mas[num,i].checked:=true;
end;

var NColumn,NLine:TRes; WriteColumn:boolean;
begin
clrscr;
init;
NColumn:=GetMax(false);
NLine:=GetMax(true);
while (NColumn.n<>0) and (NLine.n<>0) do
begin
if NColumn.n>NLine.n then
WriteColumn:=true;
if NColumn.n<NLine.n then
WriteColumn:=false;

if NColumn.n=NLine.n then
if GetWithoutZero(true)>GetWithoutZero(false) then
WriteColumn:=true
else
WriteColumn:=true;
if WriteColumn then begin
writeln('Column ',NColumn.ind);
CrossColumn(NColumn.ind);
end
else begin
writeln('Line ',NLine.ind);
CrossLine(NLine.ind);
end;
NColumn:=GetMax(false);
NLine:=GetMax(true);
end;
readln;
end.





--------------------
Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
.helga   реализуемо ли   1.01.2007 22:55
мисс_граффити   Реализуемо. Скажи, у тебя есть идеи, каким алгорит...   1.01.2007 23:35
.helga   эмм.. нужно вычеркивать сначала те столбцы или стр...   2.01.2007 0:05
мисс_граффити   в принципе, думала примерно так же. единственное у...   2.01.2007 0:44
.helga   о, пришла бредовая мысля! :) а что, если ...   2.01.2007 1:07
Bokul   Вот мое решение: Пойдём от обратного: какое макси...   2.01.2007 4:21
.helga   а если безнулевых строк/столбцов не окажется? 1 ...   2.01.2007 4:39
Bokul   Ты не поняла шутки с random-ом - если безнулевых с...   2.01.2007 4:47
.helga   ну да. если в моем примере проводить только горизо...   2.01.2007 4:50
Bokul   .helga, почему ты так хочешь усложнить все? Хва...   2.01.2007 5:02
.helga   не хватит! потому что при некоторых примерах о...   2.01.2007 5:18
Bokul   Что требуется? Найти минимальное количество зач...   2.01.2007 5:27
.helga   Но зачеркивать-то с умом нужно) Чтобы остались эле...   2.01.2007 5:33
Bokul   :wacko: .helga, покажи как ты с умом зачеркнёшь вс...   2.01.2007 5:35
.helga   насчет тех примеров: зачеркну. сначала вычеркиваем...   2.01.2007 5:42
Bokul   Нет мой алгоритм и для такого не годится: 1111 110...   2.01.2007 6:05
.helga   хм. тогда кроме вычеркивания строк/столбцов с макс...   2.01.2007 6:16
Bokul   А полный код можешь привести?   2.01.2007 6:18
.helga   отредактировала чуток предыдущее. спать все-таки и...   2.01.2007 6:22
Bokul   Тот который будет компилироваться..   2.01.2007 6:28
.helga   на недо-паскале: program z; uses crt; var mart: ...   2.01.2007 6:51
Bokul   Конечно у тебя рекурсия вечная (до переполнения ст...   2.01.2007 6:56
.helga   а вот этот кусок for i:=1 to m do for ii:=1 to m...   2.01.2007 6:59
Bokul   Ты тестила свой код? Правильные результаты дает? ...   2.01.2007 7:56
volvo   2 Bokul: Copy+Paste - не наш метод... Убираем 2 фу...   2.01.2007 10:20
мисс_граффити   А как ты отличаешь элементы, расположенные на пер...   2.01.2007 12:37
Bokul   :yes2: :no1: Я сам сначала хотел сделать и...   2.01.2007 18:15
мисс_граффити   Везет тебе.... :) А вот автору темы нужно: А к...   2.01.2007 19:02
Bokul   Попробуй сделать - поймешь. :) [/quote] Мож...   2.01.2007 19:10
мисс_граффити   Попробовала. Сделала. Не поняла :( Файлик прицепл...   2.01.2007 23:00
Bokul   И не всегда правильно.. :( Ну сохраним. Вмес...   2.01.2007 23:12
мисс_граффити   А зачем нам их хранить? Надо подумать, как пост...   2.01.2007 23:27
Bokul   Ты права. Просто люблю все делать поэтапно.. ...   2.01.2007 23:38
мисс_граффити   ой... в смысле, вот так: n=5; ar:array[1..n,1...   2.01.2007 23:40
Bokul   :blink: Да. Проблема в том что в случае ког...   2.01.2007 23:47
мисс_граффити   я вот про этот вариант: n=5; ar:array[1..n,1....   2.01.2007 23:57
.helga   2 мисс_граффити основы алгоритмизации и программир...   3.01.2007 0:07
Bokul   :yes2: Положится на судьбу и воспользоватьс...   3.01.2007 0:23
мисс_граффити   к сожалению, внесенные изменения не в полной мере ...   3.01.2007 0:35
Bokul   :mega_chok: const n=5; ar:array[1..n,1...   3.01.2007 0:37
мисс_граффити   Идея такая: если безнулевых столбцов/строк больше,...   3.01.2007 0:44
Bokul   :no1: Я допустил ошибку: ...   3.01.2007 1:01
мисс_граффити   :) вроде как непринципиально... Я про немножко др...   3.01.2007 1:14
Bokul   :no1: 0 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 ...   3.01.2007 1:21
Bokul   Переделать старый алгоритм("то есть ищем, где...   3.01.2007 1:40
Bokul   Блин, написал код и для этого алгоритма, но он тож...   3.01.2007 8:43
мисс_граффити   почему? чем этот пример такой особенный??? покажеш...   3.01.2007 15:13
Bokul   uses crt; const n=5; ar:array[1..n,1..n...   3.01.2007 20:43
мисс_граффити   рассматиривать отдельно?... поскольку "развил...   3.01.2007 23:22
.helga   уже нет, мне изменили постановку задачи, теперь не...   3.01.2007 23:50
Malice   Проще всего сделать перебором, вот так, например: ...   4.01.2007 10:19
Bokul   Malice, можешь сделать небольшое пояснение алгорит...   4.01.2007 11:01
Malice   Malice, можешь сделать небольшое пояснение алгори...   4.01.2007 12:06


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 11.07.2025 16:17
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"