Изменения

Перейти к: навигация, поиск

Meet-in-the-middle

340 байт добавлено, 22:59, 16 декабря 2012
Нет описания правки
=== Реализация ===
// <tex>sum </tex> - массив сумм <tex> a + b</tex>, <tex> cnt </tex> - счетчик массива <tex> sum</tex> '''findsum()''' <tex> sum \leftarrow \emptyset </tex> '''for ''' <tex> a = 0 to N - 1\in A </tex> '''for ''' <tex> b = 0 to N - 1\in A </tex> <tex> sum[cnt].s = \leftarrow A[a] + AB[b];</tex> <tex> sum[cnt].a = \leftarrow a;</tex> <tex> sum[cnt++].b = \leftarrow b;</tex> <tex> cnt++ </tex> '''sort'''<tex>(sum);</tex> '''for ''' <tex> c = 0 to N - 1\in A </tex> '''for ''' <tex> d = 0 to N - 1\in A </tex> '''if (''' сумма <tex> -(A[c] + A[d]) </tex> есть в массиве массив <tex> sum)</tex> ind = <tex> index \leftarrow </tex> индекс суммы <tex> -(A[c] + A[d]) в массиве sum;</tex> print '''return''' <tex>(sum[indindex].a, sum[indindex].b, A[c], A[d]);</tex> '''return; print(''' "No solution"); 
Итоговое время работы <tex> {O(N^2\log{N}}) </tex>.
28
правок

Навигация