LINEBURG


<< Пред. стр.

страница 2
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

3.1 ЦИФРЫ ЧИСЛА
Ранее упоминалось об алгоритме определения каждой цифры числа,
который можно использовать при решении следующих задач:
- найти сумму цифр числа.
- составить программу, проверяющую, является ли заданное
натуральное число палиндромом, т.е. числом, десятичная запись
которого читается одинаково слева направо и справа налево.

Программная реализация:
uses crt;
type TArr=array[1..10]of byte; {Тип для хранения цифр числа}
var m:TArr; {Цифры}
c:byte; {Их количество}
x,sum:longint;

procedure make_digits(x:longint);{Записывает в m цифры X,в sum-
сумму}
begin
c:=0;
sum:=0;
while x>0 do
begin
inc(c);
m[c]:=x mod 10; {Очередная цифра числа}
x:=x div 10;
sum:=sum+m[c]; {Сумма цифр числа}
12
end;
end;

function is_polin(const a:TArr;c:byte):boolean; {проверка числа на
“палиндром”}
var i:byte;
begin
is_polin:=false;
for i:=1 to (c div 2) do
if a[i]<>a[c+1-i] then exit;
is_polin:=true;
end;

begin
clrscr;
writeln('Введите число:');
readln(x);
make_digits(x);
writeln('Количество цифр ',c);
writeln('Сумма цифр ',sum);
if is_polin(m,c) then
writeln('Число - палиндром')
else
writeln('Число - не палиндром');
readkey;
end.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
УЧАЩИМИСЯ
1. Дано натуральное N. подсчитать количество цифр данного числа.
2. Найти количество четных цифр числа.
3. Найти самую большую цифру числа.


3.2 ПРОСТЫЕ ЧИСЛА
Определение: натуральное число N (N>1) называется простым, если его
делителями являются только оно само и единица.
Для определения «простоты» числа (N в пределах типов BYTE и
WORD) можно воспользоваться следующими достаточно простыми и
эффективными алгоритмами:

Алгоритм 1
Если N- четное, то оно не простое (составное). Следует проверить,
cуществует ли хотя бы один делитель числа N (числа 3,5,7,........SQRT(N)-
13
проверять до N-1 и даже до N/2 нет необходимости). Если хотя бы для
одного числа ответ будет положительным, то число N- составное. Заметим
при этом, что число 2 - простое.

Программная реализация:

Procedure PROST (N: WORD);
var I: word;
SIMP: boolean;
begin
if N mod 2=0
then SIMP:=false {число составное}
else SIMP:=true;
I:=3;
while I<=Int(Sqrt(N)) and SIMP do
if N mod I=0 {I- делитель N}
then SIMP:=False {число составное}
else I:=I+2;
PROST:=SIMP;
end.

Алгоритм 3. "Решето Эратосфена"
Из множества чисел от 2 до N отбросим все числа, кратные первому
простому, то есть двойке. Наименьшее оставшееся число является вторым
простым числом. Отбросим все числа кратные этому простому числу.
Наименьшее оставшееся число является третьим простым числом и т.д.
Описание алгоритма:
1) Подготовим к работе необходимые массивы:
A - будем содержать:
0- если число не простое.
1- если число простое.
K- будем содержать:
очередные числа, которые нужно
вычеркнуть для каждого i ого простого числа.
Если I- ое число в массиве равно 0
значит число I не простое
2) Найдем все простые числа из интервала от 1 до корня из N, где N-
число до которого нужно найти простые числа.
3) Пусть M+1 – число, с которого начинается очередной массив A.
вычеркнем из этого массива все числа кратные простым числам, эти
числа мы будем брать из массива K (в ячейках этого массива для
каждого простого числа хранятся числа, которые надо вычеркнуть
(кратные простому числу)).
4) Распечатаем простые числа.
5) Увеличим переменную M на корень из N.
14
6) Перейдем на пункт 3.

Программная реализация:
uses crt;
const max=32767;
var is:array[1..max]of boolean;
m,x,i,k,n:longint;
begin
clrscr;
writeln('Введите M и N');
readln(m,n);
if (m>n)or(n>=max) then
begin
writeln('Неправильные числа!');
halt;
end;
writeln('Простые числа от ',m,' до ',n,':');
while keypressed do readkey;
readkey;
fillchar(is,sizeof(is),true);
is[1]:=false;
i:=2;
while (i<=n) do
if is[i] then
begin
if wherex>=75 then writeln;
if (i>=m) then
write(i,',');
x:=(n div i)-1;
for k:=1 to x do
is[i+k*i]:=false;
inc(i);
end
else inc(i);
gotoxy(wherex-1,wherey);
write(' ');
while keypressed do readkey;
readkey;
end.

Для чисел типа Longint приведенные выше алгоритмы являются не
достаточно эффективными, т.к. требуют выполнения слишком большого
количества операций.

Алгоритм 4.
15
{Для каждого нечётного кандидата “на простоту” достаточно
проверить делимость на предыдущие простые числа}
uses crt;
{$M 65520,0,0}
var n,i,j,pc:longint;
p:array[1..10000]of longint;
is:boolean;
begin
clrscr;
writeln('Введите N');
readln(n);
writeln('Простые числа до ',n,':');
readkey;
pc:=1;
p[1]:=2;
i:=3;
write('2,');
while (i<=n)do
begin
is:=true;
for j:=1 to pc do
if (i mod p[j])=0 then begin is:=false; break; end;
if is then
begin
inc(pc);
p[pc]:=i;
write(i,',');
end;
inc(i,2);
end;
gotoxy(wherex-1,wherey);
write(' ');
readkey;
end.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ
Задача 1.
Реализовать алгоритм определения «простоты» числа N: число
является простым, если у него всего два делителя: 1 и N.
Задача 2.
Вывести все простые числа P в указанном интервале (A;B).
Задача 3.
Дано натуральное число N. Выяснить, имеются ли среди N, N+1,....,2N
близнецы, т.е. простые числа, разность между которыми равна 2.
16
3.2.1 ПРОСТЫЕ ДЕЛИТЕЛИ
Рассмотрим две задачи:
• Задано натуральное число N. Найти и напечатать все его простые
делители.
• Дано натуральное число n. Получить все натуральные числа,
меньшие n, и взаимно простые с ним.
Алгоритм:
Взаимно простыми называются числа, наибольший общий делитель
которых равен единицы. Поэтому для решения задачи необходимо
рассмотреть все числа m=1, 2, ..., n-1 и определить НОД чисел n и m. Если его
величина 1, то число m - взаимно простое с числом n.

Программная реализация:
var
N, M, A, B, R, NOD: word;
begin
Write(' Введите число N ');
Readln(n);
Write(' Числа, взаимно простые с числом N: ');
for M:=1 to N-1 do
begin
{ Определяем НОД M и N по алгоритму Евклида:}
A:=M;
B:=N; {используем "аналоги" чисел M и N}
while B>0 do
begin
R:=A mod B;
A:=B;
B:=R;
end;
NOD:=A;
if NOD=1 {число m - взаимно простое с n}
then write(m,' ')
end;
end.


3. 3 ЧИСЛА ФИБОНАЧЧИ
Числа Фибоначчи определяются следующей рекурентной формулой:
F(0)=1, F(1)=1, F(n, n>1)=F(n-1)+F(n-2);
В задачах работа с числами Фибоначчи ограничена типом Longint, т.к.
последующие числа требуют использования т.н. «длинной арифметики».
Номер последнего числа Фибоначчи в типе Longint равен 45.
Задача1.
Вычислить число Фибоначчи по его номеру.
17
Программная реализация:
uses crt; var i,n:integer; f:array[0..45]of longint;
begin
clrscr;
writeln('Введите N');
readln(n);
f[0]:=1;
f[1]:=1;
for i:=2 to n do
f[i]:=f[i-1]+f[i-2];
writeln('F(',n,')=',f[n]);
readln;
end.

Задача 2.
Вычислить номер заданного числа Фибоначчи.

Программная реализация:
uses crt; var i,n:integer;
f:array[0..45]of longint;
begin
clrscr;
writeln('Введите F(n)');
readln(n);
f[0]:=1;
f[1]:=1;
if n=1 then i:=1 else
for i:=2 to 45 do
begin
f[i]:=f[i-1]+f[i-2];
if f[i]=n then break;
end;
if (i=45)and(n<>f[45]) then writeln('Это не число Фибоначчи!') else
writeln('n=',i);
readln;
end.
Задача 3.*
Разложить произвольное число N в виде суммы чисел Фибоначчи:
N=F(i1) +F(i2)+F(i3)+…+F(iK); iM>i(M-1)+1 для любого М.
(Доказано, что Fm =Fm-2+Fm-1)

Программная реализация:
uses crt;
var f:array[0..45]of longint;
18
i,n:longint;
begin
clrscr;
f[0]:=1;
f[1]:=1;
for i:=2 to 45 do
f[i]:=f[i-1]+f[i-2];
i:=45;
writeln('Введите n');
readln(n);
writeln('Его разложение в числа Фибоначчи:');
write(n,'=');
while n<>0 do
begin
while f[i]>n do
dec(i);
n:=n-f[i];
if n<>0 then
write(f[i],'+') else
write(f[i]);
end;
readln;
end.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ

1. «Фибина заначка»
Жил да был бухгалтер Фиба со стажем работы N лет. Честный был да
грамотный. Грамотный – потому что знал, что если не воровать, то
заподозрят, что скрывается от честного народа, а сам загребает несчитано-
немерено. А честный – потому что воровал немного, каждый год по К
условных единиц.
А в той стране, где он жил, была инфляция. Поэтому деньги и измеряли
в условных единицах. Ну и Фиба, стало быть, доход свой нелегальный с
точки зрения никому не нужного закона так же измерял.
А как пришла к Фибе старость, решил он свою заначку потратить на
шестисотый мерс, который продавала фирма за б.е. – осталось только
пересчитать в безусловные единицы. Попросил он у парней в фирме
разрешения посидеть за плохоньким ПК, да и написал нехилую программку
на Паскале, которая и перевела его заначку в б.е. – Фиба–то давно подметил,
что инфляция у него на родине растет по тому же закону, что и числа
Фибоначчи у математиков: 1,1,2,3,5,8,13,21…..
Переведите-ка и вы Фибину заначку в б.е.
Input.txt: содержит два целых числа K и N . K<2000, N<400.
19
Output.txt: Целое число – результат программы Фибы.
2. Числа вида 2P-1, где Р - простое число, называются числами Мерсенна.
Являются ли числа Мерсенна при значениях Р 2,3,5,7,11,13,17,19,23,29,31
простыми?
Программа состоит из двух частей: в первой вычисляется число
Мерсенна для значения Р (вводится с клавиатуры), во второй проверяется,
является ли оно простым.
3. Совершенным называется число, равное сумме всех своих делителей,
меньших, чем оно само. Например, 6=1+2+3, 28=1+2+4+7+14.
Составить программу проверки заданного натурального числа на
совершенство.
4. Автоаморфным называется число, равное последним цифрам своего
квадрата. Например, 5*5=25, 25*25=625. Очевидно, что автоаморфные числа
должны оканчиваться либо на 1, либо на 5, либо на 6. Составить программу
нахождения аморфных чисел, не превышающих значения 999.
5. Кубические автоаморфные числа равны последним цифрам своих кубов.
Например: 6*6*6=216. Составить программу нахождения двузначных и
трехзначных кубических автоаморфных чисел.
6. Натуральное число из N цифр является числом Армстронга, если сумма
его цифр, возведенных в N-степень, равна самому числу. Например:
153=1*1*1+5*5*5+3*3*3. Получить все числа Армстронга, состоящие из трех
и четырех цифр.
7. Найти все тройки пифагоровых чисел, т.е. целых k,l,m таких, что
k*k+l*l=m*m, при условии, что все три числа не превышают 32767.

§4 СОРТИРОВКА И ПОИСК

Алгоритмов сортировки настолько много, что им можно посвятить
целиком все методическое пособие; при этом следует учитывать, что разные
по тематике используемых алгоритмов задачи требуют использования
разных алгоритмов сортировки.
В данном разделе рассматриваются некоторые алгоритмы сортировки и
поиска с точки зрения их оптимальности и применения. Сравнительный
анализ алгоритмов – неотъемлемая часть при обучении программированию.


4.1 ПОНЯТИЕ СОРТИРОВКИ
Сортировка - это упорядочение данных по определенному признаку.
Рассмотрим одномерный массив целых чисел:
Const N=... ;
Type MyArray=Array[l..N] Of Integer;
Var A:MyArray;
20
Алгоритмы сортировки отличаются друг от друга степенью
эффективности, под которой понимается количество сравнений и количество
обменов, произведенных в процессе сортировки. Эффективность оценивается
количеством операций сравнения (порядком этого значения).
Элементы массива можно сортировать:
• по неубыванию — каждый следующий элемент не меньше
предыдущего, в случае равенства элементов они перечисляются
подряд
А[1] <= А [2] <= ... <= A[N];
• по невозрастанию — каждый следующий элемент не больше

<< Пред. стр.

страница 2
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign