Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
Форум программистов > Интересные и занимательные задачи по программированию > Конкатенация строк |
Автор: km999 24.1.2011, 23:00 |
Имеется последовательность строк. Первая строка "a", вторая "bc". Тре- тья строка является конкатенацией предыдущих двух (к первой строке приписывается вторая) – "abc". Четвертая строка – конкатенация второй и третьей ("bcabc"). Все дальнейшие строки строятся аналогично, склеива- нием предыдущих двух. Требуется определить, какой символ находится на указанной позиции в строке с заданным номером. Ввод: Два целых числа, разделенные пробелом – K и P (0 < K <= 10^9), (0 < P <= 10^9), где K – номер строки Фибоначчи, а P – номер позиции в строке. Вывод: Искомый символ для соответствующего теста: "a", "b" или "c" (символы латинского алфавита). Если Р превышает размер К-й строки (K <= 10^9), то необходимо вывести «No solution» (без кавычек). Пример Ввод: 18 58 Вывод: A Может есть хоть какие-то идеи? |
Автор: dEvIllEssE 27.1.2011, 15:24 |
Uses CRT; Var k,p,i:LongInt; x,y,z:string; Begin ClrScr; WriteLn(' „ л ¤ўҐ бва®ЄЁ: ЇҐаў п - a, ўв®а п - bc.'); WriteLn('Џа®Ја ¬¬ Їа®Ё§ў®¤Ёв Є®Є ⥠жЁо бва®Є ¬Ґв®¤®¬ ”ЁЎ® ззЁ,'); WriteLn('Ё ўлў®¤Ёв бЁ¬ў®« ў гЄ § ®© Ї®§ЁжЁЁ "p" гЄ § ®© бва®ЄЁ "k".'); WriteLn; Write('‚ўҐ¤ЁвҐ ®¬Ґа бва®ЄЁ, k='); ReadLn(k); Write('‚ўҐ¤ЁвҐ ®¬Ґа Ї®§ЁжЁЁ, p='); ReadLn(p); x:='a'; y:='bc'; If k=1 then y:='a'; If k=2 then y:='bc'; For i:=3 to k do Begin z:=y; y:=Concat(x,y); x:=z; End; If (P>Length(y)) or (P=0) then WriteLn('No solution.') else Begin y:=copy(y,p,1); WriteLn(y); End; ReadLn; End. Как вариант. Делал в обычном турбопаскале, почему-то беда со шрифтами. Думаю, можно сделать и проще, но не до этого щас. ![]() P.S. Первые три writeln - просто пояснение пользователю, что делает программа. Вторые два - соответственно, ввод k и p. Дальше все очевидно. P.P.S. В следующий раз указывайте, что это задача ФРТК. |
Автор: Akina 27.1.2011, 16:16 |
А перед Ctrl-C надо клавир в русскую раскладку переключать... А запускать-то пробовал? при К порядка сотен миллионов? Во-первых, просто построй хотя бы первые два десятка строк и посмотри на них попристальнее... сразу выяснится, что буквовка запросто определяется в зависимости от чётности номера строки и позиции символа в ней (длина периода 5 и 8 соответственно). Во-вторых, найди способ нахождения наибольшего числа Фибоначчи, не превосходящего заданное (это для определения, не надо ли вывести No solution). Или просто составь и забей в программу статическую таблицу первых 43 чисел (или напиши вычисление нужного числа). Когда всё это проделаешь - пполучишь полный алгоритм. |
Автор: dEvIllEssE 27.1.2011, 18:01 | ||
Пробовал, пробовал. Только при порядке сотен тысяч. Ответ выдавал, но проверить его нет возможности. Насчет сотен миллионов, попробую завтра, а то это же на час наверно будет. P.S. Я решал еще другую задачку от ФРТК, где надо посчитать количество чисел содержащих в себе "1", от 1 до N. Там задал N=999999999 - через 20 минут получил ответ, опять же не проверял ![]() |
Автор: Akina 27.1.2011, 18:12 |
Описанный мной подход даёт ответ практически мгновенно. |
Автор: dEvIllEssE 28.1.2011, 10:42 |
Да я и не спорю, что ваши методы круче. Я сделал тупо то, что спрашивается, особо не вдумываясь. О чем собственно и предупредил в своем посте с решением. На счет Ctrl+C, я так не делал, я просто сохранил в расширении txt. А ваще я в программировании нуб, в школе что-то учил когда-то. Просто интересно иногда подумать ![]() |
Автор: Akina 28.1.2011, 10:53 |
Но оттуда-то сюда как вставлял? Вы сделали "в лоб". Но это же не алгоритмика... она для того и существует, чтобы и найти "чёрный ход". |
Автор: dEvIllEssE 28.1.2011, 16:31 |
У меня уже в txt вставилось со сломанными шрифтами. Оттуда через Ctrl+C. А насчет "иногда подумать" - хватит уже подкалывать... Я и не претендую на то, чтобы быть мего программистом. Алгоритмика это хорошо и правильно, но требует образования и опыта. Для тебя эта задачка примитивна и легка; а я тоже понимаю, что она примитивна для настоящего программиста, но даже "в лоб" пришлось подумать. |
Автор: Akina 28.1.2011, 17:01 |
Да ладно ![]() |
Автор: km999 28.1.2011, 22:33 |
Спасибо всем за помощь. Разобрался с решением. |
Автор: Akina 31.1.2011, 17:13 | ||
Я же сказал, что так что посмотреть первые ТРИ символа - МАЛО. |
Автор: dEvIllEssE 3.2.2011, 14:07 | ||
Извините, но я такого не писал, это вы процитировали Акину, ошибочно указав на меня. Так что все стрелки на него :Р |
Автор: Silent 4.2.2011, 10:06 | ||
Как указал тов. Akina, буква действительно неким "магическим" образом зависит от позиции в строке и номера строки ![]() i-ая строка есть конкатенация строк i-1 и i-2. Следовательно, буква на позиции X в i-ой строке - либо буква на позиции X в строке i-2 (если X меньше или равно длины строки i-2), либо на позиции X-len(i-2) (len(i-2) - длина i-2-ой строки); и еще мы знаем ответы для i=1 и i=2. Вот такая реккурентная формула. Можно реализовать рекурсивно, можно циклом. Исходный код:
Возможно, мой код может быть неверен для граничных случаев, но в целом он правильный. P.S. Где-то я эту задачу уже видел, на тимусе, что ли? |
Автор: Akina 4.2.2011, 10:42 | ||
См. аттач... это для уж совсем ленивых... |
Автор: km999 5.2.2011, 00:52 | ||
Добавлено @ 00:56
Это задача из заочной олимпиады МФТИ |