Версия для печати темы
Форум «Всё о Паскале» _ Теоретические вопросы _ Алгоритмы на матрицах
Автор: Флогримм 28.10.2004 11:39
вчера сел решать задачи на тему двумерных массивов - матриц и столкнулся с проблемой; какие можете посоветовать приемы программиования для алгоритмов, вида "заполнить матрицу по спирали, зигзагом" и т.д.
мне не конкретной задачи нужно решение, а метод в целом
пришла в голову такая идея: написать процедуры движения по матрице в четырех направленияъ (вверх, вниз, влево, вправо) до тех пор, пока не встретим либо конец матрицы ("крайнюю стенку") или же уже заплненный алгоритм и циклически повторять их до тех пор пока не заполним всю матрицу... да, наверное так и попробую
хотя мне кажется, что выход, который предложил выше не совсем правильный; может все можно свести все к основной (единственной формуле) формуле где меняться будет только значение i,j-счетчиков в цикле?
вобщем матрицы для меня проблема; помогите чем могите; в книгах же только и делают, что задачки пишут, а концепцию разъясникть - :no:
вот так
а еще вопрос: 1)как в вин2к в ТП7 установить русскую раскладку клавы; 2)как прервать зациклившийся процесс? (Ctrl-Break и Ctrl-F2 не работают)
зосим откланиваюсь, с уважением, Флогримм
Автор: Altair 28.10.2004 12:12
Цитата
как в вин2к в ТП7 установить русскую раскладку клавы;
Это тема неоднократно обсуждалась!
Методтаков: создать BET файл, где прописать русификатор и TP.
Цитата
как прервать зациклившийся процесс? (Ctrl-Break и Ctrl-F2 не работают)
Прежде всего, зациклившихся процессов быть не должно!
Везде где есть рекурсия, надо писать на всякий случай
Код
If keypressed then HALT;
Это останов проги по нажатию люой клавиши. (пропиши модуль CRT)
Цитата
написать процедуры движения по матрице в четырех направлениях
Это очень хорошие алгоритм. Лучше пожалуй (в смысле универсальности), не придумать!
ТОлько это должны быть функции. Смысл в том, что достаточно указать алгоритм движения, и можно хаполнить любую матрицу как угодно... хм.. а это интересно, сейчас займусь этим... посмотрим что получится...
Автор: Флогримм 28.10.2004 13:02
вот еще несколько вопросов, пожалуй, размещу здесь, влом новую тему создавать
1) как пользоваться операторами input/output? насколько это актуально? зачем нужно(хотя догадываюсь )? почему упоминается только в старых книгах?
2) как передавать параметры программе, запуская ее через командную строку? как оформить это в самой программе?
зы вчера при компиляции программы, где использовались функции работы с файлами (assign, reset,close и т.д.) мой докторвэб выдал мне перл: "D:\TP\BIN\OLEG\PRACTP~1\LINES812.EXE инфицирован модификацией Ithaqua.12310" ;)) вот такой мя вэб умный
потом комп проверил на наличие вирей, вроде чисто...
Цитата
Это очень хорошие алгоритм. Лучше пожалуй (в смысле универсальности), не придумать!
ого... я еще и шарю
Цитата
Прежде всего, зациклившихся процессов быть не должно!
Везде где есть рекурсия, надо писать на всякий случай
это у мя не в рекурсивных алгоритма, в обычных циклах бывает в основном в результате очепяток.. бр-рр т.е. опечаток
Автор: volvo 28.10.2004 13:16
Цитата
как передавать параметры программе, запуская ее через командную строку?
В меню Run -> Parameters вводишь параметры для передачи программе так, как если бы запускал ее через DOS (но НЕ включая имя самой программы)...
Цитата
как оформить это в самой программе?
Получить доступ к параметрам командной строки можно с помощью функций ParamCount - (возвращает количество параметров) и ParamStr(i) (возвращает i-ый параметр в виде строки). Пример:
Код
var I: Word;
begin
for I := 1 to ParamCount do
Writeln(ParamStr(I));
end.
Автор: Altair 28.10.2004 13:32
Цитата
это у мя не в рекурсивных алгоритма, в обычных циклах бывает в основном в результате очепяток
Да это неважно, все равно вставляй эту сроку.
Цитата
) как пользоваться операторами input/output? насколько это актуально? зачем нужно(хотя догадываюсь )? почему упоминается только в старых книгах?
Это не операторы, это переменные ИМХО.... их когда-то использовали ...
Эта переменная типа FILE - определяет файл ввода\вывода по умолчанию... никто этим не пользуется особо, потому что неудобно, и вносит путанницу ИМХО...
Лучше опредедлить файл как FILE и не мучаться
Автор: Флогримм 28.10.2004 14:19
volvo, спасибо. Усвоил. Ща попробую.
Цитата
Это не операторы, это переменные ИМХО.... их когда-то использовали ...
Эта переменная типа FILE - определяет файл ввода\вывода по умолчанию... никто этим не пользуется особо, потому что неудобно, и вносит путанницу ИМХО...
Лучше опредедлить файл как FILE и не мучаться
ясно
Цитата
ТОлько это должны быть функции.
почему? что будет результатом работы функции? конечная точка пройденного пути(текущая координата)?
Автор: Altair 28.10.2004 14:26
Цитата
почему?
Зависит от задачи.
и от способа реализации...
Автор: Флогримм 1.11.2004 15:41
вот как на мой взгляд лучше всего решать задачу на заполнение массива значениями по спирали
Код
01|02|03|04
12|13|14|05
11|16|15|06
10|09|08|07
ГЛАВНОЕ установить ПРИОРИТЕТ направеления движения!
в данном примере это (->, \/, <-, /\)
Код
program spirall;
uses crt;
const Size=7;
k=0;
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;
procedure draw;
begin
writeln;
for i:=1 to size do begin
for j:=1 to size do write(mas[i,j]:2,'|');
writeln;
end;
end;
begin
for i:=1 to size do
for j:=1 to size do mas[i,j]:=k;
clrscr;
i:=1;
j:=1;
mas[i,j]:=1;
for a:=1 to sqr(size) do
begin
write(i,'-',j,' ');
if mas[i,j+1]=k then begin inc(j); mas[i,j]:=a+1; end else{если пустая ячейка справа, тогода перейти на эту ячейку и присвоить ей очередное значение а...}
if mas[i+1,j]=k then begin inc(i); mas[i,j]:=a+1; end else {иначе, если пустая ячейка снизу, тогда...}
if mas[i,j-1]=k then begin dec(j); mas[i,j]:=a+1; end else {иначе если пустая ячейка слева...}
if mas[i-1,j]=k then begin dec(i); mas[i,j]:=a+1; end; {...пустая сверху...}
end;
draw;
end.
я вот код написал, но где-то ошибка
у мя такое бывает, вроде все правильно, но могу чассами сидеть искать опечатку или ошибку в алгоритме
если кто в задачу врубился, помогите...
в комментария к коду именно тот приоритет, о котором я говорил, то есть если вся матрица пустая(все ячейки имеют значение 0), а текущее позиция, например, ячейка mas[1,1] то у нее рядом 2 свободных клетки - снизу и справа, но мы не можем двигаться вниз, т.к. у движения вправо более высокий приритет
идея, надеюсь, понятна
задавая, таким образом, приотритет и напрвление можно заполнять матрицы различними "узорами", не только спиральными
Автор: volvo 1.11.2004 16:59
Смотри, что я наваял:
Код
program spirall;
uses crt;
const Size=7;
k=0;
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;
type
direction = (go_right, go_down, go_left, go_up);
var current: direction;
function check_direction(i, j: integer): boolean;
function next_direction(x: direction): direction;
begin
if x <> go_up then
next_direction := succ(x)
else
next_direction := go_right
end;
var change: boolean;
begin
check_direction := true;
change := false;
case current of
go_right:
if (j = size) then
change := true
else
if mas[i, j+1] <> k then
change := true
else exit;
go_down:
if (i = size) then
change := true
else
if mas[i+1, j] <> k then
change := true
else exit;
go_left:
if (j = 1) then
change := true
else
if mas[i, j-1] <> k then
change := true
else exit;
go_up:
if (i = 1) then
change := true
else
if mas[i-1, j] <> k then
change := true
else exit;
end;
if change then
current := next_direction(current);
check_direction := false
end;
procedure draw;
begin
writeln;
for i:=1 to size do begin
for j:=1 to size do write(mas[i,j]:2,'|');
writeln;
end;
end;
begin
for i:=1 to size do
for j:=1 to size do mas[i,j]:=k;
clrscr;
i:=1;
j:=1;
mas[i,j]:=1;
for a := 1 to pred(sqr(size)) do
begin
while not check_direction(i, j) do;
case current of
go_right: inc(j);
go_down : inc(i);
go_left : dec(j);
go_up : dec(i);
end;
mas[i, j] := succ(a)
end;
draw;
end.
Добавлено:
Оптимизированный код... :D
Код
Uses Crt;
Const
size = 7;
k = 0;
Var
mas: Array[1 .. size, 1 .. size] Of ShortInt;
Type
direction = (go_right, go_down, go_left, go_up);
Var
current: direction;
{$F+}
Function getPred(x: Integer): Integer;
Begin getPred := Pred(x) end;
Function getSucc(x: Integer): Integer;
Begin getSucc := Succ(x) end;
{$F-}
Function check_direction(i, j: Integer): Boolean;
Function next_direction(x: direction): direction;
Begin
If x <> go_up Then
next_direction := Succ(x)
Else
next_direction := go_right
End;
Type
TAxis = (isVert, isHoriz);
TFunc = Function(x: Integer): Integer;
Function check_range(is: TAxis; range: Integer;
f: TFunc): Boolean;
Begin
check_range := True;
Case is Of
isVert:
If (i = range) Then
check_range := False
Else
If mas[f(i), j] <> k Then
check_range := False;
isHoriz:
If (j = range) Then
check_range := False
Else
If mas[i, f(j)] <> k Then
check_range := False
End
End;
Begin
check_direction := True;
Case current Of
go_right:
If check_range(isHoriz, size, getSucc) Then exit;
go_down:
If check_range(isVert, size, getSucc) Then exit;
go_left:
If check_range(isHoriz, 1, getPred) Then exit;
go_up:
If check_range(isVert, 1, getPred) Then exit;
end;
current := next_direction(current);
check_direction := False
End;
Procedure draw;
Var
i, j: Integer;
Begin
WriteLn;
For i := 1 To size Do
Begin
For j := 1 To size Do
Write(mas[i,j]:2,'|');
WriteLn
End
End;
Var
i, j, a: Integer;
Begin
For i := 1 To size Do
For j := 1 To size Do
mas[i, j] := k;
ClrScr;
i := 1; j := 1;
mas[i, j] := 1;
For a := 1 To Pred(Sqr(size)) Do
Begin
While not check_direction(i, j) Do;
Case current Of
go_right: Inc(j);
go_down : Inc(i);
go_left : Dec(j);
go_up : Dec(i)
End;
mas[i, j] := Succ(a)
End;
draw
End.
Автор: Флогримм 1.11.2004 17:24
Вольво, спасибо, ща попробую разобраться.
А с моим алгоритмом кто-нить поможет? в чем моя ошибка?
Автор: volvo 1.11.2004 17:39
Флогримм
У твоего алгоритма есть очень существенный недостаток: ты не проверяешь, достигло ли значение i или j максимально возможного для данной матрицы (т.е. значения size...).
Автор: Флогримм 1.11.2004 19:00
volvo
а зачем проверять?
вот смотри: доходим до правого края матрицы, пусть size=4 (т.е. текущая позиция mas[1,4] ), на следующей же итеррации цикла, у нас есть такой условный оператор
Код
...
if mas[i,j+1]=k then begin inc(j); mas[i,j]:=a+1; end else
if mas[i+1,j]=k then begin inc(i); mas[i,j]:=a+1; end else
...
т.е. мы проверяем есть ли у ячейки mas[1,4] "свободный"(значение ячейки =0) сосед: да - inc(j); mas[i,j]:=a+1; нет - переходим к проверке других "свободных" соседей
поэтому можно избежать проверки встречи с границей массива size
аналогичная проверка происходит, когда мы встречаемся с нижней границей или левой и т.д.
тока че то мой алгоритм неработает
непойму! вроде все правильно
Автор: volvo 1.11.2004 19:13
Цитата
а зачем проверять?
А попробуй откомпилировать
и запустить свою программу в таком режиме:
Код
{$R+}
Автор: Amro 1.11.2004 21:05
Можно здеся посмотреть
http://forum.pascal.net.ru/forum/index.php?showtopic=162
Тема ещё в том году обсуждалась, там есть несколько вариантов решения :D
Кстати Oleg_Z Неплохо было бы в ЧаВо такую темку создать "Олимпиадные задачи" :yes:
Автор: Altair 1.11.2004 21:19
Согласен. Можно. Так кто тебе мешает это сделать? ;)
Внесу, как появится материал...
Автор: Флогримм 2.11.2004 4:15
Цитата
{$R+}
Код
201 Range check error (Ошибка при проверке границ).
Ошибка генерируется операторами, скомпилированными в состоянии {$R+}, при возникновении одной из следующих ситуаций:
индексное выражение массива находилось вне допустимого диапазона;
была осуществлена попытка присвоить переменной значение, находящееся вне диапазона переменной;
была осуществлена попытка передать значение, находящееся вне допустимого диапазона, в качестве параметра процедуре или функции.
это я понимаю, но у мя же есть проверка! если мы находимся на "приграничной" ячейке массива, мы НЕ МОЖЕМ перещагнуть, выйти за границы массива на следующую ячейку! если size=4 то мы НЕ МОЖЕМ попасть на mas[1,5] и т.д.!!
не оебята, свой код мне ненадо! ненадо за меня код писать, я прошу помочь мне ошибку найти в моем;
можно поробовать такое условие ввести:
Код
...
if (mas[i,j+1]=k) and (j<=size) then begin inc(j); mas[i,j]:=a+1; end else
if (mas[i+1,j]=k) and (i<=size) then begin inc(i); mas[i,j]:=a+1; end else
....
где в моем коде ошибка? помогите найти
Автор: volvo 2.11.2004 5:13
Цитата
мы НЕ МОЖЕМ попасть на mas[1,5]
но при прогоне программы мы туда-таки попадаем !!!
Автор: Флогримм 2.11.2004 11:11
я понимаю!! прога работает НЕПАРВИЛЬНО! но алгоритм, на мой взгляд - правильный, попробуй устно прогнать его для нескольких значений, все получается вроде
где моя ошибка??
Автор: Бродяжник 2.11.2004 14:51
Флогримм
Вы слишком широко понимаете смысл слов "у ячейки есть свободная соседняя ячейка". Вы непроизвольно предполагаете, что это выражение значит, что а) ячейка с индексами i,j существует для данной матрицы, т.е. выражение mas[i,j] имеет смысл, а также, что б) значение mas[i,j] равно заданному к. Однако у компьютера другое мышление. Если при компиляции отключена проверка Range check, то компилятор просто генерит код, в котором адресация [i,j] заменяется относительными адресами памяти. И в этом случае адрес памяти, соответсвующий адресации [1,5] для матрицы 4х4, скорее всего, будет соответствовать адресации [2,1]. И по этому адресу записано корректное с точки зрения программы значение, а именно значение к, указывающее на то, что ячейка свободна. При этом программа не знает, что полученное значение было взято вовсе не из мифической ячейки [1,5]. Она смело переходит к не менее мифической ячейке [1,6] (а на деле [2,2])... и снова находит там значение к. "Рулез!"- думает программа. Поэтому я бы заменил прямое обращение к ячейкам [i,j] на вызов функции
Код
function freemas(i,j: shortint): boolean;
begin
if (i<1) or (i>size) or (j<1) or (j>size)
then freemas:=false
else freemas:=(mas[i,j]=k);
end;
При этом общая структура Вашего алгоритма практически не изменится. Просто вместо
Код
if mas[i,j]=k then
будет
Код
if freemas(i,j) then
...Я неправ?
Автор: Флогримм 3.11.2004 0:56
Бродяжник!
Ваше сообщение - это то, чего я так долго ждал в этой теме! спасибо огромное!
я с вашей помощи наконец решил эту задачу. Ниже приведен код.
Код
program spirall;
uses crt;
const Size=7;
k=-1; {"пустая ячейка" содержит значение k}
var mas:array[1..size,1..size]of shortint;
i,j,a:integer;
function freemas(i,j: shortint): boolean; {(с) Бродяжник - функция проверяет,}
begin {является ли ячейка с координатами i,j "пустой ячейкой"}
if (i<1) or (i>size) or (j<1) or (j>size)
then freemas:=false
else freemas:=(mas[i,j]=k);
end;
procedure draw; {печать массива}
begin
writeln;
for i:=1 to size do begin
for j:=1 to size do write(mas[i,j]:2,'|');
writeln;
end;
end;
begin
for i:=1 to size do
for j:=1 to size do mas[i,j]:=k; {заполнение массива "пустыми ячейками"}
clrscr;
i:=1;
j:=1;
mas[i,j]:=1;
{algorithm}
for a:=1 to sqr(size)-1 do
begin
if (freemas(i-1,j)) and (not freemas(i,j-1)) then begin dec(i); mas[i,j]:=a+1; end else
if freemas(i,j+1) then begin inc(j); mas[i,j]:=a+1; end else
if freemas(i+1,j) then begin inc(i); mas[i,j]:=a+1; end else
if freemas(i,j-1) then begin dec(j); mas[i,j]:=a+1; end else
continue;
end;
{/algorithm}
draw;
end.
Пришлось чуть-чуть исправить алгоритм, т.е. я установил более высокий приоритет на движение вверх и немного изменил условия этого движ-я (идти вверх, только если верхняя ячейка пуста, а правая заполнена). Можете проверить прога работает.
Я считаю, что это один из наиболее универсальных алгоритмов, потому что:
1) количество действий минимальное, для матрицы порядка n оно равно n*n
2) изменяя очередность проверки(приоритет направления) и условия перехода на новую ячейку можно задавать многие виды движений! Например, поменял местами только строки и движ-е уже абсолютно иное, чсмотрите
Код
if (freemas(i-1,j)) and (not freemas(i,j-1)) then begin dec(i); mas[i,j]:=a+1; end else
if freemas(i+1,j) then begin inc(i); mas[i,j]:=a+1; end else
if freemas(i,j+1) then begin inc(j); mas[i,j]:=a+1; end else
if freemas(i,j-1) then begin dec(j); mas[i,j]:=a+1; end else continue;
в данном случае движ-е следующее:
Код
01|08|09|16
02|07|10|15
03|06|11|14
04|05|12|13
Не в обиду Вольво будет сказано, но по-моему мой алгоритм более лаконичен и понятен, чем его продвинутые вышеприведенные алгоритмы.
2 Олег_З
если хочешь, можешь включить этот алгоритм в ФАК по матрицам.
только я до сих пор не пойму, почему компиллятор ведет себя именно так, как описал Бродяжник (я понял как ведет, только не понял почему, не логичное поведение какое-то)
Автор: Puzik89 12.06.2007 21:02
ДОБРЫЙ ДЕНЬ! Может ли кто - то мне подсказать алгоритм записи элементов матрици по спирали!
1 2 6 7 15
3 5 8 14 16
4 9 13 17 22
10 12 18 21 23
11 19 20 24 25
Автор: volvo 12.06.2007 21:06
Это не спираль, а "змейка" - в поиске найдешь...
(P.S. - сегодня день любителей некро...?)