12. Выяснить образуют ли цифры натурального числа возрастающую последовательность

Для сигнала о том, что цифры числа образуют нужную последовательность, будем использовать логическую переменную log.

program vozrcifri;

Var n,a,b:longint;

log:boolean;

Begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

log:=true; с самого начала считаем, что последовательность

возрастающая

a:=n mod 10; берем последнюю цифру числа

n:=n div 10; отрезаем ее

while n>0 do бежим по цифрам числа

begin

b:=n mod 10; берем вторую цифру с конца

if a<b then

begin log:=false;break end; если последовательность не возрастающая, то

выходим из цикла

n:=n div 10; иначе отрезаем цифру

a:=b; копируем цифру

end;

if log then write('YES') выводим результат

else write('NO');

close(output);

End.

При работе с целыми числами в Паскале необходимо всегда помнить о диапазонах изменения целочисленных типов перемееных и занимаемой памяти .

Вот они:

тип	диапазон значений	требуемая память
Shortint	-128 .. 127	1 байта
Integer	32768 .. 32767	2 байта
Longint	-2147483648 ... 2147483647	4 байта
Byte	0 .. 255	1 байт
Word	0 .. 65535	2 байта

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

+ - * div mod

Операции отношения равенство =,неравенство <>, больше или равно >=, меньше или равно <=, больше >,меньше < ., примененные к целым операндам, дают результат логического типа TRUE или FALSE ( истина или ложь ).

Например: 2<3 TRUE

2>3 FALSE

К аргументам целого типа применимы следующие стандартные (встроенные) функции, результат выполнения которых имеет целый тип:

Abs(X), Sqr(X), Succ(X), Pred(X),

и которые определяют соответственно абсолютное значение числа Х, Х в квадрате, следующее значение Х+1, предыдущее значение Х-1.

Результат выполнения функции Odd(X) - проверки целого числа на нечетность

имеет значение TRUE, если аргумент нечетный, и значение FALSE, если аргумент четный:

X=5 Odd(X)=TRUE

X=4 Odd(X)=FALSE.

Для быстрой работы с целыми числами определены процедуры:

Inc(X) равносильно X:=X+1

Inc(X,N) равносильно X:=X+N

Dec(X) равносильно X:=X-1

Dec(X,N) равносильно X:=X-N

Где X и N- целые числа.

Самое интересное из целочисленных делений, это деление на 10. Оно обладает замечательными свойствами, которые оказываются незаменимыми при решении задач.

235 mod 10=5, т.е. деление на 10 позволяет находить последнюю цифру числа.

235 div 10=23, отрезает последнюю цифру числа.

Соответственно 235 mod 100=35, позволяет находить две последние цифры числа, 235 div 100=2, отрезает две последние цифры числа.

Для того, чтобы поменять значения двух переменных местами мы будем использовать процедуру swap.

Procedure swap(var a ,b : integer); тип a и b может быть изменен

Var k : integer;

Begin

k:=a; a:=b; b:=k; обмен идет через третью ячейку по схеме треугольник

End;

Можно обойтись и двумя переменными.

Procedure swap(a, b :integer);

Begin

A := A xor B;

B := A xor B;

A := A xor B;

End;

Где операция xor это операция исключающего «или».

В теме «Целочисленная арифметика» рассматриваются следующие олимпиадные задачи:

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

2. Корни многочлена

3. Отгадай возраст

4. Квадраты

5. Основная теорема арифметики

6. Определение простоты числа

7. Найти все простые числа из отрезка [a,b]. Где a и b натуральные числа

8. Найти все простые числа, не превышающие данного натурального N и поместить их в массив констант

9. Зачеркнутая цифра

10. Наибольшее число

11. Простая задача

12. Сверхпростые числа

13. Разложить данное натуральное число N на простые множители

14. Дано натуральное число N (1<=N<=10⁶). Найти последнюю цифру количества всех делителей числа N

15. Количество делителей

16. Нахождение наибольшего общего делителя двух натуральных чисел

17. Нахождение наименьшего общего кратного натуральных чисел

18. Сложение дробей

19. Нахождение частного решения диафантова уравнения ax+by=с

20. Нахождение общего решения диафантова уравнения ax+by=с

21. Индийский алгоритм вычисления степени xⁿ

22. Сложение двух длинных чисел

23. Умножение длинного числа на короткое

24. Умножение длинного числа на длинное

25 Деление двух длинных чисел

26. Равны ли два длинных числа

27. Больше ли первое длинное число второго

28. Вычисление 2ⁿ

29. N- е число Фибоначчи

30. Вычисление N факториала

31. К-я цифра

32. Кузнечик

33. Наибольшее число

34. Найти последнюю ненулевую цифру n! (1<=n<=1000000)

35. Найти все совершенные числа, меньшие, чем заданное М

36. Сломанный калькулятор

37. Счастливый билет (Вариант с использованием массива)

38. Счастливый билет (Вариант без использования массива)

39. Таинственный предмет

40. Период дроби

41. Нахождение цифры

42. Сумма

43. Роботландия

44. Простые гири

45. Xитрое жюри

46. Число в последовательности

47. Зачеркнутая цифра

48. Постройка пирамиды

49. Три автомата

50. Гадкие парни

51. Банкноты

52. Иностранные земли

53. Коэффициенты многочлена

54 Шутка

55. Еще одна странная функция

56. Уравнение

57. Последовательность Фибоначчи

58. Теорема Цеккендорфа

59.Номерастраниц

60 Припростые числа

61. Марсианские факториалы

Задача 1 Дано натуральное число. Найти все делители данного числа и вывести их в порядке возрастания

Если найденные делители сразу записывать в массив, то перед выводом придется массив отсортировать по возрастанию. Тогда программа будет следующая.

program delitel1;

const nmax=100;

var n,i,j,t,p:longint;

a:array[1..nmax] of longint;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

i:=1;t:=0;

while i<=sqrt(n) do проверяем делимость числа N на все натуральные

begin числа меньшие квадратного корня из N

if n mod i=0

then

begin

inc(t);

a[t]:=i; помещаем первый делитель в массив

if i<>n div I если делители не равны

then

begin

inc(t);

a[t]:=n div i; помещаем второй делитель в массив

end;

end;

inc(i);

end;

for i:=1 to t-1 do сортируем массив

for j:=i+1 to t do

if a[i]>a[j]

then

begin

p:=a[i];

a[i]:=a[j];

a[j]:=p;

end;

for i:=1 to t do выводим массив делителей

write(a[i],' ');

end.

Первый вариант нахождения всех делителей не оптимальный по времени из-за сортировки.

Вот второй вариант без сортировки. М сначала добежим до квадратного корня из числа, а потом побежим обратно до 1.

Program deliteli2;

const nmax=10000;

var d:array[1..nmax] of longint;

n,i,kol:longint;

procedure delit(x:longint);

var i,j:longint;

begin

i:=1;kol:=0;

while i<=sqrt(x) do проверяем делимость числа N на все натуральные

begin числа меньшие или равные квадратного корня из N

if x mod i=0 если нашли делитель, то записываем его

then в массив

begin

inc(kol);

d[kol]:=i;

end;

inc(i); берем следующее натуральное число

end;

i:=kol;

if frac(sqrt(n))=0 then dec(i); если n- полный квадрат

for j:=i downto 1 do

begin

inc(kol);

d[kol]:=n div d[j];

end;

end;

begin

assign(input,’input.txt’); reset(input);

assign(output,’output.txt’); rewrite(output);

read(n);

delit(n); вызываем процедуру delit с параметром n

for i:=1 to kol do выводим все делители

write(d[i],' ');

close(input);

close(output);

end.

задачи

Задача 2 Корни многочлена

Даны целые числа a₀,a₁,...,a₅. Найти множество корней уравнения

a₅*x⁵ + a₄*x⁴ + ... + a₁*x+a₀ = 0, если известно, что все корни - целые числа, a₀<>0.

Входные данные:

В первой строке входного файла Input.txt записано пять целых чисел – коэффициенты многочлена.

Выходные данные:

В выходном файле Output.txt перечислены все целые корни данного многочлена в порядке возрастания.

Пример

Input.txt	Output.txt
2 3 -5 -5 3 2	-2 -1 1

Опр. Многочленом n-ой степени называется выражение вида

a_nxⁿ+a^n-1x^n-1+.a₁*x+a₀ , где aⁿ_,a^n-1,....a_1,a₀ – коэффициенты многочлена.

Опр. Корнем многочлена называется значение переменной x, при котором значение многочлена равно нулю.

Из курcа математики известно, что целыми корнями многочлена могут быть только делители свободного члена. Например, для многочлена 3x+7x⁴-2x³-8x²+x+24 целыми корнями могут быть -24,-12,-8,-6,-4,-3,-2,-1,1,2,3,4,6,8,12,24.

Среди них и надо искать корни. Перебираем их по очереди и подставляем вместо x в многочлен, вычисляя значение многочлена по схеме Горнера.

задачи

Задача 3. Отгадай возраст

Фокусник просит вас загадать любое натуральное число, умножить его на девять и прибавить свой возраст. Вы сообщаете ему свой результат, и он говорит, сколько вам лет.

Введем обозначения.

х- задуманное число

у -число ваших лет

a – результат

. Тогда 9х+у=a . В этом уравнении два неизвестных - х и у . Кажется, что узнать число лет нельзя, но оказывается можно .Немного теории

В ведем понятие цифрового корня. Возьмем натуральное число 257, найдем его сумму цифр - 14, еще раз сумму цифр - 5.Это и есть цифровой корень числа 257. То есть, чтобы найти цифровой корень натурального числа, надо складывать его цифры до тех пор, пока не получится одна цифра. Она и будет цифровым корнем числа. Обозначим цифровой корень 257=5.

Цифровые корни цифр.

Цифра	0	1	2	3	4	5	6	7	8	9
Цифровой корень	0	1	2	3	4	5	6	7	8	0

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

a+b=a+b

a*b=a*b

Например: 25+37=62

7+1=8

12 * 8=96

3 * 8=6

24=6

Почему у 9 цифровой корень 0? Так как 9*7=63 , 9*7=63=9 то 9*7=9

Это равенство может выполняться только в том случае, если цифровой корень 9 равен 0. Тогда числа, отличающиеся на число кратное 9, имеют один и тот же цифровой корень.

3=12=21=30=39 ...

Значит 9х+y имеет тот же цифровой корень что и у , то есть у=а. Цифровой корень вашего возраста совпадает с цифровым корнем результата и отличаются они на число кратное 9. Дальнейшее понятно.

Искомый алгоритм:

1. Найти цифровой корень результата

2. Прибавить к нему 9 столько раз, чтобы получить число лет из нужного десятка.

Если бы вам было от 20 до 30 лет то надо прибавлять две 9 или три и так далее.

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

Нахождение цифрового корня натурального числа

function cifrkor(x:longint):longint;

var s:longint;

begin

repeat повторять до тех пор пока не получим

цифровой корень

s:=0;

while x>0 do пока в числе есть цифры

begin s:=s+x mod 10; x:=x div 10 end; прибавляем и отрезаем последнюю цифру

x:=s; промежуточную сумму делаем

исходным числом

until x<10;

if x=9 then cifrkor:=0

else cifrkor:=s;

end;

задачи

Задача 4 Квадраты

На уроке труда всем раздали по прямоугольнику со сторонами размером A и B (целые, 1≤A, B≤2³¹-1). Мальчик Сеня очень любит резать прямоугольники , и когда учитель предлагает всем вырезать из прямоугольника квадраты, то Сеня поступает весьма хитроумно. Он одним разрезом, параллельным стороне прямоугольника, отсекает от прямоугольника квадрат со стороной, равной наименьшей стороне прямоугольника и продолжает проделывать эту же процедуру с оставшейся после разреза частью. Если часть оказывается квадратом, то Сеня успокаивается и принимается считать получившиеся квадраты. Сколько же он нарежет квадратов?

Входные данные:

Натуральные числа A и B

Выходные данные:

Количество получившихся квадратов.

Input.txt	Output.txt
1 2	2

Если представить прямоугольник шириной 1 и длиной 2³¹ – 1, то отрезая по одному квадратику 1х1 мы не успеем по времени, если на один тест дается одна секунда. Вспоминаем, что деление это многократное вычитание и тогда вместо того, чтобы много раз отнимать одно и тоже лучше один раз разделить. Тогда решение будет такое.

Program kvadrati;

Var a,b,kol:longint;

begin

assign(input,’input.txt’);

reset(input);

assign(output,’output.txt’);

rewrite(output);

read(a,b);

kol:=0;

if a=b then begin write(1); close(output);halt(0) end; частный случай

while (a<>0)and(b<>0) do

begin

if a>b

then

begin

inc(kol,a div b);

a:=a mod b;

end;

if a<b

then

begin

inc(kol,b div a);

b:= b mod a;

end;

end;

write(kol);

close(output);

end.

задачи

Нахождение делителей натурального числа.

Опр. Натуральное число b называется делителем натурального числа a, если существует натуральное число c, такое что a = b*c . Если b – делитель a, то, очевидно, a mod b = 0 и наоборот, если . a mod b = 0, то b – делитель a.

Найдем делители числа а. Для этого будем перебирать все числа i, подходящие на роль делителя. Очевидно, что 1 <= i <= a. Чтобы ускорить работу алгоритма заметим, что если i – делитель а, то a div i – тоже делитель a, и к тому же одно из чисел i и a div i не превышает Sqrt(a) (если предположить противное, то получим a = i*(a div i) > Sqrt(a)*Sqrt(a) = a – противоречие). Поэтому достаточно перебирать числа i в пределах от 1 до Sqrt(a) и находить сразу два делителя i и a div i.

Нахождение простых чисел.

Опр. Натуральное число называется простым, если оно имеет всего два делителя единицу и самого себя.

Единица не простое число. Наименьшее простое число 2. Оно единственное четное простое число.

Одним из первых, кто заинтересовался простыми числами, был Эратосфен, он собственно впервые и выдвинул метод нахождения всех простых чисел, не превосходящих N. Этот метод заключался в том, что он вначале выписывал все числа от 2 до N. Затем, пока оставались не вычеркнутые и не обведенные числа, он проделывал следующий набор операций: обводил наименьшее из оставшихся чисел и вычеркивал все числа, кратные ему После окончания работы алгоритма все простые числа были обведены. Рассмотрим задачу, которая решается с использованием решета Эратосфена.

Задача 5 Основная теорема арифметики

Основная теорема арифметики гласит, что любое натуральное число х > 1 может быть единственным образом представлено в виде произведения х = р₁^a1 …р_k^ak..., где p₁ < ... <р_k.- простые числа, а₁… а_k, — положительные целые числа. Ваша задача — написать программу, находящую такое представление для заданного числа х. Напомним, что натуральное число называется простым, если оно больше единицы и делится только на единицу и на себя. Формат входного файла: Входной файл содержит целое число х (2<= х<= 2 10⁹). Формат выходного файла: В выходной файл выведите искомое представление числа х. В качестве знака умножения выводите * (звездочка). Сомножитель вида р^а выводите как р^а. Если а = 1. то выводите просто р. Отделяйте сомножители от знака умножения пробелом. Примеры

Input.txt	Output.txt
12	2^2 * 3
16	2^4
36	2^2 * 3^2

program osnteoremaarifmetiki;

var x,n,k,p:longint;

log:boolean;

begin

assign(input,'input.txt');assign(output,'output.txt');

reset(input);rewrite(output);

read(x);

p:=2; первый возможный множитель

log:=false;

while x>1 do пока множители есть

begin

k:=0; количество повторений одного множителя

while x mod p=0 do пока число x делится на множитель

begin

inc(k); считаем его

x:=x div p; и делим на множитель

end;

if k=0 then

begin inc(p);continue; end; если на p число x не поделилось,

то переходим к следующему p

if log если это не первый множитель

then

if k=1 если множитель в одном экземпляре

then write(' * ',p) выводим * р

else write(' * ',p,'^',k) иначе * p^k

else если это первый множитель

begin выводим без знака умножения

if k=1

then write(p)

else write(p,'^',k);

log:=true; сигнал о том, что первый множитель уже был

end;

inc(p); проверяем следующее число

end;

close(input);

close(output);

end.

задачи

Задача 6 Дано натуральное число. Определить простое оно или нет

Вот логическая функция определяющая простоту числа.

function simple(p:longint):boolean;

var i:longint;

begin

simple:=false;

if p=2 then begin simple:=true;exit; end; если число =2 то оно простое,

выходим из функции

if (p=1)or(p mod 2=0) then exit; если число =1 или делится на 2

то оно не простое

i:=3; начинаем проверку с 3

while i<=SQRT(p) do проверяем все нечетные числа от 3 до

кв.корня из числа

if p mod i=0 если p делится на i, то оно не простое

then exit выходим из функции

else inc(i,2); иначе берем следующее нечетное

simple:=true е сли ни на какое число p не разделилось,

то число p простое

end;

И, наконец, можно сочетать второй и третий способы.

Задача 7 Найти все простые числа из отрезка [a,b]. Где a и b натуральные числа

Способ 1.

Нахождение простых чисел на заданном отрезке, используя решето Эратосфена.

Program Erathospen; находит простые числа на отрезке [1,N]

Var a:array[1..10000] of integer;

i,n,z,kol:integer;

Begin

N=10000; верхняя граница простых чисел

For i:=1 to n do a[i]:=i; заполняем массив натуральными числами

For i:=2 to n do

For z:=2 to n div i do a[z*i]:=0; все числа массива кратные i заменяем

нулями

For i:=2 to n do выводим все не равные нулю элементы

массива

If a[i]<>0

then

begin

write(a[i],’ ‘);inc(kol);

end;

End.

Известно, что простые числа большие 3-x представимы в виде N=6*k+1 или N=6*k-1. Воспользуемся этим фактом.

Второй способ

Procedure simple(up,down:integer); ищем простые на отрезке [up,down]

Var i,j,n,k,kol:integer;

Begin

kol:=0;

For i:=(up+1) div 6 to (down+1) div 6 do

For k:=0 to 1 do генерируем числа вида N=6*i-1 или

N=6*i+1

begin

n:=6*i+k*2-1;

j:=3;

While (j<=sqrt(n)) and (n mod j<>0) do inc(j,2); проверяем на простоту

If (j>sqrt(n))and (n>=up)and(n<=down) если n простое,то

then begin write(n,’ ‘); inc(kol); end; выводим его и считаем

end;

End.

Эта процедура находит все простые числа большие 3. Нахождение 2 и 3 приходится обрабатывать отдельно.

Третий способ.

Решение: Перебираем все натуральные числа из отрезка [a,b] и проверяем каждое на простоту с помощью функции simple.

program prosta_b;

var j,a,b,t:longint;

function simple(p:longint):boolean; определение простоты числа

var i:longint;

begin

simple:=false;

if p=2 then begin simple:=true; exit end;

if (p=1)or(p mod 2=0) then exit;

i:=3;

while i<=sqrt(p) do

if p mod i=0

then exit

else inc(i,2);

simple:=true;

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(a,b);

t:=0;

for j:=a to b do перебираем все числа от a до b

if simple(j) then простые числа выводим по 15 в строке

begin

inc(t);

if t mod 15=0 через пробел

then writeln(j)

else write(j,' ');

end;

close(input);

close(output);

end.

задачи

Задача 8 Найти все простые числа, не превышающие данного натурального N и поместить их в массив констант

Сначала пишем программу – генератор простых чисел, в которой используется функция simple.

Алгоритм будет следующий:

1. Запускаем программу – генератор

2. Переходим в окно файла output.txt. Ставим курсор на первое простое число 2. Нажимаем Ctrl+K+B, отмечая начало блока простых чисел.

3. Нажимаем Ctrl+PageDown для перехода в конец блока простых чисел. Стираем последнюю запятую. Нажимаем Ctrl+K+K, чтобы отметить конец блока.

4. Нажимаем Ctrl+Insert, помещая блок простых чисел в буфер.

5. Переходим в окно с программой и устанавливаем курсор в строку const p=array[1..] of integer =(); между круглыми скобками.

6. Нажимаем Shift+Insert, для вставки блока простых чисел из буфера.

Количество простых чисел можно посмотреть в переменной t в окне Watches или вывести в файл output.txt, а потом стереть. Это количество записываем в квадратные скобки в разделе описания массива констант (см. задачу 8).

program gensimple; программа – генератор простых чисел

{простых чисел меньше 1000000 всего 78498}

var

t,i,n:longint;

function simple(p:longint):boolean;

var i:longint;

begin

simple:=false;

if p=2 then begin simple:=true; exit; end;

if (p=1)or(p mod 2=0) then exit;

i:=3;

while i<=round(sqrt(p)) do

begin

if p mod i=0 then exit

else inc(i,2);

end;

simple:=true;

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(n);

t:=0; счетчик количества простых чисел

for i:=1 to n do

if simple(i) если число простое

then

begin

inc(t); считаем его

if t mod 20 =0 если в строке уже 20 чисел, то

then writeln(i,',') переводим курсор на новую строку

else write(i,',');

end;

close(input);

close(output);

end.

задачи

Задача 9 Зачеркнутая цифра

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

Входной файл Input.txt содержит:

• в первой строке одно натуральное число, содержащее N цифр (1<N100000) – разность большего и меньшего чисел без вычеркнутой цифры.

Выходной файл Output.txt должен содержать одно натуральное число - зачеркнутую цифру.

Пример:

Input.txt	Output.txt
180186	3

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

program raznostj;

var s,n:integer;

c:char;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

while not eof do пока не дошли до конца файла

begin

read(c);

n:= ord(c)-ord('0'); получаем значение цифры

inc(s,n);

s:=s mod 9;

end;

write(9-s);

close(input);

close(output);

end.

задачи

Задача 10 Наибольшее число

Дана последовательность натуральных чисел. Найти в ней наибольшее число, сумма цифр соседей которого есть простое число (у первого и последнего по одному соседу). Если таких чисел нет, то вывести –1.

Формат входного файла:

• в первой строке одно натуральное число N (N100000).

• во второй строке N натуральных чисел , записанных через пробел а₁,а₂,…а_n (а_i10⁶).

Формат выходного файла

одно натуральное число.

Пример:

Input.txt	Output.txt
5 4 6 7 9 3	6

задачи

Задача 11 Простая задача

Требуется вывести ВСЕ простые числа большие А и меньшие В.