Форум программистов, компьютерный форум, киберфорум
Наши страницы

Pascal (Паскаль)

Войти
Регистрация
Восстановить пароль
 
chealbert
237 / 127 / 45
Регистрация: 13.10.2011
Сообщений: 421
#1

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

27.02.2016, 14:56. Просмотров 822. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Самый быстрый перебор пар чисел (Pascal):

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

перебор чисел - Pascal
есть уравнение 13n+21m=Y Значение Y известно Требуется перебрать числа n и m от 0 до 30 000 и известо что n>=m Помогите реализовать...

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

Сколько пар одинаковых чисел в последовательности - Pascal
дана послед из 7 чисел. Выяснить сколько в ней пар одинаковых. Чисел стоящих рядом Добавлено через 9 часов 5 минут program q; uses...

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

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

3
Cyborg Drone
Модератор
5490 / 3099 / 1286
Регистрация: 17.08.2012
Сообщений: 10,015
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 / 45
Регистрация: 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
3749 / 2446 / 1306
Регистрация: 22.11.2013
Сообщений: 6,788
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
Привет! Вот еще темы с ответами:

Найти большее из наименьших значений пар чисел - Pascal
№1(с помощью процедуры) Даны действительные числа S,t. Получить Z=f(t,-25,1.17) + f(2.2,t,S-t), где f(a,b,c)=(2a -b-sin(c)) / (5+c). ...

сколько в последовательности содержится пар чисел одного знака - Pascal
В сформированной вами таблице из N случайных действительных чисел A1 ,A2 , A3,... AN ,где 5&lt;N&lt;50 и -100 требуется: подсчитать , сколько в...

Включить в программу функцию, возвращающую true, если самый высокий ученик имеет и самый большой все, и fal - Pascal
Включить в программу функцию, возвращающую true, если самый высокий ученик имеет и самый большой все, и false в противном случае.

Дан массив чисел. Найти сколько в нем пар одинаковых соседних элементов. - Pascal
(1). Дан массив А(n) состоящий из целых чисел. Определить количество элементов имеющих четные порядковые номера, и являющихся нечетными...


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

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

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