Матрица и массив, Никак не пойму...... |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Матрица и массив, Никак не пойму...... |
fanatik |
Сообщение
#1
|
Группа: Пользователи Сообщений: 2 Пол: Мужской Реальное имя: Андрей Репутация: 0 |
Кто-нить помогите решить задачку. Текст следующий: Даны целочисленная матрица X[1:n,1:m] и целочисленный массив Z[1:r]. Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы. Буду очень благодарен за помощь.
|
мисс_граффити |
Сообщение
#2
|
просто человек Группа: Пользователи Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
что значит запомнить?
-------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
SuperMozg |
Сообщение
#3
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Если я правильно понял, то надо запомнить индексы обнуленных элементов матрицы:
const Сообщение отредактировано: volvo - |
Bokul |
Сообщение
#4
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
uses crt; -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
Сообщение
#5
|
Гость |
Ребята, это все прекрасно, конечно, но решение "в лоб" никогда быстротой не отличалось...
Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы? Есть предположение, что если отсортировать массив Z, то можно вместо прямого поиска в нем использовать, скажем, бинарный, что ускорит программу... |
SuperMozg |
Сообщение
#6
|
Группа: Пользователи Сообщений: 4 Пол: Мужской Репутация: 0 |
Заметьте, о величинах M, N и R ничего не сказано. А если они будут порядка сотен? Представляете себе время работы программы? Есть предположение, что если отсортировать массив Z, то можно вместо прямого поиска в нем использовать, скажем, бинарный, что ускорит программу... Это все верно, но задачка-то явно учебная... Вряд ли в ней нужны такие навороты. Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор... |
Bokul |
Сообщение
#7
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
SuperMozg, что-то мне кажется, что твоя прога не совсем правильно работает... Вот добавил к ней пау строчок для заполнения массивов данными, так получинные результаты не есть верными.
uses crt; Ошибка в цикле проверки - надо сверять каждый элемент матрицы X со всема элементами массива Z, ты же сравниваешь только с одним. volvo, n=100; m=500; r=100; Время - где-то секунда... -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
Сообщение
#8
|
Гость |
Цитата Время - где-то секунда... Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось...Цитата но задачка-то явно учебная... И что? Ограничений на средства достижения результата поставлено не было. Если тебя НЕ интересует оптимизированный вариант - дело твое...Цитата Если впихнуть в код бинарный поиск да еще и сортировку Хоара, то точно будет перебор... Хоар на больших значениях может и захлебнуться. Я бы не стал его использовать... Есть много других методов сортировки... |
Bokul |
Сообщение
#9
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Цитата Ты на чем компилировал? FPC? На TP будет больше... Попробую, завтра напишу, что получилось... FPC -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
Сообщение
#10
|
Гость |
Bokul, не стал я ждать до завтра, сделал сегодня
На не очень больших значениях тесты показывают примерно одинаковое время (порядка 16-20 ms), но при значениях: r=1200; разброс по времени такой (время замерялось GetTickCount()-ом, соответственно, понятно что FPC): Цитата(Console) Volvo: (замерял только время поиска, время вывода на печать не учитывалось...)359 Bokul: 8437 |
Bokul |
Сообщение
#11
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
Цитата Volvo: 359 Bokul: 8437 Впечетляет. volvo, кодом поделишься? -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
Сообщение
#12
|
Гость |
Поделюсь, только причешу малость ( может, еще быстрее сделаю ). Но вот это - точно завтра... Кстати, и >>сортировку<< и >>поиск<< брал с нашего форума...
|
volvo |
Сообщение
#13
|
Гость |
Bokul,
вот такой код получился (код тестовый, поэтому в нем присутствуют директивы условной компиляции {$ifdef}...{$else}...{$endif}, за объяснениями - по ссылке)... speed_test.pas ( 3.37 килобайт ) Кол-во скачиваний: 530 Чтобы прогнать тестовое значение, и посморреть правильность работы алгоритма достаточно определить условный символ TEST_SMALL (добавлением строки {$define TEST_SMALL} в начало программы, сейчас она уже добавлена), при этом на печать будет выведена и исходная матрица, и массив, и результат, т.е. все позиции элементов в матрице. Для тестирования на скорость (при больших массивах) эту строчку надо либо удалить, либо между символами { и $ добавить пробел (тогда эта строка превратится в комментарий), и перекомпилировать программу (!!!), и программа будет тестироваться с большими значениями, БЕЗ вывода на печать, только сам процесс поиска. То же самое касается и автора - с определенным __BOKUL будет выполняться алгоритм Bokul-а, иначе - мой... Вот что выдала программа у меня: Цитата(Console) Volvo: 391 Bokul: 11356 (кстати, Bokul, при TEST_SMALL внимательно посмотри на результаты работы своего алгоритма. Есть подозрение, что он находит элементы неправильно, ибо на показанных местах в матрице стоят также и НЕ присутствующие в массиве элементы)... |
fanatik |
Сообщение
#14
|
Группа: Пользователи Сообщений: 2 Пол: Мужской Реальное имя: Андрей Репутация: 0 |
Ребята, спасибо! Вы мне очень помогли Чтоб я без вас делал просто не представляю!!!!
|
Bokul |
Сообщение
#15
|
Гуру Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: 11 |
volvo, начал разбираться.
Вот, что-то я не понимаю : Цитата Есть подозрение, что он находит элементы неправильно, ибо на показанных местах в матрице стоят также и НЕ присутствующие в массиве элементы Ну так же вроде и надо?: Цитата Обнулить элементы матрицы X, которых нет в массиве Z и запомнить обнулённые элементы -------------------- Лао-Цзы :
Знать много и не выставлять себя знающим есть нравственная высота. Знать мало и выставлять себя знающим есть болезнь. Только понимая эту болезнь, мы можем избавиться от нее. |
volvo |
Сообщение
#16
|
Гость |
Ну, да... Я почему-то пропустил слово "НЕТ"... Тогда в моем алгоритме "<>" поменять на "=".
Кстати, обнаружилось еще, что у нас i/j неодинаково заносятся в структуры. У меня i0 := i; j0 := j;а у тебя - наоборот, тоже надо подправить... Но на скорость это не повлияет... |
Текстовая версия | 6.12.2024 18:42 |