Last active
August 29, 2015 14:21
-
-
Save iidaatcnt/3f6bf464247d08b79a18 to your computer and use it in GitHub Desktop.
100個のフィボナッチ数のリストを計算せよ
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env xcrun swift | |
import Foundation | |
let N = 100 // 配列要素はN+1個 | |
let M = 100 // 300桁(3*M) 10進数の取り出し回数 | |
let RADIXBITS = 15 | |
let RADIX:UInt16 = 0b1000000000000000 | |
func error(message:String) { | |
println("\(message)") | |
} | |
func add(a:[UInt16], b:[UInt16], inout c:[UInt16]) -> Int { | |
var u:Int32 = 0 | |
for var i = N; i >= 0; i-- { | |
u += Int32(a[i]) + Int32(b[i]) | |
c[i] = UInt16(u) & (RADIX - 1) | |
u >>= 15 | |
} | |
return (u != 0 ? -1 : 0) | |
} | |
func divs(a:[UInt16], x:Int, inout b:[UInt16]) -> UInt16 { | |
var t:UInt32 = 0 | |
var i = 0 | |
for i = 0; i <= N; i++ { | |
t = t << 15 | |
t = t + UInt32(a[i]) | |
b[i] = UInt16(t / UInt32(x)) | |
t = t % UInt32(x) | |
} | |
return UInt16(t) | |
} | |
func isZero(a:[UInt16]) -> Int { | |
var ret = 0 | |
for var i = 0; i <= N; i++ { | |
if a[i] != 0 { | |
ret = -1 | |
break | |
} | |
} | |
return ret | |
} | |
func printans(a:[UInt16]) -> String { | |
var ret:UInt16 = 0 | |
var str:String = "" | |
var ans:String = "" | |
var x:Int = 1000 | |
var i = 0 | |
var startp = 0 | |
var b:[UInt16] = Array(count: N+1, repeatedValue: 0) | |
var c:[UInt16] = Array(count: N+1, repeatedValue: 0) | |
c = a | |
while( 0 != isZero(c) ) { | |
ret = divs(c, x, &b) | |
str = String(format: "%03d",ret) + str | |
c = b | |
} | |
for i = 0; i < count(str); ++i { | |
if "0" != str[advance(str.startIndex,i)] { | |
break | |
} | |
} | |
startp = i | |
ans = str.substringFromIndex(advance(str.startIndex, startp)) | |
return ans | |
} | |
var ans:String | |
var ofcheck = 0 | |
var f0:[UInt16] = Array(count: N+1, repeatedValue: 0) | |
var f1:[UInt16] = Array(count: N+1, repeatedValue: 0) | |
var ot:[UInt16] = Array(count: N+1, repeatedValue: 0) | |
// フィボナッチ数を計算する | |
// a[n] <- 0 ... 32767 | |
// n = 0:top 10:bottom | |
f1[N] = 1 | |
println("1\t0") | |
println("2\t1") | |
//for var i = 3; i <= 1000; i++ { | |
for var i = 3; i <= 100; i++ { | |
ofcheck = add(f0, f1, &ot) | |
if (ofcheck != 0) { | |
error("Overflow") | |
break | |
} | |
ans = printans(ot) | |
ans = String(i) + "\t" + ans | |
println(ans) | |
f0 = f1 | |
f1 = ot | |
} | |
/**** | |
1 0 | |
2 1 | |
3 1 | |
4 2 | |
5 3 | |
6 5 | |
7 8 | |
8 13 | |
9 21 | |
10 34 | |
11 55 | |
12 89 | |
13 144 | |
14 233 | |
15 377 | |
16 610 | |
17 987 | |
18 1597 | |
19 2584 | |
20 4181 | |
21 6765 | |
22 10946 | |
23 17711 | |
24 28657 | |
25 46368 | |
26 75025 | |
27 121393 | |
28 196418 | |
29 317811 | |
30 514229 | |
31 832040 | |
32 1346269 | |
33 2178309 | |
34 3524578 | |
35 5702887 | |
36 9227465 | |
37 14930352 | |
38 24157817 | |
39 39088169 | |
40 63245986 | |
41 102334155 | |
42 165580141 | |
43 267914296 | |
44 433494437 | |
45 701408733 | |
46 1134903170 | |
47 1836311903 | |
48 2971215073 | |
49 4807526976 | |
50 7778742049 | |
51 12586269025 | |
52 20365011074 | |
53 32951280099 | |
54 53316291173 | |
55 86267571272 | |
56 139583862445 | |
57 225851433717 | |
58 365435296162 | |
59 591286729879 | |
60 956722026041 | |
61 1548008755920 | |
62 2504730781961 | |
63 4052739537881 | |
64 6557470319842 | |
65 10610209857723 | |
66 17167680177565 | |
67 27777890035288 | |
68 44945570212853 | |
69 72723460248141 | |
70 117669030460994 | |
71 190392490709135 | |
72 308061521170129 | |
73 498454011879264 | |
74 806515533049393 | |
75 1304969544928657 | |
76 2111485077978050 | |
77 3416454622906707 | |
78 5527939700884757 | |
79 8944394323791464 | |
80 14472334024676221 | |
81 23416728348467685 | |
82 37889062373143906 | |
83 61305790721611591 | |
84 99194853094755497 | |
85 160500643816367088 | |
86 259695496911122585 | |
87 420196140727489673 | |
88 679891637638612258 | |
89 1100087778366101931 | |
90 1779979416004714189 | |
91 2880067194370816120 | |
92 4660046610375530309 | |
93 7540113804746346429 | |
94 12200160415121876738 | |
95 19740274219868223167 | |
96 31940434634990099905 | |
97 51680708854858323072 | |
98 83621143489848422977 | |
99 135301852344706746049 | |
100 218922995834555169026 | |
****/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment