Задачи по программированию ч.1 Функции массивы

Упражнения программисту

1.1)Даны 2 переменные. надо поменять их значения. не исп вспомогат переменную.

А) a = a + b; b = a - b;  a = a - b;  б)

1.2) Даны перем A, B, C. Изменить их зн, переместив содерж A в B, B — в C, C — в A,

и вывести новые значения перем A, B, C.

A:=A+B;   B:=A-B; A:=A-B;{Закончился перевод А в В}

  B:=B+C; C:=B-C;  B:=B-C;

2) Дано действит число a. Не польз никак др арифм оп, кр умножения, получить:

a) a⁴ за 2 оп; ж) a¹³ за пять оп; б) a⁶ за 3 оп;з) a¹⁵ за пять оп; в) a⁷ за 4е оп; и) a²¹ за 6 оп;

г) a⁸ за 3 операц; к) a²⁸ за 6 операц; д) a⁹ за 4 оп; л) a⁶⁴ за 6о; е) a¹⁰ за 4 оп.

3). Выполнить нижеприведенную программу при х = 3, у = 7, z = 11:

начало

x := y+z;z := x+z; y := y+x; x := y-xx := x*z; z := y+z

конец

1)Чему равны знач перем х, y, z после вып прогр? Отв: x = 203, y=25, z=54

ЗАД1) Пошаг (алгоритм) записью выч выр наз такая запись, при кот каждая вып опер запис отдельно (на новой строчке), рез-т каждой операц заносится в отд перем (яч) – напр y1, y2, y3, .... , и только окон рез-т запис в перем, которая стоит в левой части исх записи.

ПРИМЕР. y :=(a-b)/(c+d) в пошаговой записи будет иметь вид:

1) y1 :=a-b 2) y2 :=c+d 3) y := y1/y2

При этом до вып правило: если на каком-то шаге в принципе м вып неск разных оп, то следует выб "край левую" из возм оп (следуя этому правилу, мы в привед прим пост 1й оп вычисл a-b, хотя в принципе м б бы начать с вычисл c+d).

Задание. Записать в пошаговой записи y :=(a+b)*(c-d)/(e+f)

ОТВЕТ: 1) y1:=a+b 2) y2:=c-d 3) y3:=y1*y2 4) y4:=e+f 5) y:=y3

Записать выражения

Задания на программы Целые числа

1)Ручка стоила K руб. 1 сент стоимость ручки увелич ровнона P%. Опр, сколько ручек м купить на Sруб после подорожания. исх данн 3 целых положит.K –стоимость ручки в руб до подорожания. P –вел подорожания ручкив %. S– сумма денег.

Дано 3зн число. Исп 1 оп деления нацело, вывести 1ю цифру данного числа (сотни).

2а) Дано 3-зн число. Выв внач его послед цифру (ед), а затем — его сред цифру (десятки).

2б) Дано 3-зн число. Вывести все его цифры

2в) Дано трехзначное число. Замените среднюю цифру на ноль

3) Дано3-зн число. Найти сумму и произведение его цифр кот вводит пользователь.

5)проверить что введенное 4-значн число является палиндромом

3)Два авто едут др за др с постоян скоростями и км/час. Если то авто едут навстр. Опр, через какое время авт встретятся, если расст между ними б S км или если встреча невом вывести сообщение

4)Даны целые числа h, m, s (0

5)Работа светофора для пешеходов : в начале каждого часа в теч 3 мин горит зеленый, затем в теч 2 мин — красный, в теч 3 мин— опять зеленый и т. д. Дано вещ число t, оз время в мин, прошедш с начала очередного часа. Опред, сигнал какого цвета горит для пешеходов в этот момент.

5) Пятница, 13-еКаленд жит пл Плюк сост из N мес, кажд мес сост из 30 дней, неделя - из 7 дн. Ос несчастл на пл Плюк счит 13-е чло мес, если оно выпад на пятн.Изв что Н год на пл Плюк нач в k-й по сч день нед(1-й день нед — понед, 2-й —вторн, 3-й —среда,, 7-й — воскр).

Опр, ск в этом году на пл Плюк будет особо несчастливых пятниц, 13-е. исходн. данные

1е число — кол месяцев в календ план Плюк 10

. 2е число — номер дня недели, на кот приходится 1е число 1го мес нов года, м прин зн от 1 до 7.

Прогр д вывести единств целое — кол несчастливых дней в этом году.

6) завод отпр один и тот же объем колы в л. обычно исп для транспортир колы емкости объемом или только 50 л, или только 70 л.Если доставка с пом емк в 50 л, то для перевозки имеющ объема колы н A емк. А если с пом емк в 70 л, то н B емк. При этом в каждом из сл одна из емк м б заполн не полн. решили утв новый объем емкдля дост колы — 60 л. Ск емк теперь н для доставки того же самого объема колы? Исх данные А,В

Логические условия

1а)Проверить что введенное число является четным

1б). Дано целое X. Определить кратно ли оно 2, 3 и целому числу P.

1в) Вво два целых . Пров дел ли 1е на 2е. Выв на экран сообщ об этом, а также остаток (если он есть) и частное (в любом случ).

2а)найти макс 2 чисел a и b (Запис операторы)2б) Вв 3 целых числа. Оп какое из них наиб.

3) Вв целое число, обозн код симв по табл ASCII. Опр, это код англ буквы или какой-л иной симв

4)Даны действительные числа x,y. Вычислить Z:

если

5) Даны действительные числа x, y, z. Вычислить:

а) max (x+y+z, xyz) б) (min(x+y+z/2,xyz))² + 1 (нсп пошаговую запись)

6) Даны 3 действит числа a,b,c. Возвести в квадрат те из них, знач кот неотрицательны..

7).Даны 2действ числа. Вывести 1е число, если оно 2го, и оба числа, если это не так.

8) даны 3 числа. a,b,c Сколько среди них отрицат

9))целые числа вводятся с клав. Конец ввода -0. А)Найти мах б)мин в)ср арифметич

10)Опр, войдет ли в конверт с внутр размерами a и b мм прямоугольн открытка размером с и d мм. Для размещ открытки в конверте необх зазор в 1 мм с каждой стороны.

Логические выражения логич операторы ifelsecase

1)Вычислить значение выражений. При a = 10, b = 20, c = true, d= false

a) (a5) and (b5) and (aб) not(a

в) c or d and (b=20) г)k mod 7 = k div 5 – 1при k=15 д)odd (trunс (10*p)) при p = 0.182

е)not odd (n) при n = 0 ж)false з)pred (true) и) (pпри p=q=true

к) ord (succ (false)) 0 л) not (pred(c) or (ord (c) = 1))) при c=true

м) a and b a or b при a=false, b= true

2. Вычислитьзначениявыражений:

А) a or b and not a при a=true, b=false; б) not a and b при a=true, b=false;

в) (pпри p, q=true.г)) a or (not b) при a=false, b=true.

д) a and ba or b при a=false, b=true; е) (a or b) and not a при a=true и b=false;

ж)) not (a and b) при a=true и b=false.

3. Указать порядок вып операторов при вычисл выр (надписать над зн оператора ном действия):

1) (x=0) or t and z or (y*y4) 2) a and b or not c and d

4. Доказатьтождества:

a or (not a)=true; a and (b or c)=(a and b) or (a and c); a and (not a)=false; a and b=(a

false and a =false; not (not a)=a; true or a =truea

5.Объяснить ошибки в следующих записях:

1) true + false; 3) not 2=5; 5) x0 or y=4.

2) 1 and 0; 4) true

6.Записать на Паскале выр, истин при вып указан усл и ложное в против случае:

А)0X=MAX(x,y,z) в)XMAX(x,y,z)

Г)хотя бы 1 логич перем А и В имеют зн trueД)обе логичперем А и В имеют зн true

Е)x принад [2,5] или [-1,1] ж) x лежит вне отрезков [2,5] и [-1,1]

З) y ном года. Явл ли год високосн.(Год високос, если он дел на 400 или дел на 4 но не дел на 100)

И) целые N и К имеют одинак четностьК) только одна из логич пере А и В имеют зн True

Л)a, b, c — стороны треуголь. Записать, что треугольник существует.

М)3 целых числа n, k, m имеют одинаковую четность

7)Даны 2 целых числа: D (день) и M (месяц), опр правильную дату невисокосного года. Вывести зн D и M для даты,а)предш указанной.б) следующей за указанной.

8) Робот м перемещ в 4 нап («С» — север, «З» — запад, «Ю» — юг, «В» — восток) и приним 3 цифр команды: 0 — продол движ, 1 — поворот налево, –1 — поворот направо. Дан симв C— исх направл робота и целое N — посла ему команда. Выв напр робота после вып получ команды

7)Поле шахм доски задано парой целых чисел, каждое из кот

а) На поле (a, b) распол ладья. Записать усл, при кот она угрожает полю (c, d).

б) На поле (a, b) распол слон. Записать усл, при кот он угрожает полю (c, d).

в) На поле (a, b) распол король. Записать усл, при кот он может 1 ходом попасть на поле (c, d).

г) На поле (a, b) распол ферзь. Записать усл, при кот он угрожает полю (c, d).

д) На поле (a, b) белая пешка. Записать усл, при кот она м1 ходом попасть на поле (c, d):

д1)при обычн ходе; д2)когда она «бьет» фигуру или пешку соперн. Белые пешки перемещ на доске снизу вверх.

8) Шахм доска сост из n × m клеток, покраш в черный и белый цв. При этом клетка в левом нижн углу доски черная. Опр, ск всего на доске черных клеток. 

Pascal	C++
if n*m mod 2 =0 then result:=n*m div 2 else result := (n*m+1) div 2;	if (n*m % 2 ==0) k= else

1. Опр знач переменной «a» после выполнения фрагмента программы:

a := 10; b := 5; ifnot (a

a := 10; b := 5; if (a 5) and (a

a := 10; b := 5; if (a 1) or (a if (a 1) and (a = b) then a := a - 5;

a := 10; b := 5; if (a 1) and (a if (a 1) and (a = b) then a := a - 5;

3.Какую логич оп н доб в прогр вместо многоточ, чтобы зн перем «a» после вып фрагм прогр стало

равно 3?	равно 15?	равно 17
a := 10; b := 5; if (a b) then a := a – 7 else a := a + 7;	a := 10; b := 5; if (a b) then a := a – 5 else a := a + 5;	a := 10; b := 5; if (a 1) ... (a else a := a + 7;

8). 2 отрезка на плоскости заданы целочисл к-тами своих концов в декарт системе к-т. Треб опре, существует ли у них общая точка.

9) Время зад в формате час, минута, сек. Реализовать:

а) вычит из времени указан польз количества секунд;

б) подс числа секунд между 2 мом времени, леж в пределах одних суток.

10)Манхэттен. Кв-лы Манхэт сост из авеню, напр с юга на север и улиц, напр с запада на вост. Все у и авеню пронум числами, нач с 1 подряд (1я ул, 2я ул, 3я ул и т. д.). Передвиг м только по ул или по авеню. М попал на Манхэтт.он сто на пересеч авеню x1 и ул y1. Ему н попасть на перекр авеню x2 и ул y2.Опр маршрут, кот он д пройти. вход 4 числа: x1, y1, x2, y2, запис в отд строках. Все числа нат, Прогр д выв посл-ть из лат загл букв,описать маршр, кот д след Миша. N обозн перемещ на 1 кв-л на север, S — на юг, W на запад, E — на восток.Прогр д выве самый корот из всех возм маршр, если же кратч неск, то вывести любой из них(но только 1).

прим вх данных x1=1 y1=3 x2=4 y2=1 вывод EEESS

11)В выписал на доске посл-ть: 1 2 3 2 3 4 3 4 5 4 5 6 5 6 7...После этого В задался вопр, на каком месте в ней впервые встрет число k? Напиш прогр, кот ответит на его вопрос.

Вх данные нат число k (1 ≤ k ≤ 100).

вых данные- число - поз, на кот 1й раз встр число k. Члены посл-ти нумер с 1.

Вх данн	1	2	4
Вых данн	1	2	6

12) Стоянка Заплатив a ед, можно использовать парковку в теч 1 дня.

Заплатив b ед, м использ парковку в течение 1 недели, т е 7 дней.

Заплатив c ед м использ парковку в течение 4 недель, т е 28 дней.

Какое мин колич денег н заплатить, чтобы иметь возможн использ стоянку все n дней?

стандартный ввод	стандартный вывод
4 7 20 N=10	14
2 9 38 n=36	47

В прим 1 выгодно взять 2 абон на неделю, это б стоить 2* 7 = 14 и позв опл парковку на 14 дней.

В прим 2 выгодно взять 5 абон на неделю и 1 на день -опл парковку на 36 дней

11)Кредит.Предпр, взял кредит  k руб под p % годов и влож его в св дело , его дело д дав прибыль  r руб в год. См ли он накопить сумму, достат для погаш кредита, и если да, то через ск лет?

12) перевозкиИз порта в др н перевез 15 разл грузов. Грузоподъемн судна- перевозч, 50 т. Грузы пронум, и инф о массах грузов хран в массиве М(15). Опр, ск рейсов н сделать судну, если грузы неделимы и м перевоз только подряд в порядке их нумерац. ( масса отд груза не превыш 50 т).

13)) Даны действ числа a, b, c (a0). Выяснить, имеет ли уравн действит корни. Если действ корни имеются, то найти их и их колич. Иначе выдать сообщ, что действ корней нет.

Вычислительная геометрия

1) Даны действит числа a, b, c 0. сущ ли треугольник с длинами сторон a, b, c

и если да то Определить тип т: тупоугольный, прямоугольный или остроугольный.

2) Концы отрезка на пл-ти имеют целочисл к-ты. выч, ско всего точек с целочисл к-тами на нем

4)3 попарно непараллельные прямые заданы коэфф a_i, b_i, c_i соотв уравн a_ix + b_iy = c_i. Коэфф a_i и b_i не могут быть одновр =0. написать прогр, опр площадь треугольника, образован этими прямыми.

ЦИКЛЫ

Вывод всех натур делителей числа x в порядке возрастания (включая 1 и само число).

Pascal	С++
Var I,x:integer; Begin Readln(x); For i:=1 to x do If x mod i=0 then write(I,’ ‘); End;	int x; cin x;  for (int i = 1 ; i if ( x % i == 0 ) cout

1)на окружности n точек. Кузнечик прыгает на к-точку по час стрелке. Найти мин кол прыжков для возврата в исходную точку

2) Авто на каждом из n участках дороги зад длины шел с изв средней скоростью. определить на всем пути а) среднюю скорость б)максимальную скорость

3) Возв вв с клав число, в степень n, степень тоже вв с клав. Возв в степень организ с исп циклов.

4)Колцелых чисел внутри круга радR. К-ты т внутри круга удовл усл

5а)Вкладчик взял кредит у банка на сумму под p% годовых. Схема начисл в конце i-периода Банк начисл проценты, а затем вкладчик переводит сумму a т.е

А)рассч колич периодов n погашения кредита. Для этого в прогр сделать цикл While(S0)

Б)При каком условии кредит не может быть погашен? (

5б)Вкладчик в начале каждого периода кладет на счет сумму а в конце периода Банк начисляет

p% на сумму вклада. Рассч 1)колич периодов n до накопления суммы

2) среднемес доход для каждых i периодов

З3.Убрать усл оператор «Если» из след блока (А м принять зн 0 или 1):

Если (А = 0) Тогда    B = 2;
Иначе    В = 1;
КонецЕсли;

Не доп исп ЛЮБЫХ других условных операторов (напр, ?(А = 0;2;1))

З 4.Имеются 2 массива данных А[а] и B[в] (а и в – кол эл массива). Изв, что оба массива упоряд по

возр. Н написать алг, проходящ по этим массивам за 1 цикл вида:Для Сч = 1 По а + в Цикл и

выдающ з обоих массивов в порядке возр т.е. как бы объед оба массива и отсорт их по возраст.

З5.Имеется неупорядоч массив из n разл целых чисел от 0 до n(0,1,…,j-1,j+1,….,n). Н за один цикл опред недостающее число j.

З6а). Даны целые положит числа N и K. Исп только оп слож и вычит, найти частное от дел нацело N на K, а также ост от этого дел.б)даны Aи B (A B0). На отрезке длины A размещ макс возм кол отрезков длины B (без налож). Не исп оп умн и дел, найти а)длину незанятой части отрезкаA б)кол отрезковB, размещен на отрезкеA.

Дано целое K, а также K наборов ненул целых чисел.
а)Каждый набор содерж ≥2 эл, призн его заверш явл 0 а)Для каждого набора вып: если эл набора возр то выв 1; если убыв, то выв ¡1; если не возр ине убыв, то вывести 0

Б) набор содерж ≥3эл Найти кол-во пилообразных наборов

В)если набор пилообр то вывести кол его эл; в прот сл выв номер 1гоэл, кот не явл зубцом

Алгебра

1)Количество целых точек на отрезке [a,b];

Pascal uses math	C++ #include
Ceil(X) - до целого в большую сторону; Floor(X) - до целого в меньшую сторону; Round(X) - до целого в ближайш сторону; Trunc(X) - до целого путем отбрас дробн части.	сeil(X) - до целого в большую сторону; floor(X) - до целого в меньшую сторону

Pascal	C++
a,b: real; k1,k2,k:integer; k2:=floor(b); k1:=Ceil(a); k:=k2-k1+1;	int k,k1,k2; float a,b; k1=ceil(a); k2=floor(b); k=k2-k1+1;

2а)ал Евклида вычисл НОД(a,b) Б))ИспНОД(a,b) вычислить НОК(a,b)

3)Тройка натур чисел a,b,c наз пифагоровой, если вып a²+b²=c² (как в прямоуг треуголь с катетами a,b). Эти тройки формир через параметры u, v по схеме: ; , где u,v - также натур числа, причем uv (пров вып рав a²+b²=c² м одной строчкой ал выкладок). Нарис блок-сх прог, кот д сформир пифагор тройки a,b,c. В блок-схпредусм блок, выдачи тройки a,b,c.

4) решить линейное уравнв кольце вычетов по модулю m (т.е.чисел от  до ). Предусмотреть случай отсутствия решения

5) колич неотриц ре диофант ур (размен суммы с купюрa,b), Прогр д проверить условие делимости с на НОД(a,b)

6)Дано натур число. а)получить колич его делителей б) Получить все его делители.

7) можно ли с использ только операций + 3 и + 5 получить из числа 1число N (N - нат,

Вх данные -число N.Вых дан -YES, если число N м получ из числа 1, или NO - в прот сл.

8)Нат число наз совершен, если оно = сумме всех св делителей, не= самому числу. Найдите все соверш числа, меньшие данн натn.

9)ШестеренкиДаны 2сцепл шестеренки. У 1й шестер N зубцов, у др – K. Треб найти, какое ми число поворотов на 1 зубчик треб сделать, чтобы шестеренки верн в исх состояние.

Вычислительная геометрия

1) Составить функцию-предикат, определяющую пересекаются ли 2 отрезка

2)Треугольн задан коорд верш A,B,C:TPoint; зад т P:TPointСост функ-предикат, опред лежит ли точка P внутри треуг. Указ. Сост функцию оп знак поворота вектора отн вектора по знаку выр(b.x-a.x)*(p.y-a.y)-(b.y-a.y)*(p.x-a.x);

Задачи на последовательности

0)Дано целое N( 0). Исп 1 цикл, найти а) сумму1 + 1/(1!) + 1/(2!) + 1/(3!) + …+ 1/(N!)Получ число явл прибл зн конст e = exp(1). Б)

1) Нарис блок-сх алг, для зад: изв целое число х1=2, явл нач для посл-ти х1, х2, х3, ....; каждое след число в посл-ти вычисл через предыд: x_i = 3*(x_i-1) - 2, при i1. (или x_i := 3*(x_i-1) - 2)

В прогр надо вычислитьn член посл-ти { x_i} и сумму S перых n членов посл-ти. Вывод получ результатов на блок-схеме обозн в виде параллелограмма, напр: Вывести "xn, S"

2) а)Найти сумму 1-х n членов посл=ти с и n ввести с клавиатуры.

Проверить что при увелn сумма стремится к пределу

Б)Найти сумму членов посл-ти превосх зад зн К. Вывести ск членов ряда н б сложить

3).Возвратные последовательности. А)

б) в)

4) Дано вещ  ϵ (0). Посл-ть вещ чисел AK опр след обр:  A1=1,A2=2, AK=(AK−2+2∗AK−1)/3,

K=3,4,… . Найти 1й из ном K, для кот вып усл |AK—AK−1|, и выв этот ном, а также

числа AK−1 и AK.

5)вычислить цепную дробь. Кол элем дроби зад с клавиатуры.

А) б)в)

6)Даны действит числа х, а, нат число n.Вычислить

Преобразования и перевод чисел

Дано целое число N( 0). Исп оп деления нацело и взятия остатка от деления,

А)вывести все его цифры, начиная с самой правой (разр единиц).б)предусм ввод основания системы счислp и вывести все цифры введ целого числа p-чного вида

В)найти колич и сумму его цифр г)найти число, получ при прочтении числа N справа налево.

Вывод цифр числа в обратном порядке

Pascal	С++
while N0 do   begin    Writeln(N mod 10);   N:=N div 10;   end;	while (n0) {        printf("%i\n",n%10);        n /=10;    }

9) Вводится число. Преобр его в другое число, цифры кот будут след в об порядке по сравн с введен числом. Указ 1) взять послед цифру в 1м числе; 2) записать ее в конец 2го; 3) убрать послед цифру из 1го числа. При этом 2е число изнач не д иметь знач разрядов. Таким обр послед цифра 1го числа окаж 1й цифрой во 2м; предпосл цифра 1го числа - 2й во 2м числе; и т. д.

10)6)Реализовать перевод 10-ичного числа N в q-ичную систему счисления

А)в виде обратной последовательности цифр б)в виде прямой последовательности с помощью 2 циклов While в 1 цикле вычислить минимальное к

1) Двоичный тренажера) Прогр задум сл число от 0 до 15 и выдает его в двоичн виде, польз д вв 10ичн(или 16ичн) аналог. А)' преобр числа в двоичн вид б)к-ль введ символов

в) разраб инт=са (внешний вид, реакции на о, поощрит сообщения и т.п.)

б) Прогр д анализир время ожид ответа польз, и выдавать оценку за вып, доп, 20 заданий, учит число ошибок и сумм время затраченного на ответы.

Теория игр

1) Исполнитель Водолей У исполнителя “Водолей” есть 2сосуда, 1й объемом A л, 2й объемом B ли, а также кран с водой. Водолей м выполнять следующие операции:

Наполнить сосуд A ( A). Наполнить сосуд B ( B).

Вылить воду из сосуда A ( A). Вылить воду из сосуда B ( B).

Перелить воду из сосуда A в сосуд B к AB). Перелить воду из сосуда B в сосуд A ( BA).

Команда переливания из одного сосуда в др приводят к тому, что либо 1й сосуд полностью опустоша, либо 2й сосуд полность наполняется.

Входные данные -три натуральных числа A, B, N, не превосх 10⁴.

Выходные данные - вывести алгоритм действий Водолея, кот позволяет получить в точности N л в одном из сосудов, если же такого алгоритма нет, то прогр выводит текст Impossible. Примеры

Входные данные	Выходные данные
3 5 1	A AB A AB
3 5 6	Impossible

2)Зад правила игры в камни. Играют двое. В куче N камней. Кажд игрок обязан выним камней если это воз, иначе – доб камней. Выиграет тот после чьего хода в куче не ост камней.

А)проанализир игру Выиг ли 1й или проигр при

Б)составить алгоритм и программу поиска выигрышных позиций при любых рассмотреть отдельно случаи и

15)Игра камни Играют 2 Каждый обязан выним или камн .Проигр тот, кто не см сдел ход.

А)проанализир игру Показать что список выигр-проигр позиций имеет период Выиграет ли 1й или проиграет при при при ?

16) Написать прогр определ кол 6-зн счастливых билетов, у кот сумма 1х 3 цифр совпадает с суммой 3 последних.Оптимизировать решение по кол-ву операций

Указ Сумма цифр от 0 до 27, т.е. м просто посчит ск чисел от 0 до 999 с данной суммой цифр и записать это зн в массив M[i] .и далее

For I := 0 to 27 do

L := L + M[I] * M[I];

Простые процедуры, функции

И1. Что делает следующая функция:

int f (int x, int n) { int res = 1; while (n 0) { if (n % 2 == 1) res *= x; n /= 2; x *= x; } return res; }

f (x,n:Integer):integer; Begin Result:=1; While n0 do Begin If n mod 2 =1 then Result := Result *x; n:= n div 2; x:=x*x; End; End;

2).Калькулятор арифм действий с пом ф видаFunctionимя (a,b:real):real;

Вид оп опред целым парам Op: 1 — вычит, 2 — умн 3 — деление, ост зн — сложение.

3)Даныдействчислаa, h, натуральное n.Вычислить
f(a)+2f(a+h)+2f(a+2h)++2f(a+(n–1)h)+f(a+nh),гдеf(x)=( x2 +1)cos2x.

4)Исп процедуру для выч степени числа, найти зн выр:

а) y= a₄*x⁴ + a₃*x³ + a₂*x² + a₁*x¹ + a₀коэфф a₄, a₃, a₂, a₁, a₀и x - ввсклавиатуры;

5)ф Power1(A, B) вещтипа, нахAB = exp(B¢ln(A)) ( A иB — веществ).
В сл A ≤0 ф возвр 0. С пом этой ф найти степени если даны P, A, B, C

Алгебра

1.задано кольцо вычетов (т.е.чисел от  до ).

Обратным к числу  по модулю  наз число , что: и его обозн через .для 0 обратного элемента нет никогда; для остальных же элем обратный м как существовать, так и нет. Утв, что обратный существует только для тех элементов , которые  взаимно просты с модулем .

А)Составить ф суммы разности и произв 2 эле кольца видаFunction имя (a,b,m:byte):byte;

Б*) функцвозвробратныйэлFunctionobr(a,byte;m:byte):byte;

предусмслучаи a=0 и отсутствия обратного (использовать процедуру nod(a,m)

2) функция- реш квадр уравн. Параметры коэфф и корни кв уравн., возв Значение,-: 2 – два разных корня, 1 – корни одинаковые, 0 – уравнение не имеет решения, -1. исходные данные не верные,

3)написатьфункцию swap(int* a, int* b, int* c), кот изменяет зн параметров по правилу abca.

Pascal	C++
Swap(var a,b,c:Integer)	swap(int* a, int* b, int* c), swap(int& a, int& b, int& c),

Сортировки

0)Сортировка пузырьком

1)Удалить из массива все мин элементы, остав отсортировать по возрастанию

2)ввод 2 массива. Получ результир отсортиров массив, сост из неповтор элем 2 зад массивов сохраняющим порядок их следов. ввести перем показывающую. длину нового массива.

Напр : Из A[10] = {2,5,2,6,8,5,1,9,4,3 } н получ массив B[6]={6,8,1,9,4,3)

3а)Какова мин воз сложность (число сравн в наихудш сл) алг отыск самого легкого из n камней? Док, что невозм док что данн камень — самый легкий среди n камн, сделав

3б) Док, что м найти самый легкий и самый тяжелый из 2n + 1 камней (одновр), сдел 3n взвеш.[Указ. Для нач разоб камни на пары (n пар, 1 камень ост непарн) и срав камни внутри пар.

Функциипосложнее

1)Напишфунf(int& m4, int& m3, int& m2, int& m1,int& m0, int N),

возвр все цифры 5зн нат числа N

2)функf(int& h, int& m, int& s, int sec), котприним кол сек, прошед с нач дня, и возвр 3 целых перем (часы, мин и сек)

3а)фf(int& minval, int& maxval, int* arr,int N), нах и возвр наим и наиб зн из набора целых чисел arr зад размера N.Б)фf(double* minval, double* maxval,double* arr, int N), кот нахо и возвр наими наиб зн из наб double чисел arr задразм N

4а)ф sorti(int* arr, int N) сортирует по возра массив int arr заданного размера N

4б)sortif(int* arr, int N, PIFII f), сортир по возр массив int arr зад разм N с пом ф сравн int compare(int m, int n).Тип PIFII (PointertoIntegerFunction с арг IntandInt)опр с помоперtypedef.

4в)фsortxt(char* txt[], int N, PIFPCPCf), сортир массив char* arr[] с пом фсравн int compare(char* t1, char* t2). Тип PIFPCPC (Pointer to Integer Function аргChar* and Char*) опрспомоп typedef.

Массивы

Массив вводится с клавиатуры либо генерируется с помощью ДСЧ

Pascal	C++
const n=10; var a: array[1..n] of integer;	const int n=10; int x[n]; srand(time(0)); // автоматичерандомизация for (int i=0;i { x[i]=rand() % 10; cout cout

Ввод и вывод массивов из файла

Чтение размерность изв		Чтение размерность неизв		запись
Var f:text; a:array of integer; AssignFile(f,'inp.txt'); Reset(f);Read(f,n) for i := 1 to n do read(f,a[i]); close	Var f:text; a:array of integer; AssignFile(f,'inp.txt'); Reset(f); while not eof(f) dobegin read(f,a[i]);inc(i); end;

Чтение размерность изв	Чтение размерность неизв	запись
ifstream f; f.open("dan.txt"); fn; for (i=1;i { fa[i]; cout f.close();	ifstream f("inp.txt"); while (!f.eof()) {fcur; cout f.close();	ofstream f;

После завершения работы с файлом надо его закрыть, f.close().

-----------------------------------------------------------------------------------------------

1)длякаждого разного э массива подсч его кратн 2)анайти кол локальн максим массива

б)Максим длина локальн максимума посл-сти.в)Кол возрас участков после-ти

г)Найти максим из его локальн мини д)максим из его эл, не явл ни локальн мин, ни локальн макс

2)Сгруппир положит элементы массива в его начале, а отриц- в конце с сохр их порядка.

3) Задана посл-ть, содерж n целых чисел. Н найти число, кот встреч в этой посл-ти наиб колич раз, а если таких чисел неск, то найти мин из них, и после этого перемесвсе такие числа в конец зад посл-ти. Порядок распол остальных чисел д остаться без изменений.

4)В целочисл массиве a[1] . . . a[n] хранится перестановка чисел 1 . . . n (каждое из чисел встреч по 1 разу).(а) Опр чётн перестан (б) Не исп других массивов, заменить перест на обратную (если до работы программы a[i] = j, то после должно быть a[j] = i).

[Указ. (а) Чётность перестан определ кол циклов. Чтобы отлич уже пройд циклы, у их элем м, напр, менять знак. (б) Обращение производим по циклам.]

5)Дан неубыв массив положит целых a[1]a[2] . . . a[n]. Найти наим целое полож число, не предст в виде суммы несэл этого массива (каждый эл массива м б испне б 1 раза). Число действий пор n.

Подск. Пусть изв, что числа, предст в виде суммы эл a[1], . . . , a[k], заполн отрезок от 1 до нек N. Если a[k+1] N+1, то N+1 и будет мин числом, не предст в виде суммы эл a[1] . . . a[n]. Если же a[k+1]N+1, то числа,предст в виде суммы эл a[1] . . . a[k+1], запол отрезок от 1 до N+a[k+1]

6)Дан массив A разм N. Выв его эл в след порядке: а)

Б)

7)Инф о кол осадков, вып в теч мес, и о темпер воздуха задана в виде 2 масс. Опр, какое кол осадков вып в виде дождя, какое в виде снега. (Счит, что идет дождь, если темпер возд0 град.)

Т) ТапочкиВ прихожей в ряд стоит N тапок, кот быв разных разм, а также левыми и правыми. Гость выб 2 тапка, удовл след усл:а)Выбр тапочки д б одного размера б)Из выбр тапок левый тап до стоять левее правого в)Если м выбр неск пар тапок, удовл 1м 2 усл, то выб 2 тап с наим расст между нимиВ 1 строке вх данных запи число тапок N. Во 2й строке запис разм тапок в пор слева направо, при этом левые тапки усл обозн отриц числами (т е −s  обозн левый тапок, а s обозн прав тапок разм s).Выв 1 число: мин расст между 2 тапками одного размера таких, что левый тапок стоит левее правого. Если таких пар тапок нет, то выводится 0.

В прим подходят тапки 40 разм (расст между ними = 5) и 42 разм (расст меж ними = 2).

http://www.olympiads.ru/zaoch/2009/problems/b.shtml

1) Про каждый из 31 дня мес изв сколько сотр пришло на раб также изв, что каждый из служ берет ровно по 4 вых в мес. Вывед единств число - общее кол работ офиса. Гарант отв не превыш 100.Пример

b.in	b.out
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 0 0 0 0	10

J: Абсолютный минимум температуры

Метеорол ведут многолетн наблюд за тем, в каком году была мин темпер в данный день года.

В теч k лет метеорол вели наблюд за n днями года. Для кажд из этих n дней укаж мин температуру, кот была в этот день за k лет наблюд.

1 строка вх данных содерж 2 числа k и n. Далее идет k строк, i-я стр содер n чисел: знтемпер для n дней наблюд i-го года.Прогр д вывести n чисел: мин знач темпер для кажд из дней наблюд.

K: Наименьш кол осадковДаны рез-ты метеор набл: кол осадков в кажд из 31 дня марта.н опр, какая из недель марта была наим дождл. Нед — это 7 дн с понед до воскр, т е в марте м б три или четыре полные нед.Прогр получ на вход 31 целое неотриц число через пробел: кол осадков для кажд из дней. В след строке запис число от 1 до 7: день нед, на кот прих 1 марта (1 озн понед, 2  вторн и т д).Прогр д опр неделю с наим сумм ч=лом осадков и выв сумм чло остатк на этой неделе.

Прим . 1 марта — это четверг, поэтому 1е 4 дня ме пропуск. Ост слелующей недели: 4 4 6 2 4 8 3 (сумма 31), 1 4 5 8 1 6 3 (сумма 28), 8 4 6 2 9 4 0 (сумма 33). После 6 дней месяца полной неделей не являются, поэтому не учитываются.

L: Дома и магазины

На Новом пр постр подряд N зданий. Каждое зд м б либо жилым домом, либо магазином, либо офисным зд. Для разраб плана развития общ трансп мэр города попросил выясн, какое же наиб расст прих преодол жителям Н пр, чтобы дойти от своего дома до ближ магазина.

1я строка вх дан содерж кол домов на Новом пр N. 2я строка содер N чисел, разд пробел. Каждое число зад тип здания на Н пр: число 1 обозн жилой дом, число 2 обозн маг, число 0 обозн офисное здание. Гарант, что на Новом пр есть хотя бы 1 жилой дом и хотя бы один магазин.

Вывести 1 целое: наиб расст от дома до ближ к нему магаз. Расст между 2 сосед домами счит = 1 ( если 2 дома стоят рядом, если между 2 домами есть еще 1 дом, то расст между ними = 2 и т.д.

1)Располож торг центра. Есть n домов на одной прямой ул, зад массивом к-т и колич жителей в каждом доме Найти к-ту распол ТЦ из усл мин суммы расст лля каждого жителя до ТЦ

2) Манхэттен. На пл-ти задано n точек. Расст между т (x₁, y₁) и (x₂, y₂) бвычисл как сумму модулей разностей их к-т: r = |x₁ - x₂| + |y₁ - y₂|. Найти т, сумма расст от кот до зад n точек мин.

задачу минимиз зад суммы м свести к 2 подзад: для x и для y. Рассм 1-мерн задачу для x. По зад x1, x2, ..., xn найти x, такое что s(x) = |x - x1| + |x - x2| + ... + |x - xn| мин. Пусть x - т, в кот s(x) достиг мин. Пусть слева от нее k1 точек, а справа k2 т. Если k1 = k2. Анал k1

3) Расстояние Хэмминга. Из п A в п B было послано одно из n сообщ m1, m2, ..., mn. В п B б принято сообщ s.опр наиб вероят исх сообщ. Оно будет одним из тех, расст Хэмминга меж кот и строкой s мин.Расст Хэмминга двух строк a и b одинак длины наз кол поз, в кот эти строки разл (кол эл в множестве {i | 1 ≤ i ≤ |a|, ai ≠ bi }).

1 строка вх файла INPUT.TXT содер s — принятое сообщ. 2 строка содерж целое n — кол сообщ, кот м б отправл. След n строк содер mi — эти сообщ. Длины всех сообщ(|s| = |m1| = |m2| = ... = |mn|). Сообщ непустые, состоят только из 0 и 1.

В 1 строку вых файла OUTPUT.TXT выведите k — кол сообщ, на кот достиг мин расс Хэмминга. Во 2 строку выв в порядке возрас k чисел — номера этих сообщ.

INPUT.TXT	OUTPUT.TXT
010101 3 110011 011001 000111	2 2 3

Случ блуждание

1)Паук нах на пл-ти в точке с к-тамиx=50 и y=50. Каждую сек он делает шаг влево, вправо,вниз или вверх с равной вер. Смоделир движ паука с по гсч. К=ты x(t) и y(t) сохре в одномер массивах. Напеч траект паука в файл п=ла в виде табл, к содер в клетке с к-тами x и y символ +, еслипаук там побывал, и символ -, если он там не побывал

2)Компл сост из M одинак объектов, кажд изкот в нач нах в испр сост. Противпроизв одна за др атаки, в ходе кажд из кот онзапуск K боегол, причем цели – об компл– выб случ обр. Противн не знает,какие об уже пораж и м обстр поражобъект еще раз. Ск атак переживет компл, если дляобесп жизнедеят дост иметь N испробъект причем M=16, K=3, N=4. Рез-ты предст в нагл форме

3)Напис игру «Угадай число»: прогр задум число от 1 до 1000, а польз угады. После каждой попытки прогр м выдав 3 сообщ (введ число задум)OK «Вы угадали!»Указ: в б-ке stdlib.h есть ф rand, кот. Для сброса гсч исп ф srand. На вход м подать выход функции time из б=ки time.h Получ случ числа от 1 до 1000. Фу rand() возвр сл число в диап от 0 до RAND_MAX, поэтому необх арифм преобр.

О4)Разбиение посл-тиПосл-ть нат чисел от 1 до N н разбить на 2 части от1 до K и от K+1 до N так, чтобы абс зна разности суммы чисел в 1й и 2й части посл=ти было как м меньше. Те найти такое K, что зн выр=мин. Напр, дляпосл=ти чисел от 1 до 4 мин разб б |(1+2+3)-(4)|=2,ост 2 возмразбиения дают большее знразности:|(1)-(2+3+4)|=8, |(1+2)-(3+4)|=4.
Напи прог, кот для задN находит мин разб. 1я строка ввода - одно целое N(2 ≤ N ≤ 109).
Выв одно целое K. Если сущ неск вар разб,то выв меньшее из возмK.

Индуктивные функции (по А.Г. Кушниренко) и их применение

Пусть M — некот мн-во. Функция f, аргументом кот явл посл-ти элем множества M, а знач — элем некот множества N, назыв индуктивной, если её знач на посл-ти x[1] . . . x[n] восстанавливаются по её знач на посл-ти x[1] . . . x[n-1] и по x[n], т е если существует функция F : N × M → N, для кот

Здесь f0 — зн ф на пустой посл-ти ( длины 0). Если ф f опр только на непустых Посл-тях, то 1я строка заменяется на k:=1; f:=f();Прим

1) суммой элементов посл-ти f(y, a) = y+a.

2) максимальным эл посл-ти f(y, a) = max(y,a).

Если функция f не явл индуктивной, полезно искать её индуктивное расширение — такую индуктив функцию g, знач кот опр знач f (это значит, что сущ такая функция t, что при всех

до, что среди всехиндукт расшир сущ мин расшир F (т е для любого индукт расши g зн F опред зн g).

0)данафункция  количество максим элементов посл-ти целых чисел

А)док что она не явля индуктивной б) построить ее индуктивное расширение

1)Указать индуктивные расширения для следующих функций:

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

(а) среднее арифметическое последовательности вещественных чисел;

(б) число элементов посл=ти целых чисел, равных ее максим элементу;

(в) 2й по вел эл-т посл-ти целых чисел (тот, кот будет 2м, если перестав члены в неубыв порядке)

(г) максимальное число идущих подряд одинаковых элементов;

(д) максим длина монотон (неубыв или невозраст) уч-ка из идущ подряд эл в посл-ти целых чисел

(е) число групп из единиц, разд нулями (в посл-ти 0 и 1).

2)Даны две посл-ти x[1] . . . x[n] и y[1] . . . y[k] целых чисел. Найти максим длину посл-ти, явл под-посл-тью обеих посл-тей. Кол операций порядка n · k.

Реш Обоз через f(p, q) максим длину общей подпосл-ти посл-тей x[1] . . . x[p] и y[1] . . . y[q]. Тогда

x[p] 6 = y[q] ⇒f(p, q) = max (f(p, q−1), f(p−1, q));

x[p] = y[q] ⇒f(p, q) = max (f(p, q−1), f(p−1, q), f(p−1, q−1)+ 1);

(т к f(p − 1, q − 1) + 1f(p, q − 1), f(p − 1, q), во 2 сл мах 3 чисел м заменить на 3е из них.) Поэтому м

заполн табл зн функ f, имеющ размер n · k. М обой и памятью порядка k (или n), если индуктивно (по p) выч hf(p,0), . . . , f(p,k)i (как функция от p этот набор индуктивен).

3)  для функции  колич максимальных элем посл=ти целых чисел

Написать прогр вводящ посл-ть целых чисел, и печат кол ее макс элементов.

4)Дана посл-ть целых x[1], . . . , x[n]. Найти макс длину её возр подпосл-ти (чло действ пор n log n).

Реш. Иск функция не индуктивна, но имеет след индукт расшир: в него вх кр максим длины возраст подпосл-ти (обозн ее k) также и числа u[1], . . . , u[k],

где u[i] — мин из последних членов возраст подпосл-тей длины i. Оч, u[1] . . . u[k]. При доб нового

члена в x зн u и k корректир.n1 := 1; k := 1; u[1] := x[1];

{инвар: k и u соотв данному выше опис}	испидеюдвоичнпоиска; винваруслполаг,цель: u[i] x[n1]u[i+1].
while n1 n do begin | n1 := n1 + 1; | ... | {i - наиб из тех чисел отр1..k, для кот u[i] | if i = k then begin | | k := k + 1; | | u[k+1] := x[n1]; | end else begin {i | | u[i+1] := x[n1]; | end; end;	i:=0; j:=k+1; {u[i] i} while (j - i) 1 do begin | s := i + (j-i) div 2; {i | if x[n1] | | j := s; | end else begin {u[s] | | i := s; | end; end; {u[i]

Замеч. Б простое (но не мин) индуктивное расшир получ, если для каждого i хранить максим длину

возраст подпосл-ти, оканч на x[i]. Это расшир приводит к алг с числом дейст порядка

Порождение комбинаторных объектов

1)Перечислить все k|-элементные подмножества множества 1..n| (лестницы от (0,0) до (k,n-k)

Реш Б предст каждое подмн-во посл-тью x[1]..x[n] 0 и 1 длины n, в кот ровно k ед-ц.

1я посл-ть: 0..01..1 (n-k нулей, k ед-ц) последняя посл-ть: 1..10..0 (k единиц, n-k нулей)

алг перехода к след за х[1]..x[n] посл-ти (предп, что она есть): решение lestn.pas, lestn.cpp

Битовые операции

В Паскале обычн логич опе и побитовые обозн одинаково. 1е прим, если операнды имеют булевый тип (они получ в рез-те простых логич оп, Оп and, or, xor и not примен к целым. В этом сл, они дел ту логич оп, за кот отвеч, но над каждым битом двоич предст числа.Напр, 10 and 12 = 1010 and 1100 = 1000 = 8. Почему not 5 = -6, -5 получ из числа 5, если инвертир и приб 1 А если просто инверт not), то получ на 1 меньше. Т е not 5 = -5-1 = -6 not x = -x – 1.

0) Вып логич побит оп "И", "ИЛИ" и др. над числ5 и 6. Вып над числом 5 побит сдвиг вправо и влево на два знака. Объясн полученный результат.

побитовое "ИЛИ": 101® 110 =100 побит искл "И": 101+110 =_011 - это число 3.

если n and 1 возвр 0, значит число n четное, иначе – неч. Пров, явл ли число степ двойки, м вычис n and (n - 1). Если это выр= 0, то n явл степенью двойки

1)Возвести число в степень N за не более чем умножений

2)найти поз самой старшей единицы в битовом представлении данного целого числа.

3)Написать функц, записыв 0 или 1 в указ бит данн целого числа и ост ост биты без изменений.

4) с помощью побитовых операций реализовать вызов функции swap(n) языка pascal

var a,b:word;  ... b:=a; a:=a shr 8;  b:=b shl 8;  a:=a or b

5) Быстрое умнож Даны числа a и b. Не испоп  *, /, % вычислить их произведение.

Кодирование, шифрование

1)  Шифрование перемешиванием

Дано число, перестав его сосед биты (т е помен местами биты 0 и 1, 2 и 3, 4 и 5 и т.д.). Разреш исп битовые операц. Запрещ использ арифм оп ветвления, циклы. Общее число бит в числе не превосх 32. Тест n=78 shifr=141

2)Кодирование повторений –это замена цепочки одинах цифр симв самим симв и числом повтор (возм включ разделит). Напр, для посл-ти: 55556666888888 получ посл-ть: 5(4)6(4)8(6), метод м б исп для эфф кодиров растровых форматов изображ. Реализ ф кодиров повторений. Исх строку символов сгенерирс Д.С.Ч.

3) Кодирование циклическим сдвигом буквы Закодир буква получ из исх буквы путем циклич сдвига в алфавите на зад число позиций

прим сдвиг =-1, исх строка АБРАКАДАБРА кодир ЯАПЯЙЯГЯАПЯ

реализовать функции кодирования и декодирования

4)Изв, что сейф откр при правильном вводе кода из 3 цифр 0…9. Зада код и затем откр сейф, испметод перебора с пом неск операт цикла for реш см.файл seif_isp.cpp

5) Распаковка строчки рассм только строчки, сост из загл лат. Напр AAAABCCCCCDDDD. Длина этой строки14. Поск строка сост только из лат повт симв м бы удал и замен числами, опр кол повт. Т е данная строка м б предст как 4AB5C4D. Длина строки 7.-упаковка строки. Напиш прогр, кот берет упак строчку и восст по ней исх строку. вх дан 1 упаков строка. м встреч только констр вида nA либо констр вида A, т е символ без числа длина строки ≤ 80 оканч симв перевода

Н выв восст строку. строка д б разбита на стр длиной 40 симв (за искл послед, кот м б 40 симв).

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

3A4B7D AAABBBBDDDDDDD

22D7AC18FGD DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF

FFFFFFFGD