Решить предыдущую задачу не используя дополнительных переменных и предполагая что значениями
Решить предыдущую задачу не используя дополнительных переменных и предполагая что значениями
На этом шаге мы немного «отдохнем» от теории, составляя несколько простых линейных программ.
Задача 1. Даны две целые переменные a, b. Составить программу обмена значениями этих переменных.
Решение. Введем дополнительную переменную t и выполним следующие присваивания: t:=a; a:=b; b:=t;. Попытка обойтись без дополнительной переменной, написав: a:=b; b:=а; не приведет к цели (безвозвратно утрачивается значение переменной a):
Текст этой программы можно взять здесь.
Задача 2. Даны две целые переменные a, b. Составить программу обмена значениями этих переменных не используя дополнительных переменных и предполагая, что значениями целых переменных могут быть произвольные целые числа.
Решение. Существует несколько способов сделать это:
Текст этой программы можно взять здесь.
Для всех ли значений (целых, вещественных) будет всегда «работать» такой вариант обмена? Если нет, то для каких значений переменных этот алгоритм не будет приводить к результату?
Ответ вы можете посмотреть здесь.
б) можно использовать логическую операцию XOR (исключающее ИЛИ) (смотри таблицы 1 и 3 шага 14). Эта операция над двумя переменными в компьютере реализуется как побитовая операция над двоичным представлением чисел. Поэтому, в частности:
A XOR A = 0, A XOR B = B XOR A, A XOR 0 = A.
Текст этой программы можно взять здесь.
Надеемся, что вы получили представление о том, как создаются линейные программы. Следующий шаг будет посвящен созданию разветвляющихся программ.
Решение задач. День третий. Задачи Begin21-30
Здравствуйте, дорогие читателинашего сайта. На этой недели счетчик посещаемости наконец-то сдвинулся с мертвой точки. Это не может не радовать. Если вы новоиспеченный постоянный посетитель этого сайта, оставьте комментарий к любому посту, чтобы мы не думали, что на нашем сайте обитают только боты 🙂 Ну что ж, приступим к решению задач Begin21-30.
Begin21. Даны координаты трех вершин треугольника: (x1, y1), (x2, y2), (x3, y3). Найти его периметр и площадь, используя формулу для расстояния между двумя точками на плоскости (см. задание Begin20). Для нахождения пло щади треугольника со сторонами a, b, c использовать формулу Герона: S = √(p ⋅ ( p − a) ⋅ ( p − b) ⋅ ( p − c)), где p — полупериметр.
На первый взгляд задача может показаться весьма и весьма трудной, и для того, чтобы не заблудиться в решении, составим план наших действий:
Begin22°. Поменять местами содержимое переменных A и B и вывести новые значения A и B.
Эта классическая задача является основой более сложных алгоритмов. Представьте, у Вас есть два кувшина: первый наполнен водой, второй — соком. Требуется поменять жидкости местами, то есть, перелить воду во второй кувшин, а сок — в первый. Как Вы решите данную проблему? Скорее всего, Вы возьмете третий кувшин и временно перельете в него содержимое одного из кувшинов. Так и в Паскале: сначала мы присваиваем значение любой из двух переменных третьей, а уже потом перемещаем значения переменных.
Вода и персиковый сок
Begin23. Даны переменные A, B, C. Изменить их значения, переместив содер жимое A в B, B — в C, C — в A, и вывести новые значения переменных A, B, C.
И снова мы используем дополнительную переменную.
Begin24. Даны переменные A, B, C. Изменить их значения, переместив содержимое A в C, C — в B, B — в A, и вывести новые значения переменных A, B, C.
Задача, противоположная предыдущей.
Begin25. Найти значение функции y = 3·x 6 – 6·x 2 – 7 при данном значении x.
Begin26. Найти значение функции y = 4·(x–3) 6 – 7·(x–3) 3 + 2 при данном значе нии x.
В данной задачи требуется использовать вспомогательную переменную и три операции умножения, поэтому мы не можем использовать функцию power.
Begin29. Дано значение угла α в градусах (0 этого же угла в радианах, учитывая, что 180° = π радианов. В качестве зна чения π использовать 3.14.
Две следующие задачи является актуальными для нас. Ведь функции sin, cos, arctan работают только с радианами. И программа, которая быстро переводит градусы в радианы или радианы в градусы, очень ценна. А теперь формула: Радианы = Градусы * pi / 180.
Begin30. Дано значение угла α в радианах (0 этого же угла в градусах, учитывая, что 180° = π радианов. В качестве зна чения π использовать 3.14.
Формула нахождения градусов следует из предыдущей формулы : Градусы = Радианы * 180 / pi. Кстати, в решении данной задачи я использую стандартное значение Pi = 3.14159265358979
На сегодня все! Мы с вами решили целых десять задач. Конечно, они не очень сложные, но ведь цель этих задач познакомить вас с основными функциями, вводом и выводом и показать вам то, как легко и интересно программировать на любом из языков программирования.
Решить предыдущую задачу не используя дополнительных переменных и предполагая что значениями
Задание №1.
Составить алгоритм, определяющий количество дней между двумя датами, вычисляя вначале количество дней от начала летоисчисления по григорианскому календарю.
Задание №2.
Составить алгоритм, который заносит в таблицу первые 1000 натуральных чисел, делящихся на 13 или 17.
Задание №3.
Решить головоломку: (((((1?2)?3)?4)?5)?6)=36.
Заменить «?» на знаки арифметических операций так. чтобы получилось верное
равенство.
Задание №б.
Дано натуральное п. Сколько различных цифр встречается в его десятичной записи?
Задание №7.
В некотором арифметическом выражении удалили все символы, кроме скобок. Составить алгоритм, определяющий по полученной последовательности скобок, правильно ли они были первоначально расставлены.
Задание №8.
Король Артур послал римскому императору срочное сообщение, в котором содержатся числа, записанные арабскими цифрами. Написать программу, которая поможет императору понять сообщение путем преобразования входного потока в идентичный выходной с переводом всех чисел в римскую систему счисления. (Примечание: в сообщении встречаются только положительные целые числа, не превосходящие 4000).
Задание №10.
Изобразите треугольник, вращающийся вокруг точки пересечения его высот.
Задание №11.
Заданы целые числа Х1,Х2,…Х30> которые означают ежедневный спрос на продукцию в мае месяце. Постройте график зависимости спроса от дня месяца. Отрезки прямых, расположенных выше оси абсцисс и расположенных ниже её, должны быть окрашены в разные цвета.
Задание №12. Задача Диксона.
Будем говорить, что три натуральных числа образуют дружественную тройку, если сумма собственных делителей каждого числа равна сумме двух других чисел. Найдите хотя бы одну дружественную тройку натуральных чисел.
Задание №13.
Проверьте, является ли заданное натуральное число п>1 простым.
Задание №14.
Даны натуральные числа пик, п>1. Напечатайте к десятичных знаков числа 1/п. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.
Задание №15.
Дано натуральное число п>1. Определите длину периода десятичной записи дроби 1/п.
Задание №16.
Разрешим использовать команды write(i) лишь при I=0,1. 9.
Напишите программу, выводящую десятичную запись заданного натурального
числа п>0 в обратном порядке. (Для п=173 надо вывести 371.)
Задание №18.
Составьте программу, находящую разложение на простые множители заданного натурального числа п>0 (другими словами, требуется выводить только простые числа и произведение напечатанных чисел должно быть равно п; если п=1, то выводить ничего не надо).
Задание №19.
Дано целое число а и натуральное (целое неотрицательное) число п. Вычислите а в степени п. Другими словами, составьте программу, при исполнении которой значения переменных а и п не меняются, а значение некоторой другой переменной (например, Ь) становится равным а в степени п (разрешается использовать и другие переменные). Однако необходимо, чтобы число действий (выполняемых операторов присваивания) было порядка log n (не превосходило бы Clog n для некоторой константы С).
Задание №20.
Дано целое число а и натуральное (целое неотрицательное) число п. Вычислите а в степени п. Другими словами, составьте программу, при исполнении которой значения переменных а и п не меняются, а значение некоторой другой переменной (например, Ь) становится равным а в степени п (разрешается использовать и другие переменные).
Задание №21.
Найдите большее (меньшее) из двух целых чисел без использования оператора условного перехода
Задание №22.
Даны две целые переменные а и Ь. Составьте фрагмент программы, после исполнения которого значения переменных поменялись бы местами («новое» значение а равно «старому» значению b и наоборот).
Задание №23.
Решите предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).
Задание №24.
Найдите все трехзначные числа, представимые в виде сумм факториапов своих цифр. Используйте рекурсивную функцию вычисления п!.
Задание №25.
Определите число, получаемое выписыванием в обратном порядке цифр заданного натурального числа. Используйте рекурсивную функцию.
Задание №26. Задача Ферма.
Найдите куб, который в сумме со всеми его собственными делителями дает квадрат.
Задание №28.
Найдите наименьшее общее кратное четырех заданных натуральных чисел.
Задание №29.
Даны координаты вершин двух треугольников. Определите, какой из них имеет большую площадь.
Задание №30.
Даны координаты вершин треугольника и координаты некоторой точки внутри него. Найдите расстояние от данной точки до ближайшей стороны треугольника. (При определении расстояний учесть, что площадь треугольника вычисляется и через три его стороны, и через основание и высоту.)
Профи 
Группа: Пользователи
Сообщений: 775
Пол: Мужской
Репутация: 
0 
Бывалый
Группа: Пользователи
Сообщений: 239
Пол: Женский
Реальное имя: Юлия
Решить предыдущую задачу не используя дополнительных переменных и предполагая что значениями
1.1.1. Даны две целые переменные a, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот).
Решение. Введем дополнительную целую переменную t.
Попытка обойтись без дополнительной переменной, написав a := b; b := a; не приводит к цели (безвозвратно утрачивается начальное значение переменной a).
1.1.2. Решить предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).
Решение. (Начальные значения a и b обозначим a0, b0.)
1.1.3. Дано целое число а и натуральное (целое неотрицательное) число n. Вычислить а в степени n. Другими словами, необходимо составить программу, при исполнении которой значения переменных а и n не меняются, а значение некоторой другой переменной (например, b) становится равным а в степени n. (При этом разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0 до n, причем поддерживается такое свойство: b = (a в степени k).
while k <> n do begin
Другое решение той же задачи:
while k <> 0 do begin
Решение. Внесем некоторые изменения во второе из предложенных решений предыдущей задачи:
while k <> 0 do begin
if k mod 2 = 0 then begin
Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечетно, то после вычитания единицы становится четным), так что за два цикла величина k уменьшается по крайней мере вдвое.
while k <> b do begin
1.1.6. Даны натуральные числа а и b. Вычислить их сумму а+b. Использовать операторы присваивания лишь вида
1.1.7. Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 = 0; d > 0>
1.1.8. Дано натуральное n, вычислить n!
1.1.9. Последовательность Фибоначчи определяется так: a(0)= 0, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2. Дано n, вычислить a(n).
1.1.10. Та же задача, если требуется, чтобы число операций было пропорционально log n. (Переменные должны быть целочисленными.)
Указание. Пара соседних чисел Фибоначчи получается из предыдущей умножением на матрицу
так что задача сводится к возведению матрицы в степень n. Это можно сделать за C*log n действий тем же способом, что и для чисел.
1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+. +1/n!.
1.1.12. То же, если требуется, чтобы количество операций (выполненных команд присваивания) было бы не более C*n для некоторой константы С.
Решение. Инвариант: sum = 1/1! +. + 1/k!, last = 1/k! (важно не вычислять заново каждый раз k!).
Решение ( вариант 1).
if a > b then begin
while not ((a mod k = 0) and (b mod k = 0)) do begin
while not ((m=0) or (n=0)) do begin
if m >= n then begin
if m = 0 then begin
1.1.14. Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД (a, b) = НОД (a mod b, b) при a >= b, НОД (a, b) = НОД (a, b mod a) при b >= a.
1.1.15. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.
Решение. Добавим в алгоритм Евклида переменные p, q, r, s и впишем в инвариант условия m = p*a + q*b; n = r*a + s*b.
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
m = p*a + q*b; n = r*a + s*b.>
while not ((m=0) or (n=0)) do begin
if m >= n then begin
if m = 0 then begin
1.1.16. Решить предыдущую задачу, используя в алгоритме Евклида деление с остатком.
1.1.17. (Э.Дейкстра). Добавим в алгоритм Евклида дополнительные переменные u, v, z:
m := a; n := b; u := b; v := a;
while not ((m=0) or (n=0)) do begin
if m >= n then begin
if m = 0 then begin
Доказать, что после исполнения алгоритма значение z равно удвоенному наименьшему общему кратному чисел a, b: z = 2 * НОК (a,b).
Решение. Заметим, что величина m*u + n*v не меняется в ходе выполнения алгоритма. Остается воспользоваться тем, что вначале она равна 2*a*b и что НОД (a, b) * НОК (a, b) = a*b.
1.1.18. Написать вариант алгоритма Евклида, использующий соотношения
НОД (2*a, 2*b) = 2* НОД (a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b,
не включающий деления с остатком, а использующий лишь деление на 2 и проверку четности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)
while not ((m=0) or (n=0)) do begin
if (m mod 2 = 0) and (n mod 2 = 0) then begin
d:= d*2; m:= m div 2; n:= n div 2;
end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
end else if (m mod 2=1) and (n mod 2=1) and (m
Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам.
1.1.19. Дополнить алгоритм предыдущей задачи поиском x и y, для которых ax+by=НОД(a,b).
Решение. (Идея сообщена Д.Звонкиным) Прежде всего заметим, что одновременное деление a и b пополам не меняет искомых x и y. Поэтому можно считать, что с самого начала одно из чисел a и b нечетно. (Это свойство будет сохраняться и далее.)
Теперь попытаемся, как и раньше, хранить такие числа p,q,r,s, что
Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двоично-рациональными). Двоично-рациональное число естественно хранить в виде пары (числитель, показатель степени двойки в знаменателе). В итоге мы получаем d в виде комбинации a и b с двоично-рациональными коэффициентами. Иными словами, мы имеем
(2 в степени i)* d = ax + by
для некоторых целых x,y и натурального i. Что делать, если i > 1? Если x и y чётны, то на 2 можно сократить. Если это не так, положение можно исправить преобразованием
(оно не меняет ax+by). Убедимся в этом. Напомним, что мы считаем, что одно из чисел a и b нечётно. Пусть это будет a. Если при этом y чётно, то и x должно быть чётным (иначе ax+by будет нечётным). А при нечётном y вычитание из него нёчетного a делает y чётным.
1.1.20. Составить программу, печатающую квадраты всех натуральных чисел от 0 до заданного натурального n.
<инвариант: k 1.1.21. Та же задача, но разрешается использовать из арифметических операций лишь сложение и вычитание, причем общее число действий должно быть порядка n.
while not (k = n) do begin
while not (k = n) do begin
k_square := k_square + k;
k_square := k_square + k;
1.1.22. Составить программу, печатающую разложение на простые множители заданного натурального числа n > 0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно n; если n = 1, печатать ничего не надо).
n, напечатаны только простые числа>
while not (k = 1) do begin
while k mod l <> 0 do begin
числа просты; k не имеет делителей, меньших l>
while not (k = 1) do begin
if k mod l = 0 then begin
меньших l, значит, l просто>
1.1.23. Составить программу решения предыдущей задачи, использующую тот факт, что составное число имеет делитель, не превосходящий квадратного корня из этого числа.
Решение. Во втором варианте решения вместо l:=l+1 можно написать
if l*l > k then begin
1.1.24. Проверить, является ли заданное натуральное число n > 1 простым.
1.1.25. (Для знакомых с основами алгебры). Дано целое гауссово число n + mi (принадлежащее Z[i]). (a) Проверить, является ли оно простым (в Z[i]); (б) напечатать его разложение на простые (в Z[i]) множители.
знаков, что в base; base = 100..00>
while base <> 1 do begin
(Типичная ошибка при решении этой задачи: неправильно обрабатываются числа с нулями посередине. Приведенный инвариант допускает случай, когда k 1.1.27. То же самое, но надо напечатать десятичную запись в обратном порядке. (Для n = 173 надо напечатать 371.)
while k <> 0 do begin
1.1.28. Дано натуральное n. Подсчитать количество решений неравенства x*x + y*y
неравенства k*k + y*y while k*k + l*l >
всех решений неравенства k*k + y*y
1.1.29. Та же задача, но количество операций должно быть порядка (n в степени 1/2). (В предыдущем решении, как можно подсчитать, порядка n операций.)
находится сразу над k-ым столбцом;
Обозначим эти условия через (И).
while принадлежит X do begin
для которых не принадлежит X >
while not (l = 0) do begin
вниз, чтобы восстановить И >
while (l <> 0) and ( не принадлежит X) do begin
s равно искомому числу>
1.1.30. Даны натуральные числа n и k, n > 1. Напечатать k десятичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.
Решение. Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число (10 в степени k)/n. Нам надо напечатать его целую часть, т. е. разделить (10 в степени k) на n нацело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел. Поэтому мы сделаем иначе (следуя обычному методу «деления уголком») и будем хранить «остаток» r:
while l <> k do begin
write ( (10 * r) div n);
1.1.31. Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n.
Решение. Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности остатков и затем минимальное k, при котором (n+1+k)-ый член совпадает с (n+1)-ым.
while l <> n+1 do begin
while r <> c do begin
1.1.32. (Сообщил Ю.В.Матиясевич) Дана функция f:1..N->1..N. Найти период последовательности 1,f(1),f(f(1). Количество действий должно быть пропорционально периоду (который может быть существенно меньше N).
Решение. Если отбросить начальный кусок, последовательность периодична, причем все члены периода различны.
while a <> b do begin
while a <> b do begin
1.1.33. (Э. Дейкстра). Функция f с натуральными аргументами и значениями определена так: f(0) = 0, f(1) = 1, f (2n) = f(n), f (2n+1) = f (n) + f (n+1). Составить программу вычисления f (n) по заданному n, требующую порядка log n операций.
if k mod 2 = 0 then begin
f (n) = a*f(k) + b*f(k+1) = (a+b)*f(l) + b*f(l+1)>
f(n) = a*f(k) + b*f(k+1) = a*f(l) + (a+b)*f(l+1)>
1.1.34. То же, если f(0) = 13, f(1) = 17, а f(2n) = 43 f(n) + 57 f(n+1), f(2n+1) = 91 f(n) + 179 f(n+1) при n>=1.
Указание. Хранить коэффициенты в выражении f(n) через три соседних числа.
1.1.35. Даны натуральные числа а и b, причем b > 0. Найти частное и остаток при делении а на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 четных чисел; число шагов не должно превосходить C1*log(a/b) + C2 для некоторых констант C1, C2.