ФГБОУ ВО «БГПУ» им. М. Акмуллы
Центр развития одаренности школьников
ОТВЕТЫ И ПРИМЕРЫ РЕШЕНИЙ
к заданиям 2 тура дистанционной олимпиады по программированию
для 10-11 классов
Общие замечания по проверке ответов:
Работу программ с ответами по заданиям можно посмотреть на странице:
http://elismod. ru/olymp17/t2
В демонстрационных примерах использовались языки JavaScript и PHP. Синтаксис этих языков программирования близок к С++, Python, Pascal. Поэтому эти алгоритмические решения по заданиям 2 тура участникам олимпиады можно использовать для сравнения с собственными решениями.
Приведенные примеры не являются единственно возможными. Для каждого задания существую различные решения на различных языках программирования с использованием возможностей языков программирования и собственных имен переменных.
РЕШЕНИЯ С ОТВЕТАМИ ПО ЗАДАНИЯМ 2 ТУРА
Приводятся только наиболее важные фрагменты решений, которые могут отличаться по решениям и возможностям других языков программирования.
Задание 1
Разработайте программу, которая шифрует и дешифрует текст, используя шифр Цезаря для заданного сдвига номера каждой буквы алфавита на фиксированное число позиций от 1 до 20.
Примеры входных и выходных данных (ответов):
Входные данные
Шифрование - 1, дешифрование – 2: 1
Сдвиг (1-20): 1
Текст: Дорогу осилит идущий.
Выходные данные
Шифрование: Епспдф птймйу йефъйк.
Входные данные
Шифрование - 1, дешифрование – 2: 2
Сдвиг (1-20): 1
Текст: Епспдф птймйу йефъйк.
Выходные данные
Дешифрование: Дорогу осилит идущий.
Решение:
В этом варианте программы однобайтовый шифр Цезаря шифрует только буквы кирилицы:
$Dlin=strlen($sx2);
for ($i=0;$i<$Dlin;$i++)
{$Ind=ord($sx2[$i]);
if (($Ind>=192) and ($Ind<=255) )
{$Cez=ord($sx2[$i])+$Ln; // Шифрование
if ($Cez>255)
{$Cez=$Cez-64;}
$Sim=chr($Cez);
$Sbor=$Sbor.$Sim;}
else
{$Sbor=$Sbor.$sx2[$i];// Другие символы
}}
В дешифровании используется обратное действие:
$Cez=ord($sx2[$i])-$Ln; // Дешифрование
Задание 2
Разработайте программу, производящую расчет количества любых слов и различных букв в предлагаемой фразе, а также количество различных букв в словах.
Пример входных и выходных данных:
Входные данные
Строка текста: Viam supervadet vadens.
Выходные данные
Кол-во слов - 3. Всего кол-во различных букв - 12.
Viam - 4 различные буквы.
supervadet - 9 различных букв.
vadens - 6 различных букв.
Решение:
В цикле проверяются символы и выделяются отдельные слова:
if ((($re==" ") or ($re==".") or ($re==",")) and (strlen(trim($Sb))>0))
{
print(" Слово: $Sb. ");
}
В каждом слове подсчитываются буквы и счетчик слов увеличивается на единицу:
$Ld=strlen($Sb)+1;
$Co=0;
for ($iv=0;$iv<=$Ld;$iv++)
{
$Nas=0;
if(strlen(trim($Sb))>0)
{
$rev = substr($Sb,$iv,1);
if($rev!==" ")
{$Nas=substr_count($Sb,$rev);
if ($Nas>=1)
{$Co++; // Счетчик букв
$Sb=str_replace($rev," ",$Sb);}}}
}
print(" Кол-во различных букв: $Co.<br>");
$Covs++; // Счетчик слов
$Sb="";
print(" Кол-во слов: $Covs. <br>");
Такой же алгоритм используется для подсчета разных букв во всех словах.
Задание 3
Разработайте программу вычисления числа Пи методом Монте-Карло с помощью отношения числа удачных выстрелов к общему числу выстрелов по круглой мишени. Используйте функцию генератора случайных чисел для имитации координат попаданий и не менее 10000000 испытаний.
Пример входных и выходных данных:
Входные данные
Input number of tests: 10000000
Выходные данные
Pi = 3.14113
Решение:
$m=0;
$n=0;
$pi=0; //$i – задает количество испытаний
for ($i=1;$i<= 10000000;$i++)
{ $x=rand(0,100000)/100000;
$y=rand(0,100000)/100000;
// echo " Xi = $x Yi = $y <br> ";
$z=pow($x,2)+pow($y,2); // Попадание в круг
if($z<=1)
{ $m++; }
$n++; // Всего испытаний
}
$pi=$m*4/$n;
echo " m(число попаданий в круг) = $m     n(число попаданий в квадрат) = $n         Число Pi = $pi<br> ";
Задание 4
Разработайте программу, которая, используя рекурсивную функцию, вычисляет факториал числа и определяет максимально возможное значение факториала для используемого алгоритма и системы программирования.
Примеры входных и выходных данных (ответов):
Входные данные
5
Выходные данные
5!=120
Максимально возможные значения:
12! = 479 001 600
или
15! = 1 307 674 368 000
или
21! = 51 090 942 171 709 440 000
Решение:
Функция
function fact($x)
{if ($x <= 1)
{return 1;}
else
{$x=$x*fact($x-1);}
return $x;
}
Программа
$a=$sx1*1;
$Fa=fact($a);
print(" <br> Входные данные - Число: $a.");
print(" <br> Выходные данные - Факториал числа: $Fa.");
$Fo=$Fa."_";
if(strpos($Fo,"+"))
{echo "<br> Превышено максимально возможное значение факториала для числа $a.";}
Задание 5
Разработайте программу, которая после выбора функций выводит графики трех функций (y=kx, y=k*sin(x), y=k*x^2 ) в одной системе координат.
Примеры входных и выходных данных (ответов):
Входные данные
Какие функции выбираем (1, 2, 3)? 2, 3
Введите k2, x2, k3, x3
Выходные данные
Изображение графиков функций y=k*sin(x) и y=k*x^2.
Допускается выбор функций по значениям k не равным 0.
Решение:
header ("Content-type: image/png");
$img = imagecreatetruecolor(320, 240);
$ink = imagecolorallocate($img, 255, 255, 255);
$k1=$_GET['k1'];
$x1=$_GET['x1'];
$k2=$_GET['k2'];
$x2=$_GET['x2'];
$k3=$_GET['k3'];
$x3=$_GET['x3'];
for ($i=0;$i<320;$i++)
{imagesetpixel($img,$i,142,$ink); // Ось X
imagesetpixel($img,1,$i,$ink); // Ось Y}
// шкала X
$x=-40;
for ($i=0;$i<320;$i++)
{$x=$x+38;
for ($j=140;$j<145;$j++)
{ imagesetpixel($img,$x,$j,$ink); }
}
// шкала Y
$y=-50;
for ($i=0;$i<320;$i++)
{$y=$y+48;
for ($j=0;$j<5;$j++)
{ imagesetpixel($img,$j,$y,$ink); }
}
if ($k1<>0)
{ //1 График y=kx
$x=$x1*34; $smy=-143;
for ($i=$x;$i<320;$i++)
{$x=$x+1;
$smx=$x*$k1*1.5;
$y=-($smy+$smx);
imagesetpixel($img,$x,$y,$ink); // График y=kx
}}
if ($k2<>0)
{// 2 График y=k*sin(x)
$x0=$x2*80;
$x=-0.1;
for ($i=0;$i<640;$i++)
{$xi=$i/2;
$x=$x+0.0132;
$smy=140;
$y=$smy-$k2*48*sin($x);
if($i>=$x0)
{imagesetpixel($img,$xi,$y,$ink); // График y=k*sin(x)
}}}
if ($k3<>0)
{// 3 График y=k*x^2
$x=$x3*34;
$sm=140;
for ($i=$x;$i<320;$i++)
{ $x=$x+1; $smx=$x;
$y=($sm-0.0445*$x*$x*$k3);
imagesetpixel($img,$smx,$y,$ink); // График y=k*x^2
}}
imagepng($img);
imagedestroy($img);
Посмотрите из регламента олимпиады пример оформления работы в Приложении 1.
Ответственный: , доцент кафедры прикладной информатики (*****@***ru).
Приложение 1
Пример фрагмента работы участника олимпиады
Задание 1
Разработать программу, которая выводит на экран все простые числа в диапазоне от 1 до 1000.
Выполнение 1 задания:
Программа Pascal ABC (Версия 3.0.1.35 [17.4.207])
var
i, j,k, n:integer;
begin
n:=0;
for i:=1 to 1000 do
begin
k:=0;
for j:=1 to 1000 do
begin
if i mod j =0 then k:=k+1; {считает количество делителей}
end;
if k<3 then
begin
n:=n+1;
write(' ',i); {если количество делителей меньше 3, то выводит результат}
end;
end;
writeln; writeln(' Простых чисел: ',n);
end.
Входные данные: Целые числа от 1 до 1000.
Выходные данные: 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997
Простых чисел: 169
Скриншот начального фрагмента исходного кода:
Скриншот вывода результата:
Внимание:
Баллы выставляются за правильно работающую программу, а не за скриншоты.
По скриншоту исходного кода можно понять, в какой системе программирования выполнялись задания. Указывайте и версию языка программирования. Например, Pascal ABC (Версия 3.0.1.35 [17.4.207]).
Скриншоты и имена переменных используются для дополнительной проверки того, что ученик выполнил работу самостоятельно, а не использовал точный повтор чужого текста решения.
Ограничивайте площадь скриншотов для того, чтобы не увеличивать объем отправляемой на конкурс работы. Большой объем отправляемого файла может затруднить передачу работы на сайт.
Указывайте в файле выполненных заданий свою электронную почту. Это позволит быстро сообщить Вам о получении от Вас пустого файла или заданий без решений в случае неудачного или неправильного отправления.
