How Many Fibs?/1002

input space 로 볼때 최악의 경우가 1~10^100 일 수 있겠다는 생각을 하면서 뭔가 다른 공식이 있겠다 생각, 피보나치의 closed-form 을 근거로 해결할 방법에 대해 궁리해보다. a,b 구간에 가장 가까울 f(x),f(y)를 각각 구하고, y-x 를 구하면 되리라고 생각. 하지만 3시간동안 고민했는데 잘 안되어서, 그냥 노가다 스러운 방법으로 풀기 시작.

~cpp
def fibo(n):
    s=[1,2]
    if n in [1,2]: return s[n-1]

    i=2
    while True:
        i+=1
        fiboI=s[0]+s[1]
        if n==i: return fiboI
        s[0],s[1] = s[1], fiboI

def howmany(a,b):
    i,count=1,0
    while True:
        fiboI = fibo(i)
        if a < fiboI < b: count+=1
        if fiboI > b: return count
        i+=1

print howmany(10,100)
print howmany(1234567890,9876543210)
print howmany(1,10**100)

근데, a,b=(1,10^100) 로 해도 1초도 안걸린다. 처음에는 'big integer 를 만들어라!' 라는 문제가 아니라고 생각했는데, 풀고 나니 뭔가 허탈함. 글쌔. 출제자가 원한 답은 big integer emulation 이였을까. 흑..
덤 : 피보나치 closed form

~cpp
def fiboClosedForm(n):
    return int(((1+sqrt(5))**n - (1-sqrt(5))**n) / (2**n * sqrt(5)))

기타 덤 : fibonacci 의 수열 당 자릿수 값.

1:1     2:1     3:1     4:1     5:1     6:2     7:2     8:2     9:2     10:2
11:3    12:3    13:3    14:3    15:3    16:4    17:4    18:4    19:4    20:5
21:5    22:5    23:5    24:5    25:6    26:6    27:6    28:6    29:6    30:7
31:7    32:7    33:7    34:7    35:8    36:8    37:8    38:8    39:9    40:9
41:9    42:9    43:9    44:10   45:10   46:10   47:10   48:10   49:11   50:11
51:11   52:11   53:11   54:12   55:12   56:12   57:12   58:12   59:13   60:13
61:13   62:13   63:14   64:14   65:14   66:14   67:14   68:15   69:15   70:15
71:15   72:15   73:16   74:16   75:16   76:16   77:16   78:17   79:17   80:17
81:17   82:17   83:18   84:18   85:18   86:18   87:19   88:19   89:19   90:19
91:19   92:20   93:20   94:20   95:20   96:20   97:21   98:21   99:21   100:21
101:21  102:22  103:22  104:22  105:22  106:23  107:23  108:23  109:23  110:23
111:24  112:24  113:24  114:24  115:24  116:25  117:25  118:25  119:25  120:25
121:26  122:26  123:26  124:26  125:26  126:27  127:27  128:27  129:27  130:28
131:28  132:28  133:28  134:28  135:29  136:29  137:29  138:29  139:29  140:30
141:30  142:30  143:30  144:30  145:31  146:31  147:31  148:31  149:31  150:32
151:32  152:32  153:32  154:33  155:33  156:33  157:33  158:33  159:34  160:34
161:34  162:34  163:34  164:35  165:35  166:35  167:35  168:35  169:36  170:36
171:36  172:36  173:37  174:37  175:37  176:37  177:37  178:38  179:38  180:38
181:38  182:38  183:39  184:39  185:39  186:39  187:39  188:40  189:40  190:40
191:40  192:40  193:41  194:41  195:41  196:41  197:42  198:42  199:42  200:42
201:42  202:43  203:43  204:43  205:43  206:43  207:44  208:44  209:44  210:44
211:44  212:45  213:45  214:45  215:45  216:46  217:46  218:46  219:46  220:46
221:47  222:47  223:47  224:47  225:47  226:48  227:48  228:48  229:48  230:48
231:49  232:49  233:49  234:49  235:49  236:50  237:50  238:50  239:50  240:51
241:51  242:51  243:51  244:51  245:52  246:52  247:52  248:52  249:52  250:53
251:53  252:53  253:53  254:53  255:54  256:54  257:54  258:54  259:54  260:55
261:55  262:55  263:55  264:56  265:56  266:56  267:56  268:56  269:57  270:57
271:57  272:57  273:57  274:58  275:58  276:58  277:58  278:58  279:59  280:59
281:59  282:59  283:60  284:60  285:60  286:60  287:60  288:61  289:61  290:61
291:61  292:61  293:62  294:62  295:62  296:62  297:62  298:63  299:63  300:63
301:63  302:63  303:64  304:64  305:64  306:64  307:65  308:65  309:65  310:65
311:65  312:66  313:66  314:66  315:66  316:66  317:67  318:67  319:67  320:67
321:67  322:68  323:68  324:68  325:68  326:68  327:69  328:69  329:69  330:69
331:70  332:70  333:70  334:70  335:70  336:71  337:71  338:71  339:71  340:71
341:72  342:72  343:72  344:72  345:72  346:73  347:73  348:73  349:73  350:74
351:74  352:74  353:74  354:74  355:75  356:75  357:75  358:75  359:75  360:76
361:76  362:76  363:76  364:76  365:77  366:77  367:77  368:77  369:77  370:78
371:78  372:78  373:78  374:79  375:79  376:79  377:79  378:79  379:80  380:80
381:80  382:80  383:80  384:81  385:81  386:81  387:81  388:81  389:82  390:82
391:82  392:82  393:82  394:83  395:83  396:83  397:83  398:84  399:84  400:84
401:84  402:84  403:85  404:85  405:85  406:85  407:85  408:86  409:86  410:86
411:86  412:86  413:87  414:87  415:87  416:87  417:88  418:88  419:88  420:88
421:88  422:89  423:89  424:89  425:89  426:89  427:90  428:90  429:90  430:90
431:90  432:91  433:91  434:91  435:91  436:91  437:92  438:92  439:92  440:92
441:93  442:93  443:93  444:93  445:93  446:94  447:94  448:94  449:94  450:94
451:95  452:95  453:95  454:95  455:95  456:96  457:96  458:96  459:96  460:96
461:97  462:97  463:97  464:97  465:98  466:98  467:98  468:98  469:98  470:99
471:99  472:99  473:99  474:99  475:100 476:100 477:100 478:100 479:100 480:101
481:101 482:101 483:101 484:102 485:102 486:102 487:102 488:102 489:103 490:103
491:103 492:103 493:103 494:104 495:104 496:104 497:104 498:104 499:105

피보나치 수가 굉장히 크게 늘어나는 수라는 점을 생각했더라면, input space 가 크더라도 fibo(n) 의 n 값이 커지지 않을 것이라는 것을 미리 알고 있었더라면 저런 고민을 안했을 것 같긴 하다. 하지만, 이러한 사전지식이 없는 가운데, 문제를 풀라고 한다면 어떻게 접근하는게 가장 좋았었을까. 고민된다.

• 컴퓨터의 속도를 무시하지 말자.;
  
• 그럼에도 불구하고.. '정말 big integer 만들기' 문제였을까? 다시금 고민하게 되다.
  
• closed form 과 관련하여 Generating Function 이 아직도 익숙치 않아서 mathworld 의 힘을 빌리다. GF 를 공부해야겠다.
  
• 구간 계산과 관련, 'a 와 가장 가까운 fibonacci 값을 구하기' 는 반복문 돌리기 & if 로 비교 말고 다른 방법이 없을까?
  
• bigint 를 지원하는 python 이나 matlab 같은 언어에서는 더 할일이 없는 문제. 내가 공식 궁리하는 동안 옆의 분이 matlab 으로 10분만에 풀어버리다. 흑.