Разработать программы до 15.09

Лабораторная 1_1. Целочисленная арифметика

Разработать алгоритмы и составить программы для решения следующих задач: Гарантируется , что все числа (в том числе для промежуточных вычислений) для задач сложности А-С, не более 2 147 483 647 (тесты, содержащие большие числа, могут быть добавлены для тех, кто уже умеет программировать)

Сложность А. Типовые задачи (надо уметь делать все)

А1.0 Заданы три целых числа, которые задают некоторую дату. Определить дату следующего дня.

А2.0 Найти НОД и НОК двух натуральных чисел a и b.

А3.0 Задано натуральное число. Проверить, является ли заданное натуральное число палиндромом.

А4.0 Определить является ли заданное натуральное число простым.

А5.0 Найти сумму и количество цифр у заданного натурального числа.

А6.0 Найти количество различных цифр у заданного натурального числа

А7.0 Найти наибольшую цифру натурального числа.

А8.0 Найти все простые делители заданного натурального числа.

А9.0 Возвести число А в натуральную степень n.

А10.0 Вычислить число сочетаний из N элементов по M.

А11.0 Совершенным называется число, равное сумме всех своих делителей, не равных самому числу, учитывая и 1. Проверить является ли заданное число совершенным.

А12.0 В представлении десятичного целого числа в n-ой системе счисления (2<=n<=9) найти количество цифр

А13.0 Задано число, содержащее от двух до четырех цифр. Между каждой парой соседних цифр, вставить 9.

А14.0 Задано число А, содержащее не более четырех цифр. Каждое вхождение наибольшей цифры, использованной в записи числа А, продублировать. Например,

4241 -> 442441

А15.0 Последовательность Фибоначчи определяется так: a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2. Дано n, вычислить a(n). (Не использовать массив).

Разработать программы до 15.09

(не менее одной задачи)

Сложность В

В1.0 Найти НОД и НОК двух натуральных чисел a и b и такие целые x и y,

что nod = a*x + b*y.

В2.0 Найти количество повторений каждой цифры у заданного натурального числа (не используя массивов).

(Не использовать массив).

В3.0 Найти наименьшее (наибольшее) трехзначное число, сумма кубов цифр которого равна заданному М.

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

В5.0 Напечатать в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр. Операции деления не использовать.

В6.0 Найти все натуральные числа, не превосходящие заданного N и равные сумме кубов своих цифр.

В7.0 Два числа называются дружественными, если каждое из них равно сумме всех делителей второго, не считая самого этого числа. Проверить являются ли заданные числа А и В дружественными.

В8.0 Для натуральных чисел Х и У найти такие простые P1и P2, что X*X-Y*Y=P1*P2.

В9.0 Найти все натуральные числа, не превосходящие К, сумма цифр каждого из которых в некоторой степени дает это число (9²=81,18³=5832).

В10.0 Напечатать N автоморфных чисел (автоморфным называется число, совпадающее с младшими цифрами своего квадрата). ( напр. 25,625).

В11.0 Найти N пар взаимно-простых натуральных чисел.

В12.0 Найти М троек чисел Пифагора.

Разработать программы до 15.09

(не менее одной задачи)

Сложность C.

С1.0 Заданы три целых числа, которые задают некоторую дату. Определить номер дня недели по заданной дате.

С2.0 Найти пары натуральных чисел, не превосходящих N, произведение которых содержит цифры большего множителя, раздвинутого нулями. Например, 111*91=10101.

С3.0 Написать вариант алгоритма Евклида, использующий соотношения

НОД(2*a, 2*b) = 2*НОД(a,b)

НОД(2*a, b) = НОД(a,b) при нечетном b, не включающий деления с остатком, а использующий лишь деление на 2 и проверку четности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.).

С4.0 Задано натуральное число n.Найти первую справа ненулевую цифру у числа n!..

С5.0 Подсчитать количество решений неравенства x*x + y*y < n в натуральных (неотрицательных целых) числах, не используя действий с вещественными числами, но количество операций должно быть порядка (n в степени 1/2).

С6.0 Даны натуральные числа n и k, n > 1. Напечатать k десятичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.

С7.0 Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n.

С8.0 Даны натуральные числа а и b, причем b > 0. Найти частное и остаток при делении а на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 четных чисел; число шагов не должно превосходитьC1*log(a/b) + C2 для некоторых констант C1, C2.

С9.0 Найти k-ое простое число в арифметической прогрессии 11, 21, 31, 41, 51, …

С10.0 Найти k-ую цифру в ряду цифр, составленных из подряд идущих натуральных чисел, начиная с 1. 123456789 10 11 12 13

С11.0 Представить дробь p/q (0<p<q<16) в виде суммы различных дробей, числитель которых равен 1.

С12.0 Вводится некоторое натуральное число N, состоящее не более чем из 10 различных цифр (первая цифра - не 0). Определить, сколько существует различных чисел, больших N и составленных из тех же цифр (и в тех же количествах), что и N. Например, для числа 315 таких чисел 3. Эти числа: 351, 513 и 531.

5/7