Разбор задач с "Ломоносова" по информатике ч.2

Разбор задач с “Ломоносова” по информатике, ч. 2 27.01.13

Йохохо, %USERNAME%! Сегодня я продолжаю разбор задач с Ломоносовской олимпиады по программированию. Первую часть можно прочитать по ссылке.

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

В прошлой записке я остановился на 3 задании, следующее, что я выполнил идет под номером 6. С него и начнем, интересующихся прошу под кат.

Задание №6.

Формулировка: последовательность цифр: 146891012141516… образована выписыванием подряд
чисел, не являющихся простыми. Укажите в ответе 10 цифр последовательности, начиная с
2012-й цифры. Нумерация цифр последовательности начинается с единицы.

Составим алгоритм нахождения ответа:

Записать в массив все простые числа от 2 до N( устанавливается эксперементальным путем)
Записать в массив последовательно все числа от 1 до N
Вычесть из второго массива первый

Итак. Нам нужен алгоритм нахождения всех простых чисел от 2 до N.

Какие варианты приходят в голову? В цикле перебирать числа от 2 до N, деля их на 2\3\5\7, а те, что не делятся записывать в массив. Да, такое решение будет работать. Со скоростью черепахи :)

Сходим за помощью на википедию. В разделе «Алгоритмы поиска и распознавания простых чисел» увидим почти решение всех наших проблем: Решето Эратосфена, решето Сундарама и Решето Аткина. Какой из этих трех алгоритмов выбрать и что вообще они из себя представляют?

1) Решето Эратосфена:

Решето Эратосфена: наглядное представление

Описание с вики кажется мне несколько сложным, поэтому объясню проще.

Выпишем все числа от 2 до N. Теперь примем p=2 и зачеркнем в последовательности чисел все кратные 2( синие крестики: 4\6\8\10 итд). Затем примем p=3, так как оно идет сразу за 2, и зачеркнем все кратные 3( зеленые крестики: 9\15\21 итд). Теперь возьмем p=5, так как оно близжайшее к 3 и не зачеркнуто. Уберем из последовательности все числа, кратные 5( красные крестики: 10, 15, 20, 25 итд). Наконец, возьмем p=7, так как 6 зачеркнута, и уберем из последовательности числа, кратные 7( желтые крестики: 14, 35, 49 итд).

Выпишем отдельно все, что осталось, и получим последовательность простых чисел от 2 до N( в случае с анимированной гифкой N=120).

Простой алгоритм, я считаю. И довольно эффективный для задач вроде нашей, так как по сути нам нужно не супер оптимальное нахождение всех простых, а просто достаточно быстрое.

2) Решето Сундарама:

Алгоритм основывается на идее вычеркивания всех составных чисел, после чего остаются лишь простые. Выбрасывание чисел происходит следующим образом: выписываются все натуральные числа от 1 до n, далее выкидываются все числа равные i+j+2*i*j, где i и j — все возможные сочетания чисел от 1 до n, причем всегда i<=j.
Все оставшиеся в массиве числа умножаются на в два раза и увеличиваются на единицу. В итоге остаются только простые числа.

Не знаю насчет тебя, %USERNAME%, но я не понимаю этот алгоритм, а потому переходим к более современному творению А. О. Л. Аткина и Д. Ю. Бернштайна.

3) Решето Аткина:

Извращенский и ассимтотически более выгодный, чем стандартный алгоритм Эратосфена, алгоритм Аткина достаточно сложен:

Выписываются все натуральные числа из диапазона от 1 до n, перебираются все возможные пары чисел x, y, где x<=sqrt(n) и y<=sqrt(n). Т.е. (1,1), (1,2),…, (1,sqrt(n)), (2,1), (2,2),…, (sqrt(n),sqrt(n)), для каждой пары чисел вычисляются значения следующих трех уравнений:
a) 4*x^2+y^2;
b) 3*x^2+y^2;
c) 3*x^2-y^2, значение вычисляется только при x>y.
Для каждого вычисленного значения уравнений вычисляются остатки от деления на 12, причем
a) если остаток равен 1 или 5 для значения первого уравнения;
b) если остаток равен 7 для значения второго уравнения;
с) если остаток равен 11 для значения третьего уравнения.
То в исходном ряду чисел от 1 до n число помечается как простое.

Алгоритм Аткина выигрывает в производительности метод Эратосфена, начиная с N=10^9, но ведь наши числа куда скромнее, а потому идеальный вариант- первый.

Текст решения:

n = 849
a = range(n+1)
a[1] = 0
lst_1 = [2]
lst_2 = [i for i in range(1,n)]
lst_3=[]
result = []
i = 1
while i <= n:
    if a[i] != 0:
        lst_1.append(a[i])
        for j in xrange(i, n+1, i):
            a[j] = 0
    i += 2
result = [item for item in lst_2 if item not in lst_1]
for item in result:
  lst_3.append(str(item))

print ''.join(lst_3)[2012:2022]

n = 849

a = range(n+1)

a[1] = 0

lst_1 = [2]

lst_2 = [i for i in range(1,n)]

lst_3=[]

result = []

i = 1

while i <= n:

if a[i] != 0:

lst_1.append(a[i])

for j in xrange(i, n+1, i):

a[j] = 0

i += 2

result = [item for item in lst_2 if item not in lst_1]

for item in result:

lst_3.append(str(item))

print ''.join(lst_3)[2012:2022]

Пояснения по коду:
4 строка: в списке простых изначально содержится цифра 2, причина в экономии памяти в цикле while
14 строка: математики заметили, что единственное четное число в среди простых- двойка, а потому, прибавляя к итератору 2, а не 1, уменьшаем число проходов в 2(!) раза. Потому в 4 строке изначально стоит 2, иначе оно будет пропущено.

Итак, ответ задачи: 8448458468

Задание №10

Формулировка: Рассмотрим 64 знака числа e после десятичной точки (начинающиеся с 718281).
Выпишем все 64 циклических перестановки этого числа, то есть само число, число, в котором
первый знак переставлен в конец, число, получающееся из этого перестановкой первого знака в
конец и т. д. Отсортируем 64 получившихся строки лексикографически и возьмем последний
столбец. Такое преобразование называется преобразованием Бэрроуз-Уилер (Burrows-Wheeler
Transform).
Какая получилась строка в результате преобразования?

Ход решения:

Все довольно просто и очевидно: переносим первый символ из исходной строки на каждой итерации в конец и записываем массив символов в подмассив output 64 раза. Затем сортируем массив по значениям и выводим последний символ из каждого подмассива output.

Уже не помню почему, но изначально написал 10 задание на PHP, а потом было лень переделать на что- то вменяемое: задача- то сделана и ответ получен :)

<?php
$eiler = "7182818284590452353602874713526624977572470936999595749669676277";
//Разбиваем строку в массив по 1 символу в элементе
$eiler = str_split($eiler);
//создаем массив выходных строк
$output=array();
//создаем подмассив 
$out=array();
//64 раза проходим цикл
for($i=0;$i<64;$i++){
	//извлекаем первый элемент из массива $eiler. $first= первый элемент, $eiler уменьшается на один элемент
	$first=array_shift($eiler);
	//добавляем в конец массива $eiler первое число( основа алгоритма Берроуз- Уиллер)
	$eiler[]=$first;
	//присваиваем элемету $i выходного массива массив чисел $eiler;
	$output[$i]=$eiler;
}
//Лексикографическая сортировка массива $output
asort($output);
//Проходим циклом foreach по каждому элементу $output
foreach($output as $elem){
	//Выводим в терминал\на экран последний элемент подмассива $elem массива $output
	echo end($elem);
}
?>

<?php

$eiler = "7182818284590452353602874713526624977572470936999595749669676277";

//Разбиваем строку в массив по 1 символу в элементе

$eiler = str_split($eiler);

//создаем массив выходных строк

$output=array();

//создаем подмассив

$out=array();

//64 раза проходим цикл

for($i=0;$i<64;$i++){

//извлекаем первый элемент из массива $eiler. $first= первый элемент, $eiler уменьшается на один элемент

$first=array_shift($eiler);

//добавляем в конец массива $eiler первое число( основа алгоритма Берроуз- Уиллер)

$eiler[]=$first;

//присваиваем элемету $i выходного массива массив чисел $eiler;

$output[$i]=$eiler;

}

//Лексикографическая сортировка массива $output

asort($output);

//Проходим циклом foreach по каждому элементу $output

foreach($output as $elem){

//Выводим в терминал\на экран последний элемент подмассива $elem массива $output

echo end($elem);

}

Ничего сложного, да? Ответ задачи: 69777857656880125908277274337949367299634475857679221122505946496

Хех, я несколько устал писать эту записку, так что ждите решений еще 3-4 задач в следующих статьях цикла «Разбор задач с «Ломоносова 2012″».

Спасибо за прочтение, удачного вам кода и поменьше логических ошибок!

Разбор задач с “Ломоносова” по информатике, ч. 2

Задание №6.

Задание №10

Похожие материалы: