Использование цикла для решения простых перебор..


Использование цикла для решения простых переборных задач (поиск наименьшего простого делителя данного натурального числа, проверка числа на простоту, и т.д.).
Поиск делителей числа. Простые числа
Натуральное число b называют делителем, натурального числа а, если а представимо в виде произведения
а=bс, (1)
где с натуральное число. В этом случае говорят, что число а делится без остатка на число b, или, короче, число а делится на число b. Из формулы (1) следует, что число а также делится на число с, т. е. сделитель числа а. Например, 15==3*5, 3 и 5делители числа 15.
Число 1 является делителем любого натурального числа, поскольку любое натуральное число делится на 1 (а:1=а).
Число, делящееся на 2, называют четным; число, не делящееся на 2, называют нечетным.
Кратным числа b называют число а, которое нацело делится на b. Множество чисел, кратных данному числу b, бесконечно.
В программировании для определения того, является ли число b делителем числа а, пользуются следующим свойством:
если число а делится на число b, то остаток от деления равен 0.
если mod (a, b)=0
то р:=«Делится» (1-1)
иначе Р:==«Не делится»
все
Задача. Написать программу нахождения всех делителей заданного натурального числа.
Натуральное число а, не равное 1, называется простым, если оно делится только на себя и на 1, т. е. имеет только два натуральных делителя. Натуральное число, отличное от 1 и не являющееся простым, называется составным. Другими словами, натуральное число называется составным, если оно имеет более двух делителей. Число 1 не относится ни к простым, ни к составным числам, поскольку имеет лишь один делитель. Наименьшим простым числом является число 2. Это единственное четное простое число. Остальные простые числа являются нечетными.
Для того чтобы найти делители числа а, мы должны попытаться делить данное число на все отличные от 1 числа, меньшие а. Если а не разделилось ни на одно из них, то оно является простым.
Массив В будем использовать для хранения делителей числа а, переменную Р для определения того, простое число или составное, переменную К для обозначения первого свободного места в массиве В.
Р: =«простое»
В[1]:=1
В[2]:=а
К:=3 (1.2)
нц для i от 2 до а1
если mod (a, i)=0
то B[K]:=i
К:=К+1
Р:= «составное»
все
кц
После выполнения алгоритма первые К-1 элементов массива В будут содержать все делители числа а.
В приведённом алгоритме мы делили число а на все отличные от 1 числа, меньшие а. На самом деле делитель не может превышать а/2 (почему?). Учет этого очевидного факта приводит к увеличению скорости работы программы в два раза.
Алгоритм (1.2), кроме нахождения делителей числа а, определяет, является ли число а простым или составным. Если требуется только определить, простое число или составное, то данный алгоритм можно улучшить. В самом деле, цикл для i от 2 до а-1 выполняется а-2 раза. Однако для проверки простоты числа а достаточно выполнить данный цикл 13 EMBED Equation.DSMT4 1415 раз (13 EMBED Equation.DSMT4 1415целая часть от корня квадратного из а). Это вытекает из следующих соображений: если а число составное, его можно представить в виде а=bc, где b<=13 EMBED Equation.DSMT4 1415, с>=13 EMBED Equation.DSMT4 1415; если а делится на b, то оно будет делиться и на с; если а не делится ни на одно число, меньшее или равное 13 EMBED Equation.DSMT4 1415, то оно не будет делиться ни на какое другое число.
Р: = «простое»
нц для i от 2 до int(sqrt(а))+1
если mod (a, i)=0
то Р:=«составное» (1.3)
все
кц
Идеей уменьшения количества выполнении цикла можно воспользоваться и для нахождения делителей числа a. Попытайтесь сделать это самостоятельно, а также объясните, зачем к величине int (sqrt (а)) добавляется 1.
Алгоритм определения простого числа можно еще улучшить, если остановиться сразу после того, как установили, что число не является простым (т. е. если a разделилось на какое-либо число).
Р: = «простое»
i:=2
нц пока (i0)
i:=i+l (1.4)
кц
если mod (a, i)=0
то
P:=«составное»
все
Множество простых чисел является бесконечным. Очевидно, что множество простых чисел, не превосходящих некоторого числа N, будет конечным. Возникает вопрос: как же найти эти простые числа?
Можно, конечно же, просмотреть первые N натуральных чисел и для каждого проверить, является ли оно простым. Однако данный метод, хоть и кажется простым с первого взгляда, не является эффективным, так как программа будет работать очень медленно даже для небольших N. (Проверьте самостоятельно.)
Лучше всего делать это методом, который предложил Эратосфен Киренский (ок. 276194 гг. до н. э.). Называется метод решето Эратосфена.
Суть метода следующая. Выпишем подряд все числа от 1 до N. Первым стоит число 1, оно не является простым. Вычеркнем это число. Следующее число 2, это простое число. Оставляем его и вычеркиваем все числа, кратные 2. Для этого достаточно вычеркнуть каждое второе число, начиная счет с 3. Первым не вычеркнутым числом будет 3. Это простое число. Оставляем его и вычеркиваем все числа, кратные 3. т. е. каждое третье число, начиная счет с 4. (При счете необходимо учитывать и ранее вычеркнутые числа, поэтому некоторые числа вычеркиваются второй раз: это 6, 12, 18 ...). После этой операции первым не вычеркнутым, а значит простым, будет число 5. Оставляем это число и вычеркиваем все числа, кратные 5, т. е. каждое пятое число, начиная счет с 6. Затем переходим к следующему не вычеркнутому числу 7 и т. д. Таким способом мы вычеркиваем все составные числа, остаются лишь простые.
Метод Эратосфена получил название решета по следующим причинам. Древние греки писали заостренной палочкой на восковых дощечках. Такой палочкой Эратосфен прокалывал те места, где были написаны составные числа. После этого дощечка становилась похожей на решето. Применяя метод Эратосфена, как бы отсеивают, пропускают через решето все составные числа и оставляют только простые.
Для хранения чисел создадим массив В[1..n]. Вначале занесем в него число 2 и все нечетные числа, так как все четные, кроме числа 2, являются составными. Затем будем заменять нулями все числа, кратные 3. После этого найдем первое ненулевое число после числа 3 и будем заменять нулями все числа, кратные ему. Так продолжаем до тех пор, пока не просмотрим весь массив.
N:=div((N+1), 2)
В[1]:=2
нц для i от 2 до N
B[i]:=2*i-1 : первоначальное заполнение
: массива
кц
j:=2
нц пока j < = N
i:=J+B[j] индекс первого обнуляемого
нц пока i <=N . (1.5)
B[i]:=0 обнуление чисел,
i:=i+B[j] кратных текущему
кц
j:=j+1
нц пока (J<=N) и (B[j]=0) поиск очередного
j:=j+1 ненулевого числа
кц
кц
Этот алгоритм работает достаточно быстро, однако у него есть один недостаток: для хранения всех чисел требуется массив слишком большой размерности (5000 элементов для N= 10 000). Поэтому можно воспользоваться другим алгоритмом, который работает медленнее, однако не требует сохранения в массиве всех нечетных чисел.
В массиве будем хранить только простые числа. Вначале в массив поместим число 2. Рассматривая очередное нечетное число X, будем делить его на
· предшествующие ему простые числа. И если ни на одно из предшествующих простых чисел текущее число не делится, то оно само является простым. Проверку на делимость числа нужно заканчивать после того, как проверена делимость на простое число, не превосходящее [sqrt(X)].
В[1]:=2
j:=2
i:=3
нц пока i <=N
k:=1
d:=int(sqrt(i))+1
нц пока (B[k]0)
k:=k+l
КЦ (1.6)
если B[k]>=d
то B[j]:=i
J:=J+1
все
i:=i+2
кц
Следует обратить внимание и на необходимость введения переменной d. Выражение, значение которого присваивается переменной d, можно вычислять непосредственно в условии цикла, однако это удлинит работу программы. (Проверьте и подумайте, почему так происходит.)
3. Поиск НОД
Если a и b два натуральных числа, и если число c таково, что a делится на с и b делится на c, то число c называют общим делителем чисел а и b. Произвольные два числа всегда обладают общим делителем. Таким делителем является число 1. Если других общих делителей нет, то числа а и b называют взаимно простыми.
Число d называют наибольшим общим делителем (НОД) чисел а и b, если 1) d является общим делителем чисел а и b; 2) d делится на любой другой общий делитель. Другими словами, d наибольший из всех общих делителей чисел а и b.
В курсе математики приводился следующий алгоритм нахождения НОД. Необходимо разложить числа а и b на простые множители и затем выбрать те из них, которые входят и в одно, и в другое разложение. Рассмотрим пример: найти НОД (2520, 2475).
2520 2
1260 2
630 2
315 3
105 3
35 5
7 7
1

2475 3
825 3
275 5
55 5
11 11
1
Общие множители подчеркнуты. НОД(2520, 2475)= 3*3*5=45.
Данный алгоритм на практике обычно не применяется, так как разложение числа на простые множители уже является достаточно трудоемкой задачей, а ведь еще потребуется найти среди них одинаковые. Поэтому очень часто для нахождения НОД применяют метод, который называется алгоритмом Евклида.
Это один из самых древних алгоритмов, он описан еще в «Началах» Евклида.
Прежде чем описать сам алгоритм, укажем несколько свойств НОД, на которые опирается алгоритм Евклида.
Пусть а и b отличные от нуля натуральные числа, причем a>b, тогда
1) НОД(а, b)=НОД(а-b, b)
2) НОД(а, а)=а
3) НОД(а, 0)=а
Равенства 2) и 3) являются очевидными.
Равенство 1) будет доказано, если мы установим, что множество общих делителей чисел a и b совпадает со множеством общих делителей чисел a-b и b, т. е всякий общий делитель X чисел а и b является делителем чисел a-b и b, и наоборот. Если Xделитель а и b, то a=kX и b=lХ для некоторых k и l. Тогда а-b=(k-l)Х, т. е. X является общим делителем чисел a-b и b. Наоборот, пусть a-b=mХ и b=nХ для некоторых m и n. Складывая эти равенства получаем а=(n+m)X. Таким образом, Х является общим делителем а и b.
Перечисленные равенства подсказывают идею алгоритма нахождения НОД: нужно от большего числа отнимать меньшее до тех пор, пока они не станут равными, после чего НОД найдется по свойству 2).
Пример: НОД(530, 155), а=530, b=155.
а b
530 155
375 155
220 155
65 155
65 90
65 25
40 25
15 25
15 10
5 10
5 5
Алгоритм будет следующим:
нц пока а<>b
если а>b то а:=a-b
иначе b:=ba
все
кц
NOD:=a
Если проанализировать работу данного алгоритма, то можно заметить, что одно и то же число нужно отнимать несколько раз. Этого можно избежать, если вместо нескольких вычитаний находить остаток от деления большего числа на меньшее (подумайте, почему). В этом случае свойство 1) можно записать в виде НОД(а, b)=НОД(а mod b, b). Для окончания работы алгоритма нужно воспользоваться свойством 3).
Пример: НОД(530, 155), а=530, b=155.
а b
530 155
65 155
65 25
15 25
15 10
5 10
5 0
Алгоритм будет выглядеть следующим образом:
нц пока (а<>0) и (b<>0)
если а>b то a:=mod(a, b) иначе b:=mod(b, a) все
кц
если а=0 то NOD:=b иначе NOD:=a все
4. Поиск НОК
Если а и b - два натуральных числа, и если число с таково, что с делится на а и c делится на b, то число с называют общим кратным чисел а и b. Произвольные два числа всегда обладают общим кратным. Таким кратным является число, равное произведению аb.
Число d называют наименьшим общим кратным (НОК) чисел а и b, если 1) d является общим кратным чисел а и b; 2) на d делится любое другое общее кратное. Другими словами, dнаименьшее из всех общих кратных чисел а и b.
Для нахождения НОК можно воспользоваться алгоритмом, известным из курса математики. Нужно разложить числа а и b на простые множители, а затем из двух разложений выбрать те сомножители, которые входят хотя бы в одно разложение.
Пример: НОК(52, 65)
52 2 65 5
26 2 13 13
13 13 1
1
52=2*2*13; 65=5*13; НОК(52, 65)=2*2*13*5=260. Однако применять такой алгоритм на практике не стоит по описанным выше причинам. Для нахождения НОК можно воспользоваться следующим свойством:
НОК(а, b)=а*b/НОД(а, b) (докажите самостоятельно). Для нахождения НОД следует применять алгоритм Евклида.
Задачи.
1. Сократить дробь а/b (а, b натуральные числа).
Решение:
var a,b,d:word;
function nod(x,y:word):word;
var r:word;
begin
r:=x mod y;
while r<>0 do
begin
x:=y;
y:=r;
r:=x mod y;
end;
nod:=y;
end;

begin
readln(a,b);
d:=nod(a,b);
writeln(a div d,'/',b div d);
end.
2. Даны 4 целых числа а, b, с, d. Написать программу, вычисляющую сумму обыкновенных дробен a/b+c/d в виде х/у.
var a,b,c,d,nd,p,q:integer;
function nod(x,y:word):word;
var r:word;
begin
r:=x mod y;
while r<>0 do
begin
x:=y;
y:=r;
r:=x mod y;
end;
nod:=y;
end;
begin
readln(a,b,c,d);
p:=a*d+b*c;
q:=b*d;
nd:=nod(abs(p),abs(q));
writeln(p div nd,'/',q div nd);
end.
Задачи для самостоятельного выполнения
Найти сумму делителей каждого из целых чисел от 50 до 70.
Найти натуральное число из интервала от a до b с максимальной суммой делителей.
Дано натуральное число n. Напечатать разложение этого числа на простые множители. Реализовать два варианта: а)каждый простой множитель должен быть напечатан один раз; б) каждый простой множитель должен быть напечатан столько раз, сколько раз он входит в разложение.
Дано натуральное число n. Получить все делители этого числа.
Дано натуральное число n. Получить все натуральные числа, меньшие n и взаимно простые с ним (два натуральных числа называются взаимно простыми, если их наибольший делитель равен 1).
Даны натуральные числа m и n. Получить все натуральные числа, меньшие n и взаимно простые с m.
Найти все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не превышают 7 (дробь задается двумя натуральными числами – числителем и знаменателем).













Каникулярное домашнее задание (олимпиадные задания)

13 PAGE \* MERGEFORMAT 14715




Заголовок 215

Приложенные файлы

  • doc 6627568
    Размер файла: 66 kB Загрузок: 0

Добавить комментарий