Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
BF_
3 / 3 / 1
Регистрация: 07.09.2013
Сообщений: 78
1

Написать функцию которая возвращает True, если есть пара чисел, которая удовлетворяет условие

28.12.2016, 14:36. Просмотров 926. Ответов 7
Метки нет (Все метки)

Есть массив:
Pascal
1
arr : array[1..1000] of Integer;
Заполненный случайными числами от -32,768 до 32,767.

Нужно написать функцию которая возвращает True, если есть пара чисел, которая удовлетворяет условие:

Pascal
1
arr[i] + arr[j] = 0;
Если такой пары нет, то False

Пример:

-7 + 7 = 0 - True

P. S: Тупо перебирать все пары нельзя, потому что массив может быть на большее количество значений и это будет не оптимальное решение.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2016, 14:36
Ответы с готовыми решениями:

Рекурсия: создать логическую функцию, которая возвращает True, если ее аргумент - простое число
С помощью рекурсии, создать логическую функцию, которая возвращает True, если...

Написать функцию, которая возвращает значение Тrue, если аргумент - гласная буква
Задание №5.Составить программу на языке Pascal, используя процедуру или...

Написать функцию, которая возвращает максимальное из двух целых чисел, полученных в качестве аргумента
привет. не поможете с задачей на Паскале? Написать функцию, которая...

Написать функцию, которая возвращает N правых символов в виде строки
Помогите пожалуйста с программой: Функция - RIGHT(C:STRING;n:INTEGER):STRING...

Написать функцию, которая возвращает количество появлений заданного символа в строке символов
Требуется аписать функцию,которая возвращает кол-во появлений заданного символа...

7
vint-81
охотник
1009 / 533 / 650
Регистрация: 29.09.2014
Сообщений: 1,083
28.12.2016, 18:41 2
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function prot(arr:mas):boolean;
 var i,j:integer;
     f:boolean;
 begin
  i:=1;
  f:=false;
  while (not f)and(i<=n) do 
   begin
    j:=i+1;
    while (not f)and(j<=n) do
     begin
      if arr[i] + arr[j] = 0 then f:=true;
      inc(j)
     end;
    inc(i)
   end;
  prot:=f
 end;
ps: если массив будет такой: (4, 3, 2, 1, -1) программа тупо будет перебирать все пары
0
BF_
3 / 3 / 1
Регистрация: 07.09.2013
Сообщений: 78
29.12.2016, 10:20  [ТС] 3
vint-81, я решил эту задачу точно также, только через цикл for. На собеседовании мне сказали что это не оптимально и такое решение не подходит =)

Хотя Ваш вариант мне нравится больше, потому что тут
Pascal
1
if arr[i] + arr[j] = 0 then f:=true;
я делал тупо Exit;
0
AHBAR
239 / 239 / 167
Регистрация: 05.04.2013
Сообщений: 1,111
29.12.2016, 10:59 4
еще можно брать случайные индексы массива, так чтобы они не повторялись, до тех пор пока хотя бы одна пара не найдется.. Но если не найдется ни один, так и так переберется весь массив. так что это по сути тоже самое
0
BF_
3 / 3 / 1
Регистрация: 07.09.2013
Сообщений: 78
29.12.2016, 12:15  [ТС] 5
Я думал может есть алгоритм какой-то, возможно поиска. Потому что в теории, если это какая-то реальная выборка данных из базы на миллион записей и нужно обработать по этому алгоритму, то перебором всех элементов она будет выполнятся вечность.
С другой стороны такую выборку можно сделать и на сервере. Но это реальная задача с собеседования.
0
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4147 / 2740 / 2173
Регистрация: 22.11.2013
Сообщений: 7,660
29.12.2016, 13:28 6
Лучший ответ Сообщение было отмечено BF_ как решение

Решение

vint-81,
так короче:
Pascal
1
2
3
4
5
6
7
8
9
function prot(const a: array of Integer): Boolean;
var i, j: Integer;
begin
  prot:=True;
  for i:=Low(a) to High(a) do
    for j:=i+1 to High(a) do
      if a[i]=-a[j] then Exit;
  prot:=False;
end;
Добавлено через 10 минут
Цитата Сообщение от BF_ Посмотреть сообщение
на миллион записей
Если количество данных существенно шире диапазона Integer (65536 значений), то может иметь смысл:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const r1=-32768; r2=32767;
type TSmallInt = r1..r2;
function Test(const a: array of TSmallInt): Boolean:
type TInts = array [TSmallInt] of Integer;
var
  b: ^TInts;
  i, j: Integer; k: Longint;
begin
  New(b); FillChar(b^,SizeOf(b^),#0);
  for k:=Low(a) to High(a) do Inc(b^[a[k]]);
  i:=r2; j:=-r2;
  while (i<j) and not ((b^[i]=1) and (b^[j]=1)) do begin Inc(i); Dec(j); end;
  Dispose(b);
  Test:=i<j;
end;
В отличие от прежнего варианта, имеет линейную зависимость от исходных данных, а не квадратичную.

Добавлено через 1 минуту
или
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const r1=-32768; r2=32767;
type TSmallInt = r1..r2;
function Test(const a: array of TSmallInt): Boolean:
type TInts = array [SmallInt] of Byte;
var
  b: ^TInts;
  i, j: SmallInt; k: Longint;
begin
  New(b); FillChar(b^,SizeOf(b^),#0);
  for k:=Low(a) to High(a) do b^[a[k]]:=1;
  i:=-r2; j:=r2;
  while (i<j) and (b^[i]+b^[j]<>2) do begin Inc(i); Dec(j); end;
  Dispose(b);
  Test:=i<j;
end;
Добавлено через 3 минуты
Для FPC можно использовать
Pascal
1
2
3
4
type TInts = packed array [-32768..32767] of Boolean;
...
... b^[a[k]]:=True;
while (i<j) and b^[i] and b^[j] do ...
Такой массив легко влезет в стек (65536/8 = 8192 байт):
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
const r1=-32768; r2=32767;
type TSmallInt = r1..r2;
function Test(const a: array of TSmallInt): Boolean:
var
  b: packed array [TSmallInt] of Boolean;
  i, j: SmallInt; k: Longint;
begin
  FillChar(b,SizeOf(b),#0);
  for k:=Low(a) to High(a) do b[a[k]]:=True;
  i:=-r2; j:=r2;
  while (i<j) and not (b[i] and b[j]) do begin Inc(i); Dec(j); end;
  Test:=i<j;
end;
Добавлено через 8 минут
На самом деле эффект начнет проявляться где-то выше (пара вложенных циклов (i:1..n, j:i+1..n) меньше n-квадрат) 256 элементов (корень квадратный из 65536), плюс накладные расходы на просмотр 65536 значений.
1
BF_
3 / 3 / 1
Регистрация: 07.09.2013
Сообщений: 78
29.12.2016, 13:29  [ТС] 7
bormant, это круто, спасибо огромное!!
0
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4147 / 2740 / 2173
Регистрация: 22.11.2013
Сообщений: 7,660
29.12.2016, 14:37 8
BF_,
всю цепочку привожу только для иллюстрации того, как могли бы двигаться рассуждения.
Будет круто, когда научитесь сразу писать финальный вариант.

На самом деле последний и предпоследний варианты являются иллюстрацией компромисса память/скорость, в последнем компилятор будет хранить по 8 логических значений в байте, но для доступа к ним потребуются дополнительные операции: вычисление нужного байта и нужной маски. Не исключено, что при ручном программировании этих действий может быть какой-либо потенциал для экономии (циклический сдвиг масок, при переполнении изменение счетчика байтов), но возможно ли его реализовать средствами языка, не опускаясь на уровень ассемблера, судить не возьмусь.

Добавлено через 55 минут
Если для массива из 1000 разных значений (худший случай) квадратичный вариант работает за 24m48.583s, то линейный вариант с подсчетом -- за 0m0.001s. Цифры попугайские, но сопоставимые, поскольку получены в одних и тех же условиях.
0
29.12.2016, 14:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2016, 14:37

Написать функцию Procent, которая возвращает процент от числа полученного в качестве аргумента
Написать функцию, Procent, которая возвращает процент от числа полученного в...

Напишите рекурсивную функцию, которая возвращает среднее из n элементов массива чисел
Напишите рекурсивную функцию, которая возвращает среднее из n элементов массива...

. Написать функцию, которая по двум заданным одномерным массивам (A размера m и B размера n) вычисляет двумерный массив c(ij)=a(i)*b(j) и возвращает
Написать функцию, которая по двум заданным одномерным массивам (A размера m и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru