Цитата(Akina @ 28.2.2013, 16:25  ) |
| Какие имеются ограничения на элементы массива? |
Могут они быть отрицательными? дробными? тысячезначными? повторяющимися?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > помогите с алгоритмом |
| Автор: knut 28.2.2013, 14:37 |
| добрый день помогите с алгоритмом. задача. есть два неупорядоченных массива a и b. b отличается тем что в нем отсутствует 2 элемента, (т.е их удалили) наиболее оптимальным методом найти эти два элемента. Пример. 1 4 5 2 6 7 3 10 1 5 6 7 2 3 10 и 4 |
| Автор: Lipetsk 28.2.2013, 15:05 |
| отсортируйте один из массивов берите по очереди элементы из второго массива и ищите их в первом, если нашли, то вычеркивайте из первого |
| Автор: Akina 28.2.2013, 15:25 |
| Какие имеются ограничения на элементы массива? |
| Автор: Zmaster555 28.2.2013, 15:48 |
| Думаю довольно неплохим тут будет следующий алгоритм. Для начала сортируем оба массива (по возрастанию, например). Если в неполный массив подставить 2 отсутствующих элемента, то он будет полностью идентичен первому массиву, соответственно эти два недостающих элемента и в отсортированных массивах должны будут находится на одних и тех же местах. Следовательно, просто остается сравнить каждый элемент первого массива с соответствующим элементом второго (неполного) массива. Пример: 1 4 5 2 6 7 3 10 {1 массив} 1 5 6 7 2 3 {2 массив} 1 2 3 4 5 6 7 10 {1 отсортированный массив} 1 2 3 5 6 7 {2 отсортированный массив} Пусть полный массив это A, неполный - B, дальше смотрим: A[1]=B[1], все норм, совпадают A[2]=B[2], тоже A[3]=B[3], тоже A[4]!=B[4], а вот тут нет, элемент неполного массива не совпадает => отсутствует элемент, равный A[4], т.е. четверка. И тут либо вставляем этот элемент в неполный массив и продолжаем, либо убираем этот элемент из полного массива. Ну и так далее. Извини за много букв, люблю все разжевывать до мелочей. |
| Автор: knut 28.2.2013, 15:54 |
| сложность алгоритма o(n) + m и можно использовать дополнительную память только для одной переменной |
| Автор: Akina 28.2.2013, 16:29 | ||
knut, повторяю
Могут они быть отрицательными? дробными? тысячезначными? повторяющимися? |
| Автор: knut 28.2.2013, 16:44 |
| Akina, натуральные положительные числа ,нет они не повторяются. спасибо. |
| Автор: Akina 28.2.2013, 16:50 |
| knut, ты способен отвечать на вопрос ПОЛНО? Есть ли верхняя граница? или, просмотрев весь список, можно в конце обнаружить число из миллиона цифр? |
| Автор: knut 28.2.2013, 16:58 | ||||||
Akina,
нет
число не одно а два. да можно обнаружить в конце. |
| Автор: Akina 28.2.2013, 17:52 |
| Ок. Первый проход. Находим самое большое число. Второй проход. Зная диапазон, XORим числа обоих списков общим потоком, используя память для одной переменной. Результат равен XORу двух отсутствующих во втором списке чисел. Как действовать дальше, не имея доп. памяти, пока не придумал. |
| Автор: Pavia 28.2.2013, 17:56 | ||
knut,
Не получиться такой список не поместиться в память компьютера. Да тут даже одно число не влезет в память компьютера. Так что пока вы не сделаете реального условия вы не получите реального ответа. Добавлено через 1 минуту и 42 секунды Akina, По моему автор путает цифры с числами. |
| Автор: Akina 28.2.2013, 19:25 | ||
На такие мелочи я не стал обращать внимание... в его словах всё ещё несколько нестыковок и нелепиц... |
| Автор: volatile 1.3.2013, 00:05 |
| за O(n) проходов можно решить c 2-мя переменными (достаточной точности.) S = 0; P = 1; for (i = 0; i < size; ++ i) { S += first [i] - second [i]; P *= first [i] / second [i]; } пробегаем весь массив. В результате имеет сумму и произведение двух оставшихся неизвестных чисел. решить элементарное уравнение x + y = S x * y = P труда, думаю уже не составит.  |
| Автор: Lipetsk 1.3.2013, 07:50 |
| volatile, классная идея только не хватает пары if, т.к. размеры массивов разные |
| Автор: Akina 1.3.2013, 08:14 |
| volatile, теоретически алгоритм верен. Практически же... Если на стадии суммирования-вычитания можно принять меры к тому, чтобы не возникло вычислительных проблем (например, в зависимости от текущей суммы и следующих членов рядов - либо вычитать, либо прибавлять), то вот с умножением и делением будет большая проблема - потеря точности... даже принимая специальные меры, можно за счёт неточного представления промежуточного произведения получить неверный результат. |
| Автор: Akina 1.3.2013, 09:09 |
| Вот только что промоделировал на случайном массиве из 64к элементов в пределах unsigned long. Если вычисления проводить в double - ну более-менее, хотя один расчёт из двадцати дал ошибку на единицу (102201990, расчётно 102201989). Счас попробую в single (он, как и ulong, 4 байта)... боюсь, будет грустно. |
| Автор: Akina 1.3.2013, 09:37 |
| Один расчёт из 10 дал ошибку - 17123904, расчётно 17123903... |
| Автор: maxim1000 1.3.2013, 11:19 |
| думаю, лучше считать вместо произведения сумму квадратов - ошибки меньше будут |
| Автор: Akina 1.3.2013, 11:36 | ||
1*1+8*8=4*4+7*7=65 аналогично с кубами 1*1*1+12*12*12=9*9*9+10*10*10=1729 То же и с остальными степенями... не пойдёть. |
| Автор: maxim1000 1.3.2013, 15:32 | ||
то, что квадраты требуют больше места, чем числа - ожидаемо просто, если среди чисел нет уж очень большого неравенства (типа, одно огромное, а остальные маленькие), то в случае с квадратами результирующее число будет меньше понятно, что это уже использует какие-то предположения о числах... |
| Автор: maxim1000 1.3.2013, 15:55 |
| о... если предположить, что в дополнительных переменных у нас достаточно бит для хранения любого числа из массива, то можно найти числа по половинкам: 1. сначала рассматриваем младшую половину бит каждого элемента, считаем для них суммы и суммы квадратов - всё поместится, находим пару младших половинок 2. то же самое для старших - находим пару старших половинок чтобы понять, какую младшую половинку соединить с како старшей, просто пробуем оба варианта, проверяем, какой подходит |
| Автор: volatile 1.3.2013, 23:41 | ||||
а точнее, переменная P Должна быть в 2 раза длиннее чем типы массива. переменная S Должна иметь на 1 бит больше чем типы массива. Тогда решаецца строго, для любых данных. (при аккуратном программировании). double не подойдет для 32 разрядов, так как там 56 бит (если не ошибаюсь.) а нужно 64 битов мантисы. float тем более. long double в gcc, должен подойти. long double у M$ не пойдёт. Ну или делать как предлагает maxim1000, длинную арифметику вручную. |