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

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Матрица и массив, Никак не пойму......
сообщение
Сообщение #1





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

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


Кто-нить помогите решить задачку. Текст следующий: Даны целочисленная матрица X[1:n,1:m] и целочисленный массив Z[1:r]. Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы. Буду очень благодарен за помощь.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

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


что значит запомнить?


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





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

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


Если я правильно понял, то надо запомнить индексы обнуленных элементов матрицы:

const
r=10;
n=5;
m=7;
type
rec = record
i0,j0: integer;
end;
index = array[1..r] of rec; {массив записей для хранения индексов обнул. эл-тов}

massiv = array[1..r] of integer;
matrix = array[1..n, 1..m] of integer;
var
mas: index;
x: matrix;
z: massiv;
i, j, k: integer;
count: integer; {кол-во обнул. эл-тов}

begin
count:= 0;
for k:= 1 to r do
for i:= 1 to n do
for j:= 1 to m do
if (x[i,j] = z[k]) and (x[i,j]<>0) then
begin
x[i,j]:= 0;
count:= count+1;
mas[count].i0:= i;
mas[count].j0:= j;
end;
for i:= 1 to count do
writeln(mas[i].i0, mas[i].j0);
readln;
end.


Сообщение отредактировано: volvo -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гуру
*****

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

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


uses crt;
const
n=10;
m=10;
r=10;
type
coor=record
x,y:byte;
end;
var
x:array[1..n,1..m] of integer;
z:array[1..r] of integer;
mem:array[1..n*m] of coor;
max:integer;
i,j,k:byte;
b:boolean;
begin
clrscr;
for i:=1 to n do
begin
for j:=1 to m do
begin
x[i,j]:=random(10);
write(x[i,j],' ');
end;
writeln;
end;
writeln('-------------------------------------');
for k:=1 to r do
begin
z[k]:=random(10);
write(z[k],' ');
end;
writeln;
writeln('-------------------------------------');
b:=false;
max:=0;
for i:=1 to n do
for j:=1 to m do
begin
for k:=1 to r do
if z[k]=x[i,j] then
b:=true;
if b=false then
begin
x[i,j]:=0;
inc(max);
mem[max].x:=j;
mem[max].y:=i;
end
else
b:=false;
end;
for i:=1 to max do
write('x=',mem[i].x,' y=',mem[i].y,'| ');
readln;
end.


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


Гость






Ребята, это все прекрасно, конечно, но решение "в лоб" никогда быстротой не отличалось...

Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы?

Есть предположение, что если отсортировать массив Z, то можно вместо прямого поиска в нем использовать, скажем, бинарный, что ускорит программу...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





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

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


Цитата(volvo @ 22.10.2006 9:22) *


Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы?

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


Это все верно, но задачка-то явно учебная... Вряд ли в ней нужны такие навороты. Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гуру
*****

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

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


SuperMozg, что-то мне кажется, что твоя прога не совсем правильно работает... Вот добавил к ней пау строчок для заполнения массивов данными, так получинные результаты не есть верными.
uses crt;
const
r=10;
n=5;
m=7;type
rec = record
i0,j0: integer;
end;
index = array[1..r] of rec;
massiv = array[1..r] of integer;
matrix = array[1..n, 1..m] of integer;
var mas: index;
x: matrix; z: massiv;
i, j, k: integer;
count: integer;
begin
clrscr;
for i:=1 to n do
begin
for j:=1 to m do
begin
x[i,j]:=random(10);
write(x[i,j],' ');
end;
writeln;
end;
writeln('-------------------------------------');
for k:=1 to r do
begin
z[k]:=random(10);
write(z[k],' ');
end;
writeln;
writeln('-------------------------------------');
count:= 0;
for k:= 1 to r do
for i:= 1 to n do
for j:= 1 to m do
if (x[i,j] = z[k]) and (x[i,j]<>0) then
begin
x[i,j]:= 0;
count:= count+1;
mas[count].i0:= i;
mas[count].j0:= j;
end;
for i:= 1 to count do
write('y=',mas[i].i0, ' x=',mas[i].j0,'|');
readln;
end.


Ошибка в цикле проверки - надо сверять каждый элемент матрицы X со всема элементами массива Z, ты же сравниваешь только с одним.



volvo,
n=100;
m=500;
r=100;
Время - где-то секунда...


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


Гость






Цитата
Время - где-то секунда...
Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось...

Цитата
но задачка-то явно учебная...
И что? Ограничений на средства достижения результата поставлено не было. Если тебя НЕ интересует оптимизированный вариант - дело твое...

Цитата
Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор...
Хоар на больших значениях может и захлебнуться. Я бы не стал его использовать... Есть много других методов сортировки...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гуру
*****

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

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


Цитата
Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось...

FPC


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


Гость






Bokul, не стал я ждать до завтра, сделал сегодня smile.gif

На не очень больших значениях тесты показывают примерно одинаковое время (порядка 16-20 ms), но при значениях:
r=1200;
n=1100;
m=1200;


разброс по времени такой (время замерялось GetTickCount()-ом, соответственно, понятно что FPC):
Цитата(Console)
Volvo:
359

Bokul:
8437
(замерял только время поиска, время вывода на печать не учитывалось...)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гуру
*****

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

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


Цитата

Volvo:
359

Bokul:
8437

Впечетляет.
volvo, кодом поделишься?


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


Гость






Поделюсь, только причешу малость ( может, еще быстрее сделаю smile.gif ). Но вот это - точно завтра... Кстати, и >>сортировку<< и >>поиск<< брал с нашего форума...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






Bokul,
вот такой код получился (код тестовый, поэтому в нем присутствуют директивы условной компиляции {$ifdef}...{$else}...{$endif}, за объяснениями - по ссылке)...

Прикрепленный файл  speed_test.pas ( 3.37 килобайт ) Кол-во скачиваний: 489


Чтобы прогнать тестовое значение, и посморреть правильность работы алгоритма достаточно определить условный символ TEST_SMALL (добавлением строки {$define TEST_SMALL} в начало программы, сейчас она уже добавлена), при этом на печать будет выведена и исходная матрица, и массив, и результат, т.е. все позиции элементов в матрице. Для тестирования на скорость (при больших массивах) эту строчку надо либо удалить, либо между символами { и $ добавить пробел (тогда эта строка превратится в комментарий), и перекомпилировать программу (!!!), и программа будет тестироваться с большими значениями, БЕЗ вывода на печать, только сам процесс поиска. То же самое касается и автора - с определенным __BOKUL будет выполняться алгоритм Bokul-а, иначе - мой...

Вот что выдала программа у меня:
Цитата(Console)
Volvo:
391

Bokul:
11356


(кстати, Bokul, при TEST_SMALL внимательно посмотри на результаты работы своего алгоритма. Есть подозрение, что он находит элементы неправильно, ибо на показанных местах в матрице стоят также и НЕ присутствующие в массиве элементы)...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14





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

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


Ребята, спасибо! Вы мне очень помогли good.gif Чтоб я без вас делал просто не представляю!!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гуру
*****

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

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


volvo, начал разбираться.
Вот, что-то я не понимаю :
Цитата
Есть подозрение, что он находит элементы неправильно, ибо на показанных местах в матрице стоят также и НЕ присутствующие в массиве элементы

Ну так же вроде и надо?:
Цитата
Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы


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


Гость






blink.gif Ну, да... Я почему-то пропустил слово "НЕТ"... Тогда в моем алгоритме "<>" поменять на "=".

Кстати, обнаружилось еще, что у нас i/j неодинаково заносятся в структуры. У меня
i0 := i; j0 := j;
а у тебя - наоборот, тоже надо подправить... Но на скорость это не повлияет...
 К началу страницы 
+ Ответить 

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

 





- Текстовая версия 28.03.2024 14:58
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name