x+1=-13; y+1=-77;
y+1=1; x+1=1001;
y+1=-1; x+1=-1001;
y+1=7; x+1=143;
y+1=-7; x+1=-143;
y+1=11; x+1=91;
y+1=-11; x+1=-91;
y+1=13; x+1=77;
y+1=-13; x+1=-77;
Из уравнения (*) видно, что значения целочисленных переменных x и y меняются в диапазоне от -1002 до 1000. При описании переменных x и y используем тип LongInt, так как произведение x*y не всегда будет попадать в диапазон чисел, соответствующий типу Integer. Переборное решение выглядит так:
Program obl2;
Uses Crt;
Var x, y:Longint;
Begin
ClrScr;
For x:=-1002 To 1000 Do
For y:=-1002 To 1000 Do
If x+y+x*y=1000
Then Writeln('x = ',x,'; y = ',y);
Readln;
End.
Задача 3
Метод Монте-Карло назван в честь одноимённого города в княжестве Монако, знаменитого своими игорными домами. Метод основан на применении случайных чисел, а одним из простейших приборов, который генерирует такие числа, является рулетка. Как же вычислить число π? Возьмём кусок картона, нарисуем квадрат и впишем в него четверть круга. Если такой чертёж некоторое время подержать под дождём, то на его поверхности останутся следы капель. Подсчитаем число капель внутри четверти круга Nкр и внутри квадрата Nкв. Так как попадание капель в различные части чертежа равновероятно, то отношение числа капель, попавших в четверть круга и квадрат, должно быть отношению площадей соответствующих фигур. Тогда π ≈ 4Nкр/Nкв. Возьмём квадрат со стороной, равной 1. Положение капли можно описать двумя случайными числами, характеризующими её координаты.
В Паскале имеется функция Random, которая, если не указан аргумент, выдаёт случайное число из интервала [0;1). Если аргумент задан, то функция работает по-другому. Например, Random(200) выдаёт случайное целое число из диапазона [0;199]. Перед первым обращением к этой функции необходимо с помощью вызова процедуры Randomize инициализировать программный генератор случайных чисел. Сгенерированная точка (x;y) лежит внутри четверти круга, если выполняется неравенство x2+y2≤1 (при его не выполнении точка лежит вне круга). Естественно, что все сгенерированные точки лежат внутри квадрата. Интуитивно ясно, что чем больше берётся точек, тем будет более точное значение.
Ниже приведена возможная программа.
Program obl31;
Uses Crt;
Var k, n,m:Longint;
x, y,p:Real;
Begin
ClrScr;
Randomize;
Write('n= ');
Readln(n);
m:=0;
For k:=1 To n Do
Begin
x:=Random;
y:=Random;
If x*x+y*y<=1 Then m:=m+1;
End;
p:=4*m/n;
Writeln('Число Пи равно: ',p:5:3);
Readln;
End.
В качестве числа n надо ввести достаточно большое число, чтобы получить правильное значение с точностью до 0,001. Следующий вариант этой же программы последовательно считает значения для n и 2n и сравнивает полученные значения. Первоначальное значение n надо взять достаточно большим, иначе можем получить неточное значение числа π.
Program obl32;
Uses Crt;
Var k, n,m:Longint;
x, y,p1,p2:Real;
Begin
ClrScr;
Randomize;
n:=1000000;
m:=0;
p2:=0;
For k:=1 To n Do
Begin
x:=Random;
y:=Random;
If x*x+y*y<=1 Then m:=m+1;
End;
p1:=4*m/n;
While abs(p2-p1)>0.0005 Do
Begin
n:=2*n;
m:=0;
p2:=p1;
For k:=1 To n Do
Begin
x:=Random;
y:=Random;
If x*x+y*y<=1 Then m:=m+1;
End;
p1:=4*m/n;
End;
Writeln('Число Пи равно: ',p1:5:3);
Readln;
End.
Задача 4
По условию задачи муравей всегда завершает путь на краю листа, т. е. находится вне замкнутой области. Пусть муравей движется с исходной точки до края листа в любом направлении. Если пересечений линий не было, либо количество пересечений было равно четному числу, то муравей находился вне замкнутой области (в область надо зайти и выйти, а область не самопересекающаяся). Если число пересечений равно нечётному числу, то муравей находился внутри области. Остаётся только показать технику работы с файлами. Для удобства работы с координатами введём запись.
Program obl4;
Uses Crt;
Const maxn=100;
Type dat=Array[1..maxn,1..maxn] Of Byte;
coord=Record
x, y :Real; {координаты точки}
End;
Var a:dat;
i, j,ax, ay, bx, by:byte;
f :text;
p1,p2,q1,q2 :coord;
count, coll :integer;
Function max(x, y:real):Real;
{находит максимальное из двух чисел}
Begin
If x>=y Then max:=x Else max:=y;
End;
Function w(p, q,z:coor):integer;
{выдает - 1, если точка z ниже прямой pq;
0 - на прямой; 1 - выше прямой}
Var a, b,c, r:Real; {коэффициенты уравнения ax+by+c=0}
Begin
a:=q. y-p. y;
b:=p. x-q. x;
c:=p. y*(q. x-p. x)-p. x*(q. y-p. y);
r:=a*z. x+b*z. y+c;
If r>0 Then w:=1
Else If r<0 Then w:=-1
Else w:=0;
End;
Function per(a1,b1,a2,b2:coord):Byte;
{1 – есть пересечение, 0 - нет}
Begin
If (w(a1,b1,a2)*w(a1,b1,b2)=-1) and (w(a2,b2,a1)*w(a2,b2,b1)=-1)
Then per:=1
Else per:=0;
End;
Begin
{начало программы}
ClrScr;
count:=0;
Assign(f,'mur. dat');
Reset(f);
Readln(f, coll);
Readln(f, q1.x, q1.y);
q1.x:=q1.x+0.5;
q1.y:=q1.y+0.5;
q2.x:=0.5;
q2.y:=0.0;
For i:=1 To coll Do
Begin
Readln(f, ax, ay, bx, by);
If ax=bx Then Begin {горизонтальная линия}
If Abs(ay-by)=1 Then Begin
p1.y:=max(ay, by);
p2.y:=p1.y;
p1.x:=ax;
p2.x:=ax+1;
End;
End
Else If ay=by Then Begin {вертикальная линия}
If abs(ax-bx)=1 Then
Begin
p1.x:=max(ax, bx);
p2.x:=p1.x;
p1.y:=ay;
p2.y:=ay+1;
End;
End; {иначе неверная строка}
count:=count+per(p1,p2,q1,q2);
End;
Close(f);
{проверка на чётность}
If Odd(count) Then Writeln('Муравей был внутри!')
Еlse Writeln('Муравей был снаружи!')
End.
Второй день
Задача 1
Задача сформулирована не совсем корректно: из записи условия не видно увеличивается числитель на 2 или же удваивается. Считаем, что числитель, как и знаменатель, увеличивается на 2. Тогда идея очень проста: в цикле прибавляем 2 поочередно к числителю (переменная x) или к знаменателю (переменная y). Произведение накапливаем в переменной Res.
Program obl5;
Uses Crt;
Var res:real;
k, n,x, y, m: integer;
Begin
ClrScr;
Write('n=');
Readln(n);
res:=1;
m:=0;
x:=2;
y:=1;
For k:=1 To n Do
Begin
res:=res*x/y;
If m=0 Then y:=y+2
Else x:=x+2;
m:=1-m;
End;
Writeln('res=',res);
Readln;
End.
Задача 2
Если роботов много, то им выгоднее собираться по 5, потому что 3 пятерки соберут 27 роботов, а 5 троек только 25. Рассмотрим все случаи, когда количество роботов не делится на 5.
Если количество роботов при делении на 5 дает остаток 1, то все роботы, кроме 6, собираются пятерками, а 6 оставшихся образуют 2 тройки (2 тройки соберут 10 роботов, а одна пятерка только 9).
Если количество роботов при делении на 5 дает остаток 2, то все роботы, кроме 12, собираются пятерками, а 12 оставшихся образуют 4 тройки (4 тройки соберут 20 роботов, а 2 пятерки только 18).
Если количество роботов при делении на 5 дает остаток 3, то роботы собираются пятерками, а три оставшихся робота составляют одну тройку.
Если количество роботов при делении на 5 дает остаток 4, то все роботы, кроме 9, собираются пятерками, а 9 оставшихся образуют 3 тройки (3 тройки соберут 15 роботов, а одна пятерка лишь 9).
Остаётся лишь грамотно описать всё вышесказанное.
Program obl6;
Uses Crt;
Var i, k,n, s,s0,s1,s2,s3,x:integer;
Begin
ClrScr;
Write('Начальное количество роботов k= ');
Readln(k);
Write('Количество лет n= ');
Readln(n);
s0:=k; {количество роботов, которым 0 лет}
s1:=0; {количество роботов, которым 1 год}
s2:=0; {количество роботов, которым 2 года}
s3:=0; {количество роботов, которым 3 года}
{роботы живут три года}
For i:=0 To n Do {n – число лет}
Begin
s:=s0+s1+s2+s3; {число всех роботов}
Case s mod 5 Of {рассматриваем случаи}
0: x:=(s div 5)*9;
1: If s=1 Then x:=0
Else x:=(((s-5) div 5)*9)+10;
2: If s=2 Then x:=0
Else If s=7 Then x:=10
Else x:=(((s-10) div 5)*9)+20;
3 : x:=((s div 5)*9)+5;
4 : If s=4 Then x:=5
Else x:=(((s-5) div 5)*9)+15;
End;
{определение нового количества роботов}
s3:=s2; {роботы стали старше на год}
s2:=s1;
s1:=s0;
s0:=x; {новые собранные роботы}
End;
Writeln('Через ',n, ' лет будет ',s,' роботов');
Readln;
End.
Задача 3
Выбираем показания 2-х сработавших детекторов и проверяем, лежат ли другие сработавшие детекторы на одной прямой с ними. Если да, то имеем след прямолинейно двигавшейся частицы. Пусть координаты первого детектора (х1, y1), а второго – (x2,y2). Найдем dx=x2-x1 и dy=y2-y1. Разделим dx и dy на их наибольший общий делитель, получаем несократимую дробь. Для каждой точки с координатами (x, y) находим расстояние (x-x1) и (y-y1). Точка находится на прямой, проходящей через первый и второй детекторы, если (x-x1) и (y-y1) пропорциональны dx и dy. Для хранения координат сработавших детекторов используем массив записей.
Program obl7;
Uses Crt;
Сonst max = 100; {число сработавших детекторов}
Type coord = Record {координты сработавшего детектора}
x, y:Byte
End;
Var b:Array [1..max] Of coord;
n, i,dx, dy, z:Integer;
f:Boolean;
Function nod(x, y:Byte):Byte; {нахождение НОД x и y}
Var k:Byte;
Begin
If x<y Then Begin
k:=x;
x:=y;
y:=k;
End;
If (x=0) Or (y=0) Then nod:=1
Else Begin
While x mod y <> 0 Do
Begin
k:=x mod y;
x:=y;
y:=k;
End;
nod:=y;
End;
End;
Begin
ClrScr;
Write('Число точек: ');
Readln(n);
For i:=1 To n Do
Begin
Write('Координаты точки ',i,': ');
Readln(b[i].x, b[i].y)
End;
dx:=b[1].x-b[2].x;
dy:=b[1].y-b[2].y;
z:=nod(abs(dx),abs(dy));
dx:=dx div z;
dy:=dy div z;
i:=3;
f:=True;
While f And (i<=n) Do
Begin
f:=(b[i].x-b[1].x)*dy = (b[i].y-b[1].y)*dx;
i:=i+1;
End;
If f Then Writeln('Траектория частица прямолинейна')
Else Writeln('Траектория частицы не прямолинейна');
Readln;
End.
Задачи для самостоятельного решения
1. Найти количество способов, которыми можно добраться до 15 ступеньки, если можно подниматься на следующую ступеньку, через одну и через две ступеньки. Подсказка: составьте рекуррентное соотношение.
2. Дана обыкновенная дробь a/b. Сократите эту дробь, если это возможно. Подсказка: используйте алгоритм Евклида.
3. Светофор работает так: зелёный и красный свет горят по 3 минуты, а в промежутках между ними 2 минуты горит жёлтый свет. Определить, какой свет будет гореть через t минут, если в начальный момент загорелся зелёный свет.
4. В одном из замкнутых городков с населением S жителей началась эпидемия «Чихундры». Болезнь протекает следующим образом: если на тебя сегодня чихнули, то на следующий день ты чихаешь на двух случайных прохожих, после чего моментально излечиваешься и приобретаешь иммунитет. Составить программу, определяющую через сколько дней закончится эпидемия и каково при этом будет число жителей не заболевших и переболевших «Чихундрой», если считать, что в первый день эпидемии болел только один житель.
5. Дана строка английского текста. Текст содержит строчные и заглавные английские буквы, знаки пунктуации и пробелы. Найти все различные символы в тексте и определить, сколько раз встречается каждый символ. Строчные и заглавные буквы не различать.
6. Определить количество пятниц в XXI веке, приходящихся на 13 число. Определить также количество таких пятниц в текущем году.
7. В древней Руси при составлении секретных бумаг использовали тарабарскую грамоту: все согласные русские буквы записывались в два ряда: одна половина букв сверху, другая – снизу, причём в обратном порядке (одна буква под другой).
Б В Г Д Ж З К Л М Н
Щ Ш Ч Ц Х Ф Т С Р П
При шифровке согласные взаимно заменяются (Б – Щ, Ф – З и т. д), а гласные и буквы Й, Ъ, Ь остаются без изменений. Составьте программу шифровки вводимой с клавиатуры строки.
8. Длина отрезка задана в дюймах (1 дюйм = 2,54 см). Перевести значение длины в метрическую систему, выразив её в метрах, сантиметрах и миллиметрах.
9. Пройдёт ли кирпич со сторонами a, b и c сквозь прямоугольное отверстие со сторонами p и q?
10. Треугольник задаётся сторонами a, b и c. Найти минимальный радиус круга, из которого можно вырезать этот треугольник.
11. Имеется n бактерий красного цвета. Через один такт красная бактерия меняется на зелёную, а затем снова через такт делится на две: красную и зелёную. Сколько будет всех бактерий через k тактов?
12. Последовательность строится так:
шаг 0: пустая последовательность;
шаг 1: a;
шаг 2: baa;
шаг3: cbaabaa и т. д.
Какой символ стоит на n-м месте?
13. Все натуральные двузначные числа выписаны подряд: 1011…9899. Какая цифра находится в заданной позиции? Задачу решить двумя способами: без использования строк и с использованием строк.
14. Даны 4 точки, заданные своими координатами. Являются ли они вершинами трапеции?
15. Дано повествовательное предложение (слова разделены одним пробелом, спереди и сзади пробелов нет). Расположить в нём слова в порядке возрастания числа букв.
Литература
1. , , 100 задач по программированию. – М.:Просвещение, 1993.-255 с.
2. . Решение сложных и олимпиадных задач по программированию: Учебное пособие.– СПб.: Питер, 2006, -366 с.
3. Джон Бентли. Жемчужины программирования.–СПб.:Питер, 2002, -272 с.
4. Фёдор Меньшиков. Олимпиадные задачи по программированию.–СПб.: Питер, 2006, -315 с.
5. Окулов программирования. – М.: ЮНИМЕДИАСТАЙЛ, 2002. –424 с.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
