U E D R , A S I H C RSS

How Many Fibs?/1002

approach

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๋ถ„๋งŒ์— ํ’€์–ด๋ฒ„๋ฆฌ๋‹ค. ํ‘.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:25
Processing time 0.0078 sec