<HELP> for explanation

Блог им. umnikum

Простая задачка ....

Года 90-лохматого с задачки на Олимпиаде по программированию (тогда на 8-битных «калькуляторах»).
Всем фибонастам понравится ;)

1. есть ряд «аля фибо» 0-1-1-2-3-5-8 ....
2. продолжаем ряд сложением предыдущих 2х чисел для получения нового.
3. все получаемые числа дописываем в ряд 0112358 и тд.

Задача (собственно):
Какое число (символ, цифра) будет 2011м в этом ряду ;)

Это как бы и к роботостроительству (на предмет построения алгоритма вычисления).
 

Ответ 6. 13й знак в числе 30960598847965100000000000000 и будет 2011 в ряду записи.
Хотя вероятность числа 0 около 50% при таком формате записи в строку, т.к. каждое число начиная с 75го оканчивается на 0, и количество нулей в строке с увеличением ряда будет только расти.
avatar

alexv1975

вспомнил молодость)
участник всероссийской олимпиады школьников по программированию 1993г г.Троицк

и че я до сих пор руками торгую)))?
avatar

alexv1975

ща на PHP в две строки цикл кину… гляну что выйдет :)
דמיטרי,
Ну что там, рассчиталось? ))
avatar

Kolaider

вот 50 строк dioxid.ru/fibo.php
но жутко грузится :) и вообще я немного не понял задачу если честно :) что там надо сделать то?
דמיטרי,
склеить ряд по условиям в одну строку, а затем назвать символ #2011 в склеенном ряду
avatar

alexv1975

alexv1975, клеить не обязательно, достаточно знать два последних числа из ряда Фибоначи и номер в ряду у последней цифры второго из этих чисел. Смещаясь в цикле вправо добираемся до 2011 знака.
avatar

__________

Wilson,
а я ряды фибоначчи не знаю)
или знал, но забыл. решал как обычно с извращенной логикой)
avatar

alexv1975

alexv1975, а чё там знать, тебе же в условии задачи всё написали. В ряде Фибоначи каждое последующее число равно сумме двух предыдущих.
avatar

__________

Wilson, мммм… объясни — ну очень интересно!
דמיטרי, ок. 13-е число в ряде фибоначи это — 144. 14-е число в этом ряду — 233. В числе 233 последняя цифра 3 занимает в будущем склееном сплошном ряду 23-й номер.Следущее число в ряду Фибоначи равно 144+233=377, цифра 7 (последняя в этом числе) будет под номером 23+3=26. Теперь забываем про цифру 144 и идем дальше также с двумя последними цифрами (т.е. формируем цикл) и добираемся до 2011-й цифры.
avatar

__________

alexv1975, спасибо — я так и думал но уже больно сомневался :)
011235813213455891442333776109871597258441816765109461771128657463687502512139319641831781151422983204013462692178309352457857028879227465149303522415781739088169632459861023341551655801412679142964334944377014087331134903170183631190329712150734807526976777874204912586269025203650110743295128009953316291173862675712721395838624452258514337173654352961625912867298799567220260411548008755920250473078196140527395378816557470319842106102098577231716768017756527777890035288449455702128537272346024814111766903046099419039249070913530806152117012949845401187926480651553304939313049695449286602111485077978050341645462290671055279397008847608944394323791460144723340246762002341672834846770037889062373143900613057907216116009919485309475550016050064381636700025969549691112300042019614072749000067989163763861200011000877783661000001779979416004710000288006719437082000046600466103755300007540113804746350000122001604151219000001974027421986820000031940434634990100000516807088548583000008362114348984840000013530185234470700000021892299583455500000035422484817926200000057314784401381700000092737269219307900000015005205362069000000002427893228399980000000392841376460687000000063563069930068500000001028472075761370000000016641027750620600000000269257485082343000000004356677625885490000000070492524767089100000000114059301025944000000000184551825793033000000000298611126818977000000000483162952612010000000000781774079430987000000000126493703204300000000000020467111114739900000000003311648143516980000000000535835925499097000000000086700073985079500000000001402836665349890000000000022698374052006900000000000367267407055058000000000005942511475751270000000000096151855463018400000000000155576970220531000000000000251728825683550000000000000407305795904081000000000000659034621587630000000000000106634041749171000000000000017253750390793400000000000002791715456571050000000000000451709049565039000000000000073088059522214500000000000001182589644787180000000000000019134702400093300000000000000309605988479!6!5100000000000000
в общем конечно это 6 — но только благодаря компьютерным технологиям…
само число вот оно: 30960598847965100000000000000 и в конце символ = 6 это 2011 символ
Но как это решить просто по формуле я не понял
Ответ 2. Это 9-ая цифра в числе 3807901929474030000000000000000
avatar

__________

Wilson,
ждем автора, пусть рассудит)
avatar

alexv1975

alexv1975, мне Эксель так посчитал, а как правильно я не знаю
avatar

__________

alexv1975, как оказалось Эксель с определенного регистра начинает округлять цифры, щас буду с настройками Экселя разбираться
avatar

__________

с Экселем не разобрался, не умеет он с большими числами работать, первый раз в жизни он меня подвел.
avatar

__________

Wilson,
а я в экселе и считал. там формат ему на ячейку числовой задаешь и все путем.
а вот перевести из числа в текст и длину символов взять, тут на 20ти знаках эксель обламал, пришлось некоторую длину чисел руками добавить для поиска 2011 номера.
avatar

alexv1975

эксцель все умеет! это руки кривые.
avatar

del

Макс, сам попробуй вначале в Экселе сделать, а потом руки чужие обсуждать будешь.
avatar

__________

Wilson, Про эксель читай ниже ;)
Макс, назови мне для начала 75-е число в ряду Фибоначи, посчитанное Экселем.
avatar

__________

Wilson,
ексель 1304969544928660 75ое число
avatar

alexv1975

alexv1975, а должно быть .......657
avatar

__________

alexv1975, вот посмотри предыдущие два числа и сложи их вручную
avatar

__________

Wilson,
о, точно косяк екселя))
тогда мой ответ неправильный)))
претензию надо биллу гейтсу писать)
avatar

alexv1975

alexv1975, предполагаю, что где то в настройках Экселя есть поле где можно повысить точность вычислений (а косяк стопудово из-за округлений которые делат Эксель), но я сам не нашел где это можно сделать в Экселе.
avatar

__________

Доброго дня всем!

У меня лично ответа нет, потому что лень алгоритм писать. Просто вчера вдруг вспомнилось (было несколько разговоров, которые параллельно сцеплялись в небольшой части, что случайно выстрелилось воспоминаниями).

Собственно, в то время (а это была олимпиада по информатике) необходимо было не только запрограммировать, но и на бумаге расписать алгоритм. А программить пришлось на БК-001 ;) Кто помнит — это 8-битная архитектура.

Задачка, как 2 пальца об асфальт, однако самое сложное и тем именно интересное:
Именно как числовой ряд — загнать в 8-битную не выйдет.

В тот раз, насколько помню, дабы не тратить времени на разработку какого-то «научного алгоритма» просто циклами отсекал часть получаемого ряда, оставляя только хвост.
Для примера:
2011 символов — это 201 блок по 10 символов + 1 символ (как раз наш искомый).
Значит просто при добавлении в ряд очередного числа, смотрим на длину ряда оставшегося после усечения, отсекаем по 10 символов в мусорку, оставляя «хвост», и добавляя каждый раз к счетчику +1 (+1 блок из 10 символов).
Примерно так.

Хотя, если поразмыслить, то и в Экселе можно настрогать быстро. Просто для отображения ВСЕГО ряда, нужно его из числового формата превратить в текстовый ;) И, соответственно, вновь получаемое число фибо конвертировать в текст и прикреплять к основному ряду ;) А уж 2011-й символ в текстовом массиве найти просто ;)
— Комментарии только сейчас прочитал, но сразу же не понял про «13й знак в числе 30960598847965100000000000000 и будет 2011 в ряду записи.», «Ответ 2. Это 9-ая цифра в числе 3807901929474030000000000000000» и подобные комментарии.
— Если честно, просто в Юмор топик явно не засунуть, потому в основном пришлось сделать. Даже не ожидал, что интересно будет ;)

А вот интересен не сам 2011й символ, а алгоритм/алгоритмы. Соответственно, наиболее короткий в виде кода ;)
avatar

уМникум

уМникум, ты не сможешь ничего перевести в экселе из чисел в текст, т.к. эксель не корректно считает такие числа.
avatar

__________

Wilson, Честно говорю, не задавался целью ;)
Просто вчера было «короткое замыкание», которое разомкнул сюда ))))))))))
уМникум, задайся же и сделай
avatar

__________

Wilson, хаха.
Настряпал длиннющий комментарий и опаньки… свет рубанулся во всем здании, а UPS как сетевой фильтр давно уже :(

В общем в Экселе заняло примерно 2 минуты. 4 столбца, 138 строк тупого копирования строк ;)
Но это только для того, чтобы найти 6 или 9 как ответ. Хотя икак алгоритм с переводом числа в текст в иных языках — тоже сойдёт на быструю руку ;)
уМникум, назови для начала 75-е число в ряду Фибоначи из твоего Экселевского столбца
avatar

__________

Wilson, 1304969544928660
уМникум, не правильно
avatar

__________

Wilson, считаем от 0 или 1?
Wilson, надо было на Вискарь спорить ;)
Всё сверхпросто:
уМникум, я знаю как выглядит Эксель, мог бы картинку и не выкладывать
avatar

__________

Wilson, что-то циферки поплыи при вставке картинки
уМникум, не растраивайся, они у тебя всё равно не правильные
avatar

__________

Wilson, Всё правильно. «Ты, Зин, на грубость нарываешьси» ©
;)
уМникум, сложи ручками 73-е и 74-е число и сравни с тем что тебе написал Эксель про 75-е число. Считаем конечно же с 0, как и полагается.
avatar

__________

Wilson, всосал )))) про 15 символов.
уМникум, ну вот видишь, а то «Зин...», а некоторые еще и про ручки что-то тут писали.
avatar

__________

Wilson, хахахха…
Вот с этим на БК-001 ещё раньше можно было столкнуться (не на 75м числе), потому побыстрому просто отсекал часть цифр, уменьшая сам ряд, если очередное число «вываливалось» за возможности машины.
Точно уже и не вспомню сейчас, но на досуге могу попытать ум ;)
— А «Зина» была привязана к «не расстраивайся» (чего у меня и в мыслях не было) ;)
уМникум, можно Эксель конечно обмануть, разбив большие числа на два числа (правая часть и левая), но вот эту хрень программировать что то не хочется, точнее именно сейчас на это времени точно нет, хотя механизм реализации примерно мне понятен.
avatar

__________

Wilson, угу.
Об этом я выше и писал. И не только эксельку так можно обмануть.
уМникум, При вставке ГИФкой почему-то терял цвет
уМникум, описание короткого алгоритма я привел выше в описании, там не надо строить массив из всех чисел Фибоначи.
avatar

__________

если нумерация с 1, то ответ 6, если с нуля то 9
avatar

LordNikon

Хорошая задача. Особенно для калькулятора
avatar

Рафаэль


Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.

Залогиниться

Зарегистрироваться
....все тэги
Регистрация
UPDONW