1 Востаннє редагувалося Yola (26.11.2015 21:27:50)

Тема: Найбільше впорядковане число з елементів двох масивів.

Маємо два масиви довжини M і N, що мають елементи 0-9. Потрібно створити найбільше можливе число довжини K з елементів цих масивів, так що впорядкування цифр у отриманому числі збігається з впорядкуванням у масивах з яких ці цифри взяли. Якщо два елементи a, b взяли з масив1 і a передує b у масив1, то у отриманому числі a повинно передувати b.
Приклад: N=4 і M=6
Масив1 = {3,4,6,5}
Масив2 ={9,1,2,5,8,3}
Нехай K = 5, тоді число буде {9,8,6,5,3}
Видно, що {9,8,3} взяли з Масив2 у тому ж порядку як вони зустрічаються в цьому масиві, аналогічно {6,5} взяли з Масив1 і 98653 - це максимальне з можливих чисел.

2

Re: Найбільше впорядковане число з елементів двох масивів.

На перший погляд не бачу нічого кращого за трохи оптимізований перебір:
- беремо максимальну цифру, що знаходиться якомога лівіше так, щоб ще K-1 цифра лишалася в обох масивах (тобто якщо нам треба набрати 5 цифр і масиви виглядають {1,1,7} і {3,4,5,6,9}, то нам потрібна 7, а не 9 - бо якщо взяти 9, лишиться ще всього 3 цифри).
- якщо ця цифра одна, просто викидаємо те, що лівіше за неї (і її також), зменшуємо K на 1 і шукаємо далі
- якщо цих цифр дві (в обох масивах), то розглядаємо два варіанти (найпростіше - рекурсією) і беремо максимум.

Подякували: Yola1

3

Re: Найбільше впорядковане число з елементів двох масивів.

Гм... Цікавий підхід. Гадаю він спрацює, хоча буде й багато галужень в алгоритмі.

Для мого підходу я зробив таке спостереження:

Якщо нам потрібно знайти найбільше число довжини К. То воно складатиметься з М цифр одного масиву і К-М цифр другого масиву. І обидві складові являтимуть собою максимальні числа відповідних довжин з відповідних масивів.

Отже нам потрібно вибрати з кожного масиву максимальні числа довжин від 0 до К. Злити відповідні двійки чисел 0-K, 1-(K-1) і т.д. в одне як це робиться в сортуванні злиттям. І вибрати найбільше.

Знайти найбільше число необхідної довжини з одного масиву не складно.

4

Re: Найбільше впорядковане число з елементів двох масивів.

Правда ваша.