Отправляет email-рассылки с помощью сервиса Sendsay

Дистанционное обучение

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 406 RSS
←   Октябрь 2008   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://дистанционный-репетитор.рф
Открыта: 04-12-2005

Автор
Андрей Темнов

Статистика

406 подписчиков
0 за неделю
←   Все выпуски   →

Уроки и методика преподавания информатики для учителей задача №1 www.thl.narod.ru


Задача №1. Удвоение строк.
Последовательность строк формируется следующим образом:
S[1]=?a?;
S[2]=?aab?;
?
S[n]=S[n-1]+S[n-1]+letter[n], где letter[n] ? n-ная буква латинского алфавита. Требуется найти i-й символ k-й строки.
Во входном файле input.txt содержится две строки: в первой ? N ? номер строки 1<=N<=26, во второй ? K ? номер искомого символа.
Выходной файл output.txt должен содержать искомый символ.
Пример:
input.txt
3
5
output.txt
a

Решение.

Задача №1.
Идея состоит в следующем: если требуемый символ является последним в строке, то выводим этот символ (по номеру строки он определяется однозначно). В противном случае, вычтем единицу, получив строку с четной длиной. Получившая строка состоит из двух одинаковых, поэтому, если номер символа попадает во вторую часть, то мы уменьшим его на n/2, при этом искомый символ не изменится. Будем повторять указанную процедуру. Очевидно, что рано или поздно искомый символ будет найден.

var inp, outp: text;
l, i, n, s: longint;
begin
assign(inp,'input.txt');
assign(outp,'output.txt');
reset(inp);
rewrite(outp);
readln(inp,n);
readln(inp,s);
l:=(1 shl n)-1; {вычисление длины строки}
while s<>l do
begin
dec(l);
if s>l div 2 then s:=s-l div 2;
l:=l div 2;
dec(n);
end;
write(outp,chr(ord('a')+n-1));
close(outp);
close(inp);
end.

А теперь я предлагаю подумать над решением следующей задачи:
Задача №2. Строки Фибоначчи
Последовательность строк Фибоначчи определяется следующим образом: S[1]=?b?, S[2]=?a?, S[k] = S[k-1] + S[k-2] для k>2. Например, S[3]=?ab?, S[4]=?aba?, S[5]=?abaab? и т. д.
Даны натуральные числа N, М, L. Требуется вывести подстроку строки s[N], начинающуюся с позиции M и имеющую длину L.
Входной файл INPUT.TXT содержит одну строку, в которой находятся три разделённых пробелом натуральных числа N, M и L, где
1<=N<=40; 1<=M<=length(S[N]), 1<=L<=1000.
Выходной файл OUTPUT.TXT содержит подстроку строки S[N], начинающуюся с позиции M и имеющую длину L (длина выведенной подстроки может оказаться меньше, если длина оставшейся части строки S[N] , начинающейся с позиции M, меньше L).
Пример:
input.txt
5
3
10
output.txt
aab
В избранное