IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Последовательность букв
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 28

Репутация: -  0  +


Последовательность состоит из латинских букв таким образом:
На первом этапе она пустая, на каждом следующем она удваивается и в конец добавляется следующая буква лат.алфавита (a, b, c, …).Задание: за заданным числом n, определить символ, который стоит на n-вом месте в последовательности, которую мы получили после 20 шагов.


--------------------
С уважением,
Таука.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


N337
****

Группа: Пользователи
Сообщений: 737
Пол: Мужской

Репутация: -  26  +


Пусть 1 <= n < 2^20 - 1, тогда
1) решение "в лоб":
Код
program LatSeq1;

var
 i, n: LongInt;

procedure Rec(s: Integer);
begin
 if s = 0 then Exit;
 Rec(s - 1);
 Rec(s - 1);
 if i = n then
   begin
     Writeln(Chr(s + Ord('a') - 1));
     Halt;
   end;
 Inc(i);
end;

begin
 Write('n>');
 Readln(n);
 i := 1;
 Rec(20);
end.


2) решение 1) после небольшой оптимизации:
Код
program LatSeq2;

var
 n, m: LongInt;
 s: Integer;

begin
 Write('n>');
 Readln(n);
 s := 20;
 while n <> LongInt(1) shl s - 1 do
   begin
     Dec(s);
     m := LongInt(1) shl s - 1;
     if n > m then Dec(n, m);
   end;
 Writeln(Chr(s + Ord('a') - 1));
end.


--------------------
The idiots are winning.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Смотрю...
*****

Группа: Пользователи
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

Репутация: -  6  +


Я что-то не врубился в ход решения... huh.gif
А где сама последовательность? Или все обошлось без нее?

Каюсь, слишком сильно не вникал, но чего-то я не понял....

xds , поясни пожалуйста, а то я в недоумении - либо я тупой, либо ты гений! rolleyes.gif


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Прогрессор
****

Группа: Пользователи
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


А сама последовательность и не нужна - у нас есть закон, полностью определяющий её построение!
По-научному иожно бы было сказать, что перед нами - программирование на основе инварианта. (Очень хорошая вещь... в частности, многие рекурсивные вычисления(или даже любые?) можно очень хорошо оптимизировать по времени, переделав её на итерацию, если найден подходящий инвариант, - что само по себе бывает очень сложно).
Конечно, xds мог поступить иначе - за минутку написать рекурсивную процедуру, строящую последовательность, а потом просто выдающую запрошенный символ по номеру. Это выглядело бы просто и наглядно... и даже удобно для малых номеров... но вот для достаточно больших...уу-у angry.gif sad.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Смотрю...
*****

Группа: Пользователи
Сообщений: 1 055
Пол: Мужской
Реальное имя: Пшеничный Алексей Анатольевич

Репутация: -  6  +


Оригинально!
Надеюсь автору топику подойдет такой вариант решения...

xds, поощраю!


--------------------
Если что-то не делает того, что вы запланировали ему делать - это еще не означает, что оно бесполезно.
--------------------
Прежде, чем задать вопрос - Правила :: FAQ :: Поиск
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 28

Репутация: -  0  +


Спасибо за ответ!Сейчас буду разбираться. Я в самом деле делала так: пыталась построить последовательность, а потом по номеру определять какой же это элемент, проблема состояла в том, что при больших n ничего не получалось.


--------------------
С уважением,
Таука.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.12.2024 20:45
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name