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

Самый быстрый перебор пар чисел

27.02.2016, 14:56. Просмотров 1001. Ответов 3
Метки нет (Все метки)

Задача: Есть число N. Найти все пары чисел от 1 до N, которые в сумме дают M.
Можно так:
Pascal
1
2
3
for i:=1 to n-1 do
 for j:=i to n do
  if i+j=m then write('(',i,',',j,')');
При больших N будет работать медленно. Как сделать быстрее? Какой алгоритм вообще самый быстрый?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.02.2016, 14:56
Ответы с готовыми решениями:

Из пункта А в пункт Б самый быстрый путь
Ребята, выручайте. Задача интересная, прикладная, но что-то я подвис с её...

Найти количество пар натуральных чисел, где одно из чисел делится на другое
Есть число n, оно от 1 до 1000. Нужно найти количество пар натуральных чисел,...

Среди заданных чисел найти количество пар чисел, модуль разности которых равен заданному числу
Дана строка из n целых чисел. Найти кол-во пар чисел модуль разности которых...

перебор чисел
есть уравнение 13n+21m=Y Значение Y известно Требуется перебрать числа n и m...

Перебор чисел (Задача)
Есть массив M с произвольными числами от одного до тысячи, N<16. Нужно выяснить...

3
Cyborg Drone
Модератор
5296 / 3175 / 2442
Регистрация: 17.08.2012
Сообщений: 10,189
27.02.2016, 15:40 2
Задание некорректное. Таких чисел, вообще говоря, бесконечное множество. Буду считать, что Вы полагаете, что числа бывают только натуральные.

Перебирать только нужные пары:
Pascal
1
2
3
4
  if n > m
    then k := m - 1
    else k := n - 1;
  for i := 1 to k do writeln(i, ', ', m - i);
Если зеркальные пары не вычислять, тогда так:
Pascal
1
2
3
4
  if n > m
    then k := m div 2
    else k := n div 2;
  for i := 1 to k do writeln(i, ', ', m - i);
Так, из праздного любопытства: а зачем вообще нужно эти пары перебирать?
0
chealbert
237 / 127 / 80
Регистрация: 13.10.2011
Сообщений: 421
27.02.2016, 17:45  [ТС] 3
Спасибо за ответ. Что-то я действительно неконкретно озадачил)
Уточняем - числа только целые, положительные, в пределах longint.
Задача: найти все "взаимнопростые" (т.е у которых только один общий делитель - 1) пары чисел до N.
Искал как быстрее перебирать пары для проверки.
Но если уж поконкретнее , то хорошо бы еще и поиск "взаимной простоты ускорить"
Моя функция для проверки:
Pascal
1
2
3
4
5
6
7
8
9
10
function prost(var x,y:longint):bolean;
var i:longint;
begin
 prost:=true;
 if x<y then
  for i:=2 to x do
   if x mod i=0 then 
     if y mod i=0 then prost:=false;
 else begin x:=x+y; y:=x-y; x:=x-y; prost(x,y) end;
end;
0
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
3909 / 2565 / 2086
Регистрация: 22.11.2013
Сообщений: 7,182
27.02.2016, 20:30 4
Предварительно вычислите список простых от 2 до 65535, проверяйте делимость только на простые, не превышающие кв.корня из меньшего, плюс делимость большего на меньшее.

Добавлено через 1 минуту
В строке 9 было достаточно
Pascal
1
else prost(y,x);
Добавлено через 2 минуты
После проверки делимости на 2 достаточно проверять делимость только на нечетные (сразу уменьшите количество проверок вдвое). Проверять достаточно до корня из x. Параметры-переменные тут вряд ли нужны.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.02.2016, 20:30

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

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

Сколько пар одинаковых чисел в последовательности
дана послед из 7 чисел. Выяснить сколько в ней пар одинаковых. Чисел стоящих...


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

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

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