Алгоритмы - [9] :: Прикладное программирование :: Компьютерный форум Ru.Board

Перейти из форума на сайт.

Новости • Файловые архивы
Поиск • Активные темы • Топ лист
Правила • Кто в on-line?

Вход • Забыли пароль? • Первый раз на этом сайте? • Регистрация

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Алгоритмы

Модерирует : ShIvADeSt
Версия для печати • Подписаться • Добавить в закладки
Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Открыть новую тему

Написать ответ в эту тему

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

все вопросы по алгоритмам, их созданию и сопровождению без привязки к какому-нибудь конкретному языку программирования...
ну или с привязкой :)
дать идею, помочь с математикой или, если вам не помогли в профильном топе...

по возможности используйте псевдокод в своих сообщениях

ссылки

"ebook'и -- сборники алгоритмов"

только помните, что тут никто ничего _делать за вас_ не обязан!
для этого есть специальные места со своими ценами...

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 09:28 16-12-2016 | Исправлено: akaGM, 09:03 12-07-2019

MBK2 Gold Member	Редактировать \| Профиль \| Сообщение \| Цитировать \| Сообщить модератору akaGM Я вам показал алгоритм, который корректно обрабатывает все вышеприведенные коллизии. Хотите пользуйте, хотите велосипедьте дальше.
	Всего записей: 5152 \| Зарегистр. 18-09-2018 \| Отправлено: 08:40 09-09-2023

akaGM Platinum Member	Редактировать \| Профиль \| Сообщение \| Цитировать \| Сообщить модератору MBK2 ок, ок, спасибо :)
	Всего записей: 25186 \| Зарегистр. 06-12-2002 \| Отправлено: 09:05 09-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

cваял :)

как-то слишком просто...
можно придираться :)

вставить массив Xsrc в Xdst без изменения размера.
массивы -- значения с плав.точкой, отсортированные по увеличению,
нумерация с единицы.

Xdst -- массив-приёмник, кот. надо изменить;
Xsrc -- источник, из него вставляется;
Xout -- выходной результирующий массив;
Nsrc, Ndst -- размеры;
currPos -- индекс, текущая позиция в массиве Xdst.

Код:

////////////////////////////////////////////////////
Xout = Xdst // copy for preserving orig Xdst

currPos = 1

for n from 1 to Nsrc do begin

while ( Xout[currPos] < Xsrc[n] ) do
currPos = currPos + 1

Xout[currPos] = Xsrc[n]
currPos = currPos + 1 // next pos/element

endfor
////////////////////////////////////////////////////

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 22:52 13-09-2023 | Исправлено: akaGM, 01:06 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

NB

* размер массива Xsrc всегда меньше Xdst, причём много меньше, всегда;
* элементы Xsrc располагаются внутри Xdst, тоже всегда;

поэтому никаких проверок на этот счёт делать не надо.
остальные комментарии по поводу гран.условий и критических ситуаций приветствуются...

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 01:04 14-09-2023 | Исправлено: akaGM, 01:05 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Код:

import numpy as np

list1 = [2.2, 3.9, 4.1]
list2 = [1, 5, 6, 7]

np_array = np.asarray(list2)
ret_array = list2.copy()
mx = -max(list2)
for val in list1:
idx = (np.abs(np_array - val)).argmin()
ret_array[idx] = val
np_array[idx] = mx

print(sorted(ret_array))

находит в list2 индекс ближайшего элемента из list1 и заменяет, после чего отодвигает его в копии подальше, чтобы не переопределился снова другим элементом из list1

если в списке могут быть и отрицательные числа, то mx нужно задать немного иначе.
например так
mx = -max(np.abs(list2)) - max(np.abs(list1))

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 02:45 14-09-2023 | Исправлено: Mavrikii, 03:00 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

увы и ах, питон не подойдёт...

Цитата:

все вопросы по алгоритмам без привязки к конкретному языку

вот если б паскаль/с/фортран, я б даже жабу с js съел, а питон -- никак...

Цитата:

могут быть и отрицательные числа

нет, их там нет...

спасибо за внимание...

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 03:12 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Цитата:

я б даже жабу с js съел,

https://jsfiddle.net/thqx3fw9/

Код:

const list1 = [2.2, 3.9, 4.1],
list2 = [1, 5, 6, 7];

let ret_array = [...list2],
mod_list2 = [...list2],
mx = Math.max(...list2.map(Math.abs)) + Math.max(...list1.map(Math.abs));

function find_closest(arr, val) {
let idx = 0, dist = Math.abs(arr[0] - val);
for (let idx_ = 1; idx_ < arr.length; idx_++) {
let dist_ = Math.abs(arr[idx_] - val);
if (dist_ < dist) {
dist = dist_;
idx = idx_;
}
}
return idx;
}

for (let idx = 0; idx < list1.length; idx++) {
let idx_ = find_closest(mod_list2, list1[idx]);
ret_array[idx_] = list1[idx];
mod_list2[idx_] = -mx;
}

alert(ret_array.sort());

ps: вариант покороче
жертвует list2, и еще неизвестно заранее, какой из list1 может оказаться ближе к элементу list2 при замене, так как не просматривается заранее.

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 04:47 14-09-2023 | Исправлено: Mavrikii, 01:47 15-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

всё это здорово, но у меня уже _написан, встроен и работает_ мой код, и я бы был гораздо более благодарен за слова в его адрес...
// ненавижу править/разбираться в чужом коде :)

почему-то мой код кажется короче (если брать строчки от 'function' и перед alert'ом) и эффективнее чем... :)

Добавлено:

я думал, это ты написал :)
да ещё погляд только под VPN...

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 07:01 14-09-2023 | Исправлено: akaGM, 07:16 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Цитата:

я думал, это ты написал

я и написал, просто думал в другом направлении - ища ближайший элемент.

Цитата:

Xout[currPos] < Xsrc[n]

этот вариант может выйти за пределы массива

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 07:27 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

Цитата:

я и написал

а что выложил... куда-то в недружественную страну? ;)

Цитата:

Xout[currPos] < Xsrc[n]

этот вариант может выйти за пределы массива

вот это супер! большое человеческое...

while ( (Xout[currPos] < Xsrc[n]) and (currPos < Ndest) )

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 07:44 14-09-2023 | Исправлено: akaGM, 07:51 14-09-2023

MBK2

Gold Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Цитата:

как-то слишком просто...
можно придираться

Да нет, вроде все ok

Всего записей: 5152 | Зарегистр. 18-09-2018 | Отправлено: 07:57 14-09-2023 | Исправлено: MBK2, 08:07 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Цитата:

while ( (Xout[currPos] < Xsrc[n]) and (currPos < Ndest) )

не поможет. если первый элемент, после которого вставить, находится на позиции к краю ближе количества элементов в первом списке.

Цитата:

а что выложил... куда-то в недружественную страну?

пользуюсь тем, что удобно.

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 08:03 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

Цитата:

не поможет. если первый элемент, после которого вставить, находится на позиции к краю ближе количества элементов в первом списке.

не очень понял "элемент, после которого вставить" и "количества элементов в первом списке" -- это всё первый список и есть.
в моих обозначениях можешь написать?

Цитата:

пользуюсь тем, что удобно.

ну правильно, пусть зрители сами там с впн ковыряются,
я лично с третьего захода только увидел...

Добавлено:
MBK2

Цитата:

Да нет, вроде все ok

оказывается не всё...

Добавлено:

на двух реальных наборах моих данных пока отработало, посмотрим...

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 08:11 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

akaGM

Цитата:

ну правильно, пусть зрители сами там с впн ковыряются,

я код процитировал

Цитата:

в моих обозначениях можешь написать?

пример
[5, 6] -> [3, 4] или [5.5, 8]
в первом случае вообще не вставится.
во втором - только вместо 8

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 08:17 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

Цитата:

пример

неудачный пример:
Цитата:

* размер массива Xsrc всегда меньше Xdst, причём много меньше, всегда;

Цитата:

я код процитировал

свой?

Добавлено:

повторю на всякий...

Цитата:

* элементы Xsrc располагаются внутри Xdst, тоже всегда;

по величине

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 08:28 14-09-2023

Mavrikii

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:

* размер массива Xsrc всегда меньше Xdst, причём много меньше, всегда;

да, блин.. ну добавить сколько угодно слева.
[5, 6, 7] -> [1, 2, 3, 4] или [1, 2, 5.5, 8]

Цитата:

свой?

свой

Всего записей: 15885 | Зарегистр. 20-09-2014 | Отправлено: 08:30 14-09-2023 | Исправлено: Mavrikii, 08:32 14-09-2023

akaGM

Platinum Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

Цитата:

[5, 6, 7] -> [1, 2, 3, 4]

нефизичный пример, по реальным данным такого быть не может,
но устроит 0 + [5, 6, 7] или + 10

Цитата:

[1, 2, 5.5, 8]

будет [1, 2, 6, 8]
да, дырка, но это тоже нестрашно, тк нереализуемо...
но править, конечно, надо...

еще одна нота бене

массив, в кот. вставляют -- равномерная однородная сетка (с очень мелким шагом в надежде "поймать" значения В), задаваемая с запасом
если B[B1..Bm] вставляют в [A1..An],
то A1 << B1, Bm << An

Всего записей: 25186 | Зарегистр. 06-12-2002 | Отправлено: 09:14 14-09-2023 | Исправлено: akaGM, 09:45 14-09-2023

MBK2

Gold Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Mavrikii

Цитата:

[5, 6] -> [3, 4]

Ну я так понимаю, что сразу по двум критериям не проходит: 1) второй массив должен быть больше первого 2) все элементы первого массива должны попадать внутрь второго или хотя бы быть меньше

Всего записей: 5152 | Зарегистр. 18-09-2018 | Отправлено: 12:50 14-09-2023

akaGM Platinum Member	Редактировать \| Профиль \| Сообщение \| Цитировать \| Сообщить модератору я ошибся... мой алг на данных [5, 6, 7] -> [1, 2, 5.5, 8] отработал как == [1, 2, 5, 6] неплохо на плохой синтетике...
	Всего записей: 25186 \| Зарегистр. 06-12-2002 \| Отправлено: 14:09 14-09-2023

MBK2

Gold Member

Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:

мой алг на данных

[5, 6, 7] -> [1, 2, 5.5, 8]

А вот это, кстати, и вправду баг. На этих данных ваш алгоритм рушится на 2 шаге по выходу за границы массива

Всего записей: 5152 | Зарегистр. 18-09-2018 | Отправлено: 15:06 14-09-2023

Открыть новую тему

Написать ответ в эту тему

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Алгоритмы

Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2025

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC