Question

Дан массив из N целых чисел. Zero- quadruple- это произвольные четыре числа из этого массива, сумма которых равна нулю. Найдите сколько различных Zero- quadruple существует в этом массиве

Answer 1

Var a:array [1..100] of integer;
      n, i, zq, k, l, j: integer;
begin
readln(n);
for i:=1 to n do  a[i] := random(500) - 249;
for i := 1 to n do 
      for j := i to n do   
           for k := j to n do
                for l := k to n do 
                   if a[i] + a[j] + a[k] + a[l] = 0 then inc(zq);
writeln(zq);
end.

Answer 2

Для нахождения числа различных Zero-quadruple в данном массиве из N целых чисел, вам нужно рассмотреть все возможные комбинации четырех чисел и проверить, сумма которых равна нулю. Ниже представлен пример алгоритма на языке Python:

def find_zero_quadruples(arr):
    n = len(arr)
    zero_quadruples = set()

# Сортируем массив для оптимизации
    arr.sort()

# Перебираем все возможные комбинации четырех чисел
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            left = j + 1
            right = n - 1

while left < right:
                current_sum = arr[i] + arr[j] + arr[left] + arr[right]

if current_sum == 0:
                    zero_quadruples.add((arr[i], arr[j], arr[left], arr[right]))
                    left += 1
                    right -= 1
                elif current_sum < 0:
                    left += 1
                else:
                    right -= 1

return len(zero_quadruples), zero_quadruples

# Пример использования
arr = [1, 0, -1, 0, -2, 2]
count, quadruples = find_zero_quadruples(arr)

print(f"Количество различных Zero-quadruple: {count}")
print("Zero-quadruple:")
for quad in quadruples:
    print(quad)

Этот алгоритм использует сортировку массива для оптимизации процесса. Затем он перебирает все уникальные комбинации четырех чисел, используя два вложенных цикла и два указателя (left и right), чтобы проверить сумму. Если сумма равна нулю, то данная четверка добавляется во множество `zero_quadruples`. После завершения перебора возвращается количество уникальных Zero-quadruple и сами Zero-quadruple.

Примечание: Этот код предполагает, что массив может содержать дубликаты чисел, и он включает только уникальные Zero-quadruple во множество `zero_quadruples`.