Така че, ако сте се натъкнали на този проблем или нещо подобно, ето как да го разрешите.
Първо изложението на проблема.
Даден ви е набор S от цели числа между -30 000 и 30 000 (включително).
които удовлетворяват:
d!=0
Вход
Първият ред съдържа цяло число N (1 ≤ N ≤ 100), размерът на набор S.
Елементите на S са дадени в следващите N реда, по едно цяло число на ред. Дадените числа ще бъдат различни.
Изход
Изведете общия брой възможности.
Тази редакционна статия не е просто решение на проблема, а мисловен процес, върху който ще надграждаме с времето, така че да можете да мислите следващия път, когато възникне подобен проблем.
Да започваме!
Когато интерпретираме задачата, това са изводите.
1. От дадения масив трябва да изберем 6 числа.
2. Числата могат да се повтарят. Това означава, че нямате нужда от минимум 6 числа (не се притеснявайте, дори това да е условието, ще можете да го разрешите, след като приключим).
пример, да кажем, че трябва да изобразите 4 числа от масив [2,1,3] за образуване на 6: Можете да изберете 2 три пъти, или 3 два пъти, или 1 шест пъти или 1,2 и 3, за да образувате 6.
3. Тези 6 числа имат за да удовлетвори уравнението. Това означава, че LHS и RHS трябва да са еднакви.
И така, първият подход на груба сила, за който би се замислил всеки начинаещ състезателен програмист, е как да изберем числа от масив, какви са комбинациите. Нека сега да разгледаме подбора в детайли.
да кажем масив = [1,3,4] и трябва да изберем 4 числа
можете да изберете
1,1,1,1
1,1,1,3
1,1,1,4
1,1,3,1
1,1,3,3
1,1, 3,4
1,1,4,1
…. и така нататък .
Наблюдавайте внимателно сега! Променям само 1 число наведнъж с всички възможни числа.
Това означава, че за да изберете 4 числа от произволен масив, имате нужда от 4 цикъла, където индексът се променя един след друг (i,j,k,l )
Така че псевдо кодът ще бъде както следва.
var комбинации = празен масив
за i=0 до i‹дължина на масива:
за j=0 до j‹дължина на масива:
за k=0 до k‹дължина на масива:
за l=0 до l‹дължина на масива:
променлива комбинация = [масив[i],масив[j],масив[k],масив[l]]
добавяне на комбинация към набор от комбинации
- Имайте предвид вдлъбнатината.
Така че просто получихме всяка комбинация в комбинации
Сега всичко, което трябва да направим, е да проверим за комбинации, които отговарят на определени критерии
Но не е ли това най-лошият възможен начин за решаване на нашия проблем.
Нашият проблем ще има времева сложност от n степен 6.
Нека помислим за начин, по който можем да намалим това.
Вижте уравнението, което ни е дадено.
((a*b+c)/d)-e=f
можем ли да променим това, за да изберем само 3 числа
Да, можем
a*b+c = (f+e)d
Така че сега можем да поставим комбинации от лявата страна (lhs) в един масив и комбинации от дясната страна (dhs) в друг и ще ни трябват само 3 цикъла за това.
Страхотно, нали?
Нека направим това
за i=0 до i‹дължина на масива:
за j=0 до j‹дължина на масива:
за k=0 до k‹дължина на масива:
lhs.append(arr [i]*arr[j]+arr[k])
rhs.append(arr[k]*(arr[i]-arr[j]))
Сега всичко, което трябва да направим, е да видим колко числа в lhs съвпадат с числа в rhs.
Още 1 концепция (малка) — Пример „c1.
Да кажем, че имате масив [2,2,3,4,5,5,6]
и други като [2,3,3,5,5,5,6,6]
Всеки от двата масива има уникален начин да стигне до това число
така че ако ви попитам сега по колко начина (комбинации) можете да получите число 5, което е и в двата масива, какъв ще бъде вашият отговор?
Брой 5 в масив1(x), умножен по брой пъти в масив2(y)!
Което е 2*3 = 6(x*y)
Ако имаше 3 масива, бихте умножили броя на изявите и в трите масива (x*y*z)
Така че ще приложим тази концепция към lhs и rhs масиви.
Обобщете го, за да получите общ брой пъти!
Общо = сбор от възможности
Както в примера „c1“: Общо = 2*1 + 1*2 + 1*0 + 2*3 + 1*6
което не е нищо друго освен възможности от съответно 2,3,4,5,6.
Последната част включва Долна граница и Горна граница, за да получите брой във всеки масив, с който всички са запознати (предполагам).
Също така не забравяйте, че има условие d!=0: Така че, ако d е 0, не вземайте предвид тази комбинация.
Това е всичко, до следващия път. Успокой се!
